자료구조

배열

• 생성 시, 고정된 크기를 가진다.
  • 크기를 변경하기 어렵고, 공간을 효율적으로 사용하려면, 크기를 미리 예측해야 한다.
• 연속된 메모리 공간에 요소들이 저장된다.
  • 인덱스를 통해 빠른접근이 가능.

연결리스트

• 데이터를 감싼 노드의 포인터를 가리켜서 연결하여 공간적인 효율성을 극대화시킨 자료구조.
• 삽입 및 삭제가 용이하다.
• 순차적으로 탐색해야 하므로 성능이 떨어진다.
• 배열에 비해 구현이 복잡할 수 있다.

스택

• 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 특징(LIFO, Last In First Out)을 가진 자료구조.
• 재귀적인 함수, 웹 브라우저의 뒤로 가기, 실행 취소, 수식 괄호 검사 등에 주로 쓰인다.

큐

• 먼저 들어간 데이터가 먼저 나오는 특징(FIFO, First In First Out)을 가진 자료구조.
• 프린터 대기열, 작업 스케줄링, 캐싱, 너비 우선 탐색(BFS)에 자주 쓰인다.

트리

• 계층적인 자료를 표현하는 데 이용되는 자료구조.
• 노드와 엣지로 구성.
  • 루트 노드
    • 가장 상위에 있는 노드, 부모 노드가 없음.
  • 내부 노드
    • 루트를 제외한 모든 노드는 하나의 부모 노드를 가짐.
    • 각 노드는 0개 이상의 자식 노드를 가짐.
  • 리프 노드
    • 자식 노드가 없는 노드.
• 깊이
  • 루트 노드에서 특정 노드까지의 경로 길이
• 파일 시스템 구조(디렉토리), 데이터베이스 인덱싱 등에 쓰인다.

그래프

• 객체 간의 복잡한 관계를 나타내기 위해 사용되는 자료구조.
• 정점(Vertex)과 간선(Edge)의 집합으로 구성.
  • 정점
    • 그래프의 개체
  • 간선
    • 정점 간의 연결 관계
• 순서가 없다.
• 방향성이 있는 그래프를 방향 그래프, 방향성이 없는 그래프를 무방향 그래프.
• 지도 및 GPS, 소셜 네트워크, 컴퓨터 네트워크 등에 쓰인다.

---

알고리즘

주로 사용되는 알고리즘에는 정렬과 탐색이 있다.

정렬

• 버블 정렬(Bubble Sort)

  • 인접한 두 원소를 비교하여 정렬해 나가는 방식.
  • 최악, 최선의 경우 모두 $O(N^2)$의 시간 복잡도.
  • 작은 데이터셋이나 거의 정렬된 데이터의 경우, 사용하기 쉽고 충분히 빠른 성능.

• 선택 정렬(Selection Sort)

  • 주어진 배열에서 가장 작은 값을 찾아 배열의 맨 앞에 위치한 값과 교환하는 과정을 반복하는 방식.

• 삽입 정렬(Insertion Sort)

  • 각 숫자를 적절한 위치에 삽입하는 방식으로 작동하며, 전체 배열에 대해 반복하는 방식.

• 병합 정렬(Merge Sort)

  • 분할 정복 알고리즘에 기반한 효율적인 정렬 방법.
  • 입력 데이터를 점점 작은 부분으로 나누고, 나눈 부분들을 정렬한 다음, 다시 병함하여 원래의 순서대로 정렬된 전체 데이터를 얻는 과정.

탐색

• 이진 탐색(Binary Search)

  • 정렬된 배열이나 리스트에서 특정한 값을 찾는 효율적인 알고리즘.
  • 매 단계에서 배열이나 리스트의 중간 요소와, 찾고자 하는 요소의 값을 비교하면서 범위를 좁혀나가며 찾는 방식.

• 깊이 우선 탐색(DFS)

  • 그래프나 트리와 같은 자료구조를 탐색하는 알고리즘.
  • 시작 정점에서 가능한 한 깊이 있는 정점을 우선으로 탐색하고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아와서 다른 루트를 탐색하는 방식.
  • 재귀 호출을 이용한 구현, 스택을 이용한 구현이 일반적.

• 너비 우선 탐색(BFS)

  • 시작 정점에서 시작해서 가장 가까운 정점을 먼저 방문한 다음, 그 다음 거리들의 정점들을 방문하는 방식으로 진행.
  • 동일한 거리에 있는 정점들을 동일한 레벨로 생각하고 너비를 우선적으로 탐색하는 방식.
  • 주로 큐(Queue)를 사용하여 구현.