1장: 알고리즘이란?

1장: 알고리즘이란?

선형 탐색법: 선택지를 순서대로 조사하는 방법
이진 탐색법: 선택지를 반씩 나누어 조사하는 방법

깊이 우선 탐색: 무작정 값을 정해 풀어보고, 맞지 않으면 한 단계 돌아가서 다른 선택지를 선택하여 다시 값을 가정하는 식으로 되풀이 하는 방식
너비 우선 탐색: 해당 단계에서 가능한 모든 선택지의 값을 구하고 다음 선택지로 넘어가는 방식

연습문제
Q: 1.2 나이 맞히기 게임에서 A씨의 나이가 0세 ~ 100세 미만일 때, 예/아니오로 답 할수 있는 질문을 반복해서 나이를 맞힌다고 할 때, 확실하게 맞힐 수 있는 질문 횟수는 6? 7?

A: 이진 탐색으로 해당 문제를 접근하는 경우, N번의 질문으로 거를 수 있는 경우의 수는 2의 N승 (2N)이다. 따라서 100가지 경우의 수는 64(26) < 100 < 128(27) 이므로, 7번이라고 할 수 있다.