poksul_log

📍백트래킹이란 ? 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 즉, 해를 찾을 때 중간에 해가 아니어서 막힐 경우, 이전 단계로 되돌아가 해를 다시 찾는 기법 📍백트래킹의 쓰임 최적화 및 조합, 결정 문제를 풀 때 쓰인다. 주로 DFS(깊이 우선 탐색)와 묶여서 잘 쓰이는데, DFS는 가능한 모든 경로를 탐색한다. 따라서, n이 큰 경우 경우의 수를 줄여야 할 필요성이 있다. → 이 때 백트래킹을 사용하여 불필요하거나 불가능한 경로를 사전에 차단하는 것을 통해 경우의 수를 줄일 수 있다. 즉, 가지치기를 할 수 있다는 것 ! ▶ DFS와 쓰일 때 흐름은 다음과 같다. DFS로 모든 경우의 수를 탐색할 때, 조건문을 걸어 불가능한 경우를 정의하고, 해당 상황일 때 탐색을 중지 이후 ..

관련 알고리즘 : 재귀, DP 문제 링크 : https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 해결 과정 문제를 보면, 어떤 아이디어를 SNS에서 퍼뜨리고자 할 때 얼리 아답터가 아닌 사람은 모든 친구가 얼리 어답터여야 아이디어를 받아들임 얼리 어답터인 사람은 친구가 얼리 어답터인지 여부에 관계없이 아이디어를 받아들임 즉, 얼리 어답터가 X인 사람 => 연결된 친구들이 모두 얼리 어답터----------- 얼리 ..

관련 알고리즘 : 재귀 문제 링크 : https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 문제 풀이 문제의 조건을 보면, 1. 한 번에 한 개의 원판만 이동 가능 2. 쌓아 놓은 원판의 크기는 항상 아래로 갈수록 커져야 함 을 만족 시켜야 한다. 위 두 조건을 만족하면서 n개의 원판을 1번에서 3번 장대로 이동시키기 위해서 그 흐름을 생각해 보았다. n번 원판은 3번 장대 위에 있어야 나머지 (n-1)개의 원판들이 순서대로 n번 원판 ..