파게로그

문제 링크: 11066번 파일 합치기 https://www.acmicpc.net/problem/11066 일단 DP문제라고 하는데 왜 DP인지부터 생각해보자. 그다지 바람직하지는 않지만, 우리가 적절한 알고리즘을 고르는 데에 사용할 수 있는 판단 근거 중 하나는 주어지는 값의 범위이다. 이 문제에서는 소설을 구성하는 장의 수 K가 500 이하로서 스위핑으로 해결되기는 힘들며, O(n^2)이라고 하기에도 약간 작은 숫자이므로 O(n^3) 정도를 생각해봐야 한다는 것을 알 수 있다. 또한 "여러 장들이 연속이 되도록 파일을 합쳐나가"라는 부분에서 인접한 파일만 합쳐야 한다는 것을 알 수 있는데, 따라서 정렬이나 투 포인터 등 처리 순서가 자유로울 때에 사용할 수 있는 기법들도 여기서는 모두 후보군에서 제외해..

문제 링크: 10775번 공항 https://www.acmicpc.net/problem/10775 먼저, i번째 비행기는 gi에 도킹해야 하는 것이 아니라, [1, gi]에 도킹해야 함에 주목해야 한다. 이는 곧, 들어오는 비행기마다 그리디하게, 가능한 한 오른쪽에 도킹시켜야 한다는 것을 의미한다. 그래야만 늦게 도착하는 비행기의 도킹 가능 범위가 먼저 도착한 비행기의 도킹 가능 범위보다 작더라도, 즉 gi+k가 gi보다 작을 때 도킹 가능한 경우가 있음에도 불구하고 도킹을 못하는 경우가 발생하지 않기 때문이다. 해결하기 어려운 문제는 여기서 발생한다. 만약에 2, 3번 게이트에 이미 비행기가 도킹되어 있다고 하고, 이 때 gi = 3인 비행기가 도착하면, 이 비행기는 1번 게이트에 도킹시켜야 한다. 그..

나에게 코딩테스트를 준비하면서 가장 어려운 부분이 어디냐고 묻는다면 나는 단언컨대 binary search와 parametric search를 말할 것 같다 말했을 것이다. 꼭 정리하겠다고 마음먹은 부분인 만큼, 간단하게나마 정리해보고자 한다(원리를 자세히 설명해준 롸와 PS에서 이용할 수 있는 팁을 준 채완이, 백발이에게 고마움을 표한다). 이 글에는 약간의 오류, 특히 용어상의 오류가 발견될 수 있다. 지속해서 수정해나가는 중이므로 참고용으로만 보면 된다. 1. binary search vs parametric search 결정 문제(decision problem, 판정 문제)는 수학적으로 계산 가능한 문제 중 결과를 YES 또는 NO의 두 가지로 답할 수 있는 문제를 의미한다. 하지만 우리가 만나는..

문제 링크: 1005번 제목 https://www.acmicpc.net/problem/1005 대표적인 위상정렬 문제로 보인다. 위상정렬에 대해서는 여기에 포스팅해두었다. 아래에서 accu는 해당 건물을 짓기 직전까지 필요한 최소 시간을 저장하고 있다. 그런데 무작정 최솟값만 갱신하면 되는 것이 아니다. 왜냐하면 '어떤 건물'을 짓기 위한 여러 선결 조건이 있을 때, 해당 조건들은 모두 만족되어야만 하기 때문에, 요구사항이 가장 거대한 건물이 완성되어야만 '어떤 건물'을 지을 수 있다. 그렇기에 최댓값을 갱신해준다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IO..

문제 링크: 2239번 스도쿠 https://www.acmicpc.net/problem/2239 empty는 채워지지 않은 칸의 인덱스들을 저장하고 있고, fill은 empty의 emptyId번째 칸을 채우는 함수이다. 즉, emptyId == empty.size()라는 조건은 empty의 모든 칸들을 다 채웠다는 것을 의미하므로, 그 때 스도쿠 퍼즐을 출력하면 된다. 51번째 라인의 존재 의의는 무엇일까? '지금의 상태'가 '불가능한 상태'인 것에는 두 가지 경우가 있다. 첫째는, candis의 크기가 0인 것이다. 둘째는, fill()내의 for문을 다 돈 경우이다. 두 번째 경우를 고려해서, 이 때에는 값을 초기화해놓고 전 상태로 돌아가야 한다. 그렇지 않으면, emptyId가 자신보다 큰 empt..

헷갈리는 용어들을 간단하게 정리하면 다음과 같다. LCS(Longest Common Substring, 최장 공통 부분문자열) ABCDE, ZBCDZE의 최장 공통 부분문자열은 BCD(연속성이 요구됨) LCS(Longest Common Subsequence, 최장 공통 부분수열) ABCDE, ZBCDZE의 최장 공통 부분수열은 BCDE(연속성이 요구되지 않음) LIS(Longest Increasing Subsequence, 최장 증가 부분수열) 5 2 4 3 7 8 1 9의 최장 증가 부분수열은 2 3 7 8 9(연속성이 요구되지 않음) 다음을 예시로 해서 Longest Common Substring, Longest Common Subsequence의 길이를 구해보자. s1 = "POCKETNIZED" ..

문제 링크: 9935번 제목 https://www.acmicpc.net/problem/9935 s = ABCABCDEDE, p = ABCDE인 경우를 생각해보자. 스택에 C, 2 B, 1 A, 0 를 push한 이후, 다시 A를 만나게 되면, 패턴과 일치하지 않는다. 다만 새로 만나게 된 문자가 A로서 패턴의 첫 번째와 일치하므로(그렇지 않다면 A -1을 넣었을 것) A, 0을 넣어준다. 이렇게 하면, E, 4가 스택에 push된다는 것은 곧 패턴과 일치하는 문자가 스택에 포함되어 있다는 것을 보장한다. 따라서 p의 길이만큼 스택을 pop한다. pop한 이후에는, pi를 스택의 top의 idx 다음 것으로 해서 패턴이 계속해서 연속되는지 확인한다. import java.io.IOException; imp..

방향이 있는 그래프(directed graph)에서 꼭짓점들이 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 대개 많이 언급되는 예시로 대학 강의에서의 선수과목 체계가 제시된다. 너무 질리니까 여기서는 게임 스킬트리의 일종이라고도 할 수 있는, 스타크래프트의 프로토스 테크트리로 대체해서 설명한다. 다음은 모든 건물들을 제시하고 있지는 않지만, 실제 선결 조건들이 제시되어 있다. 위상정렬은 위와 같이 비순환 유향 그래프(DAG, directed acyclic graph)의 건물들을 선후 관계에 따라 정렬하고자 할 때 이용되며, 그 결과는 여러가지일 수 있다. 위상정렬을 수행하기 위해서 비순환 그래프이어야 하는 이유, 즉 사이클이 존재하지 않아야 하는 이유는, 사이클이 있으면 시작점을 어느 정점으로 ..