형식을 맞추는 목적 오늘 구현한 기능이 다음 버전에서 바뀔 확률은 아주 높다. 하지만 구현한 코드의 가독성은 앞으로 바뀔 코드의 품질에 지대한 영향을 미친다. 적절한 행 길이를 유지하라 신문 기사처럼 작성하라 이름은 간단하면서도 설명이 가능하게 짓는다. 소스 파일 첫 부분은 고차원 개념과 알고리즘을 설명한다. 아래로 내려갈수...

문제 링크 원래 특정 문제에 대한 포스팅은 지양하는 편이지만, 이 문제는 나를 너무 고생시킨 기념으로 포스팅한다. 주아이디어 기본적인 아이디어는 “매개 변수 탐색”이다. 주어진 C번 만큼만 끊어서, 특정 숫자((min+max)/2)만 하품하는 경우를 만들 수 있는지 확인하면 된다. 아마 대부분 이 아이디어까지는 금방 도달했으리라 생각한다. 사실...

Chapter 03 - 함수 작게 만들어라 함수를 만드는 첫째 규칙은 ‘작게’이다. if 문/else 문/while 문 등에 들어가는 블록은 한 줄이어야 한다. 아마 대게 그 한줄은 함수 호출일 것이다. 그러면 바깥을 감싸는 함수(enclosing function)가 작아질 뿐 아니라, 블록 안에서 호출하는 함...

의도를 분명히 밝혀라 변수, 함수, 클래스는 존재 이유, 수행 기능, 사용 방법을 주석 없이 이름만으로도 파악할 수 있어야 한다. 예시1: int d는 아무 의미도 드러나지 않는다. 주석없이, 측정하려는 값과 단위를 표현하는 이름이 필요하다. // Bad int d; // 경과 시간(단위: 날짜) // Good int elapsedT...

2-SAT(satisfiability) 문제는 n개의 bool 변수로 이루어진 2-CNF 식이 true가 되게 하는 경우가 있는지, 있다면 각 변수에는 어떤 값이 들어가야 하는지 정하는 문제이다. 이 문제에서 2-SAT이 무엇인지 잘 설명해주고 있다. 참고로 3-SAT(또는 SAT)는 NP-complete 문제이다.(Cook-Levin theorem)...

개요 구간 합(range sum)은 부분 합(partial sum)을 이용하여 아주 빠르게 계산할 수 있다. 부분 합: psum[pos] = arr[0] + arr[1] + … + arr[pos] [left, right]의 구간 합: psum[right] - psum[left-1] 펜윅 트리(Fenwick Tree) 또는 이진 인덱스 트...

개요 모스 알고리즘은 업데이트가 없는 구간 쿼리들을 빠르게 처리하는 알고리즘이다. 이때 쿼리는 구간의 합, 최댓값, 최솟값 등이 될 수 있다. 기본 아이디어는 아주 간단하다. ‘앞선 쿼리로 인해 계산된 값을 최대한 활용하자‘이다. 특히 쿼리의 순서를 자유롭게 바꿀 수 있는 환경(즉, 조회만 하는 경우)에는 앞선 쿼리에서 많은 정보를 다시 이용할 수 ...

백준 13977을 해결하기 위해서는 3가지 테크닉을 알아야한다. 분할정복을 이용한 거듭제곱 모듈러 연산 특징(for 이항계수 모듈러 연산을 위한 역원) 페르마의 소정리(for 이항계수 모듈러 연산) 거듭제곱 1. 일반적인 거듭제곱 : $O(n)$ 일반적인 거듭제곱의 코드는 다음과 같다. // 재귀함수를 이용한 거듭제곱 int pow(i...

개요 네트워크 플로우 알고리즘(Network Flow Algorithm)은 그래프 이론에서 사용되며, 여러 목적에 맞게 사용될 수 있다. 그 중 이번 포스팅에서 알아볼 것은 최대 유량(maximum flow)을 찾는 알고리즘이다. 이때 유량(flow)은 한 노드에서 다른 노드로의 데이터 전송량을 의미한다. 예를 들어, 기름을 전송하는 파이프(pipe...

N명의 사람이 M개의 일을 처리해야 한다. 각 사람은 최대 1개의 일만 할 수 있고, 각 일(job)도 최대 1명만 담당할 수 있다. 최대한 많은 일을 처리하려면 어떻게 해야 할까? 이때 사용하는 알고리즘이 이분 매칭이다. 이분 그래프(Bipartitle Graph) 이분 그래프란 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 ...