자료구조 06. 선형구조, 비선형구조

2019.04.12 TIL

(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)

# 질문에 답하기

1. 자료구조

자료구조에 대한 정의는 너무나도 많다.
그 중에 가장 마음에 와닿는 글이 있어서 정리를 해본다.

" 프로그래밍은 결국 데이터를 다루는 방법입니다. 데이터를 입력받고, 데이터를 처리하여 도출된 데이터를 출력합니다.

자료구조는 데이터를 입력 받아 어떻게 저장하는 지에 대한 학문입니다.
데이터를 어떻게 저장하는지(입력), 어떻게 찾는지(탐색), 어떻게 지우는지(삭제)가
자료구조의 종류에 따라 천차만별입니다.

그럼, 어떤 자료구조를 언제 사용해야 할까요? 이는 결국 성능과 효율적인 메모리 사용에 달려있습니다.
프로그래머가 처한 상황에서 가장 뛰어난 성능을 내고 또 가장 효율적으로 메모를 사용한다면 그 자료구조를 선택하면 됩니다.

알고리즘은 방법론입니다. 많은 알고리즘이 있지만, 자료구조에 연관된 알고리즘만 언급하겠습니다.
자료구조와 알고리즘은 매우 밀접한 연관을 가지고 있습니다. 위에 언급한 삽입 정렬과 병합 정렬은 엄밀히 말해 알고리즘입니다. 하지만 자료구조를 배울 때 반드시 마주치게 되지요. 알고리즘은 자료구조를 구현하는 방법이라고 보시면 될 것 같습니다. "

“프로그래머가 갖추어야 할 ‘기본’은 무엇인가?” 넥슨 개발자 컨퍼런스(NDC) 참관 후기 | 패스트캠퍼스

자료구조의 구성

1. insert : 어떻게 데이터를 넣을 것인가?
2. search : 어떻게 데이터를 찾을 것인가?
3. delete : 어떻게 데이터를 삭제할 것인가?

자료구조의 분류

• 단순구조 : 프로그래밍에서 사용되는 기본 데이터 타입
• 선형구조 : 저장되는 자료의 전후관계가 1:1 (리스트, 스택, 큐 등)
• 비선형구조 : 데이터 항목 사이의 관계가 1:n 또는 n:m (트리, 그래프 등)
• 파일구조 : 서로 관련된 필드들로 구성된 레코드의 집합인 파일에 대한 자료구조
• 출처 : 강의노트 17. 알고리즘, 자료구조 개요 · 초보몽키의 개발공부로그

선형구조(배열과 linked list 그리고 스택과 큐)

1. 배열(array)
   1. 같은 자료형의 변수를 모아 놓은 것
   2. 인덱싱 활용 가능(search)
      1. 검색으로 배열을 이길 수는 없다.
   3. 데이터가 군집화 되어있다.
      1. 캐시히트의 가능성이 높다.
   4. 검색속도가 그 어떤 자료구조보다 빠르다.O(1)
   5. 데이터의 삽입과 삭제가 느리다. 최악의 경우 O(n)
      1. 맨 앞에 데이터를 삽입하게 되면 모든 데이터를 복사해서 한칸씩 다 옴겨야 한다.
      2. 배열은 공백을 인정하지 않는다. O(n)
2. Linked list ( 데이터의 삽입과 삭제가 많고, 검색이 별로 없을 때)
   1. 검색 속도 최악 O(n)
   2. 데이터의 삽입과 삭제는 O(1)
      1. 어디든 데이터를 놓고 연결만 해주면 된다.
   3. 데이터가 흩어져 있다.
      1. 캐시히트의 가능성이 굉장히 떨어진다. -> 캐시미스 발생
      2. 페이지폴트까지 날수도 있다.
   4. 미리 힙을 주고 흩어져 있는 문제를 해결할 수 있다.
      1. 다이나믹 힙
3. Stack
   1. 무언가를 쌓는다라는 의미를 가진 자료구조이다.
   2. LIFO(Last in, First out) : 후입선출
4. Queue
   1. 우리의 일반적인 줄서기
   2. FIFO(First in, First out) : 선입선출

만약에 배열과 Linked list 2개 다 사용가능한 상황이면 무조건 배열을 쓴다.
배열은 메모리의 스택에 할당해서 사용한다.

파이썬에서의 list

파이썬의 list는 배열과 다르다.
파이썬은 포인터 배열이다.
포인터는 배열처럼 일렬로 되어 있으나, [1,2,3]
1은 class int 여서 상수객체이기 때문에 4바이트보다 훨씬 크다.

파이썬의 리스트는 파이썬에서는 같은 자료형의 변수를 모아 놓은 것이 아니다.
파이썬에는 배열이라는 자료구조가 없는 것이다. 즉 지원하지 않는다.

예시

얕은 복사

>>>    #얕은 복사
>>>    li = [1,2,3,4]
>>>    li3 = li.copy() # or copy.copy(li)도 가능
>>>    li3     #[1,2,3,4]
>>>    li3.append(5)
>>>    li3      #[1,2,3,4,5]
>>>    li       #[1,2,3,4]
>>>

위의 내용을 이해하기 위해서는 단순히 객체가 [1,2,3,4]의 형태처럼 메모리에 올라가 있다고 생각하면 안된다.
실제적으로 파이썬에서 list를 생성한다고 하더라도 모두 모여서 메모리에 올라가지 않는다. [* , * , * , * ]와 같은 형태로 생성되어 첫번째 * 은 1을 가르키고 두 번째 * 은 2를 가르키고 이런 형식이다. 얕은 복사는 [* , * , * , * ]를 복사해 온 것이다. 따라서 li3는 li의 [* , * , * , * ]를 복사해온 것이다. 따라서 li3에서 append를 통해 새로운 요소를 추가하게 되면 li3의 [* , * , * , * ]가 [* , * , * , * , * ]가 되어서 마지막 * 가 새로운 요소를 가르키게 된다. 따라서 li3가 변경되더라도 li는 변경되지 않는다.
하지만 여기에서도 예외는 있다.

>>>    #얕은 복사
>>>    li = [1,2,3,[4,5]]
>>>    li3 = li.copy()
>>>    li3    #[1,2,3,[4,5]]
>>>    li3[3].append(6)
>>>    li3    # [1,2,3,[4,5,6]]
>>>    li     # [1,2,3,[4,5,6]]
>>>

위에서 보면 알 수 있듯이 원래 얕은 복사에서라면 li3를 바꾼다고 해서 li가 바뀌어서는 안된다. 하지만 li는 변경되었다. 그렇다면 li3는 왜 변경되었을까? 위에 언급한대로 li3는 li의 [* , * , * , * ]를 복사해 온 것이다. 위에 예시에서 마지막 * 은 3번째 인덱스 [4,5]을 가르키고 있다. li3와 li 모두 [4,5]을 가르키고 있는 것이다. 따라서 li3를 통해 [4,5]를 변경하게 되면 마지막 *가 가르키는 것이 변경되는 것이므로 li 역시 변경되게 된다.(즉 li와 li3의 내부리스트는 각은 객체를 참조하기 떄문이다.)

이러한 것을 맡기 위해서는 깊은 복사가 필요하다.

깊은 복사

>>>    import copy     #deepcopy를 위해서는 copy를 import 해주어야 한다.
>>>    li = [1,2,3,4]
>>>    li4 = copy.deepcopy(li)
>>>    li4        # [1,2,3,4]
>>>    li4.append(5)
>>>    li4        # [1,2,3,4,5]
>>>    li         # [1,2,3,4]
>>>    li = [1,2,3,[4,5]]
>>>    li4 = copy.deepcopy(li)
>>>    li4        # [1,2,3,[4,5]]
>>>    li4[3].append(6)
>>>    li4        # [1,2,3,[4,5,6]]
>>>    li         # [1,2,3,[4,5]]

깊은 복사를 통해서는 완전히 동일한 새로운 객체를 생성하는 것이므로 li4에 어떤 요소를 추가해도 li는 전혀 영향을 받지 않는다. 따라서 상황에 맡게 단순 객체 복사, 얕은 복사, 깊은 복사를 사용해야 한다.

참고 : 2019_03_23_TIL(깊은 복사 얕은 복사)

비선형구조

트리

• connected acyclic graph
  • 사이클(순환)이 없는 연결된 그래프
  • 루트노드(root)를 반드시 가진다.
  • 트리를 구성하는 노드 간에 단순 경로가 반드시 존재한다.
    • 단순경로란 지나왔던 접점을 다시 지나지 않는 경로
    • 한 개의 노드에서 다른 한개의 노드를 선택하면 단순 경로가 항상 존재
  • 루트 노드를 제외한 나버지 노드들은 분리집합으로 분할이 가능하며 이 집합들은 각각 하나의 트리를 구성한다(재귀적 정의)

트리 용어 정리

부모노드와 왼쪽 자식노드 , 오른쪽 자식노드로 나누어짐

• 루트노드 : 뒤로 뒤집어서 보면 여기서부터 쭉 퍼져나가므로 root(뿌리) 노드이다. 트리의 시작점
• 에지 : 노드를 연결하는 선
• 리프노드 : 자식노드가 하나도 없는 노드
• 인터널노드 : 자식노드가 하나라도 있는 노드
• 차수 : 자식노드의 갯수
• 트리의 차수 : 트리에 있는 노드들 중 최대 차수

이진 트리

• 어떤 노드의 자식 노드의 수가 최대 2개인 트리

이진 트리의 종류

• 포화 이진 트리
  • 모든 레벨이 꽉 차 있다.
  • 즉 모든 노드들의 2개의 자식노드를 가지고 있다.(리프노드 제외)

• 완전 이진 트리
  • 트리의 노드가 위에서 아래로, 왼쪽에서 오른쪽으로 채워지는 트리
  • 가장 높은 레벨 단계에서 항상 왼쪽에서 오른쪽으로 채워져 있어야 한다.

트리의 순회는 다음 장에서 추가로 공부한다!

• 순회란 트리의 모든 노드를 중복하지 않으면서 방문하는 것을 말하며, 데이터를 찾고, 저장하고, 삭제하는데 쓰인다.