자료구조 정리

CS 기술면접 대비 그리고 개인 공부를 위해 2학년 때 배웠던 자료구조 과목 정리본을 다시 노션 및 티스토리에 정리해서 올려보려 한다.

각 알고리즘 및 자료구조에 대해 상세하게 설명하기 보단, 핵심 개념만 간단히 짚고 정리한 것이라 이해가 잘 되지 않는다면 각각의 개념을 검색해보는걸 추천한다.

---

자료구조와 알고리즘이란?

자료구조는 데이터를 원하는 규칙 또는 목적에 맞게 저장하기 위한 구조이고, 알고리즘이란 자료구조에 쌓인 데이터를 활용해 어떠한 문제를 해결하기 위한 여러 동작들의 모임이다.

대표적 자료구조

스택 : FILO구조 처음 넣은 게 가장 마지막에 나오는 구조

큐 : FIFO구조 처음 넣은게 가장 먼저 나오는 구조

• 우선순위 큐 : 원소마다 우선순위를 가지고 이 우선순위에 따라 OUT되는 큐
  • 구현방법 : 배열, 연결리스트, 힙
  • 시간 복잡도
    • 
    • 힙 : 부모노드의 키가 자식 노드들의 키보다 모두 크거나 작은 완전 이진트리
      • 배열을 이용하여 구현한다.
        • 완전 이진트리기에 노드에 번호를 붙일 수 있다.
        • 왼쪽 자식의 인덱스 = 부모노드 인덱스 *2
        • 오른쪽 자식 인덱스 =부모 인덱스 *2+1
        • 부모 인덱스 = 자식인덱스/2 (int)
      • 삽입 : 제일 끝에 삽입하고 부모와 비교하여 전체 트리가 조건을 만족하게끔 교환한다.
      • 삭제 : 말단 노드를 삭제하는 것은 의미가 없고 루트 노드를 삭제하는 것만을 다룬다
        • 루트 노드를 삭제하고 마지막 노드를 루트 노드로 이동한 후 밑으로 쭉 swap을 진행하여 트리를 갱신한다.
      • 힙 정렬 : 힙을 이용해 주어진 수들을 정렬하는 것을 의미한다.
        • 삽입, 삭제 모두 O(logN)이므로 N개의 원소를 삽입하고 (O(NlogN)) N개의 원소를 다시 삭제하여 (O(NlogN)) 최대값을 순서대로 뽑아낸다. (만약 오름차순을 원한다면 index값을 거꾸로 부여한다 ( 배열의 크기가 k라면 k-1부터))

트리 : 정점과 간선을 이용해 사이클을 이루지 않도록 구성한 Graph의 특수한 형태 계층 데이터 표현에 적합하다.

• 즉, 리스트,스택,큐와 같은 선형구조가 아닌 계층적인 구조를 나타내는 자료구조이다.
• 트리를 구성하는 요소를 모두 node라 한다
• 트리의 최정점에 위치한 노드를 Root라 한다
• Subtree란 특정 노드와 그 자식들로 이루어진 트리를 의미한다.
• 단말노드 (leaf node, terminal node)는 자식이 없는 노드를 의미한다
• 비단말노드는 반대로 자식이 있는 노드를 의미한다.
• 트리의 레벨은 트리의 각 층의 번호를 의미하는데, 보통 루트의 레벨을 1혹은 0으로 정하고 밑으로 내려갈 수록 증가한다.
• 높이는 트리의 최대 레벨을 의미한다.
• 차수는 해당 노드가 가진 자식 노드의 개수를 의미한다.
  • 손주( 자식의 자식)노드는 세지 않는다.
• 트리는 이진 트리, 일반 트리로 나누어지는데
  • 이진 트리란, 모든 노드가 2개의 서브 트리를 가지는 트리, 즉, 모든 노드는 최대 2개의 자식 노드를 가지는 트리이다.
  • 
    • 노드의 개수가 n개라면 간선의 개수는 n-1개이다
    • 높이가 h인 이진트리는 최소 h개 최대 2^h -1개의 노드를 가진다
    • 포화이진트리, 완전이진트리, 기타 이진트리로 나뉘는데
    • 포화이진트리란 말그대로 비단말 노드의 차수가 2인 트리이다.
    • 완전 이진트리란, 단말 노드가 있는 레벨을 제외하곤 포화 이진 트리의 속성을 만족하고, 마지막 레벨에선 왼쪽에서 오른쪽으로 노드가 순서대로 채워진 이진 트리를 의미한다.
    • 배열(포화 이진 트리라 가정하고 번호를 붙여서), 포인터(이중 연결 리스트)를 이용해 표현할 수 있다,
    • 이진트리의 순회는 전위,중위 후위 순회로 나뉜다.
    • 
      • 전위순회: VLR, 루트노드를 먼저 방문
      • 중위순회 : LVR, 왼쪽 자손, 루트, 오른쪽 순으로 방문
      • 후위 순회 : LRV : 자손을 먼저 방문
        • 디렉토리 용량 계산 및 수식 계산에 용이하다.
    • 레벨 순회 : 각 노드를 레벨 순으로 (위→아래, 왼→오) 순회하는 방법 , 위의 순회들과 달리 스택을 사용하지 않고 큐를 사용하여 순회한다.
    • 
    • 수식을 위처럼 순회를 이용하여 표현할 수 있다.
  • 이진 탐색 트리
  • 
    • 왼쪽 서브트리 ≤ 루트노드≤ 오른쪽 서브트리 의 형태로 값이 구별된 트리
    • 즉, 어떤 노드의 왼쪽 서브트리는 모두 해당 노드보다 작고 오른쪽 서브트리는 해당 노드 보다 모두 값이 크다
    • 이렇게 되는 경우 중위순회를 하여 오름차순으로 정렬된 값을 얻을 수 있다.
    • 
    • 삽입의 경우 삽입할 값을 대상으로 탐색을 진행하다 실패한 위치가 삽입할 위치가 된다.
    • 삭제는
      • 단말노드라면 그냥 부모를 찾아 연결을 끊고 free하면 끝나고
      • 서브트리를 하나 가지고 있는 경우 노드를 삭제하고 서브트리의 부모를 삭제한 노드의 부모에 붙여준다.
      • 두개의 서브트리를 가지고 있다면 서브트리의 모든 노드 중 삭제할 값과 차이가 가장 작은 값을 삭제할 노드의 위치로 변경한다.
        • 즉, 왼쪽 서브트리에서 제일 큰 값 혹은 오른쪽 서브트리에서 가장 작은 값 중 더 가까운 값을 삭제할 노드와 변경한다.

힙 : MaxHeap, MinHeap과 같이 최대 혹은 최소값을 찾아내기 쉽게 만들어진 구조, 각 노드의 키값이 자식의 값보다 작지 않거나(MaxHeap) 크지 않은(MinHeap) 완전 이진 트리이다.

 

원형 연결 리스트

• 이 경우 맨 앞에 원소를 삽입하려면
  • 현재 헤드의 link(next)를 새로운 노드의 link(next)로 만들고, 현재 헤드의 link를 새로운 노드로 한다.
• 리스트의 맨 뒤에 원소를 삽입하려면
  • 현재 헤드의 Link를 새로운 노드의 link로 만들고 현재 헤드의 link를 새 노드로 바꾼 후 헤드가 새로운 노드를 가르키도록 변경한다.
• 프로세스의 대기 큐 - Ready Queue - 실행 으로 이어지는 과정을 원형 연결 리스트로 구현할 수 있다.

이중 연결 리스트

• 단일 연결 리스트의 경우 자신의 선행노드 (prev)를 알기 힘들기에, 두 개의 링크 (prev,next)를 가지는 리스트
• 보통 헤드 노드를 두는데, 데이터를 가지지 않고 단지 삽입,삭제를 위해 만들어진 노드
  • init시점엔 헤드 노드만 존재하고 prev,next모두 자기 자신을 가르킨다.
• 삽입
  • target노드의 오른쪽에 새 노드를 삽입한다면
  • 새 노드의 prev=target, next=target.next
  • target.next.prev=새 노드, target.next=새 노드
  • 이렇게 해주면 된다.
• 삭제
  • 삭제할 노드를 target이라 하면
  • target.prev.next=target.next, target.next.prev=target.prev로 바꾸고
  • target노드를 free해준다.

그래프

• 인접 행렬 혹은 인접 리스트로 구현한다. (인접 리스트로 구현하는 것이 O(n+e)로 탐색에 유리)
• 탐색 알고리즘
  • DFS(깊이 우선 탐색)
  • BFS(너비 우선 탐색)

신장 트리 (spanning tree)

• 그래프 내의 모든 정점을 포함하고 n개의 정점이 있을 때 n-1개의 간선으로 이루어진 트리
• MST(최소 신장 트리, Minimum Spanning Tree) : 최소의 비용을 가지는 신장 트리
• 그리디 메소드 : 각 단계에서 최선의 선택을 반복하는 기법
• Kruskal의 MST
  • 모든 엣지를 오름차순으로 정렬한다
  • 순서대로 채택을 하지만 만약 사이클을 형성하면 넘어간다.
    • Union-Find로 판단한다.
    • 
    • 
      • 하나의 집합에 원소를 추가하는데, 만약 새로운 현재 엣지로 인해 추가되는 원소가 속한 집합의 부모 노드와 현재 집합의 부모 노드가 같다면 같은 집합이기에 넘어간다
        • 즉, 이미 집합에 속한 원소로의 엣지이기에 사이클을 형성하게 된다. 그러므로, 해당 엣지는 추가하지 않는다.
    • 모든 노드를 포함시킬 때 까지 반복한다.
    • 간선을 quickSort로 정렬한다면 O(elog(e))의 시간복잡도를 가진다.
• Prim의 MST
• 
  • 시작 점에서 출발해 신장 트리 집합을 단계적으로 확장하는데 인접한 정점들 중 가장 싼 정점을 선택하여 집합에 추가한다.

  • 

  • O(n^2)의 시간 복잡도를 가진다.
• 간선이 매우 밀집되어 있는 경우는 Prim이 유리하고 그렇지 않다면 Kruskal이 유리하다.

최단경로

• 다익스트라 : 하나의 시작 점에서 다른 점까지의 최단 경로 계산
• 
• 플로이드 : 모든 점에서 다른 모든 점까지의 최단 경로 계산

정렬

• 정렬의 안정성 : 동일한 값을 갖는 레코드들의 상대적 위치가 정렬 후에도 바뀌지 않는다
• 
  • 이 경우 안정하지 않은 정렬이다.
• 선택정렬 : 정렬이 되지않은 리스트에서 최솟값을 찾아 정렬이된 리스트로 옮긴다.
  • 실제로 옮기진 않고 정렬된 인덱스를 0부터 시작해서 배열의 끝까지 옮겨가는데
  • i번째 인덱스까지 정렬되었다면 i+1~n까지의 원소 중 최솟값을 i+1번째 원소와 swap한다
  • 이렇게 끝까지 실행하면 배열이 모두 정렬된다
  • 안정성을 만족하지 않는다
• 삽입 정렬 : 정렬되어 있는 부분에 새로운 레코드를 올바른 위치에 삽입한다.
  • 선택정렬처럼 정렬된 배열에 앞에서 부터 삽입 대상과 비교해가며 해당 대상의 위치를 찾아 그곳에 넣는 정렬방법
  • 안정된 정렬방법이다.
  • 정렬된 배열일수록 효율적이다.
• 버블정렬 : 인접한 2개의 레코드를 비교하여 정렬한다.
• 
  • 이동 횟수가 평균 O(n^2)으로 이동시간이 과하게 소요된다.
• 셀 정렬 : 전체리스트를 일정 간격으로 나누어 부분리스트로 만들고 이 각각 부분리스트에 대해 삽입정렬을 한다
  • 삽입 정렬이 이미 정렬된 배열에 대해서 효율적이라는 점에 착안하여 만들어진 방법
  • 간격을 5,3,1 이런식으로 줄여가며 정렬을 진행한다.
  • 적은 이동 시간으로 제자리를 찾을 확률이 늘어난다.
• 합병 정렬 (merge sort) : 리스트를 두개로 나누고 각각 정렬한 후, 다시 합쳐 전체 리스트를 정렬한다.
• 
  • 전체 리스트를 최대한 쪼갠 후, 인접 부분 리스트끼리 다시 합친 후 정렬하는 것을 반복하여 전체리스트를 정렬한다.
• 
• 
  • 2n*log(n)번의 이동이 발생되기에 레코드가 큰 경우 이동에 시간적 소모가 크다
  • 안정적이다
• 퀵정렬 : 평균적으로 가장 빠른 정렬, 분할정복법을 사용한다.
  • 리스트를 2개의 비균등 분할 (중간에 피벗 원소를 하나 잡는다)하고 각각의 부분리스트를 다시 퀵정렬을 한다.
• 
• 
• 
  • 위와 같은 과정으로 정렬을 진행한다.
  • 이동 횟수의 경우 상대적으로 매우 적기에 무시해도 된다.
  • 극도로 불균등하게 분할되는 경우 n^2의 비교를 해야되지만 중간값을 피벗으로 선택하면 완화가 가능하다.
• 기수 정렬 : 레코드를 비교하지 않고 정렬을 한다.
  • 0~9까지의 수를 담당하는 버킷을 만들고 앞에서부터 쭉 버킷에 값을 넣은 후, 0부터 값이 들어있는 버킷에서 쭉 값을 꺼내 배열에 담으면 정렬이 된다.
• 
  • 자리수가 둘 이상인 수를 정렬하는 경우 맨 뒤 혹은 맨 앞부터 순서대로 자리수 별로 배열을 정렬해나간다.
    • 즉, 1의자리로 분류 →10의 자리로 분류 →100의 자리로 분류 .. 이런식으로 진행한다.
  • n개의 레코드 d개의 자릿수를 정렬하는경우 O(dn)의 시간 복잡도를 가진다
    • 여기서d는 충분히 작은 수이기에 매우 빠르게 정렬이 된다.
• 전체적인 시간 복잡도

탐색

• 순차 탐색 : 처음부터 끝까지 하나씩 검사하는 것 (O(n))
• 이진 탐색 : 정렬된 배열에서 중앙값을 기준으로 탐색 대상이 왼쪽에 있는지 오른쪽에 있는 지 알아내어 탐색의 범위를 좁혀나가는 탐색
• indexed 순차 탐색 : 인덱스 테이블을 이용하여 순차 탐색 (단, 인덱스 테이블, 자료 리스트 모두 정렬되어 있어야 한다.) (O(m+n))
• 
  • 15란 값을 찾으려면 3과 22사이이니 3에 해당하는 인덱스 0번부터 탐색을 순차적으로 진행한다.
• 보간 탐색 (interpolation search) : 사전이나 전화번호부 보는 것 처럼 하는 탐색
• 
  • 이진 탐색과 유사하지만 탐색 범위를 갱신하는 부분이 좀 다르다.
• 이진 탐색 트리
  • AVL트리 : 모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차가 1이하인 이진 탐색트리
    • 트리가 비균형 상태가 되면 스스로 노드들을 재배치하여 균형을 찾는다
    • 균형 인수가 2이상인 노드가 불균형을 만드는데, 여기서 균형인수란 자신의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차를 의미한다.
    • LL,LR,RR,RL타입의 불균형이 존재하고 해당 불균형을 해결하기 위해 각각 오른쪽, 왼→오, 왼, 오→왼 회전을 한다.

    • 

  • 2-3트리 : 차수가 2또는 3인 노드를 가지는 트리
  • 

해싱

• 키 값에 대해 연산을 통해 주소를 계산하여 항목에 접근하는 것을 말한다.
• 탐색 키값을 입력으로 받고 이를 해시함수를 통해 해시 주소로 바꾼다
• 해시 테이블의 각 인덱스를 버켓이라 하고 하나의 버켓에 넣을 수 있는 원소들을 슬롯이라 부른다
• 다른 키값에 대해 같은 해시 주소가 나오는 걸 충돌
• 충돌이 버켓의 슬롯 수보다 많이 나는 경우 오버플로우라 한다
• 좋은 해시 함수란 충돌을 최소화하고 오버플로우를 일으키지 않는 함수이다.
• 해시 함수로는 정말 많은 함수들을 사용할 수 있다 (제산,폴딩,중간 제곱,…)
• 이중 해싱, 체이닝(버킷을 연결리스트로 구현) 등으로 오버플로우를 막을 수 있다.