알고리즘 개요

알고리즘이란?

- 문제를 해결하기 위한 단계적인 절차

- 알고리즘은 요리 레시피와 유사

- 효율적인 알고리즘 고안이 중요

* 시간 복잡도(주로 고려)

* 공간 복잡도(Memory)

 

최대 숫자 찾기

 

- 순차 탐색

- Brute-Force Search Algorithm

: 가능한 모든 경우의 수를 탐색하여 문제의 해를 찾는 알고리즘 방식 -> 시간 오래 걸리지만 확실한 방법

 

임의의 숫자 찾기

 

1. 정렬되지 않은 배열 대상

- 순차 탐색

: 앞에서부터 하나씩 85와 같은지 확인 -> 8번의 비교를 통해 해결 가능

만약 45를 찾는다면 1번의 비교 연산으로 해결 가능

 

=> 찾는 숫자에 따라 복불복

 

2. 정렬되어 있다면(선가공)

 

- 이진 탐색(Binary Search)

: 일단 중간값 말한 뒤 범위를 반씩 줄여나감

 

45 -> 75 -> 85

 

- 보간 탐색

: 위치 예상(찾고자 하는 숫자(85)와 제일 큰 숫자(90) 간 관계 사용)

 

 

동전 거스름돈(그리디 알고리즘)

 

물건을 사고 거스름돈을 동전으로 받아야 한다면 동전의 개수를 최소화하는 것이 좋다.

Q) 거스름돈=730원이라면

1. 가장 큰 액면의 동전 선택

730원을 넘지 않는 동전을 먼저 선택 -> 남은 230원을 넘지 않는 동전 선택 -> ..

2. "Greedy Algorithm": 주어진 순간에서 최선의 선택을 하는 알고리즘

 

한붓그리기(Euler Trail)

 

종이에서 연필을 떼지 않고 그리는 한붓그리기 문제

- 어느 한 점에서 출발하여 모든 간선을 한 번만 지나서 출발점으로 돌아오는 문제

(나갔다가 돌아오려면 짝수 개의 선과 연결돼있어야 함)

- 그리는 동안 연필이 종이에서 떨어지면 안 됨

- 점은 중복 가능

sol)

1. 현재 점으로 돌아오는 사이클이 있으면 진행

- 6,9번 가능: 7로 다시 돌아올 수 있음

- 10번 불가능: 7로 다시 돌아올 수 없음

 

2. 아직 방문하지 않은, 인접한 점이 하나밖에 없으면 사이클 체크 없이 인접한 점으로 진행

 

미로 찾기

 

(sol1) 지나갔던 곳 표시

 

(sol2) 오른손 법칙

-> 오른손으로 벽을 짚고 계속 가다 보면 미로 탈출

 

가짜 동전 찾기

 

Q) 양팔 저울을 최소 횟수로 사용하면서 가짜 동전을 찾아내기

- 아주 많은 동전 속에 1개의 가짜 동전이 있다.

- 가짜 동전은 눈으로 식별할 수 없다.

- 가짜 동전의 무게는 정상적인 동전보다 약간 가볍다.

 

(sol1)

동전 1개를 저울 한 쪽에 올리고 나머지 동전을 하나씩 다른 쪽에 올려서 비교

연산 횟수: 최소 1회 ~ 최대 (n-1)회

ex. 8개의 동전이 있을 때 -> 최소 1회 ~ 최대 7회

ex. 1024개의 동전이 있을 때 -> 최소 1회 ~ 최대 1023회

 

(sol2)

동전을 2개씩 짝을 지어 n/2쌍을 각각 저울에 달아서 가짜 동전 찾기

연산 횟수: 최소 1회~최대 (n/2)회

ex. 8개의 동전이 있을 때 -> 최소 1회 ~ 최대 4회

ex. 1024개의 동전이 있을 때 -> 최소 1회 ~ 최대 512회

 

 

(sol3)

- 동전 더미를 반으로 나누어 저울 양편에 놓아보자.

- 가벼운 쪽의 더미를 다시 반으로 나누어 저울 양편에 놓아보자.

- 2개가 남았을 때 가짜 동전을 찾게 된다.

연산 횟수: log_2(n)회

ex. 8개의 동전이 있을 때 -> 무조건 3회

ex. 1024개의 동전이 있을 때 -> 10회

 

독이 든 술단지(이진수 사용)

 

(조건 1) 독이 든 술단지를 반드시 일주일 만에 찾아내라

(조건 2) 단, 술을 맛보는 신하의 수를 가능한 한 줄여야 한다.

=> 입력의 크기가 아주 작을 때에 문제의 답을 찾아볼 것

 

1. 술단지가 2개일 때

=> 한 명의 신하가 1개의 술단지의 술을 맛본다.

 

 

2. 술단지가 4개일 때

 

Q) 세 사람이 각각 한 개씩 맛본다면?

3명이 희생 ㅜㅜ

 

Q) 두 사람으로 줄일 수는 없을까?

남은 둘 중 어느 것인지 모름

 

두 개씩 마시면 둘 중 어느 것인지 모름

 

<알고리즘>

각 단지에 2진수를 0부터 부여

첫 비트=1 -> 신하 1이 맛봄

둘째 비트=1 -> 신하 2가 맛봄

...

k번째 비트=1 -> 신하 k가 맛봄