시간복잡도 + 핵심이론 정리

시험 정보

실습

• 총 4문제. 실습때 풀어본 문제들 + 신규 문제(1~2개)

링크드리스트

garbage collector : 나중에 필요할 때 삭제된 데이터는 다시 호출 가능하다

1) position 이 주어지지 않는경우 => find and insert, delete

• 싱글리 링크드 리스트

  • head에 append : O(1)
  • head를 delete : O(1)
  • tail에 append : O(1)
  • tail을 delete : O(n) => tail의 delete 연산은 비효율적이다!
  • tail 앞에 insert / delete : O(n) => 바로 앞 위치를 못찾으므로 오래걸림
  • 중간 어딘가에 insert : O(n)
  • 중간 어딘가를 delete : O(n)

• 더블리 링크드 리스트

  • head에 append : O(1)
  • head를 delete : O(1)
  • tail에 append : O(1)
  • tail을 delete : O(1)
  • tail 앞에 insert / delete : O(1)
  • 중간 어딘가에 insert : O(n)
  • 중간 어딘가를 delete : O(n)

2) position 이 주어진 경우 => 그냥 insert, delete

• 싱글리 링크드 리스트

  • p 에다 insert / delete : O(1)
  • p 앞에 insert / delete : O(n)

• 더블리 링크드 리스트

  • p 에다 insert / delete : O(1)
  • p 앞에 insert / delete : O(1)

스택

1. 배열기반

• access point : int top = -1;
• 공간 : O(N)
• push, pop, top : O(1) => 모든 연산 O(1)

t : 꼭대기 인덱스 번호

Algorithm push(o)
  if t = S.size()-1 then
    throw StackFull
  else
    t <- t+1
    S[t] = o

Algorithm pop()
  if empty() then
    throw StackEmpty
  else
    t <- t-1
    return S[t+1]

Algoritm top()
  if empty() then
    throw StackEmpty
  else
    return S[t]

Algorithm size()
  return t+1

Algorithm empty()
  if size() = 0 then
    return true
  else
    return false

2. 싱글리 링크드리스트 기반

• access top : Node* top;
• 공간 : O(n)
• 모든 연산 O(1)
• top 노드를 head 노드로 둔다. ( tail을 top으로 두면 pop연산이 O(n) 이라서 )
• 활용분야 : 함수호출시 run-time stack, 웹브라우저의 뒤로가기 버튼, Undo 기능을 구현하기 위해 명령어 저장

  
Algorithm push(data)
  p <- new node pointer struct(?)
  p.data <- data
  topNode.next <- p  // topNode : 꼭대기 노드형 포인터
  topNode <- p 
  size <- size + 1
  
Algorithm pop()
  p <- new pointer node
  p <- top
  top <- top.next
  delete p
  size <- size - 1
  
Algorithm top()
  if empty() then
    throw StackFull
  else
    return top.data;
    
Algorithm empty()
  if size() = 0 then
    return true
  else
    return false

Algorthm size()
  return size;

큐

1. 환형배열 기반
   • access point : front, rear
   • full :
   • 공간 : O(N)
   • 모든 연산 O(1) - enqueue, dequeue, front
   • 활용분야 : 관공서에서 대기열, 공유 프린터, 다중 프로그래밍
   • rear 인덱스 변수 : rear element의 다음 인덱스를 나타냄
   • mod N : 인덱스 범위가 0~N-1이 되도록 설정

Algorithm enqueue(o)
  if size() = N-1 then  // N:배열의크기(capacity)
    throw QueueFull
  else
    arr[rear] <- o
    rear = (rear+1) mod N
    n <- n + 1

Algorithm dequeue()
  if empty() then
    QueueEmpty
  else
    front = (front+1) mod N
    return arr[front-1]

Algorithm front()
  return arr[front]

Algorithm size()
  return n

Algorithm empty()
  if top = -1
    return true
  else
    return false

2. 싱글리 링크드리스트 기반

• access point : Node frontNode, Node rearNode
  ※ 환형 배열과 달리 다이렉트로 시작 원소, 마지막 원소를 가리킴(환형 배열은 rear가 마지막 다음을 나타냈음)
• 공간 : O(n)
• 모든 연산 O(1)
• dequeue 를 front에서 진행해야함 (rear에서 진행시 삭제연산이 O(n))

Algorithm enqueue(o)
  if size() = N-1 then
    throw QueueFull
  else
    tmp <- new node pointer 
    tmp.data = o
    rear.next = tmp
    rear <- tmp
    n <- n + 1

Algorithm dequeue()
  if empty() then
    throw QueueFull
  else
    tmp <- front
    front <- front.next
    n <- n + 1
    delete tmp

Algorithm front()
  if empty() then
    throw QueueFull
  else
    return front.data

벡터

• 환형배열로 구현시 우리가 생각하는 인덱스와 실제 인덱스가 달라질 수 있는다는 점 주의할것.

• 환형배열로 구현시 insert(0,x), erase(0) 같은 맨앞 삽입/삭제"만" O(1)에 가능

• 공간 : O(N) (N:처음에 할당한 배열의 크기)

• insert

  • 배열 : O(n)
  • 환형배열 : O(n) (맨앞에 insert는 O(1))
  • Growable-Array
    • O(1) (아직 다 안찼을때 insert)
    • O(1) (가득 찼을때의 insert. Doubling strategy로 구현한경우)
    • O(n) (가득 찼을떄의 insert. incremental strategy로 구현한 경우)

• erase

  • 배열 : O(n)
  • 환형배열 : O(n) (맨앞의 erase는 O(1))

• 나머지 연산 at(i), set(i,o), empty(), size() 는 모두 O(1)

Algorithm insert(o)   // 배열의 끝에 삽입 (=insert(n,o))
  if t = S.length - 1 then  // t : 배열의 끝 인덱스  S : 배열의 크기(capacity)
    A <- new array of 
      size...
    for i <- 0 to n-1 do
      A[i] <- S[i]
    S <- A
    n <- n+1

position

• 내부적으로 자료구조가 어떻게 구현되있는지 상관하지 않고 외부에서 해당 자료구조에서 원하는 원소의 위치에 access 할 수 있도록 하는 것

• p.element() : O(1) => 주어진 position p 에 해당하는 값을 리턴
  (p가 position을 나타내는 변수라면, 예를들어 iterator의 begin과 같은것)
  

• position 이 "위치"라는 개념이지만, 대게 "포인터, 즉 주소(address)" 이다.
  => 그냥 주소라고 생각하고, 해당 주소의 element 를 리턴해줘라는 의미!

리스트

• access point : Node begin, Node end
  ※ begin은 시작원소를, end는 마지막원소의 다음 주소를 가리킨다.
  begin = header
  end = tailer → next

• 공간 : O(n) 사용

  • 리스트의 각각의 position이 O(1)의 공간(= 객체 위치. position을 포인터로 따졌을때는 포인터 객체+주소값)을 차지하므로, n개의 element가 있다면 O(n)의 공간을 차지

• 모든 연산 O(1)

  • size(), empty()
  • begin() : 리스트의 시작 주소 리턴 (return header->next)
  • end() : 리스트의 마지막 주소 "다음 주소"리턴 (return trailer)
  • insert(p,e), erase(p)
  • insertFront(e), insertBack(e)
  • eraseFront(), eraseBack()

// p앞에다 데이터 e를 가지는 새로운 노드q를 삽입

Algorithm insert(p, e): {insert e before p} 
  Create a new node q
  q.data <- e
  q.prev <- p.prev
  q.next <- p
  q.prev.next <- q
  q.prev <- q
  n <- n + 1
  
Algorithm erase(p) 
  p.prev.next <- p.next
  p.next.prev <- p.prev
  delete p (또는 free p)
  n <- n-1

• position 을 기반으로 해당 자료구조의 데이터를 access

• 외부에서 해당 자료구조들 position이라는 개념으로 호출하지만, 내부적으로는 인덱스, 노드형 포인터, .. 등으로 알맞게 position이 변환되서 access 가능

• iterator를 외부에서 활용해서 리스트 내부에서 원하는 데이터의 위치를 찾아내고 access 가능 (이때 iterator는 맨앞,맨뒤의 원소에 대해서만 access)

• iterator로 begin부터 따라가면서 특정 위치인 5번째 위치를 찾아냈다면, 더블리 리스트로 구현된 내부에서는 5번째 위치의 주소값으로 변환을 통해 진행할 수 있다.

시퀀스

• 환형 배열로 구현 : insert(p,e), erase(p) 는 O(n). 나머지는 모두 O(1)
• 더블리 링크드 리스트 : atindex(i), indexOf(p)는 O(n). 나머지는 모두 O(1)
• 메소드 종류

1) 리스트 기반의 메소드(=position 으로 access하는 메소드)

• insertFront(o), insertBack(o), insert(p,o)
• eraseFront(), eraseBack(), erase(p)

2) index를 통해 access하는 메소드

• atIndex(i), indexOf(p)

3) 기타 메소드

• size(), empty()

시퀀스 상세 설명

환형 배열로 구현

• 배열의 각 인덱스 방에는 position이 저장(=주소값이 저장)
• 각 position들에 대한 시퀀스 객체들의 구성 : 데이터 필드 + 인덱스 필드
  • 데이터 필드에는 또 다른 데이터 객체에 대한 포인터 변수 주소값 저장o

1. insert(p,e) : O(n)

• 환형배열에 insert시 기존에 배열에 저장되있던 position값들을 한칸씩 뒤로미룸
• 각 position에 대한 시퀀스 객체들이 인덱스 필드값도 1씩 증가

  ---

2. insertFront, eraseFront, insertBack, eraseBack : O(1)

• insertFront : 인덱스 f의 앞셀에다 position을 삽입후 f를 1감소
• eraseFront : 인덱스 f의 값을 1증가

=> insertFront, eraseFront 연산이 진행될때마다 f가 증감하는 횟수를 카운팅해서 저장한다. 그러고 나중에 언젠가 한밤중에 카운팅한 정보를 기반으로 환형배열과 시퀀스 객체의 불일치하는 인덱스 값을 일치시키도록 다시 sorting 시킨다.
( f와 0번 인덱스와의 차이를 계산해서 sorting )

3. atIndex(i) : O(1)

• i : 환형 배열의 인덱스가 아닌, 시퀀스 객체에서의 인덱스

• 시퀀스의 인덱스와 환형배열의 인덱스가 얼마나 불일치함을 감안
  ex) i=3, f=1인 경우 시퀀스 객체에 대한 환형배열의 position은 환형배열에서 3+1 = 4번째 인덱스에 저장 => 환형배열의 4번째 방의 position을 접근해 해당 시퀀스 객체의 데이터 값을 리턴

  ---

4. indexOf(p) : O(1)

• 실제 주소값을 주므로, 주어진 주소값(position)에 대한 시퀀스 객체들 찾아내고 인덱스 필드의 값을 리턴받기

  ---

더블리 링크드 리스트로 구현

• atIndex( i ) : 인덱스i에 해당하는 실제 position을 찾아가서 데이터에 access
  • iterator를 begin부터 시작해서 for문을 조지면서(=O(n)) 도착후 해당 방에 대한 시퀀스 객체의 데이터를 조회(=O(1))

• indexOf( p ) : iterator p가 가리키는 해당 객체에서 부터 시작해서 역방향으로 맨앞 head에 도달할때까지 몇번 카운팅 됐는지를 리턴

• insert, erase 모두 position을 이용하므로 O(1)