Java

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. 위와 같은 트리를 탐색하는 중 해당 노드가 이전 노드와 비교했을 경우, 같은 열 또는 대..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 사용한 알고리즘 : DFS 풀이전략 1. 이중 ArrayList를 사용하여 각 노드가 가지고 있는 자식 노드의 번호를 저장한다. 2. 각 노드들의 부모 노드 번호를 저장하는 배열을 만든다. 3. 제거한 노드의 부모노드에 대응되는 ArrayList에서 제거한 노드의 번호를 삭제한다. 4. DFS를 통해 트리를 탐색하고, 방문한 노드 중 자식 노드가 없는 경우 count를 1씩 더한다. 제..

https://www.acmicpc.net/problem/21758 21758번: 꿀 따기 첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다. www.acmicpc.net 풀이 사용한 알고리즘 : 누적합(Prefix Sum) 풀이전략 1. 입력한 값들의 누적합을 새로운 배열에 저장한다. 2. 문제에서 구하는 최대의 꿀양이 나올 수 있는 경우는 아래의 세가지 중 하나의 경우이다. 1) 벌 벌 꿀통 좌측의 벌은 항상 배열의 최좌측에 위치, 꿀통은 배열의 최우측에 위치한다. 중간의 벌을 이동시키며 가질 수 있는 최대 꿀양을 알아낸다. 2) 꿀통 벌 벌 꿀통은 항상 배열의 최좌측에 위치, 우측의 벌은 배열의 최우측에 위치한다. 중간의 벌을 이동시키며 가질 수 있는 최대 꿀양을 알아낸다. 3) 벌 꿀통 벌 좌측의 ..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 사용한 알고리즘 : DP, LCS(Longest Common Subsequence) 풀이전략 1. 주어진 두 문자열 길이에 맞게 이차원 배열을 선언한다. int d[][] = new d[두번째문자열.length()+1][첫번째문자열.length()+1] 2. 문자열에서 동일한 문자가 있을 경우 D[i+1][j+1]=D[i][j]+1 문자열에서 동일..