Algorithm

백트래킹(Backtracking)이란?

백트래킹이란? 1. 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하다가, 가능성이 없다고 판단되면, 되돌아가서 다시 해를 찾아가는 기법 2. 조합, 순열, 부분집합도 가지치기가 없는 백트래킹이라고 할 수 있습니다. 3. 백트래킹을 이용하여, 완전탐색을 수행할 수 있고, 가지치기를 통해 최적화가 가능합니다. 백트래킹은 크게 두 부분으로 구분할 수 있습니다. void back(int depth, int m){ if(depth == m){ // 1. 선택한 원소로 기반으로 결과를 계산하는 부분 }else{ // 2. 원소를 선택하는 부분 } } 꿀팁 재귀 함수는 함수를 명확히 정의하는 것이 좋습니다. 함수를 명확하게 정의하면, 나를 이용하여 나를 정의하는 것이 명확해집니다. 예를 들어 아래와 같은 함..

[백준 1194번] 달이 차오른다, 가자. (C++)

https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 달이 차오른다, 가자 문제는 벽 부수고 이동하기, 말이 되고픈 원숭이와 유사하며, BFS와 백트래킹을 이용하여 해결할 수 있습니다. 문제에서 열쇠는 'a', 'b', 'c', 'd', 'e', 'f만 등장합니다. 따라서 비트마스킹을 사용한다면, 현재 갖고 있는 열쇠의 현황을 6비트로 표현할 수 있습니다. BitMasking 예를 들어 111111은 6개의 키를 모두 ..

[백준 9328번] 열쇠 (C++)

https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 열쇠 문제는 BFS로 해결할 수 있습니다. 상근이는 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있습니다. 따라서, 평면도의 크기를 h + 1, w + 1로 선언하고, 가장자리를 '.'로 채워놓는다면, 상근이는 어느 위치에서 시작하던 상관 없습니다. 알고리즘의 기본 틀은 아래와 같습니다. 평면도를 순회하면서, 현재 가지고 있는 열쇠로 열 수 있는 문을 모두 개방한다. 평면도를 순회한다. 문이나..

[백준 16920번] 확장 게임 (C++)

https://www.acmicpc.net/problem/16920 16920번: 확장 게임 구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위 www.acmicpc.net 확장 게임 문제는 BFS를 이용하여 해결할 수 있습니다. 현재 순서인 플레이어의 성을 한 칸씩 이동시키는 작업을 Si번씩 반복하면 됩니다. ⚠️ 단, Si가 최대 109이므로 Si을 반복하며 성을 한 칸씩 이동시키는 과정에서 시간 초과가 발생할 수 있습니다. 따라서, Sn-1번째 성을 옮길 때, 옮겨진 성이 없다면, Sn번째부터는 성을 이동시키지 않는 방법으로 시간 초과를 방지할 수 있습니다. ..

[SW Expert Academy 1248번] 공통 조상

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15PTkqAPYCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 공통 조상 문제는 크기 두 개의 과정이 필요합니다. 공통 조상 찾기 서브 트리 크기 계산 공통 조상 찾기는 아래의 과정으로 구할 수 있습니다. a 정점의 모든 부모 노드를 구한다. b 정점의 모든 부모 노드를 구한다. 이분 탐색을 위해 b 정점의 모든 노드를 정렬한다. a에 가까운 조상부터 b 정점의 조상 노드에 포함되어 있는지 확인한다. 서브 트리 크기 구하기는 아래의 과정으로 구할 수 있습니다..

[SW Expert Academy 1247번] 최적 경로

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 최적 경로 문제는 다이나믹 프로그래밍과 비트 미스킹으로 해결할 수 있습니다. N이 최대 10이기 때문에, 경로의 모든 경우의 수를 계산하여 해결할 수도 있지만, 다이나믹 프로그래밍을 이용하면 시간을 단축시킬 수 있습니다. TSP(Traveling Salesman Problem) 아래는 TSP 함수로, 현재 위치가 cur이고, 방문 상태가 visited일 때, 고객들을 모두 방문하고, 집으로 돌아가는..

[SW Expert Academy 1249번] 보급로 (C++)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 보급로 문제는 다익스트라를 이용하여 해결할 수 있습니다. 다익스트라는 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘입니다. board[x][y]의 값이 c이면, board[x][y]로 이동하는 비용은 c입니다. 따라서 이 값을, 간선의 비용으로 두고 다익스트라를 이용하여 시작점에서 도착점까지의 최단 거리를 계산하면 됩니다. 아래는 우선순위 큐를 이용한 다익스트라 코드입니다...

[백준 11562번] 백양로 브레이크 (C++)

https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 백양로 브레이크 문제는 플로이드 알고리즘을 이용하여 해결할 수 있습니다. 최소 몇 개의 일방통행인 길을 양방향 통행으로 바꿔야 출발지에서 도착지로 갈 수 있는지를 출력해야합니다. 모든 길을 양방향으로 바꾸더라도 서로 도달 불가능한 건물이 없는 입력만 주어지므로, 아래와 같은 알고리즘을 생각해볼 수 있습니다. 입력 받은 각 길이 일방통행인지, 양방향인지 기록해둔다. 모든 길을 길이가 1인 양방향 ..