배열과 연결된 리스트의 장단점

2장에서는 주된 설명은 배열과 연결된 리스트에 대한 비교 설명이 있었다.

배열은 검색이 빠른 반면 삽입이 느리다는 것

연결된 리스트의 경우 삽입이 빠르지만 검색부분에선 배열보다 느리다는 장단점이 있다.

선택정렬 (Selection Sort)

2번째 알고리즘 문제이다.

만약 주어진 배열이 있으면 그 배열을 정렬하고자 할 때 선택정렬을 사용할 수 있다.

기본 흐름은 다음과 같다. (순차적 정렬시)

1. 배열에 가장 작은 값 검색
2. 가장 작은 값 위치 값 획득
3. 그 위치 값을 배열에서 제거 하고 새로운 배열에 하나씩 추가함
4. 그렇게 해서 최종 새로운 배열로 결과값을 보여줌

Python3 으로 구현시 다음과 같다.

def findSmallest(arr):
    smallest = arr[0]
    smallest_index = 0
    for i in range(1, len(arr)):
        print(">> {0},{1},{2}".format(smallest, smallest_index, arr[i]))
        if arr[i] < smallest:            
            smallest = arr[i]
            smallest_index = i
    return smallest_index


def selectionSort(arr):
    newArr = []
    for i in range(len(arr)):
        print("arr => ", arr)
        smallest = findSmallest(arr)
        print("smallest => ", smallest)
        newArr.append(arr.pop(smallest)) # pop은 꺼낸 후 제거된다. 
    return newArr

print(selectionSort([5, 3, 6, 2, 10]))

2를 arr 에서 pop (2를 꺼내는 동시에 제거) 하고 다시 위의 반복문을 돌린다.

위 결과값 출력은 다음과 같다.

arr =>  [5, 3, 6, 2, 10]
>> 5,0,3
>> 3,1,6
>> 3,1,2
>> 2,3,10
smallest =>  3
arr =>  [5, 3, 6, 10]
>> 5,0,3
>> 3,1,6
>> 3,1,10
smallest =>  1
arr =>  [5, 6, 10]
>> 5,0,6
>> 5,0,10
smallest =>  0
arr =>  [6, 10]
>> 6,0,10
smallest =>  0
arr =>  [10]
smallest =>  0


[2, 3, 5, 6, 10] <== 최종 정렬된 값

다트 버전의 경우는 온라인 다트 편집기 에서 테스팅 가능하다.

void main() {
  print("result => ${selectionSort([5, 3, 6, 2, 10])}");
}

List<int> selectionSort(List<int> arr) {
  var newArr = [];
  var length = arr.length;
  for(var i = 0; i < length; i++) {    
      var smallestIndex = findSmallestIndex(arr);    
    newArr.add(arr[smallestIndex]);
    arr.removeAt(smallestIndex);
  }
  return newArr;
}

int findSmallestIndex(List<int> arr) {
  int smallest = arr[0];
  int smallestIdx = 0;

  var newArr = arr.sublist(1,arr.length);

  newArr.forEach((item) {    
    if(item < smallest) {
      smallest = item;
      smallestIdx = arr.indexOf(item);      
    }
  });  
  return smallestIdx;
}

................
result => [2, 3, 5, 6, 10]

빅오 표기법으로는 O(n^2) 이라고 한다.

이진탐색 (Binary Search)

시나리오

1~1000개 숫자 의 배열에서 특정 숫자만 뽑아내고 싶을 경우 어떻게 해야 될까?

1. 리스트로 한개씩 넣어서 검색해서 운좋으면 빠른 시간안에 검색이 될 수 있으나 최악의 경우 1000번의 수행을 해야 한다.
2. 이진탐색 알고리즘을 통해서 전체의 반을 검색하고 다시 반을 검색하는 방법을 사용할 수 있다.

예를 들어 100의 중간 50부터 시작되는 함수로 시작된다

4번만에 답을 찾은 경우이다. 그럼 log2 16 = 4 이라고 표시한다.

즉 로그는 거듭제곱의 반대말이다.

지수표현이 잘 안됨..

• 10^2^ = 100 -> log10100 = 2
• 10^3 = 100 -> log101000 = 3
• 2^3 = 8 -> log28 = 3 (결과값을 앞으로 보내면 된다.)
• 2^4 = 16 -> log216 = 4
• 2^5 = 32 -> log232 = 5

위의 경우에는 정렬된 배열에 한해 해당되는 내용이었다. 하지만 실무에서는 보통 정렬이 안되어있는 경우가 많은 편이다.

그럼 어떻게 구현이 될까? 파이썬으로 시작해보자.

우선 먼저 배열 전체 길이를 설정하자.

low = 0
high = len(list) - 1

그리고 가운데를 딱 나누어서 원소를 확인해보자.

mid = (low + high) / 2 //반으로 나눈값 설정
guess = list(mid) //리스트의 반이 무엇인지 예측

추측한 값이 너무 작으면 low 값을 다음과 같이 변경 처리

if guess < item:
  low = mid + 1

또 큰 경우 high 값을 설정

if guess > item
  hight = mid -1

표로 정리해보면 다음과 같다.

def binary_search(list, item):
    cnt = 0
    low = 0
    high = len(list) - 1
    print("찾는 문자 : ", item)

    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        print("번호:",cnt, " low:", low, " high:", high, " mid:", mid, " guess:", guess )
        if guess == item:
            print("in ", guess, "==", item, " return ", mid)
            return mid
        if guess > item: #item보다 guess 가 큰경ㅇ 
            print("in ", guess, ">", item, " 작다")
            high = mid - 1
        else:
            print("in ", guess, "<", item, " 크다")
            low = mid + 1
        cnt=cnt+1    
        

    return None #아이템이 리스트에 없음


my_list = list(range(1,101))
print(binary_search(my_list, 57))

결과값

찾는 문자 :  57
번호: 0  low: 0  high: 99  mid: 49  guess: 50
in  50 < 57  크다
번호: 1  low: 50  high: 99  mid: 74  guess: 75
in  75 > 57  작다
번호: 2  low: 50  high: 73  mid: 61  guess: 62
in  62 > 57  작다
번호: 3  low: 50  high: 60  mid: 55  guess: 56
in  56 < 57  크다
번호: 4  low: 56  high: 60  mid: 58  guess: 59
in  59 > 57  작다
번호: 5  low: 56  high: 57  mid: 56  guess: 57
in  57 == 57  return  56
56

다트 버전

온라인 에디터 바로가기

void main() {
  //1~100까지 생성  
  int targetNum = 57;
  var list = new List<int>.generate(100, (i) => i+1);
  print("final result =  ${binary_search(list, targetNum)}");
}

int binary_search(List<int> list, int item) {
  //초기화  
  int low = 0;
  //리스트 갯수 - 1
  int high = list.length - 1;

  //while low <= high
  while(low <= high) {  
    int mid = ((low + high) / 2).floor();    
    int guess = list[mid];
    print("$low,$high,$mid,$guess");
    if(guess == item) {
      return mid;
    }else if(guess > item) {
      high = mid -1;      
    }else{
      low = mid + 1;
    }          
  }

  return 0;

}

결과

0,99,49,50
50,99,74,75
50,73,61,62
50,60,55,56
56,60,58,59
56,57,56,57
final result =  56