백준 단계별 문제풀이 4단계 (1차원 배열) https://www.acmicpc.net/problem/10813 10813번: 공 바꾸기 도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 매겨져 있다. 바구니에는 공이 1개씩 들어있고, 처음에는 바구니에 적혀있는 번호와 같은 번호가 적힌 공이 www.acmicpc.net # 문제 도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 매겨져 있다. 바구니에는 공이 1개씩 들어있고, 처음에는 바구니에 적혀있는 번호와 같은 번호가 적힌 공이 들어있다. 도현이는 앞으로 M번 공을 바꾸려고 한다. 도현이는 공을 바꿀 바구니 2개를 선택하고, 두 바구니에 들어있는 공을 서로 교환한다. 공을 어떻게 바꿀..

백준 단계별 문제풀이 4단계 (1차원 배열) https://www.acmicpc.net/problem/10818 10818번: 최소, 최대 첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다. www.acmicpc.net # 문제 N개의 정수가 주어진다. 이때, 최솟값과 최댓값을 구하는 프로그램을 작성하시오. # 예제 입력 - 첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같..

백준 단계별 문제풀이 4단계 (1차원 배열) https://www.acmicpc.net/problem/10807 10807번: 개수 세기 첫째 줄에 정수의 개수 N(1 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 정수가 공백으로 구분되어져있다. 셋째 줄에는 찾으려고 하는 정수 v가 주어진다. 입력으로 주어지는 정수와 v는 -100보다 크거 www.acmicpc.net # 문제 총 N개의 정수가 주어졌을 때, 정수 v가 몇 개인지 구하는 프로그램을 작성하시오. 정수의 개수가 첫째줄, 배열이 둘째줄, 정수 v가 셋째줄에 입력된다. # 예제 입력 11 1 4 1 2 4 2 4 2 3 4 4 2 출력 3 # 필요개념 배열 전체를 for문으로 돌면서 카운트 하는 방법도 있지만, 이번에는 자바를 공부하면서 알게 된..

백준 단계별 문제풀이 3단계 (반복문) https://www.acmicpc.net/problem/2439 2439번: 별 찍기 - 2 첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제 하지만, 오른쪽을 기준으로 정렬한 별(예제 참고)을 출력하시오. www.acmicpc.net # 문제 첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제 하지만, 오른쪽을 기준으로 정렬한 별(예제 참고)을 출력하시오. # 예제 입력 (1 = 1 ; j--) System.out.print(" "); for (int k = n - i; k >= 0 ; k--) System.out.print("*"); System.out.println(); } } } # 결과

백준 단계별 문제풀이 3단계 (반복문) https://www.acmicpc.net/problem/15552 15552번: 빠른 A+B 첫 줄에 테스트케이스의 개수 T가 주어진다. T는 최대 1,000,000이다. 다음 T줄에는 각각 두 정수 A와 B가 주어진다. A와 B는 1 이상, 1,000 이하이다. www.acmicpc.net # 문제 본격적으로 for문 문제를 풀기 전에 주의해야 할 점이 있다. 입출력 방식이 느리면 여러 줄을 입력받거나 출력할 때 시간초과가 날 수 있다는 점이다. Java를 사용하고 있다면, `Scanner`와 `System.out.println` 대신 `BufferedReader`와 `BufferedWriter`를 사용할 수 있다. `BufferedWriter.flush`는 맨..

이번챕터에서는 branch-and-bound 알고리즘에 대해 정리할 예정이다. 목차는 다음과 같다. Branch-and-Bound algorithm 0/1 Knapsack Problem using DFS using BFS (Breath-First Search) using BFS (Best-First Search) BFS, DFS 개념은 아래 게시물에 정리되어있다. https://wanna-developer02.tistory.com/54 [알고리즘] CHAP 5. Backtracking Algorithm (백트래킹 알고리즘) - Monte Carlo Algo- 이번 챕터에서는 백트래킹 알고리즘에 대해 정리하려고 한다. 목차는 다음과 같다. Backtracking Algorithm (백트래킹) DFS BFS..

이번 챕터에서는 백트래킹 알고리즘에 대해 정리하려고 한다. 목차는 다음과 같다. Backtracking Algorithm (백트래킹) DFS BFS Monte Carlo Algorithm (몬테카를로 알고리즘) Solve problem 1. N Queens Problem 2. Sum-of-Subsets Problem 3. Graph Coloring Problem 4. Hamiltonian Circuits Problem 1. Backtracking Algorithm (백트래킹 알고리즘) 백트래킹 알고리즘은 어떤 조건을 가진 문제의 해결책을 찾기위해 탐색하는 알고리즘 중 하나이다. 모든 경우의 수를 탐색하긴 하지만, 완전탐색 알고리즘과 달리 어떤 조건을 가지고 있으므로 배제되는 경우들이 많아 효율이 더 높다..