blog

Encapsulation The core idea in object-oriented programming is to divide programs into smaller pieces and make each piece responsible for managing its own state. Different pieces of such a program interact with each other through interfaces, limited sets of functions or bindings that provide useful functionality at a more abstract level, hiding their precise implementation. Such program pieces ar..

A large program is a costly program, and not just because of the time it takes to build. Size almost always involves complexity, and complexity confuses programmers. Confused programmers, in turn, introduce mistakes (bugs) into programs. A large program then provides a lot of space for these bugs to hide, making them hard to find. console.log(sum(range(1, 10))); It is more likely to be correct b..

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..