알고리즘||코딩테스트

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 문자열에서 동일..

https://www.acmicpc.net/problem/2688 2688번: 줄어들지 않아 첫째 줄에 테스트 케이스의 개수 T(1

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 풀이 사용한 알고리즘 : 스택 풀이전략 1. 탑의 높이 입력이 들어올 때마다 입력 값이 stack의 top에 저장된 값보다 크면, 기존 stack에서 top 원소가 더 큰게 있을 때까지 pop하고 입력 값이 stack의 top에 저장된 값보다 작으면, stack의 top 인덱스를 resut에 저장하고 기존 stack의 원소들을 유지한다. 2. stack에 현재 입력값을 push 하고 1번 과정을..