바킹독3 [바킹독 실전 알고리즘 0x0B] 재귀 알고리즘 설명 재귀: 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘 다음과 같이 간단한 재귀 함수 코드를 생각해볼 수 있다. void func(int n){ if(n == 0) return; cout 2023. 2. 12. [바킹독 실전 알고리즘 0x0C] 백트래킹 알고리즘 설명 백트래킹: 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 백트래킹은 상당한 구현력을 필요로 하고, 실수하기도 쉽다. 따라서 많은 시간을 할애해 재귀의 개념을 익히고, 연습을 해야한다. 처음엔 어렵게 느껴지겠지만, 생각보다 응용의 폭이 넓지 않아 BFS와 비슷하게 기본적인 코드 뼈대를 익혀두면 훨씬 더 수월하게 풀이할 수 있다. 연습문제1 - N과 M BOJ 15649번) 백트래킹의 기본 코드는 대략적으로 익혀두는 것이 좋다. #include using namespace std; //전역 변수 int n, m; //입력 받는 값들 int arr[10]; //수열을 담을 배열 bool isused[10]; //특정 수가 쓰였는지를 나타내는 배열(상태를 저장하는 배열) //.. 2023. 2. 10. [바킹독 실전 알고리즘 0x09] BFS 알고리즘 소개 BFS(Breath First Search): 너비 우선 탐색 예시 1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김 2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행 3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입 4. 큐가 빌 때까지 2번을 반복 처음 방문 했을 때만 방문 표시를 남기기 때문에 모든 칸이 큐에 1번씩 들어간다. 따라서 시간복잡도는 칸이 N개일 때 O(N)이다. 같은 원리로 행이 R개, 열이 C개인 2차원 평면을 BFS 탐색하면 시간복잡도는 O(RC)가 될 것이다. 이제 BFS 구현에 필요한 pair STL에 대해 알아보고자 한다. pair를 이용하면 두 자료형을 묶어.. 2023. 2. 3. 이전 1 다음
