SY DevLog

10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 백준 2740번 : 행렬 곱셈을 응용한 문제이다. B의 범위가 매우 크기 때문에 단순히 2740번 문제에서 for문을 하나 더 추가해서 문제를 풀면 시간초과가 난다. 이 문제는 행렬을 곱하는 똑같은 과정을 반복하기 때문에 이미 한번 계산한 결과는 다시 재사용하면 계산 횟수를 줄일 수 있다. 따라서 분할과 정복 방법으로 문제를 해결하였다. 만약 B가 짝수라면, B번 행렬을 곱한 결과는 B/2번 행렬을 곱한 결과 * B/2번 행렬을 곱한 결과가 된다. 이 때 B/2번 행렬을 곱한 ..

1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 다이나믹 프로그래밍으로 해결할 수 있다. dp[n][l][r] : n번째 빌딩을 세울 때, 왼쪽에서 보이는 빌딩의 수가 l개, 오른쪽에서 보이는 빌딩의 수가 r개가 되도록 건물을 배치하는 모든 경우의 수 먼저, 처음으로 빌딩을 하나 세웠다고 치자. 건물이 하나밖에 없으므로 왼쪽에서 보이는 건물의 수는 1개, 오른쪽에서 보이는 건물의 수도 1개가 된다. -> dp[1][1][1] = 1 그 다음으로 두번째 빌딩을 하나 세운다. 그러면 두 가지 중 하나이다. 왼쪽에..

4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 다이나믹 프로그래밍으로 문제를 해결하였다. 메모이제이션을 위해 3차원 dp배열을 생성했다. int[][][] dp = new int[2*N+1][2*N+1][N+1]; 첫번째 인덱스는 몇일이 지났는지를 의미하고, 두번째 인덱스는 현재 시점에서 반알짜리 알약의 개수, 세번째 인덱스는 한알짜리 알약의 개수를 의미한다. dp[t][h][w] : t일이 지났을 때, 반알짜리 알약의 개수가 h개이고, 한알짜리 알약의 개수가 w개일 때 가능한 모든 문자열의 개수 점화식을 세우면 아래와 같..

2228번: 구간 나누기 N(1≤N≤100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1≤M≤⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되어야 www.acmicpc.net dp[n][m] : n개의 수를 m개의 구간으로 나누었을 때 최대 합 arr[i] : 입력받은 수들을 저장 n번째 수가 m번째 구간에 포함되어 있는지, 포함되어 있지 않는지 두 가지 경우로 나눌 수 있다. - n번째 수가 구간 m에 포함되지 않은 경우 : dp[n][m] = dp[n-1][m] n-1번째 수가 구간 m에 포함된 경우의 최대 합(dp[n-1][m])과 동일하다. - n번째 수가 구간 m에 포함된 경우 : dp[n][m] = max(d..

2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 합이 k원이 되면서, 순서만 다르고 조합이 같은 경우는 하나의 경우로 여긴다. 우선 각각의 동전의 가치를 coin 배열을 생성하여 차례대로 넣어주었다. int[] coin = new int[n]; coin[0] = 1 coin[1] = 2 coin[2] = 5 이 문제를 다이나믹 프로그래밍으로 풀기 위해 점화식을 세웠다. 처음에는 합이 k원이 되는 조합을 dp[k]라고 할 때, dp[k] = dp[k-coin[0]] + dp[k-coin[1]] + dp[k-coi..

7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net HashSet을 이용하여 직원이 들어오면("enter") set에 추가하고, 직원이 나가면("leave") set에서 제거하는 방식으로 문제를 해결하였다. 최종적으로 set에 남아있는 직원이 현재 회사에 있는 사람이 된다. Iterator를 통해 set에서 직원을 하나씩 꺼낸 다음에 list에 담고, list를 이름 역순이 되도록 정렬했다. 전체 코드 :

3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 누적합으로 문제를 해결하였다. 각각의 높이에 따라 석순과 종유석의 개수를 카운트하는 두 개의 배열 bot, top을 생성하였다. 예를 들어, 첫 번째 구간에서는 석순이 7개 존재하므로 bot[1] = 7 이 된다. 두 번째 구간에는 석순이 6개 존재하므로 bot[2] = 6 세 번째 구간에는 석순이 5개 존재하므로 bot[3] = 5 네 번째 구간에는 석순이 1개 존재하므로 bot[4] = 1 다섯 번째 구간에는 석순이 0개 존재하므로 bot[5] = 0 첫 번째 ..

3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 매번 느끼는거지만 스택을 이용한 문제는 개인적으로 너무 어렵다.. 보통 스택을 사용하는 문제의 경우, 스택 자체보다는 스택을 어떻게 사용해야할 지 생각해내는게 어려운 것 같다. 이번 문제도 역시 해결하는데 오랜 시간이 걸렸는데, 가장 어려웠던 것은 키가 같은 사람이 여러명일 경우에 어떻게 해야할지 고민을 오래 했다. 먼저, 이 문제는 특정 사람이 비교기준이 될 때, 스택안에 어떤 사람들이 들어가야 하는지 고민해야 한다. 2 4 3 2 1 ..

1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 정답률에 비해 어려웠던 문제였다. 비트마스크가 아직 익숙하지 않아서 그런지 비트마스크를 이용해서 메모이제이션을 어떻게 해야할지 고민하는데 시간이 오래 걸렸다. n번째 자리에 k라는 수가 오기 위해서는 n-1번째 자리에 k+1 혹은 k-1가 있어야 한다. 만약 비트마스크를 이용하지 않고 메모이제이션을 하면 다음과 같이 점화식을 세울 수 있다. dp[n][k] = dp[n-1][k-1] + dp[n-1][k+1] 그런데 이 문제에서는 해결해야하는 조건이 있다. 0부터 9까지 모든 수를 한번씩 사용해야 한다. 따라서, 0~9중에서 어떤 수를 사용했는가를 비트마스크를 이용하여 기록해야 ..

14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 트라이를 사용하여 문제를 해결하였다. 보통은 트라이노드의 Key값에 char형을 넣지만, 이 문제에서는 두 번째 예제의 경우 문자열이 하나의 노드에 들어가야 하므로 char형이 아닌 String형으로 변경하였다. 또한, 문제에서 알파벳 순서대로 출력해야 하므로 자식 노드들 중 알파벳 순서상 앞에 위치한 노드부터 탐색해야 한다. 따라서 TreeMap을 사용하여서 자동으로 알파벳 순으로 정렬되도록 했다. Map childNodes = new TreeMa..