백준

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

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 풀이 사용한 알고리즘 : BFS 풀이전략 전형적인 BFS문제였다. 한 정사각형에서 가로, 세로, 대각선 모두를 탐색해야 하므로, dx, dy를 총 8개 두어 모든 방향으로의 탐색이 가능하도록 했다. 제출코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java..

https://www.acmicpc.net/problem/2852 2852번: NBA 농구 첫째 줄에 골이 들어간 횟수 N(1Date로의 형변환이 가능했음 - getTime을 했을 때 반환되는 수가 음수가 나왔었다. 이는 한국 시간의 오류로 32400000를 더해주어 해결했다. 제출코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.text.ParseException; import java.text.SimpleDateFormat; import java.util.Date; import java.util.StringTokenizer; public class Main {..

https://www.acmicpc.net/problem/9079 9079번: 동전 게임 입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 세 줄로 이루어지며, 한 줄에 세 개의 동전모양이 주어지는데, 각각의 동전 표시 사이에는 하나의 공백이 www.acmicpc.net 풀이 사용한 알고리즘 : 비트마스크, bfs 풀이전략 1. 주어지는 3x3 행렬을 2진수 숫자 하나로 변환한다. ex) H=1, T=0이라고 할 때, HTT HTT = 100100011(2) THH 2. 행을 하나 뒤집었을 경우, 열을 하나 뒤집었을 경우, 대각선으로 뒤집었을 경우 등 가능한 모든 경우를 탐색하기 위해 BFS를 사용한다. 이 때, 연산을 수행할 때마다 count를 1 증가시킨..

https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 풀이 사용한 알고리즘 : 큐 풀이전략 1. 0~9의 수를 큐와 리스트에 추가한다. 2. 큐의 원소를 하나씩 deQueue하고 그 수보다 작은 수를 찾은 뒤 '(deQueue한 원소)x10 + (원래 원소보다 작은 찾은 수)'를 리스트에 추가한다. 이를 큐가 빌 때까지 반복한다. 3. 리스트의 N번째 값을 출력한다. 제출코드 import java.util.Main*; public cl..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 사용한 알고리즘 : 백트래킹 풀이전략 아래 그림은 N=4인 경우, 모든 경우의 수를 탐색할 수 있도록 만들어진 상태공간트리이다. (상태 공간 : 문제의 해답을 탐색하기 위한 탐색 공간, 상태공간트리 : 탐색 공간을 트리 형태의 구조로 암묵적으로 해석한 트리) (1,1)은 1번 행 1번째 열에 퀸을 둔다는 의미이다. 1. 위와 같은 트리를 탐색하는 중 해당 노드가 이전 노드와 비교했을 경우, 같은 열 또는 대..