💚 6603 로또 하나의 배열을 재귀적으로 사용하는 방법이다. 문제에서는 6개를 사전순으로 출력하라고 했다. 그런데 오름차순으로 배열이 정렬되어있기 때문에 아래와 같은 방식으로 재귀적으로 탐색하면 자동으로 사전순으로 출력하게 된다. #include #include #include using namespace std; vector lotto; void solve(vector &a, int index, int cnt) { if(cnt == 6) { for(int num : lotto) { cout > a[i]; } solve(a, 0, 0); cout 0) { res.push_back(calc(a, index + 1, cur + a[index], plus - 1, minus, mul, div)); } if(..

- 다 해봐야하는 경우 - 순서만 변경 가능한 경우 💚 2529 부등호 문제 한 자리 숫자, 선택된 수는 모두 달라야 한다. -> 순서만 바꿔가면서 답을 구하면 된다. - 10개의 수 중에서 k + 1개를 고름 - (k + 1)! 순서를 만든 후 부등호 유효한지 검사 너무 많은 경우의 수가 발생하기 때문에 최적화가 필요하다. 실제로 모든 경우의 수가 필요한 것이 아니라 가장 작은 수와 가장 큰 수만 구하면 된다. algorithm 헤더에 next_permutaion, prev_permutation이라는 유용한 메소드가 존재한다. 이 메서드에 vector을 넣으면 vector의 요소의 다음 순열이 리턴된다. #include #include #include using namespace std; // 입력된 ..

https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 이해하기에는 쉽지만 막상 구현하려고 하면 잘 안 풀린다. 왜냐하면 너무 오랜만에 푸는 DFS이기도 했고, 그동안 자주 접했던 DFS 문제와 살짝 달랐기 때문이다. 이전의 DFS는 한 줄로 구성되어, 한 점을 기준으로 주변을 탐색했다면 이 문제는 한 점이 아니라 7공주 그룹 전체를 중심으로 주변을 모두 탐색해야 했기 때문이다. 이와중에 중복을 제거하려고 하니 머리가 터졌다. 즉 이렇게 되면서 요구사항이..

https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 시간복잡도는 O(N), 선형적으로 진행하기 위해서 투 포인터(Two Pointers)라는 알고리즘으로 문자열을 탐색해나간다. 해당 문자열 안의 알파벳 종류의 수를 확인할 때 매번 탐색하면 비효율적이기 때문에 별도의 변수(cnt)를 통해 기록한다. 여기서 간과하였던 점은 head와 tail을 오고갈 때, 문자열에 포함된 문자의 종류를 체크하기 위해서 set을 사용하려 했다. 그런데 현재 문자열에 포함된 문자..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 백준 초창기 문제라서 그런지 우리 학교의 요소가 등장하는 문제이다. 그저 반갑 하지만 문제는 착하진 않다. 헷갈릴 만한 요소가 많았고, 질문 게시판을 보면서 답을 찾아나갈 수 있었다. 이 문제는 위상정렬(탐색) + 다이나믹 프로그래밍(해당 건물까지 도달하기에 필요한 최소 시간을 구하기)를 결합한 문제였다. 처음에 풀 때는 선후 관계가 있다는 점에 위상 정렬이라는 점을 파악하였으나, 최소 소요..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 위상정렬(Topology Sort)는 순서(선후)가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 사용하는 알고리즘이다. 위상 정렬은 여러 개의 답이 존재할 수 있다. 또한 위상 정렬은 DAG(Directed Acyclic Graph)에만 적용이 가능하다. 사이클이 발생하는 경우에는 위상 정렬을 수행할 수 없다. 위상 정렬은 시작점이 존재해야 하는..