blog

1. 문제 https://www.acmicpc.net/problem/1208 2. Note 2.1. Subset sum problem Subset sum 문제라고 생각하여 O(nS)으로 해결하려 했습니다. 그러나 원소가 음수도 될 수 있다는 걸 간과하여 런타임 에러가 발생하였고, 이를 해결하기 위해 배열의 인덱스를 보정하여 접근하는 방식을 구현했지만 메모리 초과를 받았습니다. 2.2. 분할 정복의 아이디어 한 시간 넘게 해결하지 못하여 해법을 검색해봤는데 DP가 아닌 분할 정복으로 해결할 수 있다는 사실을 알게 되었습니다.

1. 문제 https://www.acmicpc.net/problem/1248 2. Note 2.1. 완전탐색 - 백트래킹 모든 경우의 수를 구하고 이를 문제의 조건과 비교하는 문제에 익숙해져서 그런지 이런 방식으로만 문제를 해결하려 했습니다. 당연하게도 시간초과를 받았습니다. 적절히 가지치기를 수행해서 문제의 조건에 어긋나는 경우를 사전에 제거하는 백트래킹으로 접근해야 했습니다. 2.2. 문제 접근 태도 문제를 풀 때, 먼저 제한 시간을 보고 입력을 어떤 알고리즘에 욱여넣을(?) 수 있는지 확인하곤 합니다. 시간복잡도 분석은 물론 중요합니다. 그러나 문제의 본질에 집중하지 않고 익숙해진 알고리즘 유형에 끼워맞춰서 시간 내에 풀 수 있는지 확인하는 나쁜 버릇이 들었습니다. 문제에 좀 더 집중해야 합니다. ..

1. 문제 https://www.acmicpc.net/problem/9370 2. Note 2.1. 풀이 저는 Dijkstra를 세 번 사용하여 풀었는데 Dijkstra를 두 번, 심지어는 한 번만 사용해도 풀 수 있습니다. 한 번만 푸는 풀이법은 금방 이해했는데 두 번만에 푸는 풀이는 이해하는데 조금 시간이 걸려서 메모합니다. 2.1.1. 두 번 사용하는 풀이 u->v := u에서 v까지의 최단 경로 (u,v) := u와 v를 잇는 간선 dist(u,v) := u부터 v까지의 최단 거리 length(u,v) := (u,v)의 길이 먼저 s->d가 (h,g)를 포함한다고 가정합니다. 그렇다면 dist(s,h) < dist(s,g)일 때 dist(s,d) = dist(s,h) + length(h,g) + ..

1. 문제 https://www.acmicpc.net/problem/12015 2. Note 풀 수 없어서 검색하여 풀었다. 자주 쓰인다는 알고리즘이라니 잘 알아두자. (비슷한 문제 찾아보기) 2.1. 핵심 아이디어 L[i] = 길이 i인 증가하는 부분 수열을 만들 수 있는 마지막 원소 중 가장 작은 값 (L은 1-based) https://seungkwan.tistory.com/8 2.2. vector::back() 벡터의 마지막 원소를 반환한다. 간편하게 쓸 수 있어서 좋다. 2.3. 다른 풀이 세그먼트 트리로도 풀 수 있다고 한다. 세그먼트 트리를 공부한 뒤 다시 풀어보자. 3. Reference https://seungkwan.tistory.com/8

1. 문제 https://www.acmicpc.net/problem/1300 2. Note 파라매트릭 서치 문제임을 알고 풀었는데도 어떤 수보다 작은(혹은 작거나 같은) 수의 개수를 찾아내는 함수를 떠올리지 못했다. 2.1. 이분 탐색에서 right를 k로 잡아도 충분한 이유 좀 더 고민해 보아야 할 것 같다. 잘 모르겠어어서 right 초깃값을 n*n (최악의 경우 1e10)로 잡고 풀었다. 2.2. 이분 탐색으로 구한 값이 행렬 내에 실제로 존재하는가 최솟값을 구하면 그 값은 행렬 내에 존재하는 것이 명백함 2.3. Parametric Search (1) 함수를 만들어 봅니다. (2) 이것이 항상 증가, 혹은 항상 감소하는 것인지 따져봅니다. (3) 만약 그렇다면 반씩 쪼개서 풀어봅니다. - BOJ ..

1. 문제 https://www.acmicpc.net/problem/2110 2. Note 2.1. 알고리즘 "주로, 정답을 구하기는 어려운데 정답을 검증하기 쉬운 경우에 이 알고리즘을 사용하게 됩니다." https://code.plus/course/5 이분 탐색을 이용한 전형적인 파라매트릭 서치 문제이다. 이전에 푼 , 와 유사한 문제인데도 풀 지 못했다. 이분 탐색으로 거리를 정하고 검증해 보는 방식인데, 거리 지정부터 검증까지 한 번에 하려고 시도해서 끝까지 해법을 못 찾아낸 듯 싶다. 앞으로 문제를 풀 때도 추상화 된 작은 문제로 분할하여 분석하도록 노력해야 할 것 같다. 2.2. 검증 알고리즘의 유효성 구글링해서 풀이를 살펴보니 모두 첫 번째 집을 기준으로 간격이 주어졌을 때 설치 가능한 공유기..

1. 문제 https://www.acmicpc.net/problem/10816 2. Note std::lower_bound, std::upper_bound를 사용하는 문제 2.1. lower_bound(first, last, value) value보다 크거나 같은 첫 번째 iterator 반환, 없을 시 last 반환 2.2. upper_bound(first, last, value) value보다 큰 첫 번째 iterator 반환, 없을 시 last 반환 2.3. equal_range() return std::make_pair(std::lower_bound(first, last, value), std::upper_bound(first, last, value)); NOTE: 위 세 함수는 random ac..

1. 문제 https://www.acmicpc.net/problem/2261 2. Note 반으로 나눠서(Divide) 절반 크기의 문제 두 개를 풀고 반으로 나누는 기준 선분 근처의 쌍을 살펴보면 되겠다(Conquer)는 생각이 들었지만 Conquer 단계에서 O(n^2) 아래의 방법이 떠오르지 않아서 해결하지 못했다. (참고로 이러한 분할 정복 기법은 모든 쌍을 모든 문제에서 자주 쓰인다고 한다.) 2.1. 핵심 아이디어 Conquer 단계를 O(nlogn) 이하로 만드는 핵심 아이디어는 약간의 수학(특히 기하학)적 사고가 필요했다. (https://math.stackexchange.com/questions/45776/closest-pair-of-points-algorithm) 2.2. vector:..

1. 문제 https://www.acmicpc.net/problem/11004 2. Note 알고리즘 수업에서 분할 정복을 다룰 때 배운 K-th smallest 문제와 정확히 같은 문제였다. 분할 정복 문제를 푸는 김에 복습해보려고 풀었는데 생각보다 구현에 애를 먹었다. 복습하면서 다음과 같은 주제들을 다시 살펴보았다. 2.1. 시간복잡도가 O(n)임을 증명하기 위해 수학적 귀납법(Mathmetical Induction) 정수론의 Well-Ordering Property 귀류법 2.2. 컨테이너의 일부만 정렬하는 함수 (std::sort와 다름에 주의) std::partial_sort 2.3. 피봇보다 작은, 같은, 큰 컨테이너로 나누는 기법 3-way partition 3. Reference Wiki..

1. 문제 https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 2. Note 풀이를 안 보고 풀긴 했지만 "단계별로 풀어보기"에서 행렬 곱셈을 사용하라는 힌트를 보지 못했으면 못 풀었을 것 같다. 피보나치 수열의 점화식은 선형성을 갖기 때문에 행렬의 곱으로 나타낼 수 있다. +) 행렬 곱셈처럼 여러 인덱스 여러개 사용한다면 늘 인덱싱에 주의하자. 실수 때문에 로직이 맞는데도 시간을 잡아먹는 경우가 잦다. 3. Reference https://medium.com/@andrew.chamberlain/the-linear-algebra..