Java

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 사용한 알고리즘 : DFS 풀이전략 (0,0)에서 (N-1,N-1)까지의 인덱스에서 상하좌우 방향으로 dfs를 수행한다. dfs 탐색은 상하좌우 방향의 인덱스를 대상으로 방문하지 않았으면서 해당 위치의 값이 기존의 인덱스에서의 값과 일치할 때 탐색을 수행한다. 이 문제에서는 적록색약인 경우와 아닌 경우 두 가지 경우에서 나뉜 구역의 수를 구해야 하므로dfs를 구현한 함수의 매개변수에 ..

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/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 풀이 사용한 알고리즘 : DP(Dynamic Programming) 풀이전략 N=1일 때, 동물원에서 우리의 형태는 아래와 같다. 첫 행에 사자가 있을 경우는 (1) 없는 경우 ( =d[1][0]) (2) 1열에 하나 있는 경우 ( =d[1][1]) (3) 2열에 하나 있는 경우 ( =d[1][2]) 로 총 3가지 경우가 있다. N=2일 때, 동물원에서 우리의 형태는 아래와 같다. 두번째 행에서 사자가 있을 경우는 (1) 사자가 없는 경우 : 첫번째 행에서 사자가 어떤 형태로 있어도 상관없다. d[2][0] = d[1][0]+d[..

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..