1강 알고리즘 학습에 앞서서

알고리즘을 배우는 이유?

잘 알려진 특정 문제를 통해 알고리즘의 설계 및 분석 방법 습득
→ 컴퓨터 기반 문제 해결 방법에 대해 체계적으로 생각하는 훈련
→ 주어진 문제에 대한 지적 추상화 능력 및 통찰력 향상

알고리즘의 필요성

알고리즘이란 문제를 해결하기 위한 일련의 단계적인 효율적인 처리 과정 레시피 같은 것이다.

기본 자료구조

• 자료구조란?
  컴퓨터에서 데이터들이 존재할 때, 데이터 사이의 논리적 관계를 표현하고 조직화하는 방법

• 프로그램 ← 자료구조 + 알고리즘
  자료구조에 대한 고려 없는 효율적인 알고리즘의 선택, 알고리즘에 대한 고려없는 효율적인 자료구조의 선택은 무의미하다.

모든 자료형은 배열이나 연결 리스트를 사용하여 구현한다.

1. 선형 자료구조 (데이터를 논리적인 관계에 따라 한줄로 나열할 수 있다)

   1. 배열 (index, value) 의 쌍의 집합

      • 같은 자료형을 갖는 여러 개의 데이터를 하나의 변수로 모아 놓은 데이터의 집합체
      • 원소에 접근하기 위해 인덱스를 사용한다. → 내가 원하는 데이터에 바로 접근이 가능하다.
      • 논리적인 순서와 물리적인 순서(실제 컴퓨터 메모리 내에서 표현되는 방식)가 똑같다. → 순서를 항상 유지하는 것이 중요하다!
      • 데이터 삽입/삭제 → 자료의 이동이 발생하기 때문에 양이 많아지는 경우엔 과부하가 올 수 있다.
      • 1차원 배열, 2차원 배열, 3차원 배열

   2. 연결 리스트

      • 논리적인 순서와 물리적인 순서가 같지 않다. → 링크 필드의 값으로 순서를 보장해준다.
      • 원소에 접근하기 위해서는 맨 앞에서부터 순차적으로 접근해야 한다. → 데이터가 많은 경우 데이터를 찾기 어렵다.
      • 데이터 삽입/삭제 → 링크 필드를 조작하면 되기 때문에 쉽게 삽입 및 삭제가 가능하다.

      • 단일 연결 리스트: 링크필드가 1개 → 단방향

        단일 원형 연결 리스트: 맨 뒤의 원소의 링크필드가 맨 앞의 주소를 바라보며 원형을 이루고 있다.

        이중 연결 리스트: 링크 필드가 2개로 하나는 앞에 필드, 다른 하나는 뒤의 필드를 바라본다.

        이중 원형 연결 리스트: 양쪽 방향으로 원형을 이루고 있다.

   3. 스택

      • 데이터의 삽입(push)과 삭제(pop)가 한쪽 끝에서만 이루어지는 자료형이다.
      • 후입선출 (나중에 들어온 데이터가 먼저 나간다)
      • top 변수를 통해 제일 위에 있는 데이터 표시

   4. 큐

      • 데이터의 삽입과 삭제가 나뉘어져 있는 자료형이다.
      • 선입선출 (먼저 들어간 데이터가 먼저 나온다)
      • front/head, rear/tail 변수를 통해 데이터의 끝과 뒤를 표시

2. 비선형 자료구조 (데이터를 한줄로 나열할 수 없다)

   1. 트리

      • 하나 이상의 노드로 구성된 유한집합 T
      • 조건
        T의 원소 가운데 단 하나의 루트 노드가 존재한다
        루트 노드를 제외한 나머지 노드는 n개의 서로 분리된 부분집합으로 나누어지며 각 T(서브트리)는 트리가 된다.
      • 용어
        차수: 노드의 차수(각 노드가 가지고 있는 가지의 갯수), 트리의 차수(모든 노드 차수 중에서 가장 큰 차수)
        리프노드(단말노드): 노드의 차수가 0인 것
        비단말노드: 리프노드를 제외한 나머지 노드
        부모노드, 자식노드, 형제노드: 한 노드에서 봤을 때 각 위치에 따라 불린다.
        조상노드, 후손노드
        레벨: 어떠한 노드까지 루트 노드로부터의 거리
        높이(깊이): 해당 트리의 높이(맨 마지막 노드의 레벨+1)
        숲: 루트 노드를 없애면 몇개의 덩어리(서브트리)로 나뉘어 지는지
        
      • 이진트리
        각 노드의 차수가 2 이하인 순서트리(각 노드의 위치(순서)가 중요한 트리)
        노드가 아무 것도 없는 것(공백)도 이진트리이다.
        
        • 특징
          레벨 i에서 최대 노드의 갯수 → 2 ** i
          높이 h인 이진 트리의 최대 노드의 개수 → 2 ** h -1
          단말 노드의 수 = 차수가 2인 노드의 수 + 1
        • 종류
          포화 이진트리: 최대 노드의 갯수로 있는 트리
          완전 이진트리: 맨 마지막 노드를 제외한 윗부분이 포화 이진트리인 것
          전 이진트리: 각 노드의 차수가 0 또는 2인 트리
          균형 이진트리: 왼쪽 서브트리와 오른쪽 서브트리 높이 차이가 1 이하인 것
          경사 이진트리: 리프노드 외 모든 노드의 자식이 1개
          
        • 트리 구현

   2. 그래프

      • G = (V, E)
        그래프란 정점의 집합(V)과 간선의 집합(E)을 모아놓은 것이다.
      • 간선이 방향에 있는지에 따라 무방향 그래프, 방향 그래프로 나뉜다.
        무방향 그래프: (1, 2) = (2, 1)
        방향 그래프: <1, 2> ≠ <2, 1>
      • 간선에 가중치가 주어진 그래프는 가중 그래프이다.
      • 용어
        인접, 부수
        부분 그래프
        경로, 경로의 길이
        차수
        단순 경로, 사이클, 루프
        연결
        
      • 구현
        
        1. 인접 행렬(배열로 구현)
           무한대: 간선이 없는 경우
           가중치가 없으면 0 또는 1로 표현한다.
        2. 인접 리스트(연결리스트로 구현)