🎨 문제 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 📘 풀이 이 문제는 DP로 풀 수 있습니다. 우선 LCS(Longest Common Subsequence)를 예시로 이해해봅시다. 우선 두 문자열이 주어집니다. (더 많을 수도 있지만 문제에서는 2개가 주어집니다.) ACAYKP CAPCAK 서브 시퀀스는 주어진 문자열에서 순서를 바꾸지 않고 몇 개의 글자를 뺀 것을 말합니다. 첫 번째 문자열의 경우 ACA, AKP, C 등이 서브 시퀀스가 됩니다. LCS는 ..
🎨 문제 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 📘 풀이 이 문제는 BFS로 풀 수 있습니다. 이전에 풀이한 문제와 유사하여 이 글을 읽고 오시면 도움이 될 것입니다. 차이점은 토마토 농장이 높이(H)가 생긴 겁입니다. 문제 풀이 과정을 정리하면 다음과 같습니다. 익어야할 남은 토마토의 개수를 계산 BFS를 통해 익은 토마토와 인접한 토마토를 익힘 BFS가 종료되었을 때 남은 토마토가 모두 익었다면 -1, 아니라면 토마토가 익기까지 걸린 시간 반환 농장에 높이(H)가 생겼으므로..
🎨 문제 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 📘 풀이 이 문제는 BFS로 풀 수 있습니다. 익은 토마토를 큐에 넣고 빼면서 주변 토마토를 익은 토마토로 만들어주면 됩니다. 전체 토마토의 개수를 셉니다. 토마토 농장에는 벽이 있습니다. 입력을 받을 때 벽에는 토마토가 없기 때문에 전체 토마토 개수에서 벽 부분은 빼줍니다. 그리고 익은 토마토일 경우 큐에 토마토를 담아 둡니다. for (int i = 0; i < N; i++) { StringTokenizer st = new Strin..
🎨 문제 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 📘 풀이 이 문제는 DP로 풀 수 있습니다. 문제를 정리하면 다음과 같습니다. 길이가 최대 2,000인 수열이 주어진다. 수열의 [S, E] 구간의 수가 펠린드롬인지 판별한다. 판별 질의는 최대 1,000,000 주어진다. 주어진 구간이 펠린드롬인지 판별하는 일반적인 방법은 구간 양 끝점부터 서로 같은 수인지 비교를 하는 방법입니다. 이 경우 한 쿼리 당 최대 수열의 길이만큼의 확인이 필요합니다. 하지만 질의가 1,000,000번 주어지기 때문에 매 번 비교를 할 수 없습니다. 그래서 이전 쿼..
🎨 문제 1513번: 경로 찾기 첫째 줄에 0개 방문했을 때, 1개 방문했을 때, ..., C개 방문했을 때 총 경로의 개수를 한 줄에 공백을 사이에 두고 출력한다. 경로의 개수는 1,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 📘 풀이 이 문제는 DP로 풀 수 있습니다. 만약 완전 탐색을 할 경우 거쳐가는 오락실의 개수의 경우의 수(0~50)만큼 학원을 가는 경우의 수를 완전탐색으로 구하게 됩니다. 1,000,0007로 나누는 것을 보면 경우의 수가 아주 커서 이 방법은 옳지 않음을 짐작할 수 있습니다. 따라서 이동 경로를 기억하여 다음 연산에 사용하도록 합시다. DP문제 풀이의 중요한 포인트는 점화식도 있지만, 상태값도 중요합니다. 점화식은 특정 상태에서의 최적값을 구하는 식..
🎨 문제 https://www.acmicpc.net/problem/4781 4781번: 사탕 가게 각 테스트 케이스의 첫째 줄에는 가게에 있는 사탕 종류의 수 n과 상근이가 가지고 있는 돈의 양 m이 주어진다. (1 ≤ n ≤ 5,000, 0.01 ≤ m ≤ 100.00) m은 항상 소수점 둘째자리까지 주어진다. 다음 n개 www.acmicpc.net 📘 풀이 이 문제는 DP로 풀 수 있습니다. 특히 배낭 문제를 아신다면 쉽게 풀 수 있습니다. 문제의 특이한 점은 사탕의 가격이 소수점 둘째자리까지 표현된 소수인 점입니다. 소수 간 연산은 오차가 발생할 수 있으므로 소수를 정수로 변환해 주었습니다. 저는 문자열에서 '.'을 지워주는 방식을 선택했습니다. String input = "8.00"; String..
🎨 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📘 풀이 이 문제는 정렬과 그리디로 풀 수 있습니다. 폭격 미사일을 s에 대해 오름차순, e에 대해 내림차순으로 정렬합니다. // int[][] targets = [[s, e]] Arrays.sort(targets, (int[] a, int[] b) -> { if (a[0] - b[0] == 0) return b[1] - a[1]; return a[0] - b[0]; }); 요격 미사일을 최소한으로 사용해야 하기 때문에 최대한 많은 폭격 미사일이 겹치는 지점을 찾아야 합니다. 폭격 미사일은 (s, e..
🎨 문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr📘 풀이이 문제는 분할 정복으로 풀 수 있습니다. 루트 노드를 기준으로 왼쪽 서브 트리와 오른쪽 서브 트리가 포화 이진 트리인지 확인하면 됩니다. 우선 포화 이진 트리에 대해 간단히 알아보겠습니다.포화 이진 트리포화 이진 트리는 모든 내부 노드가 두 개의 자식 노드를 가지며 모든 리프 노드가 동일한 깊이 또는 레벨을 갖습니다.포화 이진트리는 레벨에 따라 노드의 개수가 정해져 있습니다. 루트 노드의 레벨을 0 레벨이라 했을 때 n 레벨의 노드의 개수는 2의 n승이 됩니다. 따라서 n레벨의 포화 이진 트리..
