STL2 [바킹독 실전 알고리즘 0x0C] 백트래킹 알고리즘 설명 백트래킹: 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 백트래킹은 상당한 구현력을 필요로 하고, 실수하기도 쉽다. 따라서 많은 시간을 할애해 재귀의 개념을 익히고, 연습을 해야한다. 처음엔 어렵게 느껴지겠지만, 생각보다 응용의 폭이 넓지 않아 BFS와 비슷하게 기본적인 코드 뼈대를 익혀두면 훨씬 더 수월하게 풀이할 수 있다. 연습문제1 - N과 M BOJ 15649번) 백트래킹의 기본 코드는 대략적으로 익혀두는 것이 좋다. #include using namespace std; //전역 변수 int n, m; //입력 받는 값들 int arr[10]; //수열을 담을 배열 bool isused[10]; //특정 수가 쓰였는지를 나타내는 배열(상태를 저장하는 배열) //.. 2023. 2. 10. [바킹독 실전 알고리즘 0x05] 스택 정의와 성질 LIFO(선입선출) 구조이다. 특정 위치에서만 원소의 추가나 제거가 이루어진다. 이 성질 덕분에 원소의 추가나 제거는 O(1)이다. 제일 상단의 원소를 확인하는 시간복잡도는 O(1)이다. 제일 상단이 아닌 나머지 원소들의 확인이나 변경은 원칙적으로 불가능하다. 원칙적으로 불가능해서 배열의 성질을 사용해 나머지 원소들의 확인이 가능하도록 구현할 수는 있지만, 스택의 응용 사례에는 제일 상단의 원소만을 다룬다. 기능과 구현 스택은 배열 혹은 연결 리스트를 사용해 구현할 수 있다. 그리고 둘 중 배열을 이용하는 구현 방법이 더 쉽다. 배열을 사용해 스택을 구현하는 방법은 생각보다 간단한데, 원소들을 모두 담을 큰 배열 하나와 인덱스를 저장할 변수 하나만을 필요로 한다. const int MAX =.. 2023. 1. 31. 이전 1 다음
