문제 설명 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제에서 중요한 부분들을 하이라이트로 표시해보았다. 이제 예제를 통해 문제를 좀 더 확실히 이해해보자. M=3인데 치킨집(2)의 개수가 3개이므로 폐업을 시킬 필요가 없다. (1,3) ~ (2,3) 사이 치킨 거리 = 1 (3,2) ~ (3,3) 사이 치킨 거리 = 1 (3,3) ~ (4,3) 사이 치킨 거리 = 1 (2,3) ~ (2,5) 사이 치킨 거리 = 2 이므로, 도시 전체의 치킨 거리는 5이다. 구현 아이디어 치킨집 중 ..

완전탐색이란? 완전탐색은 모든 경우의 수를 탐색하는 알고리즘이다. 무식하게 한다는 의미로 브루트포스(Brute Force) 알고리즘이라고도 부른다. 직관적이기 때문에 이해하기 쉬우며 문제의 정확한 결과를 얻어낼 수 있는 가장 확실하며 기초적인 방법이다. 모든 경우의 수를 탐색하는 것은 저번 포스트의 순열이나 조합을 사용하거나, 단순 구현을 하면 된다. 하지만 시간 초과가 날 수 있으므로, 보통은 최대 범위가 1억 미만일 때까지만 한다. 완전탐색으로 문제 푸는 방법 완전탐색을 활용할 때 가장 간단한 방법은 반복문(for, while)을 활용하는 것이다. 만약 반복문만 사용하는 것이 너무 복잡하거나 특정 행위를 반복하며 매개변수만 변경하면 될 것 같은 경우에는 재귀함수를 사용할 수 있다. ex. 조합/순열 ..

누적합이란? 요소들의 누적된 합. 어떠한 배열을 기반으로 앞에서부터 요소들의 누적된 합을 저장해 새로이 배열을 만들어 활용하는 것을 의미한다. 앞에서부터 더하는 prefix sum, 뒤에서부터 더하는 suffix sum이 있는데, 코딩테스트에는 prefix sum이 자주 나온다. 누적합을 만들 때, 0번째 index는 비워두고 1번째 index부터 사용하는 것이 편하다 인덱스 0 1 2 3 4 원소 0 1 10 11 100 누적합 0 1 11 22 122 누적합을 C++로 간단하게 구현할 수 있다. #include using namespace std; int a[100004], b, c, psum[100004], n, m; int main() { cin >> n >> m; for (int i = 1; i..

들어가며 코딩테스트에서는 문자열을 split하는 로직(특정 문자열을 기준으로 쪼개어 배열화)이 많이 사용된다. 하지만 C++ STL에서는 관련된 함수를 지원하지 않기 때문에 직접 구현해야 한다. split() 구현 // input: 쪼갤 문자열 // delimiter: 기준 문자열 vector split(string input, string delimiter) { vector ret; long long pos = 0; string token = ""; while ((pos = input.find(delimiter)) != string::npos) { token = input.substr(0, pos); ret.push_back(token); input.erase(0, pos + delimiter.leng..

순열 vs 조합 순서와 상관 있이 뽑는 경우 > 순열 순서와 상관 없이 뽑는 경우 > 조합 순서를 재배치하여 ~~~한 순서의 경우 최대값을 구하는 문제 > 순열 1, 2, 3에서 3개를 뽑을 때 순열 - {1, 2, 3} 조합 - {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1} next_permutation C++에서는 next_permutation이라는 함수를 제공하고 있다. bool next_permutation (BidirectionalIterator first, BidirectionalIterator last); next_permutation에서는 매개변수로 시작 지점과 끝 지점 iterator을 받는다. 주의 끝 지점의 iter..

문제 설명 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 예제에 하이라이트를 추가하여 좀 더 보기 쉽게 정리하면 아래와 같다. 이렇게 하여 만들 수 있는 서로 다른 여섯 자리의 개수를 구하면 된다. 어떤 알고리즘을 사용해야 할까? 정사각형 모양의 숫자판 인접한 네 방향으로 이동 한다는 점에서 그래프 탐색 알고리즘을 사용해야 한다고 생각하였다. 그리고 여섯 자리 수를 만들기 위해 깊숙이 들어가기 때문에 BFS(너비 우선 탐색)이 아닌 DFS(깊이 우선 탐색)을 사용해..