알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 점화식을 이용한 DP 문제였습니다. 점화식을 새울 수 있다면 쉽게 풀 수 있는 문제였습니다. N, K의 값을 입력받은 뒤, N을 K개의 합으로 만들 수 있는 경우의 수를 구하는 문제입니다. 이때, 주의할 점은 1+(N-1)과 (N-1)+1은 다른 경우로 취급한다는 것입니다. 에시를 하나 들어보겠습니다. (X, Y)는 X를 Y개로 만드는 경우라고 하겠습니다. N = 3, K = 3인 경우로 생각해보겠습니다. (0, 1) + (3, 2) / (1, 1) + (2, 2) / (2, 1) + (1, 2) / (3..

문제 링크입니다. https://www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net BFS와 DP가 섞여있는 문제였습니다. 시작하는 좌표와 방향, 끝나는 좌표와 방향이 주어졌을때, 최소한의 명령을 해야지 도착할 수 있는지 구하는 문제입니다. 문제에서 동서남북의 방향을 정해줬기에 해당하는 값을 사용했습니다. 명령에는 2가지 경우가 있습니다. 1. 1~3의 값으로 이동(로봇의 방향 기준) 2. 오른쪽 or 왼쪽으로 90˚ 이동 예를 들어, 오른쪽으로 180º 이동 후, 3칸 ..

문제 링크입니다. https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net BFS와 Dp를 사용해 풀었습니다. 두개의 C를 연결하는데 필요한 거울의 최소 갯수를 구하는 문제입니다. 먼저 거울을 설치했을 경우 레이저가 거울에 따라서 이동 방향이 달라집니다. 하지만 상하좌우 어느 방향에서 레이저가 들어오더라도 레이저의 방향이 대각선으로 변하는 경우는 없기에 이동 방향은 상하좌우만 신경쓰면 됩니다. 상하좌우만 신경쓰면 거울의 설치 갯수도 구하기 쉽습..

문제 링크입니다. https://www.acmicpc.net/problem/25216 25216번: 파밍 루트 경태는 인하대학교에서 유행하는 게임 Conquer The Planet(이하 CTP)에 빠져있다. CTP를 열심히 플레이하던 어느 날, 경태는 게임 속에 숨겨져 있던 던전을 발견했다! 던전 입구에는 플레이어를 위한 설 www.acmicpc.net 그래프 탐색과 Dp가 섞여있는 문제입니다. 1번 던전부터 시작해서 T시간이 걸릴 때까지 연결된 다른 지점을 방문해 최대 코인을 얻을 수 있는지 구하는 문제입니다. 최대 코인을 얻을 수 있는 곳에서의 필요한 방어력의 값을 구해야 합니다. 먼저, 같은 X지점을 방문했다고 해도 방문한 시간이 다르다면 서로 다른 경우로 봐야합니다. 따라서 지점과 시간을 동시에 ..

문제 링크입니다. https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net DP 문제였습니다. N개의 행렬을 합치는데 필요한 최소 연산 횟수를 구하는 문제였습니다. 위와 같이 행렬이 곱해질 때는, 행렬이 (m,k)인 행렬로 바뀌게 됩니다. 이때의 연산 횟수는 m * n * k가 됩니다. 이점을 유의하고 점화식을 접근해 보겠습니다. (1 ~ N) 까지의 행렬을 연산 횟수는 많은 경우의 수가 있습니다. 그렇기에 모든 경우의 수를 확인할 수 없으..

문제 링크입니다. https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 꽤 어려운 DP 문제였습니다. 접근이 어려워 https://js1jj2sk3.tistory.com/search/11066 해당 블로그에서 접근 방법을 알았습니다. 먼저 고려해야할 것은 인접된 파일들만 겹칠 수 있다는 점입니다. 따라서 정렬을 한 뒤 합치는등, 배열을 섞으면 안됩니다. 따라서 메모리제이션을 통해서 DP를 풀어나가야 한다는 것입니다. 저는 Dp[i][j]인 ..

문제 링크입니다! https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 그래프를 사용한 DP 문제였습니다. 먼저 지을 수 있는 건물을 지은 다음, 해당 건물을 짓고 난 다음에 지을 수 있는 건물을 지어보는 식으로 최댓값을 찾아가는 문제였습니다. ex) 1 -> X , 2 -> X , 3 -> 2 , 4 -> 1,2 , 5 -> 1,3 (A -> B는 B를 짓고 나서 A를 지을 수 있다는 의미입니다.) 해당 경우, 1번과 2번을 먼저 짓습니..

문제 링크입니다 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net DP문제였습니다. "RGB 거리1" 과는 다르게 N번과 1번의 색깔이 달라야한다는 조건이 추가되었습니다. 따라서 1번 집에 R,G,B를 선택했을때를 전부 확인한뒤, 최솟값을 비교해주면 됩니다! 문제 접근 방법 1. 1번 집의 R,G,B를 순서대로 선택한다. 2. R을 선택했을때 -> 2번 집의 G,B만 값을 구하고, R의 값에는 매우 큰 값을 넣는다. ..

문제 링크입니다 https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net DFS +DP를 이용하면 풀 수 있는 문제였습니다. 무한번 움직일 수 있는 경우, 모든 선택지마다 값을 새로 찾는 경우 -> 시간 초과가 생긴다! 따라서 해당 칸에서 움직일 수 있는 최대 횟수, 이미 왔던 곳에 다시 왔다면 무한이라고 처리해야하는 문제입니다! 문제 접근 방법 1. char배열로 값을 입력 받은뒤 int형 배열에다가 옮긴다. (H는 0으로 옮겼습니다) 2. dfs탐색..

문제 링크입니다 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제입니다. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4입니다. 가장 긴 증가하는 부분수열 4번과는 다르게 범위가 1,000,000입니다. 따라서 이중 for문을 사용한다면 시간초과가 ..

문제 링크입니다 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제입니다. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4입니다. 이때 가장 긴 길이인 4와 수열 10,..

문제 링크입니다 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 합니다. 예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, ..