카테고리 없음

자료구조

start1a 2020. 3. 2. 03:39

링크드 리스트

  • 단일 : 탐색 방향 1개. 꼬리 부분이 null -> 순회 불가능
  • 원형 : 탐색 방향 1개. 꼬리가 머리를 가리킴 -> 순회 가능
  • 이중 원형 : 탐색 방향 좌우 2개. 순회 가능

 

배열과 링크드 리스트

배열

  • 장점 : 인덱스를 활용한 빠른 탐색 가능

  • 단점 : 크기가 고정되며 순차적으로 저장되어 삽입 / 삭제에 어려움

링크드 리스트

  • 장점 : 각 데이터가 연결로 이루어져 있어 크기에 제한이 없으며 삽입 / 삭제가 용이함

  • 단점 : 필요한 데이터의 위치를 찾기 위해 이전 데이터들을 탐색해야 하므로 탐색 속도가 배열에 비해 느림

 

 

스택

  • 선형(1:1), 후입선출(LIFO) 구조

  • 배열 : top의 인덱스를 가리키는 변수가 데이터의 삽입 / 삭제에 따라 증감됨

  • 링크드 리스트 : 데이터가 없으면 null, 데이터가 추가될 때마다 top이 새로운 데이터를 가리키고 새 데이터는 이전 데이터를 가리킴

 

 

큐

  • 선형(1:1), 선입선출(FIFO) 구조

  • 배열 : 큐에서 데이터를 추출하는 head, 삽입하는 tail로 구성됨. 큐를 삽입하고 추출하면서 head, tail 인덱스가 상승

  • 링크드 리스트 : 배열과 동일

큐의 배열의 특징

  • tail이 배열의 마지막 인덱스에 도착한 후에 head에서 dequeue가 발생했을 경우 데이터를 추가할 공간이 있음에도 불구하고 더 이상 추가할 수 없는 일이 생김
    • 원형 큐로 변경해야 함
    • if (tail + 1 == QUEUE_SIZE)
        tail = (tail + 1) % QUEUE_SIZE

 

 

트리

  • 비선형(1:n) 구조

  • n(n > 2)개의 노드와 n - 1개의 간선으로 구성

  • 각 노드 간의 간선은 1개만 사용

    양 방향 모두 이동 가능

  • 트리의 종류

    • 이진 트리 : 자식을 2개 가질 수 있는 트리

    • 완전 이진 트리 : 루트 노드부터 순서대로 자식 노드를 2개씩 채워 나간 트리

    • 포화 이진 트리 : 말단 노드를 제외한 모든 부모 노드가 자식을 2개씩 가진 트리

  • 배열 : 부모 노드가 x(x >= 1)번 인덱스이면 그 부모의 자식 노드는 2x, 2x+1 위치에 있음

    반대로 부모 노드를 찾으려면 자식 노드 / 2를 함

  • 링크드 리스트 : 노드에서 좌우 노드로 향하는 주소를 지님

    부모 노드로 되돌아가기 위해서는 미리 부모 노드를 임시로 참조하고 있어야 함

 

트리의 탐색

좌측 노드로 이동 : L,  우측 노드로 이동 : R,  현재 노드 탐색 : V

  • 전위 순회 : V L R

  • 중위 순회 : L V R

  • 후위 순회 : L R V

 

 

그래프

  • 노드 간의 간선이 여러 개일 수도 있고 방향이 존재할 수 있음
  • 방향
    1개 : 단방향 그래프
    2개 : 쌍방향 그래프
  • 첫 노드에서 다른 노드로 출발했을 경우 다시 첫 노드로 돌아올 수 있으면 cyclic 그래프
    돌아올 수 없으면 acyclic 그래프

 

탐색

  • 선형 탐색 : 첫 노드의 데이터부터 마지막까지 원하는 데이터를 찾을 때까지 순차적으로 탐색
    • 장점 : 구현이 단순.
    • 단점 : 정렬이 되어있든 안 되어있든 최악의 시간 복잡도 n
  • 이진 탐색 : 정렬된 데이터를 트리 구조로 구현하여 데이터의 위치를 찾음
    • 장점 : 데이터의 값을 분기하여 탐색 크기를 반으로 줄여가므로 시간 복잡도 log n
    • 단점 : 항상 정렬된 상태로 데이터를 유지해야 하는 비용 발생

 

 

정렬

데이터를 크기에 맞게 나열

배열의 오름차순 기준으로 설명함

  • 선택 정렬
    정렬시킬 데이터 위치부터 마지막 인덱스 위치까지 차례로 하나씩 선형 탐색하여 가장 최솟값을 찾아 그 데이터와 순서를 바꿈
    • 장점 : 구현이 단순함.
    • 단점 : 최악의 시간 복잡도가 언제나 n^2
  • 버블 정렬
    첫 데이터부터 마지막에 도달할 때까지 처리. 오른쪽 데이터가 더 작으면 순서를 바꾸고 크거나 같으면 바꾸지 않음.
    • 장점 : 바로 옆 인덱스와 교환하므로 이해가 쉽고 구현이 단순.
    • 단점 : 최악의 시간 복잡도가 언제나 n^2, 값을 순서를 자주 바꾸어야 주어야 하는 부담 발생
  • 삽입 정렬
    정렬된 데이터 집합과 그렇지 않은 집합으로 구분함. 보통 가장 첫 인덱스가 전자에 속한다.
    후자의 첫 인덱스부터 하나씩 전자의 마지막 인덱스부터 차례로 앞으로 가며 비교한다. 반복하다가 더 작은 데이터를 만나면 그 데이터 옆에 위치하며 다음 정렬할 데이터를 반복적으로 처리한다.
    • 장점 : 평균 시간 복잡도 n
    • 단점 : 최악은 여전히 n^2일 수 있음
  • 퀵 정렬
    데이터 집합에서 피봇이라는 태그의 데이터를 하나 설정하여 피봇을 기준으로 집합을 둘로 나눈다. 왼쪽(L)과 오른쪽(R)에 데이터를 양 바깥에서부터 하나씩 탐색하여 L 피봇보다 크거나 같은 값을 찾고 R은 피봇보다 작은 값을 찾아 서로 교환한다. L, R이 서로 마주치면 피봇과 바꾸고 나서 끝내고 L, R이 피봇에서 마주치면 피봇을 정렬된 값으로 처리하며 그 자리에 고정한다. 그 피봇을 기준으로 좌우 집합으로 나누어 재귀적으로 다시 퀵 정렬을 처리한다.
    • 장점 : 평균 시간 복잡도 nlog n
    • 단점 : 피봇이 최솟값이나 최댓값으로만 잡힐 경우 최악의 시간 복잡도 n^2
  • 병합 정렬
    데이터 집합을 더 이상 나눌 수 없는 단위까지 나눈 후에 다시 두 집합 단위로 정렬하여 정복하는 정렬이다. 예로 8개의 데이터가 있을 경우 1,2번 3,4번, 5,6번 7,8번을 정렬하여 4개의 집합으로 만든다. 4개 -> 2개 -> 1개로 다시 정렬된 데이터가 모이게 된다. 정렬된 집합을 저장할 새로운 공간을 확보하여 두 집합의 첫번째 데이터부터 차례로 비교하여 더 작은 쪽을 먼저 새 집합에 저장하고 저장된 데이터의 다음 데이터를 차례로 비교한다.
    • 장점 : 항상 시간 복잡도 nlog n
    • 단점 : 새로운 정렬된 데이터를 저장할 별도의 메모리 공간이 필요