1. 알고리즘이란?

1.1 알고리즘이란 무엇인가.

알고리즘이란 특정한 문제를 푸는 방법과 절차를 말한다.

누군가의 나이가 20 <= x <= 35 라는 것을 알고 있다.
답을 찾기 위한 질문은 4번 할 수 있다.

• 20살인가요? 21살인가요? 22살....

이런 식으로 쭉 질문하는 것은 좋은 방법, 좋은 알고리즘이 아니다.
심심할 때 하는 업다운 게임 처럼 질문의 범위를 절반씩 쪼갠다면 어떨까?

• 28살 미만인가요? 32살 미만인가요? 34살 미만인가요? ...

결국 주어진 기회 안에서 정답을 맞출 수 있다.

전자는 선형 탐색법 후자는 이진 탐색법이다.

알고리즘의 특징은 어떠한 문제에 대해서 어떠한 경우에도 '같은 방법'으로 정답을 도출할 수 있다는 것이다. 20살이거나, 30살이거나 몇 살이라도 이진 탐색법으로 정답을 찾을 수 있다.

1.2 알고리즘 예 : 깊이/너비 우선 탐색

탐색 알고리즘 두 가지에 대해 살짝 엿보기

깊이 우선 탐색

• 깊이 우선 탐색은 무작정 값을 넣어보며 문제를 풀어보는 방식이다.

탐색의 순서는 좀 다르지만 학창시절 친구의 자물쇠를 풀듯이 말이다.
0000..0001...0002..

값을 넣어보고 맞지 않으면 다시 한 단계 돌아가서 값을 바꿔보고 다른 숫자들을 시험해보길 반복하며 정답을 탐색한다.

• 장점이 없어보이지만 탐색의 순서에 따라서 성능의 차이가 나는 탐색 알고리즘이다.
• 스도쿠, 장기(게임) 프로그램, 동적 계획법, 위상 정렬 등이 있다.

---

너비 우선 탐색

• 너비 우선 탐색은 가까운 곳부터 탐색하는 탐색 방법이다.
• 너비 우선 탐색도 모든 곳을 다 돌아보는 방법이지만 정답을 찾는 최소한의 탐색 루트를 찾을 때 유용하다.

간단하게 말하기 애매한 탐색법이라 나중에 자세한 내용을 담을 예정.