[cs50] 알고리즘 (PseudoCode, 선형탐색)

Lecture1

-알고리즘은 어떤 것인지 설명. 시간/공간 복잡도를 간단한 개념으로 알려줌.(전화번호부 예시) 

-입력값과 출력값이 있는데 그 사이에서 어떻게 출력할지를 정하는 것이 알고리즘.

 

Point 

Corner Case 예외 -> 일어날 수 있는 모든 가능성을 작성

branch 조건분기 -> 조건을 어떻게 줘야 효율적일까

ineffcient code -> How to improve? (예시: 방안에 있는 사람 수 세기)

 

PseudoCode

 

의사코드. 

 

<코드1> 첫페이지부터 smith가 있는지 찾는다. 없으면 그 다음페이지에서 찾는다. 찾을때까지 반복한다. (선형탐색) 

 

 

<코드2> 책의 가운데를 펼친다. 전화번호부는 이름순으로 정렬되어 있기 때문에 그 페이지에 mike smith가 없다면 앞쪽을 살펴봐야할지 뒤쪽을 살펴봐야할지 알 수 있다. 책의 절반을 버리고 나머지 절반에 똑같은 알고리즘을 수행한다. 

 

 

선형탐색

- 원하는 원소가 발견될때까지 처음부터 마지막 자료까지 차례대로 검색한다.

- 선형 탐색 알고리즘은 정확하지만 아주 효율적이지 못한 방법입니다. 리스트의 길이가 n이라고 했을 때, 최악의 경우 리스트의 모든 원소를 확인해야 하므로 n번만큼 실행됩니다. 여기서 최악의 상황은 찾고자 하는 자료가 맨 마지막에 있거나 리스트 안에 없는 경우를 말합니다. 만약 100만 개의 원소가 있는 리스트라고 가정해본다면 효율성이 매우 떨어짐을 느낄 수 있습니다. 반대로 최선의 상황은 처음 시도했을 때 찾고자 하는 값이 있는 경우입니다. 평균적으로 선형 탐색이 최악의 상황에서 종료되는 것에 가깝다고 가정할 수 있습니다. 선형 탐색은 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용합니다. 이러한 경우 무작위로 탐색하는 것보다 순서대로 탐색하는 것이 더 효율적입니다. 이제 여러분은 왜 탐색 이전에 정렬해줘야 하는지 알 수 있을 것입니다. 정렬은 시간이 오래 걸리고 공간을 더 차지합니다. 하지만 이 추가적인 과정을 진행하면 여러분이 여러 번 리스트를 검색해야 하거나 매우 큰 리스트를 검색해야 할 경우 시간을 단축할 수 있을 것입니다.

(출처: edwith)