알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 행렬 제곱을 분할 정복을 통해 푸는 문제입니다. 이 문제를 풀기 위해서는 행렬의 제곱을 할 수 있어야 합니다. 행렬 제곱이 어떻게 계산되는지 2 * 2 / 3 * 3 행렬을 통해 확인해보겠습니다. 2 * 2 / 3 * 3 행렬의 곱셈을 통해, 앞 행렬은 [X][Y] 중 X부분이 바뀌고, 뒤 행렬은 Y부분이 바뀌는 것을 알 수 있습니다. 이를 통해 행렬의 곱셈을 구현할 수 있습니다. matrix..

문제 링크입니다. https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net vector와 백트래킹을 이용한 문제입니다. M개가 선택된 수가 항상 오름차순이여야 되며, 같은 수가 여러번 선택되도 됩니다. N개가 입력될 때, 중복된 수가 입력될 수 있기에, 저는 중복된 수를 지우고 시작했습니다. 1. 중복된 수 지우기 sort(num.begin(), num.end()); num.erase(unique(num.begin(), num.end()), num...

문제 링크입니다. https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹을 이용한 문제입니다. N개의 수가 주어졌을 때 M개의 수를 선택하고 출력하는 문제입니다. N개의 수가 중복되어 주어질 수도 있으며, 선택된 수열이 항상 오름 or 내림차순이 아닐 수도 있는 것이 다른 점이였습니다. 저는 중복된 수가 들어왔을 때, 중복된 수를 모두 없애줬습니다. -> 백터를 사용하면 편합니다. 예를 들어 (9 7 9 1)이 입력되었을 때, (1 7 9)..

문제 링크입니다. https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 백트래킹을 이용한 문제입니다. N개의 수가 주어진뒤, 주어진 수를 통해 M개만큼 출력하는 문제입니다. 중복된 수도 출력이 되야하기에, check 배열을 통해서 선택된 수를 확인하면 안되는 문제입니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #..

문제 링크입니다. https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹을 이용한 문제였습니다. 1~N까지의 수에서 M개의 수를 선택하는 문제입니다. 중복 선택도 가능하기에, check 배열을 통해 X번째 수가 선택되었는지를 확인하지 않고 푸는 문제였습니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include..

문제 링크입니다. https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 두 문자열이 주어졌을때, 공통되는 가장 긴 수열을 찾는 문제입니다. 이 문제의 핵심은 연속된 문자열이 아닌 부분 수열이라는 점입니다. 따라서 X, Y 문자열을 하나하나 비교해나가면서 최댓값을 확인하면 됩니다. 그림으로 한번 확인해보겠습니다. X, Y 문자열이 주어졌을때, 두 문자열 중 하나를 고정시킵니다. X 문자열을 고정했다고 했을때..

문제 링크입니다. https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 행렬과 분할 정복을 이용해 푸는 문제입니다. 이 문제를 풀기 전에 피노나치 수열을 행렬로서 나타낼 수 있다는 것을 알아야합니다. 더 알아보고 싶다면 해당 링크를 확인해주세요 https://jow1025.tistory.com/101 위의 정보를 통해서 피보나치가 행렬로 계산이 가능함을 확인할 수 있었습니다. 또한 행렬의 곱셈도 어떤 방식인지 확인할 수 있었습니다. 따라서 N번째 피보나치 수열을 구할 때, N값에 따라서 나눠서 계산해 주면 됩니다. N이 짝수일..

문제 링크입니다. https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 분할정복을 이용한 거듭제곱을 활용해 푸는 문제였습니다. A를 B번 제곱을 그냥하게 되면 long long 범위도 벗어나기 때문에 다른 방법이 필요합니다. 또한 B의 범위가 21억이기에, 시간 초과가 생길 수도 있습니다. 이때 사용하는 방법이 분할 정복을 활용한 거듭제곱입니다. 먼저 제곱을 하는 코드를 만들어 보겠습니다. int ans = 1; for(int i = 1; i A >> B >> C; solve(); return 0; } 질문 및 조..

문제 링크입니다. https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net DFS를 사용하여 푸는 문제입니다. 임의의 점을 하나 선택한 뒤, 해당 점에서 다시 탐색을 하여 답을 구하는 문제였습니다. 1 ~ N까지의 정점이 있을 때, 가장 긴 노드 사이의 거리를 구하는 문제였습니다. 1번 점부터 N번 점까지 모든 경우를 확인하기에는 경우가 너무 많아 시간 초과가 생길 수 있습니다. 따라서 다른 방법을 통해 지름을 구해야하는데 그중 한 ..

문제 링크입니다. https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net DFS를 이용한 문제였습니다. 1번 정점에서 시작해서 가장 긴 거리에 있는 점을 찾은 뒤, 해당 점에서 되돌아오면서 길이를 재는 방법이였습니다. 해당 문제는 두번의 DFS를 사용해야하는 문제였습니다. 1~N번까지의 점 중에서 임의의 점을 하나 선택합니다. 해당 점에서 가장 거리가 먼 점을 하나 확인합니다. 이 점을 X라 하겠습니다.(저는 1번을 임의로 정했습니다...

문제 링크입니다. https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 비트마스킹을 이용한 문제입니다. 비트마스킹을 잘모르면 해당 링크를 통해 공부하면 풀 수 있습니다. https://rebro.kr/63 비트마스킹이 아닌 배열로서 문제를 풀면 시간초과가 걸립니다. 1~20까지의 수이니, 변수를 20자리로 생각하면 됩니다. 예를 들어 00000000000000000001 -> 1이 존재한다 01000000000000000000 -> 19가 존재한다. 따라서 X라는 수가 존재한다면 변수..

문제 링크입니다. https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 재귀를 이용한 문제였습니다. 규칙을 찾는 것이 중요했습니다. (R , C)까지 모든 경로를 탐색하는 것이 아닌 계속 구역을 나누면서 더해주는 것이 중요합니다. (R,C)가 처음에 몇분면인지, 그리고 얼마를 더해야하는지도 구해봤습니다. 이번에는 4분면으로 다시 나눌때 어떻게 해야하는지를 확인하겠습니다. 위의 정보를 이해하면 코드를 쉽게 짤 수 있습니다. 자세한 것은 코드를..