파게로그

문제 링크: 2629번 양팔저울 https://www.acmicpc.net/problem/2629 분류를 보면 꽤나 풀만한 문제이겠지만 시험 중에 만난다면 당황할 법하다. DP, 특히 배낭류 문제는 정말로 잘 보이지 않는다. 처음에는 집합을 쓸까 생각을 했다. 사실 가능한 무게를 담고있는 집합을 선언하고, 추를 하나씩 추가해나가면서 가능한 무게들을 집합에 추가해나가는 것이다. 그 구현체로 HashSet을 이용하면 특정 무게가 만들 수 있는 무게인지 확인하는 과정이 O(1)에 가능하기 때문에 가능한 풀이이며 근본적으로 냅색 알고리즘과 유사한 풀이로 보인다. 다만 문제를 풀 당시에는 집합을 새로 만들 생각을 하지 못하고 기존의 집합에 새로운 원소를 추가하려다보니 구현이 꼬여서 포기했다. 기본적인 아이디어는 ..

문제 링크: 1912번 연속합, 1749번 점수따먹기 https://www.acmicpc.net/problem/1912 https://www.acmicpc.net/problem/1749 1912번과 1749번을 풀기 위해서는 두 가지 개념을 동시에 사용해야 한다. 두 개념 모두 memoization의 기법이지만 이 문제들에서는 서로 다른 용도로 이용된다. 첫째는 누적 합이고, 둘째는 이전의 값들을 포함시킬지 말지 고려하여 최댓값을 갱신해나가는 것이다. 1. 누적 합을 통해 O(N3)을 O(N2)으로 줄이기 1912번을 나이브하게 푼다고 하면, 연속된 수 몇 개를 선택한 수열의 시작 인덱스 s와 끝 인덱스 e를 O(N2)으로 잡은 후, 해당 경우마다 [s, e] 구간의 모든 원소의 합을 구해주면 된다. 하..

문제 링크: 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의 두 가지로 답할 수 있는 문제를 의미한다. 하지만 우리가 만나는..

URL이란, "네트워크 상에서 자원이 어디 있는지를 알려주기 위한 규약" 또는 "컴퓨터 네트워크와 검색 메커니즘에서의 위치를 지정하는, 리소스에 대한 참조"이다(위키백과). 다만 URL(Uniform Resource Locator)은 URI(Uniform Resource Identifier)의 부분집합으로서, 다음과 같은 차이를 지닌다. URI URL https://www.ddoongi.com/index.html O O https://www.ddoongi.com/index O X 위를 A, 아래를 B라 하자. B의 경우라도 파일명이 index라면 URL일 수 있으나, 이 경우는 제외한다. 리소스를 식별하는 기능을 갖추기만 하면 URI라고 할 수 있기에, A뿐만 아니라 B도 URI가 될 수 있다. 그러나 ..

문제 링크: 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..