개요이전 게시글에서 백트래킹 기법을 사용해 배열을 통해 순열과 조합을 구현했다. 다만, 백트래킹을 사용한 순열과 조합의 구현은 복잡하기 때문에 실수할 여지가 있다. 이번 게시글에서는 algorithm 헤더파일의 next_permutation과 prev_permutation을 통해 순열과 조합을 쉽게 구현하는 방법을 알아보자.next_permutation로 순열 구하기next_permutationbool std::next_permutation(BidirIt first, BidirIt last) // STL 컨테이너 사용 가능bool std::next_permutation(T *first, T *last) // 배열 사용 가능[first, last) 범위에서 다음 수열 결과를 인수로 전달된 컨테이너 or 배..

백트래킹이란?백트래킹은 가능한 모든 경우의 수를 따라 들어가면서 탐색하는 알고리즘이다.답이 될 수 없는 경우 더 이상 탐색하지 않고 뒤로 돌아간다.주로 재귀 함수를 사용해 구현한다.시간 복잡도는 O(N!)으로 매우 큰 편이다. 그렇기 때문에 백트래킹 관련 문제에서는 N이 작게 주어진다. 백트래킹 구현에서 가장 중요한 점은 방문 상태 변화 & 상태 원상 복구 두 가지다. 로직을 작성할 때 항상 염두에 두자.백트래킹과 순열, 조합순열과 조합을 구할 때, 가능한 모든 경우의 수에 대해 검사하기 때문에 백트래킹을 사용할 수 있다.아래에서 설명하는 순열과 조합은 오름차순으로 정렬된 집합을 기준으로 한다. 아래 코드에서 공통적으로 나오는 변수들은 다음을 나타낸다.isUsed[i]: i번째 수가 사용되었는 지 여부를..

문제https://www.acmicpc.net/problem/9663 해당 문제에 대한 풀이는 다음 블로그 글을 참고함https://blog.encrypted.gg/945 [실전 알고리즘] 0x0C강 - 백트래킹이번에는 백트래킹을 배워보도록 하겠습니다. 백트래킹도 재귀와 더불어 많은 사람들이 고통을 호소하는 알고리즘 중 하나이지만 의외로 그 재귀적인 구조에 매료되어서 참재미를 알아버리는blog.encrypted.gg 백트래킹과 브루트 포스를 이용하는 문제다.코드// 위아래, 대각선에 대해 isUsed 배열 3개를 사용// isUsed_vertical: 같은 열에 퀸이 있는지 여부// isUsed_leftDown_rightUp: 왼쪽 아래-오른쪽 위 대각선 상에 퀸이 있는지 여부// isUsed_leftU..

문제https://www.acmicpc.net/problem/1697코드// 첫 번째 풀이// for + switch문 사용#include using namespace std;int N, K;queue q;int line[100001]; // 이동 거리를 저장할 배열void LineBFS() { while (!q.empty()) { auto x = q.front(); q.pop(); // X-1, X+1, 2*X 모두 범위, 이미 방문한 곳인지, K와 같은 지 확인 for (int i = 0; i = 100001) break; // 범위 벗어나면 if (line[x - 1] != -1) break; // 이미 방문했으면 line[x - 1] = line[x] + 1; q.pus..

문제https://www.acmicpc.net/problem/1012코드#include using namespace std;int matrix[50][50];int T, M, N, K, X, Y;int cnt = 0;queue> q;int dy[4] = { -1, 1, 0, 0 };int dx[4] = { 0, 0, -1, 1 };void BFS() { while (!q.empty()) { pair front = q.front(); q.pop(); for (int i = 0; i = M || newY = N) continue; if (matrix[newY][newX] != 1) continue; matrix[newY][newX] = 0; // 방문 처리 q.push(make_pair(new..

커플링 현상커플링 현상은 여러 클래스들이 코드 상에서 복잡하게 연결되어 있는 것을 말한다. 커플링 현상이 심해질 수록 유지보수가 어려운 코드가 된다.델리게이트델리게이트(delegate)의 사전적 의미는 '대표자', '대리자' 라는 뜻이다. 델리게이트는 일종의 메서드 리스트라고 생각하면 이해하기 쉽다.(메서드 리스트라는 용어는 단순히 이해를 쉽게 하는 것을 돕기 위해 사용한 비유적 표현이다. 공식 문서에서는 메서드 참조, 메서드 포인터로 설명하는 경우가 많다.) 델리게이트 객체에는 추가된 메서드들의 포인터(참조)가 저장되고, 이를 통해 추가된 메서드들을 코드 상에서 커플링 현상을 줄이면서 여러 기능들을 실행할 수 있다. 여기에서 중요한 점은 델리게이트 자체는 자신의 델리게이트 객체에 어떤 메서드가 추가되었..

https://blog.encrypted.gg/942 [실전 알고리즘] 0x0A강 - DFS드디어 01 02 03 이렇게 숫자를 넘어서 0A강에 도달했습니다. 아직 완결까지는 한참 남았지만 아무튼 힘을 내서 계속 잘 해봅시다. 아, 참고로 저번 단원보다는 내용이 많지 않아서 편한 마음으로blog.encrypted.gg대부분의 내용을 위의 게시물을 참고해 작성한 글이다.DFS의 기본 개념이전 게시물에서 BFS에 대해 알고 있다는 것을 전제로 설명한다. DFS를 사용하면 다차원 배열에서 각 칸을 깊이를 우선으로 방문할 수 있다. 그리고 DFS는 재귀로도 자주 사용되는데, 여기에서는 스택을 사용한 DFS만 설명하겠다. DFS에는 스택이 사용된다. BFS와 유일하게 다른 점은 큐 대신 스택이 사용된다는 것 밖에..

https://blog.encrypted.gg/941 [실전 알고리즘] 0x09강 - BFS안녕하세요 여러분, 드디어 올 것이 왔습니다. 마음의 준비를 단단히 하셔야 합니다.. 드디어 실전 알고리즘 강의에서 첫 번째 고비에 도달했는데 이 강의와 함께 이번 고비를 잘 헤쳐나가면 좋blog.encrypted.gg대부분의 내용을 위의 게시물을 참고해 작성한 글이다.BFS의 기본 개념BFS를 사용하면 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문할 수 있다. BFS는 원래 그래프에서 모든 노드를 방문할 때 사용하는 것이 맞지만... 그냥 다차원 배열에서도 사용할 수 있다고 생각하자. (다차원 배열에서의 탐색이 필요한 문제는 전부 BFS로 푼다고 생각해도 된다. DFS는 그래프나 트리에서 자주 사용됨)..