Algorithm Study 1 - 2주차

코딩클럽 알고리즘 2주차 - 탐색, 정렬

탐색 수행 능력을 평가하기 위해서는 메모리로부터 자료를 가져오는(fetch) 시간보다 자료들을 비교하는 데 걸리는 시간이 더 많이 소모되므로, 비교횟수( number of comparison )를 탐색 방법의 평가 기준으로 삼는다. 즉, 비교횟수가 적은 알고리즘일수록 좋은 성능을 보여준다고 가정한다.

왜????

데이터 양이 많아 지면 많을 수록 비교 횟수는 시간 복잡도를 잡아 먹는 원인 중 하나이기 때문에 비교 횟수가 적은 알고리즘이 탐색 및 정렬 알고리즘에 있어서 가장 중요하다. 비교 횟수가 증가 할 수록 시간 또한 증가 된다.

탐색

탐색이란, 원하는 값을 찾는 행위를 말한다. 컴퓨터 전산학에서는 탐색을 자료 구조에서 보통 값을 찾는 데 사용한다. 물론, 우리가 사용하는 상용 프로그램에서는 메일에서 보낸 이의 이름 검색, 윈도우 탐색기의 검색 기능등 많은 부분에서 우리가 알게 모르게 사용하고 있다. 검색엔진 또한 탐색에 기초로 한다. ( 내부적인 구체적인 사항은 굉장히 복잡하고 어렵다. 특히…구글 검색엔진은 시시때때로 페이지 인덱싱 알고리즘이 다르게 작동한다. )

선형탐색(Linear Search)

• 단점
  • 시간이 오래 걸린다.
• 장점
  • 데이터가 무순서여도 탐색 가능하다.
• 평균 탐색 시간
  • O(N)이 된다.
• 사용 되는 경우
  • DBMS의 FTS(Full Table Scan), Index 탐색 - Index Full Scan 사용
• 왜 탐색시간이 O(N)일까? (N은 자료의 개수)
  • 순차접근이라 모든 자료를 확인해야 한다.
• 최악(worst case), 최고(best case)의 경우에 대해 생각해 보기.
  • 최악의 경우는 맨 마지막원소에 탐색 값이 있는 경우
  • 최상의 경우는 맨 처음 원소에 탐색 값이 있는 경우
• 중복된 자료가 있을땐 어떨까 생각해 보기
  • 탐색 값을 찾더라도 맨 마지막 원소까지 찾아봐야 한다.

    이진탐색(Binary Search)

• 단점
  • 정렬이 되어 있어야 탐색 가능
• 장점
  • 1/2씩 데이터를 거르기때문에 평균 속도가 빠르다.
• 평균 탐색 시간
  • O(log n)
• 사용 되는 경우
• 자료(레코드)들의 정렬 유무
• Divide & Conquer이란?
• 최악(worst case), 최고(best case)의 경우에 대해 생각해 보기.
• 왜 탐색시간이 최악의 경우에도 O(log2N)일까?
• Array를 이용한 binarySearch( int iKey, int arr[] ){} 생각해보기.
• Arr = [3, 7, 11, 12, 27, 49, 53, 68, 72, 91] 에서 iKey=53을 탐색한다는 가정하에, 손으로 과정을 하나씩 그려보는 연습 해볼 것.
• 위에있는 Arr 배열의 특징이 무엇인가???
  • 이미 정렬이 되어 있다.
  • 중복 값이 없다.
• 이로 인한 검색을 제외한 다른 연산( 삽입, 삭제 )에서 문제점이 있을까?
  • 삽입시 재정렬을 해야 한다.
  • 삭제시 정렬 상태를 검증 필요.

    이진 트리 탐색( Binary Tree Search )

• 위의 선형탐색, 이진탐색과 가장 큰 구조적 특징은?
• 이진트리(binary tree)에 대한 간략한 설명!!!
• 부모노드(parent node) & 자녀노드(left, right child node)
• 위 3개 노드간의 관계
• 노드 클래스의 간략한 코드

  class Node{
    public int keyData; //데이터(키)
    public Node leftChild;   //노드의 왼쪽 자식
    public Node rightChild; //노드의 오른쪽 자식
  }
  

• 단점
• 장점
• 평균 탐색 시간
• 사용 되는 경우
• 자료(레코드)들의 정렬 유무
• 최악(worst case), 최고(best case)의 경우에 대해 생각해 보기.
• 왜 탐색시간이 최악의 경우에도 O(N)일까?
• 다음 자료를 갖고 이진탐색트리 그려주고 설명 해주기
• 루트 노드 = 27
• 11, 3, 68, 53, 49, 91, 12, 72, 7를 순서대로 트리에 입력
• 위의 총 3개의 탐색 방법에 대한 실제 예시를 찾아보거나, 아니면 아무 숫자로 된 자료를 통해서 3개의 탐색 방법에 대해 스스로 비교해 보고, 손으로 그려보기!
• 예) Arr = [3, 7, 11, 12, 27, 49, 53, 68, 72, 91] 를 선형, 이진, 이진트리탐색으로!

정렬

모든 정렬은 실제로 정렬되지 않은 자료를 갖고, “손으로” 각 단계별로 정렬을 해볼 수 있을 정도로 공부해 볼 것!!
다음 데이터를 갖고 각각의 정렬 방법을 통해 정렬의 특징들을 파악 해보도록 합니다.

• 장점
• 단점
• 특징 및 개선사항
• 총 비교 횟수
• 총 이동(자리바꿈) 횟수
• 알고리즘 복잡도 O()의 일반화
• 말로 풀어쓴 수도코드( 예, 첫번째: 두개의 항목을 비교한다, 두번째: 비교 후 자리바꿈한다 등)
• 각각의 정렬 코드를 통해, 해당 정렬방법이 갖고 있는 코드를 주목하고 비교 설명
• 이처럼 4개의 정렬방법(물론 더~많은 정렬방법이 있지만)이 각각 언제 사용되는지 알아보기.(데이터 크기, 남은 데이터 양, 정렬 유무 등등)들

다음 데이터를 갖고, 실제로 그림 그려가며 스텝별로 해보기.
33, 11, 99, 1, 22, 88, 55, 44, 66, 77

버블 정렬(Bubble sorting)

• 장점
  • 구현이 쉽다.
• 단점
  • 비효율적이다.
  • 비교 횟수가 굉장히 많다.
• 알고리즘 복잡도
  • O(N^2)으로 표현

• 말로 풀어쓴 수도 코드

  1. 첫 번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면, 가장 큰 원소가 마지막 자리로 정렬 됨.
  2. 즉, 계속 반복하고 나면, 뒤에서 부터 정렬이 되는 특징을 가진다.

     선택 정렬(Selection sorting)

• 장점

  • 구현이 쉽다.
  • 이미 정렬 되어 있으면 Swap 하지 않음
  • 역정렬이 되어 있다면, N번 이하의 Swap으로 정렬이 가능.
• 단점
  • 버블 정렬보다 좋을 뿐 성능은 나쁘다.
  • 비교 횟수는 여전히 많다.
• 알고리즘 복잡도
  • O(N^2)으로 표현
• 말로 풀어쓴 수도 코드
  1. 전체 원소 중에서 가장 작은 원소를 선택하여 첫 번째 원소와 자리 교환.
  2. 그 다음으로 작은 원소를 선택하여 두 번째 원소와 자리 교환.
  3. 그 다음 세 번째.. 네번째를 반복한다.
  4. 선택 정렬은 앞에서부터 정렬이 되는 특징을 가진다.

추가하자면, 선택 정렬은 자리가 데이터를 선택한다고 이해하면 쉽다. 해당 위치에 올 데이터를 min or max 값이든 찾아서 해당하는 위치에 고정시킨다고 생각하면 오름 차순이든, 내림 차순이든 쉽게 이해 할 수 있다.

삽입 정렬(Insertion sorting)

• 장점
  • 선택/버블 정렬 보다 빠르다.
  • 절반 정도 정렬 되어 있는 상황에서 효율이 좋다.
• 단점
  • 데이터의 이동이 잦다.
  • 구현이 다른 것(선택, 버블 정렬) 보다 까다롭다.
• 알고리즘 복잡도
  • O(N^2)으로 표현
• 말로 풀어 쓴 수도 코드
  1. 정렬 된 집합/아직 정렬이 안된 집합 개념으로 나뉘어 생각하면 된다.
  2. 시작 후 앞에서 부터 정렬 된 집합이라고 가정/첫 번째 원소와 정렬 집합 원소와 비교하여 적절한 자리로 이동 시킨다.
  3. (단, 삽입정렬은 Key value 변수를 두어 해당 키 값으로 원소 비교를 한다. [물론, 제자리도 가능함] )
  4. 위 방법을 정렬 안 된 집합이 공집합이 될 때까지 반복하면 정렬이 끝난다.

삽입정렬은 데이터가 자리를 찾아간다고 이해하면 될 듯 싶다. 데이터에 맞는 자리 에 낑겨 넣어지는 알고리즘?!이라고 생각하면 쉽게 이해 할 수 있다.

퀵 정렬(Quick sorting)

분할 알고리즘(partition algorithm)이란?

쉽게 설명하자면, 일정 기준 값(통상적으로 Pivot 값이라 명칭)으로 데이터 리스트를 양분 하는 알고리즘이라 할 수 있다.

피봇(pivot)?

데이터 리스트 안에 존재하는 일정 기준 값(통상적으로 Pivot 값이라 명칭)

피봇 선택기준

• 최선의 선택

  Pivot 선택 후 Partition 알고리즘 수행시 분할 된 리스트 2개의 원소 수가 일정 하다면, 좋은 분할이라고 여길 수 있다.

• 최악의 선택

  Pivot 선택 후 Partition 알고리즘 수행시 한 쪽의 크기가 n-1이고, 다른 한 쪽은 0를 만들어내는 Pivot은 최악의 성능을 만들어낸다.

• 잘못된 피봇 선택 예제 와 최선의 피봇 선택 예제

  • Pivot 값이 원소 내 최솟값/최댓값을 선택 하는 경우 (최악)

재귀 호출(Recursion)

분할 통치 기법의 경우 재귀 호출의 형태로로 짜는 것이 자연스럽다. 단, 성능상 오버헤드 증가로 퀵 정렬은 신기하게도 제자리 퀵 정렬이 가능하다. (합병정렬의 경우 제자리 정렬이 어렵다…고 전해집니다.)

• 안정성(Stability)

  같은 값이더라도 기존에 있던 순서대로 유지하는지의 여부