Coding Test

들어가며 코딩테스트에서는 문자열을 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(깊이 우선 탐색)을 사용해..