선택은 나의 것

문제 BOJ 5582 : https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 접근 문제는 LCS와 매우 유사하다. 하지만 LCS는 부분 문자열이 연속되지 않아도 상관없었지만 이 문제는 연속된 공통 부분 문자열을 구해야 한다는 점이다. 따라서 우리는 문자열 s1, s2에서 특정 위치 p1, p2에 대해 두 경우를 마주할 수 있다. 1. s1[p1] == s2[p2] 일 경우 2. s1[p1] != s2[p2] 일 경우 같을 경우 바로 직전..

문제 BOJ 10025 : https://www.acmicpc.net/problem/10025 10025번: 게으른 백곰 첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다. www.acmicpc.net 접근 슬라이딩 윈도우(Sliding Window)를 이용하여 문제를 해결하였다. 해결 방법은 백준 2531번 : 회전 초밥 문제와 매우 유사하기 때문에 이 글을 참고하길 바란다. 코드 #include using namespace std; int n, k, ice[1000005] = {0}, a, b, counter = 0, ans = 0, chk = 0; int main() { cin >> n..

문제 BOJ 1890 : https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 접근 이 문제의 최대 경로의 수는 2^63 -1 이하인 것만 봐도 다이나믹 프로그래밍(이하 DP)을 통해 문제를 풀어야 함을 알 수 있다. DP에서 메모이제이션(memoization)을 통해 중복된 경우를 잘 제거해주지 않는다면 수많은 경우를 반복하여 방문하기 때문에 메모리 초과, 시간 초과가 날 수 있다. 이 문제를 풀면서 간과하기 쉬운 점은 도착점 뿐만 아니..

문제 BOJ 11279 : https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 접근 문제의 제목 그대로 최대 힙을 통해 문제를 풀면 된다. 나는 C++ STL인 헤더에서 제공하는 컨테이너인 우선순위 큐(Priority Queue)를 이용해 문제를 해결했다. priority_queue pq; 만약 시간 초과로 고민하고 있다면 https://algoribi.tistory.com/134 이 글의 시간 초과에 관한 부분을 읽어보길 바란..

문제 BOJ 20551 : https://www.acmicpc.net/problem/20551 20551번: Sort 마스터 배지훈의 후계자 지훈이는 Sort 마스터다. 오랫동안 Sort 마스터 자리를 지켜온 지훈이는 이제 마스터 자리를 후계자에게 물려주려고 한다. 수많은 제자들 중에 후계자를 고르기 위해서 지훈이는 제자들에게 문제 www.acmicpc.net 접근 오름차순으로 정렬된 배열 arr에서 M개의 임의의 정수들을 찾는 문제이다. arr의 최대 크기는 2×10^5이므로 이분 탐색을 통해 찾아주면 된다. 이때 주의해야 할 점은 배열 안에 중복되는 값이 존재할 수 있고, 우리는 찾아야 하는 임의의 정수 d가 가장 먼저 등장하는 위치를 찾아야 하므로 이분 탐색을 Lower bound로 구현해야 한다는..

문제 BOJ 2531 : https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 접근 슬라이딩 윈도우(Sliding Window)를 이용하여 문제를 해결하였다. 연속으로 먹을 수 있는 초밥의 개수(k)만큼 윈도우에 담아주고, 윈도우를 한 칸씩 앞으로 밀어가면서 최대의 경우가 되는지 확인해 보는 것이다. 당연히 윈도우를 앞으로 밀고 나갈 때마다 새로 들어오는 초밥은 추가해 주고, 기존에 있던 초밥 하나는 빼주면서 ..