매일 조금씩

문제 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 풀이 DP를 이용하여 풀었다. 작은 문제들의 답을 구한다. dp[2] = 1, N이 2일 때는 최소 횟수가 1이다. (2으로 나눔) dp[3] = 1, N이 3일 때는 최소 횟수가 1이다 (3으로 나눔) ..

문제 https://www.acmicpc.net/problem/21771 21771번: 가희야 거기서 자는 거 아니야 베게 중 8칸이 가희에 의해 가려졌으므로, 가희는 베게 위에서 자고 있습니다. www.acmicpc.net 풀이 베개의 넓이와 베개의 원소 개수를 비교해서 베개가 가려졌는지 여부를 판단한다. 소스코드 package dp; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ11057 { public static int R, C, GR, GC, PR, PC; public static void input() throws Exception{ ..

#문제 https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net #풀이 Stack을 이용하여 풀었다. 순서대로 Stack에 막대바의 height, index 정보를 push하면서, 만약 현재 막대바의 height가 Stack의 top원소보다 작을 경우 Stack의 원소를 pop하면서 넓이를 계산해준다. #소스코드 package stack; import java.io.BufferedReader; i..

#문제 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net #풀이 백트래킹, DFS를 이용하여 풀었다. 1. 스도쿠 정보를 2차 배열에 담는다. 2. 0값의 좌표를 ArrayList로 들고 있는다. 3. 특정 좌표에 특정 Value가 할당 될 수 있는지 체크하는 함수를 생성한다. (isPossible()로 구현) - 좌표가 속한 세로, 가로, 3*3 정사각형 좌표에서 Value가 이미 존재하는지 체크한다. 4. ArrayList의 0번째 index..

#문제 https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net #풀이 bitmask 문제로 x의 범위가 20까지이기 때문에 21사이즈의 배열을 생성하여 1~20의 값을 1과 0으로 저장할 수 있게끔 하였다. 연산의 수가 최대 300만건이 될 수 있기 때문에 출력을 유의해야 한다. #소스코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io...

#문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net #풀이 Kruscal 알고리즘을 이용하여 문제를 풀었다. 두 정점 간의 비용이 주어지지 않기 때문에 간선 정보를 직접 만들어줘야 한다. 이중 For문으로 모든 정점을 순회하면서 쌍을 만들어 Edge를 생성해주었고 이때 distance를 계산해서 가지고 있게 했다. (다행히 별의 개수가 100개로 제한되어 있기 때문에 시간 초과 문제는 없었다.) 그리고 EdgeList를 distance 오름차..

#문제 https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net #풀이 LCA 알고리즘을 이용해 풀었다. 입력 시 parent, child 관계를 명시해주기 때문에 인접 노드 리스트에 정보를 양쪽으로 넣어주지 않았다. child 방향으로 인접 노드 리스트가 구성되었기 때문에, depth 갱신 시 계산된 node에 대해 calculated 여부를 체크하지 않았다. parent 정보가 이미 있기 때문에 d..

#문제 https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net #풀이 트리의 두 노드가 주어지고 최소 공통 조상을 찾는 문제이다. (Lowest Common Ancestor) 입력받은 노드의 연관 관계를 인접 노드 리스트로 저장해둔다. root node를 시작으로 dfs로 모든 node의 parent와 depth를 갱신한다. 그리고 입력 받은 두 점의 depth를 비교하여 depth의 차이가 있을 경우 depth가 더 큰 node 값을 해당 no..

#문제 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net #풀이 위상정렬 알고리즘으로 풀 수 있다. 문제노드 간의 관계는 DAG(Directed Acyclic Graph) 로 표현될 수 있다. (방향성은 있으나 Cycle이 없는 것을 의미) 이 경우 indegree가 0인 Node부터 제거해가면서 순서를 정할 수 있다. 0인 Node가 제거되면 해당 Node가 가리키고 있었던 인접 Node의 indegree를 감소시..

#문제 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net #풀이 M개의 선분이 주어지고 Cycle이 발생하는 순간의 차례를 리턴하는 문제이다. Union-find 기법의 대표적인 문제이다. MakeSet(): parent, rank 초기값 설정 parent는 자기 자신, rank는 0으로 초기화 Find(a): 원소 a의 parent node (root node)를 리턴 path-compression 기법으로 중간 가지를 없애고 parent..