자료구조

연결리스트

• 어레이
  • 파이썬의 리스트 구조 [1,2,3,4,5,6]
  • 접근은 쉬우나 삽입,삭제가 어렵다
  • 만약에 [1,2,3]에서 1,2 사이에 4를 넣기 위해서는 먼저 2와 3을 뺀 후 4를 넣고 다시 2와 3을 넣어야 된다. 이렇게 사이에 값을 넣거나 빼기 위해서는 뒤에 있는 값들을 뺀 후 값을 처리하고 다시 뺀 값은 넣어야 한다.
• 연결리스트
  • [1]-> [2]-> [3]-> [4]-> [5]-> [6] 식의 구조로 앞에 있는 값이 다음 값의 위치를 가르키는 구조
  • 순서대로 접근 하면 쉬우나 만약에 6에 접근하려면 1번 부터 순서대로 접근 해야 한다
  • 삽입 및 삭제가 쉬운 편이다. 만약에 [1]->[2]->[3] 이 있는 경우에 4를 1다음으로 삽입하려면 [1]->[4]->[2]->[3]으로 하면 되서 [1]이 가르키는 방향을 [4]로 가르키고 [4]가 [2]를 가르키게 하면 된다

 

스택

• 선입 후출의 형태
• 먼저 들어간 값이 마지막 나오는 형태의 자료구조

 

큐

• 선입선출의 형태
• 먼저 들어간 값이 먼저 나오는 형태의 자료구조

 

해시테이블

• 해시함수를 이용하여 키 값이 매핑 되는 자료구조
• 해시함수란?
  • 임의값을 고정된 크기의 값으로 매핑되도록 하는 함수
  • 간단 예로는 나머지를 반환하는 함수를 생각하면 쉽다( 1 % 2 = 1, 2 % 2 = 0, 3 % 2= 1....)
• 충돌
  • 해시함수를 사용하게 되면 임의 값들이 하나의 값과 매핑되게 되어 있다. 위의 나머지를 반환하는 함수를 보더라고 1과 3이 같은 값이 되는 걸 확인 할 수 있다
  • 충돌이 발생할때 체이닝(Chaining), 오픈 어드레싱(Open Addressing) 방식으로 충돌 된 값들은 저장 할 수 있다
  • 체이닝(Chaining)
    • 연결리스트 처럼 연결 방식으로 충돌 된 값을 저장하는 방식
  • 오픈 어드레싱(Open Addressing)
    • 가까운 빈공간은 찾아서 값을 저장하는 방식

 

 

트리

• 컴퓨터의 디렉토리 구성으로 계층적인 이루어진 자료구조
• 트리에는 나오는 용어는 외워둘 필요가 있다
  • Node: 트리에서 데이터를 저장하는 기본 요소
  • Root Node: 트리 맨 위에 있는 노드
  • Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
  • Parent Node: 어떤 노드의 상위 레벨에 연결된 노드
  • Child Node: 어떤 노드의 하위 레벨에 연결된 노드
  • Leaf Node(Terminal Node): Child Node가 하나도 없는 노드
  • Sibling: 동일한 Parent Node를 가진 노드
  • Depth: 트리에서 Node가 가질 수 있는 최대 Level
• 이진트리와 완전이진트리
  • 이진트리
    • 각 노드가 최대 두 개의 자식을 가진형태의 트리
  • 완전이진트리
    • 이진트리 형태에서 노드들이 왼쪽 노드부터 차례대로 있는 형태의 트리