알고리즘 [사전]

앞서 배운내용들을 복습하고 다시 풀어보는 시간 때문에 이번 포스팅이 조금 시간이 걸렸다.

🔎 정렬 알고리즘 비교

• 선택 정렬 : 우선순위 큐를 사용하여 정렬하며 제자리 정렬이 가능함 하지만 느리기 때문에 소규모에 적합
• 삽입 정렬 : 마찬가지로 우선순위 큐를 사욯아여 제자리 정렬이 가능하지만 느리다.
• 힙 정렬 : 우선순위 큐를 사용하여 구현(힙) 제자리 정렬이 가능하고 n log n밖에 걸리지 않기 때문에 대규모 입력에 적당함
• 합병 정렬 : 분할통치 기법을 사용하며 순차 데이터접근이 가능하고 빠름
• 퀵 정렬 : 분할통치를 사용하며 가장 빠르며 대규모 입력에 적당함

정렬의 안정성

정렬의 안정성이란. 정렬되지 않은 최신의 배열이 있다고 가정할 때 정렬 후에도 동일 키를 가진 원소들은 그 최신 순위를 그대로 가진 채로 정렬이 되어야 안정적인 정렬이라고 한다.

• 선택, 삽입, 합병 안정적
• 퀵, 힙은 안정적이지 못함

사전 ADT

• 키/원소가 쌍으로 이루어진 항목들의 모음을 사전이라고 함.

주요 작업

탐색, 삽입, 삭제

• 일반 메서드 - size(), isEmpty()
• 접근 메서드 - findElement(k)
• 갱신 메서드 - insertitem(k,e), removeElement()

사전의 활용

• 직접 응용 -> 연락처 목록, 인터넷 주소 등
• 간접 응용 -> 알고리즘 수행을 위한 보조 데이터 구조

탐색(Search)

사전에서의 탐색이란 데이터 집단으로 부터 지정된 키와 연관된 데이터 원소를 반환함을 말한다.

여기서 키는 유일키와 중복키로 나뉜다.

• 사전은 다양하게 구현이 가능한데 대표적으로 리스트, 트리, 해시테이블을 사용한다.

오늘은 리스트를 사용하여 선형탐색과 이진탐색을 사용해본다.

무순사전 ADT: 기록파일

기록파일은 무순리스트(정렬되지 않은)를 사용하여 구현된 사전이다.

• 성능 : Insertitem은 기존 리스트의 맨 앞 또는 맨 뒤에 삽입하면 되므로 O(1)시간이 소요된다. 하지만 검색의 경우 최악의 경우를 생각해 O(n)시간이 소요된다.

즉, 소규모 사전에 많이 사용되며 삽입은 빈번하게 이루어지나 탐색/삭제는 드문 사전에 많이 사용

Alg findElement(k)
  input list L, key k
  output element with key k

1. L.initialize(i)
2. while(L.isVaild(i))
  if(L.key(i) == k)
    return L.element(i)
  else
    L.advance(i)
3. return NoSuchKey

키 탐색 알고리즘은 위와 같이 하나씩 전부 다 찾아보기 때문에 선형탐색이라고 부른다.

• 최악의 경우 찾는 키가 맨뒤에 존재하거나 아예 없는 경우..

순서 사전 ADT: 일람표

일람표는 순서리스트(정렬된)를 사용하여 구현된 사전이다.

• 무순사전과 다르게 탐색은 이진탐색(분할통치와 비슷한 느낌?)을 사용하면 O(log n)시간이 걸린다.
• 하지만 새로운 원소를 삽입하기 위해선 공간 확보를 위해 O(n)의 시간 소요 / 삭제 마찬가지

즉, 소규모 사전과 탐색은 빈번하지만 삽입이나 삭제가 드문 사전에 효과적이다.

탐색 비교

선형탐색

• 실패가 예정된 선형탐색의 경우 즉, 이미 찾는 값보다 커지거나 작아진 경우 다른 조건문을 걸어 탈출조건.

Alg findElement(k)
  input list L, key k
  output element with key k

1. L.initialize(i)
2. while(L.isVaild(i))
  if(L.key(i) == k)
    return L.element(i)
++elseif(L.key(i) > k)
    return Nosuchkey
  else
    L.advance(i)
3. return NoSuchKey

이진탐색

키로 정렬된 배열에 기초한 리스트로 구현된 사전에 대해 작업을 수행

Alg findElement(k)  
  input sorted array A[0..n-1], key k
  output element with key k

1. return rEF(k,0,n-1) //재귀 호출

Alg rEF(k,l,r)
1. if(l > r) // 종료 조건
  return NosuchKey
2. mid <- (l + r)/2
3. if(k=key(A[mid]))
    return element(A[mid])
  elseif(k < key(A[mid]))
    return rEF(k,k,mid-1)
  else // k > key(A[mid])
    return rEF(k,mid+l,r)

위의 의사코드 처럼 함수가 호출될 때 마다 수가 절반씩 줄어들어 든다.

• 입력 순서 리스트가 배열로 구현된 경우 최악의 수 O(log n)
• 만약 연결리스트라면 접근하는데 걸리는 시간 자체가 O(n)시간 수행

분활통치와 이진탐색의 차이점은 분할통치는 양쪽의 범위 모두 고려 즉 재귀 안에 재귀함수 두개 구현-> 병합 / 이진탐색은 한쪽만 고려함

탐색 트리

• 이진 탐색 트리

이진 탐색트리란 내부 노드에 (키, 원소)쌍을 저장할때 다음의 성질을 만족하는 이진트리를 말한다.

• u,v,w는 모두 트리노드이며 u,w가 v의 자식일때 다음이 성립 key(u) < key(v) < key(w)
• 이진 탐색트리를 중위순회로 탐색한다면 키가 증가하는 오름차순으로 방문하게 된다.

탐색

• 키 k를 찾기 위해 루트에서 출발하는 하향 경로를 추적한다면 현재 노드와 자식노드들간 크기비교를 통해 하향한다.

Alg findElement(k)  
  input binary search tree T, key k
  output element with key k

1. w <- treeSearch(root(), k)
2. if(isExternal(w))
    return NoSuchKey
  else 
    return element(w);

Alg treeSearch(v, k)
  input node v of a binary search tree, key k
  output node w, s.t either w is an internal node
  sorting key k or w is the external node where key k 
  would belong if it existed

1. if(isExternal(v)) //종료조건 1
  return v
2. if(k = key(v)) //종료조건 2
    return v
  elseif(k < key(v))
    return treeSearch(leftChild(v), k)
  else // K > key(v)
    return treeSearch(rightChild(v),k)

삽입

Alg insertItem(k, e)
 input binary search tree T, key k, element e
 output none

1. w <- treeSearch(root(), k)
2. if (isInternal(w))
  return
 else
  Set node w to (k, e)
  expandExternal(w)
  return

삭제

Alg removeElement(k)
 input binary search tree T, key k
 output element with key k

1. w <- treeSearch(root(), k)
2. if (isExternal(w))
  return NoSuchKey
3. e <- element(w)
4. z <- leftChild(w)
5. if (!isExternal(z))
  z <- rightChild(w)
6. if (isExternal(z))   {case 1}
  reduceExternal(z)
 else       {case 2}
  y <- inOrderSucc(w)
  z <- leftChild(y)
  Set node w to (key(y), element(y))
  reduceExternal(z)
7. return e

이진탐색트리의 성능

• 한쪽으로 편향된 이진탐색 트리의 경우 O(n)의 시간이 소요되
• 균등한 이진 탐색트리의 경우 O(log n)소요