복습노트 복습노트

문제 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net n * n 행령이 주어지면 b번곱한 행렬을 출력하는 문제입니다 행렬이 너무 커질 수 있으므로 행렬이 모든 값은 1000으로 나눈 나머지입니다. 딱 보면 백준 1629 문제와 매우 유사합니다. 분할 정복으로 접근하면 될것 같습니다. 여기서 막혔던 것은 분할정복으로 이차원 배열을 return 하는 것이 까다로웠습니다. int arr[6][6]; int result[6][6]; cin >> n >> b; for (int i = 0; i < n; i++) { for (int j ..

문제 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문자열 주어지고 폭발 문자열이 주어집니다. 주어진 문자열에서 폭발 문자열이 발견되면 폭파됩니다. 예를들어 주어진 문자열이 mirkovC4nizCC44 위와 같고 폭발 문자열이 C4 라면 마지막에는 mirkovniz 남습니다. 처음에 이 문제를 발견했을 때 생각했던게 먼저 KMP 알고리즘으로 문자열과 폭발 문자열이 같은 부분을 찾고 문자열을 폭발 문자열을 빼고 합치는 과정이 번거로웠습니다. 힌트를 얻고 보니 "스택" 자료구조를 사용해 해결하였습..

문제 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net v개의 정점과 e개의 간선정보를 입력받습니다. 간선정보는 {a, b, c}로 이루어져 있는데 a로부터 b로 가는 경로가 있는데 c만큼 비용이 든다 라는 의미입니다. 시작점을 입력받을 때 시작점에서 시작해서 1번 정점부터 v번 정점까지 최단 경로 비용을 각각 구하는 문제입니다. 또한 각 정점과 정점은 여러개의 경로가 있을 수 있습니다. 일단 처음에 이 문제를 봤을 때 정점과 정점 사이의 비용이 음수가 없어서 다익스트라 알..

문제 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net n개의 사람수와 m개의 파티수가 주어집니다. 그 다음 진실을 아는 사람의 수와 진실을 아는 사람들의 번호가 주어집니다. 또한 진실을 아는 사람과 파티에 참석하면 나머지 사람들도 진실을 알게 됩니다. 그 다음 m개의 줄에 파티를 참여하는 수와 파티를 참여하는 사람들의 번호가 m개의 줄에 주어집니다. 이 때 진실을 아는 사람의 눈을 피해 거짓말을 할 수 있는 파티의 개수의 최댓값을 구하는 문제입니다. 예를 들어 3 4 1 3 1 1 1 2 2 1 2 3 1 2 3 n =..

문제 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 전위 순회한 트리가 주어지면 이를 후위순회한 결과를 출력하면 되는 문제입니다. 제가 처음에 생각한 전략은 총 2가지 입니다. 1) 전위순회한 트리가 입력이 break point가 없게 들어오므로 어떻게 입력이 끝내는지 알 수 있나? 2) 입력으로 들어온 전위 순회 트리를 트리로 구현해 다시 후위 순회한 결과를 출력 typedef struct node *pointer; typedef struct node{ int ans; pointer left,..

문제 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net n * n 배열이 주어지면 0은 무시하고 1은 집의 위치이고 2는 치킨 집입니다. 여기서 최대 m개의 치킨 집만 존재할 수 있는데 치킨 집과 집의 거리가 최소가 되게 하는 거리값을 구하는 문제 입니다. 예를들어 n = 5 , k = 3 이고 다음과 같은 배열이 주어지면 0 0 1 0 0 0 0 2 0 1 0 1 2 0 0 0 0 1 0 0 0 0 0 0 2 거리의 최솟값은 5입니다. n = 5, k = 2 이고 다음과 같은 배열이 주어지..

문제 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS란 최장공통 부분 수열이라는 의미로 예를 들어 ACAYKP CAPCAK 두개의 문자열이 주어지면 공통 부분 수열들이 존재합니다. A AC ACA ACAK 여기서 제일 길이가 긴 ACAK가 LCS가 됩니다. LCS의 길이를 구하는 방법은 여러가지가 있습니다. 그 중 2차원 배열을 사용해 DP 형식으로 풀어보겠습니다. 먼저 dp의 인덱스가 0인 부분을 모두 0으로 넣어줍니다. dp[1][1]부터 시작합니다. 점..

문제 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 다음과 같이 n행 3열의 배열이 주어지면 0열은 다음 행의 0열과 1열 중 한곳으로 이동할 수 있습니다. 1열은 다음행의 0열, 1열, 2열 중 한곳으로 이동할 수 있습니다. 2열은 다음행의 1열, 2열로 중 한곳으로 이동할 수 있습니다. 첫행부터 시작해서 마지막행까지 내려가면서 최댓값과 최솟값을 구하는 문제입니다. 처음에 단순하게 dp형태로 문제를 해결하였습니다. int arr[100001][3]; int dpx[100001][3]; int dpn[100001][3];..