khanacademy의 computing 과정을 듣고 필기한 내용입니다.
알고리즘이 필요한 이유?
- 구글 행아웃이 인터넷 간에 실시간 영상을 빠르게 전송하는 방법? -> 오디오, 비디오 압축 알고리즘
- 구글 맵스가 경로를 찾는 방법? -> 경로찾기 알고리즘
- 픽사가 가상 공간에서 캐릭터 3D 모델을 조명을 반영해 색칠하는 방법? -> 렌더링 알고리즘
- 나사가 ISS의 태양광 패널을 어디로 언제 움직일지 아는 방법? -> 최적화&스케쥴 알고리즘
결국 알고리즘은 어떤 문제를 해결하기 위한 절차의 집합이다.
좋은 알고리즘은?
- 문제를 해결할 수 있는가?
- 이를 효과적(효율적)으로 하는가?
추측 게임
컴퓨터가 1에서 16까지 정수 중 무작위로 하나를 선택하고, 우리는 무작위로 하나를 선택합니다. 컴퓨터가 고른 수를 알아낼 때까지 계속 추측하고, 각 추측마다 숫자가 높은지 낮은지 알려줍니다.(up&down 게임)
1을 고르고 2, 3, 4 순서대로 고르는 방식으로 맞을 때까지 하는 방법을 선형검색(linear search) 이라고 합니다.
일단 16의 반인 8을 고르고 up & down을 알려주면 나머지는 제하는 방식이 이진탐색(binary search) 라고 합니다.
-> 이런 식으로 진행하면 무슨 수를 고르던 최대 네 번의 추측 안에 수를 맞출 수 있습니다.
-> 1에서 300까지의 수에서도 최대 아홉 번의 추측으로 가능합니다.
-> 아마도 2의 거듭제곱으로 가능한 듯 하다. 2의 9승이 512이고 2의 8승이 256이므로 300까지의 수에서는 9번으로 가능
경로 찾기
- 1693년에 윌리엄 메리 대학을 세운 윌리엄 왕 3세와 현 윌리엄 왕자의 관계는 어떻게 될까요?
- 유령이 팩맨에 가장 빨리 다다를 수 있는 경로는 무엇일까요?
- 텍사스 달라스에서 플로리다 올랜도까지 차로 가는 가장 빠른 길은 무엇일까요?
위 질문에 답하려면 정보가 있어야 합니다. 바로 가까운 곳과 연결하는 직접적 관계를 이용하여 가까운 경로를 지도(혹은 가계도 등)에서 찾는 것입니다.
미로 게임
캐릭터가 내가 클릭하는 곳(goal)까지 최단 경로로 가려면 어떻게 해야하는가?
-> 캐릭터가 가는 길에는 여러 길이 있을 수 있으므로 프로그램은 최선의 경로를 선택해야 합니다.
알고리즘을 결정하기 전 우선 이동 규칙이 만들어져야 합니다. -> 네모마다 캐릭터가 그 정점에서 목표 지점까지 이르기 위해 거쳐야하는 단계의 최소 횟수인 비용을 할당함으로써 결정할 수 있습니다.
- 목표 네모에서 시작합니다. 목표 지점에서 목표 지점까지 얼마나 걸리나요? 0 단계이므로 목표 지점에 숫자 0이라고 표시합니다.
- 미로에서 목표 지점에서 정확히 한 단계 멀리있는 모든 네모를 찾습니다. 이들을 숫자 1이라고 표시합니다. 이 미로에서 목표 지점이 출구 네모라면 정확히 한 단계 떨어진 네모는 하나밖에 없습니다.
- 이제 목표 지점에서 정확히 두 단계 떨어져 있는 모든 네모를 찾습니다. 이 네모들은 1로 표시했던 네모에서 1 떨어져 있고, 아직 표시되지 않은 네모입니다. 이 네모들을 숫자 2로 표시합니다.
- 목표 지점에서 정확히 세 단계 떨어져 있는 모든 네모를 찾습니다. 이 네모들은 2로 표시했던 네모에서 1 떨어져 있고, 아직 표시되지 않은 네모입니다. 이 네모들을 숫자 3로 표시합니다.
- 이런 식으로 목표 지점에서의 거리가 커지는 순서대로 미로 안의 네모들을 계속 표시합니다. 숫자 kkk로 네모를 표시한 후 kkk로 표시된 네모들에서 한 단계 멀리 있고 아직 표시가 되어 있지 않은 모든 네모들을 숫자 k+1k+1k, plus, 1라고 표시합니다.
#20210610
#TIL
출처 : khanacademy
https://ko.khanacademy.org/computing/computer-science/algorithms/intro-to-algorithms/a/route-finding
