1.1 알고리즘이란

• 문제를 푸는 방법, 정차를 의미

특징

• 어떤 특정한 문제가 있을 때 그 어떠한 경우를 생각해도 같은 방법으로 답을 도출할 수 있다.

1.2 깊이 우선 탐색과 너비 우선 탐색

1.2.1 깊이 우선 탐색

• 무수한 선택지 중에서 무작정 값을 정해 풀어 보는 행위를 반복
• 무작정 진행하는 동작을 막힐 때까지 반복하고, 막히면 한 단계 되돌아가서 다음 선택지를 시험하는 걸 반복하는 탐색 알고리즘
• 탐색 순서를 어떻게 하느냐에 따라 극적으로 성능 차이가 생긴다.

응용

• 스도쿠 퍼즐
• 컴퓨터장기 프로그램에서 게임 탁색 기반 기술을 사용
• 탐색 결과를 하나하나 메모하면서 실행하면 동적 계획법
• 순서 관계를 정리하는 기법인 위상 정렬(topology sort)을 구현
• 네트워크 흐름 알고리즘에서 서브 루틴으로 기능

1.2.2 너비 우선 탐색

• 출발점에서 가까운 곳부터 순서대로 탐색하는 탐색 알고리즘
• 출발점에서 한 번에 갈 수 있는 곳을 우선 탐색해서 더 이상 없으면 두 번에 갈 수 있는곳을 탐색하고, 다시 세 번에 갈 수 있는 곳을 탐색하며, 이 과정을 안 간 곳이 없을 때 까지 반복
• 너비 우선 탐색도 깊이 우선 탐색처럼 단순 무식한 탐색 알고리즘이지만, 목표를 달성하는 최소 절차를 알고 싶은 경우에 유용

출처 : 문제 해결력을 높이는 알고리즘과 자료구조