15. 리스트(List) 4 - 다양한 리스트 알고리즘

기본적인 리스트 연산자에 대해 앞에서 배운 내용으로 코딩이 가능한가?

 

최솟값, 최댓값 알고리즘

최솟값 또는 최댓값을 찾는 알고리즘은 다음과 같다.

1. 리스트의 요소를 순서대로 하나씩 꺼낸다.

2. 첫번째 요소를 최솟값 또는 최댓값이라고 정하고 해당 값을 저장한 후, 다음 값마다 첫번째 값을 비교한다.

3. 구하는 값이 최솟값이라면, 첫번째 요소 값 보다 두번째 요소 값이 작다면, 최솟값을 두 번째 요소 값으로 바꾼다.

4. 이를 끝까지 진행한다.

 

1) 최솟값, 최댓값을 찾는 일반적인 알고리즘을 구현해라.

 

탐색(Search)

탐색(search)는 컴퓨터가 가장 많이 하는 작업 중의 하나이다. 많은 탐색 방법중 순차 탐색(sequential search)는 탐색 방법 중 간단하고 직접적인 탐색 방법이다.

 

순차 탐색(sequential search)

순차 탐색의 순서는 다음과 같다.

1. 리스트의 요소를 순서대로 하나씩 꺼낸다.

2. 꺼낼때 마다 일치하는 항목인지 비교한다.

 

2) 순차 탐색의 알고리즘을 구현해라.

 

정렬(sort)

선택 정렬의 경우 하나의 리스트를 정렬한다고 하면 두개의 리스트를 만든다. 하나는 정렬될 것이 쌓여질 리스트, 또 다른 하나는 정렬이 되지 않은 기존 리스트이다. 만약 오름차순으로 정렬한다고 하면 정렬되지 않은 리스트의 값에서 가장 작은 값을 정렬될 리스트에 값을 하나 옮긴다. 그 다음 정렬되지 않은 리스트 쪽으로 다시가서 두 번째 작은 값을 찾아 정렬될 리스트 값에 옮긴다. 이를 반복한다. 하지만 이럴 경우 메모리를 많이 차지하게 된다.

 

선택 정렬의 대안, 제자리정렬(inplace sort)

하나의 값을 변수에 담고 리스트의 루핑을 돌면서 계속 비교한다. 오름차순으로 정렬한다고 하면 나중에 작은 값이 발견될 경우 앞의 인덱스와 값을 바꿔가며 진행한다.

출처 : 인프런 강의 - 기초부터 실무까지 part2, ppt 강의 자료 참고

3. 제자리 정렬 알고리즘을 구현하라.

 

그 외 정렬 : 버블정렬, 삽입정렬, 병합정렬, 퀵정렬, 힙정렬