경일게임아카데미 멀티 디바이스 메타버스 플랫폼 개발자 양성과정 20220509 2022/04/04~2022/12/13

경일 메타버스 20220509 6주차 1일 수업내용. 자료구조와 알고리즘, 재귀 함수, 자료구조
자료구조의 내용은 시간 부족, 집중력 부족 등의 이유로 제대로 숙지를 못하였으니 후에 자습 복습 예습이 필요하다고 생각한다.

자료
https://docs.google.com/document/d/1lAZizYg8AjfkM-UqPlmkseWIs8Fagvqpo307hQA3xl4/edit

재귀

• 자료구조 : 데이터의 표현 및 저장 방법, 데이터를 조직하는 방법

• 재귀 : 함수가 자신을 호출하는 것.

  • 기저 조건(Base Condition) : 재귀를 중단시키는 조건

  • 재귀 조건(Recursion Condition) : 기저 조건까지 수렴할 동안 반복시키는 조건

• 재귀의 사용 이유
  문제에 따라 전체를 한 번에 해결하기보다 같은 유형의 하위 작업으로 분할하여 작은 문제부터 해결하는 방법이 효율적일 수 있기 때문이다.

  • 분할 정복법(divide & conquer)

• 재귀의 단점
  함수 호출에 따른 오버헤드가 있다는 것이다. 재귀가 너무 깊어지면 그만큼 호출 스택의 공간을 더 많이 사용하게 되고, 끝내는 스택 오버플로가 발생할 수 있다.

• 오버헤드(overhead) : 어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 · 메모리 등.

• 스택 오버플로(stack overflow) : 스택이 가용할 수 있는 공간을 벗어나는 것.

• 재귀의 팁

  1. 반복할 내용과 관련된 변수는 매개변수로 가져가야 한다.

  2. 점화식을 사용한다.

  3. 호출 등의 순서를 조정하는 것으로 다양한 것이 가능하다.

  4. 재귀를 이용해서 어떤 값을 올려야 할 때 전역 변수를 이용하면 구현 복잡도가 내려감.

     4-1. 다만, 멀티 스레드 상황에서 데이터 경쟁이 일어날 수 있다. 이를 방지하기 위해 반환값을 이용할 줄도 알아야 한다.

자료구조

• 자료구조는 크게 선형 구조(linear structure)와 비선형 구조(non-linear structure)로 나눌 수 있으며, 선형 구조에는 리스트, 스택, 큐가 있고, 비선형 구조에는 그래프와 트리가 있다. 또, 대부분의 자료구조는 네 가지 기본 방법을 사용하며 이를 연산이라고 한다.

  • 읽기 : 자료구조 내 특정 위치를 찾아보는 것이다.

  • 검색 : 자료구조 내 특정 값을 찾는 것이다.

  • 삽입 : 자료구조에 새로운 값을 추가하는 것이다.

  • 삭제 : 자료구조 내 특정 값을 삭제하는 것이다.

• 자료구조를 구현하는 방법에는 크게 순차 자료구조(contiguous data structure)와 연결 자료구조(linked data structure)가 있다.

  • 순차 자료구조는 구현할 자료들을 논리적인 순서대로 메모리에 연속하여 저장하는 구현 방식
  • 연결 자료구조는 노드라는 여러 개의 메모리 청크에 데이터를 저장하며, 이를 연결하여 구현하는 방식이다.
  • 순차 자료구조는 배열을 이용하고, 연결 자료구조는 포인터를 이용한다. 둘을 비교하면 아래와 같다.
    

• 지역성(locality) : CPU가 기억장치의 특정 부분에 위치한 데이터나 프로그램 코드를 집중적으로 액세스하는 현상이다.

알고리즘의 분석

• 알고리즘 : 문제를 해결하기 위한 절차.

• 문제를 해결하는 방법에는 여러가지가 존재할 수 있으며, 우리는 이 중 최선을 선택해야 한다. 다시 말해 알고리즘을 분석하고 비교할 줄 알아야 한다. 이는 알고리즘의 자원(resource)*의 사용량을 분석하는 것이며, 자원을 적게 사용할 수록 효율적인 알고리즘이라고 할 수 있다.

• 자원

  • 실행 시간
  • 메모리 사용량
  • 등등

시간 복잡도

• 알고리즘의 분석에 있어 가장 중요한 부분은 실행 시간이다.

• 알고리즘의 실제 실행은 하드웨어 및 소프트웨어 환경에 따라 천차만별이므로 단순 측정으로는 실행 시간을 분석할 수 없다.

• 시간 복잡도 : 하드웨어와 소프트웨어 환경을 배제한 객관적인 지표

  • 알고리즘을 수행하는 데 필요한 연산이 몇 번 실행되는지를 숫자로 표기한다.

  • 이 연산의 개수는 상수가 아니라 입력한 데이터의 개수를 나타내는 n에 따라 변하게 된다. 그래서 연산의 개수 n의 값에 따라 시간 복잡도를 나타낸 것을 시간 복잡도 함수라고 하며 수식으로는 T(n)이라고 표기한다.

• 입력값이 작을 때는 그 차이가 크지 않았지만, 입력값이 점점 커질 수록 엄청나게 차이가 벌어진다.

  • 이를 실행 시간의 성장률(rate of growth)이라고 한다.

Big-O 표기법

• 다항식의 시간 복잡도 함수에서 입력값이 커져감에 따라 각 항의 결과값에 관여하는 정도가 달라지게 됨

• 시간 복잡도와 뒤에 나올 공간 복잡도를 표시할 때는 각 함수의 모든 항을 표시하지 않으며 상수 계수와 중요하지 않은 항목을 제거한 점근적 표기법(asymptotic notation)을 사용한다.

• 이중 가장 많이 사용되는 Big-O 표기법은 점근적 상한선을 제공한다.

• 다음의 비교에서 왼쪽에 위치한 시간 복잡도일수록 해당 알고리즘은 빠르다고 할 수 있다.

  O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!)

• 다만, 위 그래프에서 볼 수 있듯이 언제나 Big-O 표기법에 따라 속도가 결정되진 않는다.

공간 복잡도

• 컴퓨터 내의 자원 공간을 얼마나 사용하는지 또한 알고리즘의 효율성을 평가할 때 고려해야 한다.

• 공간 복잡도(space complexity) : 알고리즘을 수행하는 데 필요한 자원 공간의 양

• 공간 복잡도 함수는 고정 공간 요구 + 가변 공간 요구로 나타낼 수 있으며 수식으로는 S(P)=c+Sp(n)으로 표기한다.

• 고정 공간 : 입력과 출력의 횟수나 크기와 관계 없는 공간

• 가변 공간 : 문제를 해결하기 위해 요구되는 추가 공간

• Big-O 표기법 상에서는, 가변 공간만을 고려하게 된다.

시간 복잡도 vs 공간 복잡도

• 효율적인 알고리즘은 실행 시간이 적게 걸리며, 자원을 적게 소모하는 것

• 시간과 공간은 반비례적인 경향이 있다.

• 보통 알고리즘의 척도는 시간 복잡도를 위주로 판단

  • 즉, 시간 복잡도를 위해 공간 복잡도를 희생하는 경우가 많다.

STL

• 대부분의 언어는 기본 자료구조와 알고리즘을 제공하고 있다.

• C++의 경우는 STL(standard template library)이라고 하며, 3가지로 구성되어 있다.

  • 임의 타입의 객체를 보관할 수 있는 컨테이너(container)
    • https://en.cppreference.com/w/cpp/container
  • 컨테이너에 보관된 원소에 접근할 수 있는 반복자(iterator)
    • https://en.cppreference.com/w/cpp/iterator
  • 반복자를 가지고 일련의 작업을 수행하는 알고리즘(algorithm)
    • https://en.cppreference.com/w/cpp/algorithm

• 컨테이너는 앞으로 배우게 될 자료구조의 구현체

• 반복자는 컨테이너의 요소에 접근할 수 있는 포인터

  • 이렇게 나뉘게 된 이유는 컨테이너 각각에 알고리즘을 구현하려면 알고리즘 코드의 개수가 엄청 많이 필요한데, 반복자의 존재로 각 요소에 추상적으로 접근할 수 있어 구현 개수를 많이 줄일 수 있었다.

리스트

• 리스트(list) : 순서를 갖고 있는 자료구조

  • 순차 자료구조엔 선형 리스트가 있다.

  • 연결 자료구조엔 단일 연결 리스트, 원형 연결 리스트, 이중 연결 리스트가 있다.

선형 리스트 == 배열

• 선형 리스트(linear list)는 순서 리스트(ordered list)라고도 한다.

• 임의 접근이 가능하다는 특징을 가지고 있다.

• 읽기

  선형 리스트는 임의 접근이 가능하기 때문에 O(1)의 시간이 걸린다.

• 검색

  하나하나 원소를 비교해가야 하므로 O(n)의 시간이 걸린다. 정렬되어 있다면 이진 검색을 사용할 수 있으며 이 경우 O(logn)이다.

• 삽입

  원소를 어디에 삽입하냐에 따라 시간이 달라진다. 맨 끝에 데이터를 추가할 경우 O(1)이지만, 처음이나 중간이라면 모든 데이터를 이동해야 하기에 O(n)이 걸린다.

• 삭제

  삽입과 마찬가지로 원소를 어디에서 삭제하냐에 따라 시간이 달라진다. 맨 끝의 데이터를 삭제할 경우 O(1)이지만, 처음이나 중간이라면 모든 데이터를 이동해야 하기에 O(n)이 걸린다.

연결 리스트

• 선형 리스트와 다르게 임의 접근이 불가능하다.

• 읽기

  연결 리스트는 임의 접근이 불가능해 요소 하나하나를 탐색해야 하므로 O(n)의 시간이 걸린다. 하지만 처음과 끝이라면 구현에 따라 O(1)이 될 수 있다.

• 검색

  하나하나 원소를 비교해가야 하므로 O(n)의 시간이 걸린다. 선형 리스트와 다르게 이진 검색을 사용할 수 없다.

• 삽입

  원소를 어디에 삽입하냐에 따라 시간이 달라진다. 앞이나 뒤에 데이터를 추가할 경우 O(1)이지만, 중간이라면 해당 위치까지 검색해야 하기 때문에 O(n)이 걸린다.

• 삭제

  삽입과 마찬가지로 원소를 어디에서 삭제하냐에 따라 시간이 달라진다. 앞이나 뒤의 데이터를 삭제할 경우 O(1)이지만, 중간이라면 O(n)이 걸린다.

스택

• 스택(stack) : 리스트의 일종으로 연산이 한 쪽 끝에서만 이뤄지는 자료구조

• 가장 나중에 들어간 것이 처음에 나온다고 하여 LIFO(Last-In First-Out, 후입선출)구조라고도 한다.

• 스택의 끝을 위(top), 스택의 시작을 밑(bottom)이라 한다.

• 괄호가 올바른지 검사 / 후위 표기식 / DFS 등에 사용될 수 있다.

• STL에서는 std::stack으로 구현되어 있다.

  • https://en.cppreference.com/w/cpp/container/stack

큐

• 큐(queue)도 리스트의 일종으로 스택과 다르게 가장 처음에 들어간 데이터가 처음에 나오는 FIFO(First-In First-Out, 선입선출) 자료구조다.

• 삽입이 일어나는 쪽을 뒤(rear), 삭제가 일어나는 쪽을 앞(front)라고 한다.

• 프린트 큐 / CPU 스케줄링 / 데이터 버퍼 / BFS 등에 사용된다.

• STL에서는 std::queue, std::deque로 구현되어 있다.

• 입력된 순서가 유지되어야 할 때 사용 가능.

그래프

• 선형 자료구조로는 표현할 수 없는 문제 : 비선형적 문제를 다룰 수 있는 자료구조

그래프(Graph)란?

• 관계에 특화된 자료구조

• 정점(vertex)과 간선(edge)으로 구성되어 있다.

  • 정점 : 고유하게 식별되는 객체

  • 간선 : 정점 간의 관계를 표현

종류

• 간선이 방향성을 가지는 가

  • 방향 그래프(directed graph)

  • 무방향 그래프(undirected graph)

• 가중치 그래프(weighted graph)* : 간선이 단순 연결 이상의 정보(가중치)를 가진다. 

• 네트워크(network)라고도 한다.

• 그래프의 종류
  https://pangtrue.tistory.com/147

순회

• 그래프 순회(graph traversal) or 탐색(search)
  정점에서 시작해 그래프에 있는 모든 정점을 한 번씩 방문하는 것.

  • 깊이 우선 탐색(depth first search)

    • 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다 더 이상 갈 곳이 없으면 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와 다른 방향의 간선으로 탐색을 계속하는 방법으로 스택을 사용한다.

  • 너비 우선 탐색(breadth first search)

    • 시작 정점에 인접한 정점을 모두 차례로 방문하고 나서 방문했던 정점을 시작으로 다시 인접한 정점을 차례로 방문하는 방식으로 큐를 사용한다.

최단 경로

• 최단 경로(shortest path)

  • 가중치 그래프에서 두 정점을 연결하는 경로 중 가중치의 합이 최소인 경로

  • 최단 경로를 구하기 위해 간선이 없다면 무한대 값으로 저장하며, 가중치가 음수여선 안된다.

  • 최단 경로를 구하는 알고리즘으로는 다익스트라 알고리즘(발전형 : A*, JPS)과 플로이드 알고리즘이 있다.

트리

• 트리(tree)
  그래프의 일종으로 계층형 자료구조(hierarchical data structure)

• 트리는 데이터가 저장된 노드(node)와 노드 간 관계를 표현하는 간선(edge)으로 구성된다.

• STL에서는 std::set / std::map / std::multiset / std::multimap 으로 구현이 되어 있다.

• 재귀적.

순회

• 트리에 대한 순회는 전위 순회(pre-order traversal) / 중위 순회(in-order traversal) / 후위 순회(post-order traversal) / 레벨 순회(level-order traversal)가 있다.

이진 검색 트리

• 이진 검색 트리(binary search tree)
  한 노드를 기준으로 왼쪽 서브 트리는 모두 그 노드보다 작은 값을 가지고 있으며, 오른쪽 서브 트리는 모두 그 노드보다 큰 값을 가지고 있는 이진 트리(binary tree)이다.

  • 이진 트리(binary tree) : 트리의 차수가 2 이하인 트리

• 수식으로 표현하면 왼쪽 자식 노드의 값 <= 부모 노드의 값 <= 오른쪽 자식 노드의 값이 된다.

힙

• 힙(heap)
  완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해 만든 자료구조

  • 최대 힙(max heap) : 키값이 가장 큰 노드를 찾기 위한 힙

  • 최소 힙(min heap) : 가장 작은 노드를 찾기 위한 힙. 우선순위 큐(priority queue)라고도 한다.

• STL에서는 std::priority_queue로 구현이 되어 있다.

해시 테이블

• 해싱(hashing) : 입력의 크기에 상관 없이 일정 크기의 값으로 변환하는 것. 이에 사용되는 함수를 해시 함수(hash function)라 한다.

  • 균일성 : 충돌이 적은 것을 의미한다.

    • 충돌(collision) : 서로 다른 값이 같은 해시 값을 생성한 것

  • 효율성 : 계산하기 쉬워야 한다.

  • 결정적 : 같은 입력에는 같은 값을 내놓아야 한다.

    • Ex. 디지털 서명, 공인 인증서 등등

• 해시 테이블(hash table) : 해싱을 활용해 데이터를 저장하는 검색을 위한 자료구조. 연관 배열(associative array)이라고도 한다. 해시 값을 테이블의 인덱스로 활용한다.

  • 검색하기 편하게 하는 자료구조.