알고리즘||코딩테스트

https://www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 풀이 사용한 알고리즘: DP 풀이전략 문제에서 주어진 식대로 d[i] = d[i/P] + d[i/Q] 를 사용하여 N에서의 An을 구한다. 단, Bottom-up 방식을 사용하면 i가 1~N까지 모든 경우의 수를 구하게 되는데 위 방식에서 Map에 많은 노드들이 삽입되어 메모리초과가 발생한다. 따라서 Top-down 방식을 사용하여 메모이제이션하는 수를 줄여야한다. Top-down 방식을 사용하면 i가 1~N까지의 모든 경우의 수를 구하지 않고, N에서 부터 정말 필요로하는 값들만을 저장해두므로 메모리초과가 발생하지 않는다. 또한 DP문제..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 사용한 알고리즘 : DP 풀이전략 문제에서 인접한 집들 간에 동일한 색이 칠해지지 않으면 된다고 했다. 즉, 첫번째 집이 빨간색으로 칠해졌다면 두번째 집은 빨간색이 아닌 초록색이라 파란색으로 칠해져야한다. 그리고 세번째집은 두번째 집이 칠해지지 않은 두 가지 색중 하나로 칠해져야한다. int d[][] = new int[N][3] 라는 2차원 배열은 특정 인덱스에서 각각..

https://www.acmicpc.net/problem/1245 1245번: 농장 관리 첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수 www.acmicpc.net 풀이 사용한 알고리즘: BFS 풀이전략 1. 주어진 입력을 2차원 배열에 작성한다. 2. (0,0)에서 (N-1,M-1)까지 각각의 인덱스를 BFS 탐색한다. 3. 특정 인덱스에서 주변에 인접한 모든 방향 탐색 중, 작성한 2차열 배열 인덱스를 넘어서지않고, 방문하지 않았으며 그래프상 같은 수를 가진 경우 방문처리하고 해당 인덱스를 Inqueue한다. 4. BFS 탐..

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 풀이 사용한 알고리즘 : DFS 풀이전략 1. 입력에 대응되는 그래프를 2차원 배열에 저장한다. 2. (0,0)에서 (n-1,m-1) 까지의 점에서 동서남북 모든 방향으로 dfs 탐색을 한다. 3. dfs 탐색 중 한 번이라도 방문하지 않은 지점을 통과하면 paintingCount를 증가시킨다. 4. 하나의 지점에서 최대로 방문한 횟수를 maxCount에 저장한다. 5. paintingCount와 ma..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 사용한 알고리즘 : 백트래킹 풀이전략 아래는 입력으로 {1,2,3}이 주어졌을 경우의 상태 트리이다. 루트 노드부터 설명하면, depth=1에서는 1이라는 원소가 삽입되는 경우 왼쪽 노드, 삽입되지 않는 경우 오른쪽 노드로 표시한다. 이와 같이 특정 원소가 삽입되는 경우는 왼쪽노드로, 삽입되지 않는 경우를 오른쪽 노드로 확장해나가면 위와같은 상태트리가 그려..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 사용한 알고리즘 : BFS, 트리구조 풀이전략 1. 주이진 입력을 BFS를 사용하여 트리로 만든다. 2. BFS로 탐색 중, 특정 노드의 부모 노드를 저장해둔다. 3. 저장해뒀던 부모 노드들을 출력한다. 제출코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이 사용한 알고리즘 : 다이나믹 프로그래밍(DP) 풀이전략 d[i] 는 2xi 직사각형을 2x1, 1x2 타일로 채우는 방법의 수를 담은 변수이다. 2x1 타일은 d[i-1] 에 하나의 타일을 덧붙인 것과 같은 결과이고, 1x2 타일은 d[i-2] 에 두개의 타일을 덧붙인 것과 같은 결과이다. 따라서 d[i] = d[i-1]+d[i-2]라는 식이 도출된다. 만약 2x2 타일도 존재했다면, d[i-2]에서 덧붙일 수 ..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 사용한 알고리즘: 다이나믹 프로그래밍 풀이전략 아래의 표는 n 입력에 따라 합으로 나타낼 수 있는 경우의 수들을 나타낸다. 빨간선을 기준으로 첫번째 문단은 1 + [이전의 경우의수] 두번째 문단은 2 + [2번째 전의 경우의수] 세번째 문단은 3 + [3번째 전의 경우의수] 가 출력되는 것을 확인할 수 있다. 따라서 d[i]를 i 입력 시 합으로 나타낼 수 있는 수의 개수라고 할 때 d[i]=d[i-1]+d[i-2]+d[i-3] 라는 식이 도출된다. 제출코드 import java.io.Bu..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 사용한 알고리즘: 다이나믹 프로그래밍 풀이전략 마지막 계단을 반드시 밟아야하므로 방법은 2가지로 나뉜다. 1. 마지막에서 2번째 전 계단을 밟고 마지막 계단을 밟는 경우 2. 마지막에서 바로 전 계단을 밟고 마지막 계단을 밟는 경우 하지만 2번의 경우에는 전전 계단을 밟았을 가능성이 있다. 이를 피하기 위해 수정을 하면 (수정후) 2. 마지막에서 3번째 전 계단을 밟고, 마지막 직전 계단과 마지막 계단을..

https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 풀이 사용한 알고리즘 : 다이나믹 프로그래밍(DP) 풀이전략 1~5000까지의 입력이 주어진다고 했으므로 바텀업 방식으로 1kg부터 5000kg까지의 결과값을 미리 구한다. i kg일 때 최소의 설탕 봉지 수는, i-3 kg에서와 i-5 kg에서의 최소 봉지수에 1을 더한 값 중 더 작은 값이다. 단, i-3 kg에서와 i-5 kg에서 3kg와 5kg 봉지를 갖고 모두 담을 수 있는 경우에서 적용된다. 1)..