자료구조와 알고리즘

자료구조

• 데이터를 효율적으로 조직화하고 저장하며, 이를 효과적으로 사용하기 위한 방법이나 기술의 집합을 나타낸다.
• 데이터를 구조화하는 것은 데이터를 삽입, 삭제, 검색 및 정렬하는데 효율적인 방법을 찾는 과정을 의미한다.
• 논리적인 관점 : 데이터 간의 관계, 조작 방법, 삽입, 및 규칙 등을 정의한다. 배열, 리스트, 스택, 큐, 트리, 그래프 등이 있다.
• 물리적인 관점 : 데이터를 메모리에 실제로 어떻게 저장하고 구성하는지를 나타낸다. 배열은 연속된 메모리 위치에 원소를 저장하고, 연결 리스트는 떨어진 위치에 있는 노드들이 서로 링크로 연결되어 있다.
  • 배열 (Array) : 동일한 자료형의 원소들이 연속된 메모리 위치에 저장된 자료구조다.
  • 연결 리스트 (Linked-List) : 각 노드가 데이터와 다음 노드를 가리키는 링크로 이루어진 자료구조다.
  • 스택 (Stack) : 후입선출(LIFO : Last in First Out) 원칙에 따라 데이터를 저장하는 자료구조다.
  • 큐 (Queue) : 선입선출(FIFO : First In First Out) 원칙에 따라 데이터를 저장하는 자료구조다.
  • 트리 (Tree) : 계층적인 구조로 이루어진 자료구조로, 각 노드는 하나의 부모와 여러 자식 노드를 가질 수 있다.
  • 해시 테이블 (Hash Table) : 해시 함수를 사용하여 데이터를 효율적으로 검색할 수 있는 자료구조다.

자료구조

 

알고리즘(Algorithm)

• 주어진 문제를 해결하기 위한 단계적인 절차나 계산 과정을 나타내는 일련의 규칙이나 명령의 집합이다.
• 데이터를 처리하고 조작하는데 사용되는 계산 과정을 설명하는데 활용된다.

알고리즘의 선택

• 정확성 : 알고리즘은 주어진 입력에 대한 올바른 결과를 제공해아한다.
• 효율성 : 알고리즘은 가능한 빠르고 효율적으로 동작해야한다. 이는 주어진 자원을 효과적으로 활용해야한다.
• 입력과 출력 : 알고리즘은 입력을 받아들이고 원하는 결과를 출력해야 한다.
• 유니버설리티 : 알고리즘은 특정한 문제뿐만 아니라 유사한 다양한 문제에 대해서도 적용 가능해야한다.
• 모듈화 : 알고리즘은 모듈화 되어 있어서 수정이나 확장이 쉽게 이루어질 수 있어야 한다.

알고리즘 분석

분석은 알고리즘을 정확히 선택하기 위한 방법이다.

시간 vs 공간(자원) - 일반적으로는 공간 보다는 시간을 중요시 여긴다.

• 경험적 분석 (Empirical Analysis)
  
  • 실제 코드를 작성 후, 실행하여 시간을 측정
  • 데이터 수를 다르게 하여 함수 관계를 유추
• 수학적 분석 (Mathematical Analysis)
  • 알고리즘 자체를 가지고 수학적인 분석을 한다.

---

• 최악의 경우(Worst case)
  • 가장 많은 시간과 자원을 필요로 하는 경우
• 최선의 경우(Best case)
  • 가장 적은 시간과 자원만이 소요되는 경우

---

• 시간 복잡도
• 빅 오(O) 표기법 - (Big-Oh Notation)
  • 알고리즘의 성능을 대략적으로 표현하며 알고리즘 간의 성능 비교 및 알고리즘의 효율성을 평가하는데 사용된다.

출처 : Algorithm Analysis & Time Complexity Simplified

 

O(1) (상수)	상수 시간 복잡도. 입력 크기에 상관 없이 일정한 실행 시간을 가진다. 해쉬검색 알고리즘 등
O(log N)	로그 시간 복잡도. 주로 반씩 나눠가며 검색하는 알고리즘에서 나타난다 이진검색, 이진트리검색 등
O(N)	선형 시간 복잡도. 입력 크기에 비례하여 선형적으로 증가하는 경우 선형 검색 등
O(N log N)	선형 로그 시간 복잡도. 대부분의 효율적인 정렬 알고리즘에 사용된다. 병합정렬 등
O(N^2)	제곱 시간 복잡도. 반복문이 중첩되어 있는 경우 삽입정렬, 선택정렬 등
O(2^N)	지수 시간 복잡도 입력 크기에 대해 지수적으로 증가하는 경우
O(N!)	팩토리얼 형태

 

맨 위에서부터 시간 복잡도가 낮고 빠르고, 아래로 갈 수록 시간 복잡도가 높고 느려진다.

제한시간 안에 올바른 output을 출력하려면 시간 복잡도를 낮춰야 한다.

 

알고리즘의 유형

• 탐색 알고리즘
  • 문제 공간을 탐색하여 원하는 조건을 만족하는 해를 찾는 알고리즘이다.
  • 선형 검색, 이진 검색, 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) 등
• 정렬 알고리즘
  • 주어진 데이터를 정해진 순서로 나열하는 알고리즘이다.
  • 버블 정렬, 삽입 정렬, 선택 정렬, 합병 정렬, 퀵 정렬 등
• 동적 계획법 (Dynamic Programming)
  • 문제를 작은 부분 문제로 나누어 해결하고, 그 결과를 저장하여 중복 계산을 방지하는 알고리즘이다.
  • 피보나치 수열 계산, 최단 경로 찾기 (Dijkstra 알고리즘)
• 탐욕 알고리즘 (Greedy Algorithm)
  • 각 단계에서 현재 상태에서 가장 좋아 보이는 선택을 하면서 최적해를 찾는 알고리즘이다.
  • 최소 신장 트리(Kruskal 알고리즘), 최단 경로 찾기 등
• 분할 정복 알고리즘
  • 문제를 둘 이상의 부분 문제로 나누고, 각 부분 문제를 독립적으로 해결한 후 결과를 합치는 알고리즘이다.
  • 합병정렬, 퀵 정렬 등
• 그래프 알고리즘
  • 그래프에서 정점과 간선의 관계를 분석하고 문제를 해결하는 알고리즘이다.
  • 최단 경로찾기, 최소 신장 트리 등
• 문자열 알고리즘
  • 문자열 데이터에 대한 처리를 위한 알고리즘이다.
  • 문자열 검색(KMP 알고리즘), 문자열 매칭(보이어-무어 알고리즘) 등

 

알고리즘의 종류

• 검색 알고리즘 : 주어진 데이터 집합에서 특정 값을 찾거나 조건에 맞는 원소를 찾는 알고리즘을 말한다.
  • 선형 검색
    • 동작 : 리스트나 배열을 처음부터 끝까지 순회하면서 찾고자 하는 원소를 찾는다.
    • 시간복잡도 : O(N) - 최악의 경우에는 리스트나 배열의 모든 요소를 확인하야한다.
  • 이진검색
    • 동작 : 정렬된 리스트나 배열에서 중간값을 선택하여 찾고자 하는 값과 비교하고, 찾고자 하는 값이 중간값보다 작으면 왼쪽 반을, 크면 오른쪽 반을 계속해서 탐색한다.
    • 시간복잡도 : O(log N) - 리스트나 배열이 정렬되어 있어야 한다.
  • 해시검색
    • 동작 : 해시 함수를 사용하여 값을 해시값으로 매핑하고, 해당 해시값을 인덱스로 사용하여 찾는다.
    • 시간복잡도 : 평균적으로 O(1), 최악의 경우 충돌이 발생할 경우 O(N)까지 증가할 수 있다.
  • 보간검색
    • 동작 : 정렬된 리스트에서 찾고자 하는 값을 현재 찾고 있는 범위에 비례하여 탐색한다.
    • 값의 분포가 균등하다고 가정할 때 사용된다.
    • 시간복잡도 : 평균적으로 O(log log N), 최악의 경우 O(N) - 이진 검색보다 빠를 수 있지만, 데이터의 분포에 따라 성능이 달라진다.
  • 트리 기반 검색 알고리즘
    • 동작 : 트리 구조를 사용하여 데이터를 저장하고 검색한다.
    • 이진 트리 검색, AVL 트리 검색 등이 있다.
    • 시간복잡도 : 트리의 높이에 따라 다르며, 평균적으로 O(log N) 이다.
• 재귀 알고리즘
• 팩토리얼 계산
  • 알고리즘 : n! 은 n부터 1까지의 모든 양의 정수를 곱한 값이며, n! = n*(n-1)*...*1입니다. -> 재귀적으로 계산 가능

def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n-1)

 

• 피보나치 수열
  • 알고리즘 : 피보나치 수열은 각 항이 바로 앞의 두 항의 합인 수열이다.
  • F(n) = F(n-1) + F(n-1)

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

• 하노이의 탑
  • 알고리즘 : 하노이의 탑은 크기가 다른 원반들이 세 개의 기둥 중 하나에서 다른 기둥으로 옮겨가는 문제이다.

def hanoi(n, source, target, auxiliary):
    if n > 0:
        // n-1개의 원반을 보조 기둥으로 옮김
        hanoi(n-1, source, auxiliary, target)
        // 남은 1개의 원반을 목표 기둥으로 옮김
        print(f"Move disk {n} from {source} to {target}")
        // 보조 기둥에 있는 n-1개의 원반을 목표 기둥으로 옮김
        hanoi(n-1, auxiliary, target, source)

• 정렬 알고리즘
  • 버블 정렬
    • 인접한 두 원소를 비교하여 순서가 맞지 않으면 교환하는 방식으로 정렬하는 알고리즘이다.
    • 시간 복잡도 : O(N^2)
  • 삽입 정렬
    • 각 원소를 적절한 위치에 삽입하는 방식으로 정렬하는 알고리즘이다.
    • 시간 복잡도 : O(N^2)
  • 선택 정렬
    • 주어진 리스트에서 최솟값을 선택하여 정렬하는 알고리즘이다.
    • 시간복잡도 : O(N^2)
  • 합병 정렬
    • 분할 정복(divide & conquer) 기법을 사용하여 리스트를 두개의 작은 리스트로 나눈 다음, 각각을 정렬하고 합치는 방식으로 정렬하는 알고리즘이다.
    • 시간복잡도 : O(N log N)
  • 퀵 정렬
    • 분할 정복 기법을 사용하며, pivot(피벗)을 기준으로 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 분할하여 정렬하는 알고리즘이다. 
    • 시간복잡도 : O(N log N) 평균적으로, 최악의 경우에는 O(N^2)