Algorithm

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

[BOJ/JAVA] 20551번: 마스터 배지훈의 후계자

20551번: Sort 마스터 배지훈의 후계자https://www.acmicpc.net/problem/20551키워드먼저 제자들에게 N개의 원소를 가진 배열A를 주고, A의 원소들이 오름차순으로 정렬된 배열 B를 만들게 한다.그 다음 M개의 질문을 한다.제자들은 주어진 정수 D가 B에서 가장 먼저 등장한 위치를 출력단, D가 B에 존재하지 않는 경우에는 -1를 출력구현정렬 후 탐색이 이루어지므로, 입력값을 정렬할 필요가 있다.중요한 것은 가장 먼저 등장한 위치를 출력이므로 이분탐색으로 찾더라도 가장 앞에 있는 원소를 찾아야 한다. 템플릿low, high 모두 범위 안에 들어오도록 한다.반복문의 속행 조건은 low≤high (항상 high가 low 이상이여야 한다.)해당 숫자를 찾은 경우가장 앞에 있는 원..