Coding Test

[BOJ/JAVA] 17609번: 회문

17609번: 회문https://www.acmicpc.net/problem/17609키워드회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)문자열 그 자체로 회문이면 0, 유사회문이면 1, 그 외는 2를 출력구현문자열이 회문인지 판단하는 알고리즘문자열이 유사회문인지 판단하는 알고리즘그 외는 둘 다 아님 → 2출력 유사회문인지 판단하는 알고리즘문자 하나를 삭제해서 회문이 되는지 판단하기 위해 2개의 포인터를 사용한다.firstIndex: 문자열 맨앞에서 중앙까지 가는 포인터lastIndex: 문자열 맨뒤에서 중앙까지..

[BOJ/JAVA] 1958번: LCS 3

1958번: LCS 3https://www.acmicpc.net/problem/1958키워드LCS(Longest Common Subsequence)문자열 3개의 LCS를 구하는 프로그램구현LCS가 무엇인가?[BOJ/JAVA] 5582번: 공통 부분 문자열5582번: 공통 부분 문자열 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 키워드 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 구현 대표적인 LCS문제. 두 문자열 중 공통 부분 문..

[BOJ/JAVA] 11060번: 점프 점프

11060번: 점프 점프https://www.acmicpc.net/problem/11060키워드i번째 칸에 쓰여 있는 수를 AiA_iAi​라고 했을 때, 재환이는 AiA_iAi​이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다.가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력구현private static int dp(int index, int count)현재 위치가 index이고, 뛴 횟수가 count일 때 끝까지 갈 때의 최소 점프 횟수 반환하는 메소드끝에 도달한 경우 (index == N-1)현재까지 뛴 횟수를 반환한다.캐시값이 존재하는 경우 (cache[index][count] ≠ -2)캐시값을 반환한다.갈 수 있는 경로를 탐색한다.범위는 [1, A[index]] 이다.만약 뛰는 거..

[BOJ/JAVA] 7562번: 나이트의 이동

7562번: 나이트의 이동https://www.acmicpc.net/problem/7562키워드나이트가 한 번에 이동할 수 있는 칸은 아래와 같다.이 때 원하는 위치에 가기까지 이동 횟수를 구하라구현final static int dydx[][] 현재 위치 기준으로 나이트가 이동할 수 있는 방향(8방향)을 기록한다. private static int solution()현재 위치에서 나이트가 목적지까지 갈 때 최소 이동 횟수를 반환한다.board[][]모든 위치의 값을 -1로 초기화한다. 현재 위치 기준으로 이동할 위치(toY, toX)를 계산한다.해당 위치가 -1값이 아니라면(방문한 적이 없다면)board[toY][toX] = here.count+1 로 갱신한다. (방문 처리)갈 수 있는 경로를 큐에 추가..

[BOJ/JAVA] 1068번: 트리

1068번: 트리https://www.acmicpc.net/problem/1068키워드트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.구현private static int solution() 노드를 돌면서 리프 노트의 갯수를 반환하는 메소드방문할 노드를 찾기tree[i] 값은 i노드가 tree[i]값을 부모로 한다는 의미이다.tree[i]는 자식을 가진 노드라는 의미이므로 이 노드는 방문할 필요가 없다.만약 현재 노드가 지워지는 노드라면부모 노드가 리프노드가 될 수 있으므로, 부모 노드 추적을 하지 않는다.boolean isLeafNode[] 에 리프 노드일 수도 있는 ..

[BOJ/JAVA] 11403번: 경로 찾기

11403번: 경로 찾기https://www.acmicpc.net/problem/11403키워드가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램구현단순 플로이드-워셜 알고리즘을 이용하여 구현한다. private static void floydWarshall()k를 경유하여 i에서 j로 갈 수 있으면 경로에 추가한다.코드import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class java_11403 { static int N; stati..

[BOJ/JAVA] 5904번: Moo 게임

5904번: Moo 게임https://www.acmicpc.net/problem/5904키워드S(0)을 길이가 3인 수열 "m o o”1보다 크거나 같은 모든 k에 대해서, S(k)는 S(k-1)과 o가 k+2개인 수열 "m o ... o" 와 S(k-1)을 합쳐서 만들 수 있다.구현정리하면 S(k) = S(k-1) + “m” + “o”*(k+2) + S(k-1) 이다.dp 를 이용하여 적당한 크기의 S(k)까지 각 수열의 길이를 저장하자.dp(int n)n == 0 인 경우moo 이므로 3을 반환moo[n] ≠ -1 인 경우moo[n] 반환moo[n] 계산moo[n] = dp(n - 1) * 2 + (n + 2) + 1moo[n] 반환findMoo(int k, long left)현재 S(k)이고, 앞에..

[BOJ/JAVA] 16974번: 레벨 햄버거

16974번: 레벨 햄버거https://www.acmicpc.net/problem/16974키워드레벨-0 버거는 패티만으로 이루어져 있다.레벨-L 버거는 햄버거번, 레벨-(L-1) 버거, 패티, 레벨-(L-1)버거, 햄버거번으로 이루어져 있다. (L ≥ 1)구현모든 버거의 상태를 문자열로 나타낼 수 없다. (메모리를 많이 잡아먹기 때문)각 레벨의 버거마다 버거의 사이즈, 버거에 들어가는 패티의 양을 저장한다.buggers[]patties[]위 두 배열을 dp를 사용하여 값을 저장한다.dp(int level)현재 레벨이 level-버거일 때 버거의 크기를 반환한다.level == 0 인 경우패티만 존재하므로 1 반환이미 계산한 값인 경우계산한 값 반환계산하기버거의 크기는 [번] [(level-1)-버거] ..

[BOJ/JAVA] 1074번: Z

1074번: Zhttps://www.acmicpc.net/problem/1074키워드2^N× 2^N인 2차원 배열을 Z모양으로 탐색N > 1인 경우, 배열을 크기가 2^(N-1)× 2^(N-1)로 4등분 한 후에 재귀적으로 순서대로 방문구현move(int y, int x, int n)size = 2^n가장 작은 경우 size가 2^0인 경우좌상단좌상단에 r, c의 범위가 있는 경우1/4 사이즈로 재귀호출한다. 시작 위치는 좌상단이므로 동일move(y, x, n - 1);좌상단에 r, c의 범위가 없는 경우좌상단의 크기만큼 count 증가우상단우상단에 r, c의 범위가 있는 경우1/4 사이즈로 재귀호출한다. 시작 위치는 우상단이므로 x 값만 (size/2)만큼 이동move(y, x + (size / 2),..

[BOJ/JAVA] 6209번: 제자리 멀리뛰기

6209번: 제자리 멀리뛰기https://www.acmicpc.net/problem/6209키워드돌섬에서 탈출구 사이에는 총 n개의 작은 돌섬선생님은 이 n개의 작은 돌섬들 중 m개를 제거하여 학생들이 최대한 멀리뛰기 연습의 효율을 높이기 위해서 학생들이 각 돌섬을 점프한 거리의 최솟값을 최대한 크게 하려고 한다.구현매개변수 탐색을 이용하여 구현한다.템플릿low, high 값은 항상 범위 내로 설정한다.low = 1high = 돌섬으로부터 탈출구 까지의 최대 거리(1_000_000_000) 반복문의 속행 조건은 low≤high 이다. long mid = (low + high) / 2;m개를 제거했을 때, 거리가 mid 이상이 되도록 할 수 있는가? mid 길이로 나눠줄 수 있다면low = mid + 1 ..