out_of_anjoong.dev

Dynamic Programming(동적 계획법)

특징

• 재귀적인 방식으로 보다 작은 부분 문제로 나누고 부분 문제를 푼 해를 조합하여 전체 문제의 해답에 이르는 방식.
• 실제로 문제를 푸는 법
  1. 테이블 정의하기(1차원(D[i] 또는 2차원(D[i][j]) 배열 설정)
  2. 점화식 찾기
  3. 초기값 설정

DFS, BFS

특징

• 그래프
  • 정점(vertex, node)과 간선(edge, link)으로 이루어진 자료구조
  • 유향(directed) 그래프와 무향(undirected) 그래프가 있다.
• 실제로 문제를 푸는 법
  1. 시작하는 칸을 queue(BFS), stack(DFS)에 넣고 방문표시를 남김.(boolean 배열 이용)
  2. 선택한 자료구조에서 원소를 꺼내며 그 칸의 상하좌우로 인접한 칸에 대해 3번 진행
  3. 해당 칸을 방문했는가?
     • yes : 아무것도 안함
     • no : 자료구조에 넣고 방문표시를 남김
  4. 자료구조가 빌 때 까지 2번 반복

Hash(해쉬)

특징

• 어떤 키 값으로 hash function(해시 함수)를 이용해 hash bucket(해시 버킷)에서 값을 저장 및 사용
• collision(충돌)이 있을 수 있음.

대표 문제

• 프로그래머스
  • 완주하지 못한 선수 https://school.programmers.co.kr/learn/courses/30/lessons/42576

Greedy Algorithm(탐욕법 알고리즘)

특징

• 알고리즘의 각 단계에서 그 순간에 최적이라고 생각되는 것을 선택
• 현재의 선택이 마지막 해답의 최적성을 해치지 않을 때
• 수학적으로 접근하여 점화식을 만들기

대표 문제

• 프로그래머스
  • 체육복 https://school.programmers.co.kr/learn/courses/30/lessons/42862
  • 큰 수 만들기 https://school.programmers.co.kr/learn/courses/30/lessons/42883 

Queue

특징

• FIFO(First In First Out) ※스택은 LIFO(Last In First Out)

주요 개념

• size(): 현재 큐에 들어 있는 데이터 원소의 수를 구함
• isEmpty(): 현재 큐가 비어 있는지를 판단
• enqueue(x): 데이터 원소 x를 큐에 추가
• dequeue(): 큐의 맨 앞에 저장된 데이터 원소를 제거하며 원소 값 반환
• front(), peek(): 큐의 맨 앞에 저장된 데이터 원소를 반환

활용

• 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 일어나는 경우
• 자료를 생성하는 작업이 여러 곳에서 일어나는 경우
• 자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우

Circular Queue(환형 큐)

특징

• 정해진 개수의 저장 공간을 빙 돌려가며 이용
• 배열로 큐를 구현했을 때 맨 앞 원소를 제거하면 나머지 원소들을 앞으로 댕겨야 하는 복잡함을 해결하기 위해 사용

주요 개념

• size(): 현재 큐에 들어 있는 데이터 원소의 수를 구함
• isEmpty(): 현재 큐가 비어 있는지를 판단
• isFull() : 큐에 데이터 원소가 꽉 차있는지를 판단
• enqueue(x): 데이터 원소 x를 큐에 추가
• dequeue(): 큐의 맨 앞에 저장된 데이터 원소를 제거하며 원소 값 반환
• front(), peek(): 큐의 맨 앞에 저장된 데이터 원소를 반환

Priority Queue(우선순위 큐)

특징

• 큐가 FIFO 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식
• Enqueue 할 때 우선순위 순서를 유지하도록 or Dequeue 할 때 우선순위 높은 것을 선택 하는 방식으로 구현
• 배열 보다는 연결 리스트가 시간적으로는 유리함.

활용

• 운영체제의 CPU 스케쥴러

Trees(트리)

특징

• 정점(node)와 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료구조

주요 개념

• root(뿌리) 노드 : 부모 노드가 없는 노드
• leaf(잎) 노드 : 자식 노드가 없는 노드
• Internal(내부) 노드 : 그 나머지 노드들은 
• sibling(형제) : 같은 부모 노드를 공유하는 노드들
• ancestor(조상) : 부모 노드의 부모 노드
• decendant(후손) 노드 : 자식 노드의 자식 노드
• height(높이) 최대 수준(level) + 1
• 서브트리 : 어느 노드부터 후손 노드들까지의 트리
• degree(차수) : 어떤 노드의 자식(서브트리)의 수

Binary Tree(이진 트리)

특징

• 모든 노드의 차수가 2 이하인 트리
• Full Binary Tree(포화 이진 트리) : 모든 레벨에서 노드들이 모두 채워져 있는 이진 트리(height = k, 노드의 개수 = 2^k - 1)
• Complete Binary Tree(완전 이진 트리) : 높이가 k일 때, k-2 까지는 모든 노드가 2개의 자식을 가진 포화 이진트리, k-1에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진트리

주요 개념

• size() : 현재 트리에 포함되어 있는 노드의 수를 구함
• depth() : 현재 트리의 깊이(height)를 구함
• traversal(순회)
  • Depth First traverSal(깊이 우선 순회) - DFS
    • in-order traversal(중위 순회) : left subtree -> 자기 자신 -> right subtree
    • pre-order traversal(전위 순회) : 자기 자신 -> left subtree -> right subtree
    • post-order traversal(후위 순회) : left subtree -> right subtree -> 자기 자신
  • Breadth First traverSal(넓이 우선 순회) - BFS
    • 수준(level)이 낮은 노드를 우선으로 방문
    • 같은 수준의 노드들 사이에서는
      - 부모 노드의 방문 순서에 따라 방문
      - 왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문
    • queue(큐)를 이용.

Binary Search Tree(이진 탐색 트리)

특징

• 모든 노드에 대해서 아래 두가지 성질을 만족하는 이진 트리
  • 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작음
  • 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큼
• 데이터 원소의 추가, 삭제가 용이
• 공간 소요가 큼

주요 개념

• insert(key, data) : 트리에 주어진 데이터 원소를 추가
• remove(key) : 특정 원소를 트리로부터 삭제
  • 키(key)를 이용해서 노드를 찾는다.
    • 해당 키의 노드가 없으면, 삭제할 것도 없음
    • 찾은 노드의 부모 노드도 알고 있어야 함.
  • 찾은 노드를 제거하고도 이진 탐색 트리 성질을 만족하도록 트리의 구조 정리 필요.
• lookup(key) : 특정 원소를 검색
• inrorder() : 키의 순서대로 데이터 원소를 나열
• min(), max() : 최소, 최대 키를 가지는 원소를 탐색

Heap(힙)

특징

• 이진 트리의 한 종류 (이진 힙 - binary heap)
• 루트 노드가 언제나 최댓값(max heap) 또는 최솟값(min heap)을 가짐
• 완전 이진 트리여야 함
• 힙은 배열을 이용하는게 편함

주요 개념

• 노드 번호 m 을 기준
  
  • 왼쪽 자식 노드의 번호 : 2 * m
  • 오른쪽 자식 노드의 번호 : 2 * m + 1
  • 부모 노드의 번호 : m // 2
• 완전 이진 트리이므로 노드의 추가/삭제는 마지막 노드에서
• 원소 삽입 O(logn)
  1. 비어있는 가장 마지막 배열에 원소 삽입
  2. 부모 노드와 키 값을 비교하며 부모 노드의 키 값 보다 작을 때 까지 교환
• 원소 삭제
  1. 루트 노드의 제거 : 원소들 중 최댓값
  2. 트리 마지막 자리 노드을 임시로 루트 노드의 자리에 배치
  3. 자식 노드와 값을 비교하여 가장 큰 키 값 찾을 때 까지 비교하며 내려감.

응용

• 우선 순위 큐
  • Enqueue 할 때 "느슨한 정렬"을 이루고 있도록 함 : O(logn)
  • Dequeue 할 때 최댓값을 순서대로 추출 : O(logn)
  • 양방향 연결 리스트로 구현한 것 보다 효율적
• Heap Sort(힙 정렬)
  • 정렬되지 않은 원소들을 아무 순서로나 최대 힙에 삽입 : O(logn)
  • 삽입이 끝나면 힙이 비게 될 때 까지 하나씩 삭제 : O(logn)
  • 원소들이 삭제된 순서가 원소들의 정렬 순서
  • 알고리즘의 복잡도 : O(nlogn)

활용 문제

• 더맵게 https://school.programmers.co.kr/learn/courses/30/lessons/42626
•  

Linked List

종류

• Linked List(단순 연결 리스트)
• Doubly Linked List(양방향 연결 리스트)
• Circular Linked List(원형 연결 리스트)

주요 개념

• 노드 : 데이터와 다음 노드를 가리키는 포인터로 이루어진 구조체이다.
            양방향, 원형 연결 리스트는 이전 노드를 가리키는 포인터도 가지고 있음.
• head : 연결 리스트의 맨 앞
• tail : 연결 리스트의 맨 뒤
• nodeCount : 연결 리스트의 사이즈
• 추가/삽입 : 삽입하려는 위치의 노드(A)와 그 다음 노드(B)가 있다.
                   A 노드의 다음 노드는 삽입하는 노드. 삽입하는 노드의 다음 노드는 B노드가 된다.
                   양방향 연결 리스트는 삽입하는 노드의 이전 노드는 A 노드, B 노드의 이전 노드를 삽입하는 노드로 설정이 필요하다.
                   (Head, Tail)더미 노드를 사용하지 않는 경우 삽입하려는 위치에 따라 Head와 Tail의 재정의가 필요할 수 있다.
  • 필요한 예외 처리
    불가능한 위치에 노드 삽입
• 삭제/제거 : 제거하려는 노드의 위치와 그 이전 노드(A), 그 다음 노드(B)가 있다.
                   A 노드의 다음 노드는 B가 된다.
                   양방향 연결 리스트의 경우 B 노드의 이전 노드는 A가 된다.
                   제거하려는 위치에 따라 Head와 Tail 정보를 재정의할 필요가 있다.
  • 필요한 예외 처리
    연결 리스트가 비어있을 경우, 불가능한 위치의 노드 제거
• 열람 : head부터(양방향 연결 리스트에서는 사이즈의 절반 부터 tail까지) 해당 위치까지 이동 후 데이터 return
• 두 연결 리스트 합치기 : 앞 연결 리스트(A), 뒤 연결 리스트(B)
                                     A 리스트의 Tail 이전 노드의 다음 노드는 B 리스트 Head의 다음 노드.
                                     B 리스트 Head의 다음 노드의 이전 노드는 A리스트의 Tail 노드의 이전 노드.
                                     A 리스트의 Tail의 이전 노드는 B 리스트의 Tail의 이전 노드로 재정의.
  
  • 필요한 예외 처리
    A가 비어있을 경우, B가 비어있을 경우

Stack

특징

• LIFO(Last In First Out)

주요 개념

• size(): 현재 스택에 들어 있는 데이터 원소의 수를 구함
• isEmpty(): 현재 스택이 비어 있는지를 판단
• push(x): 데이터 원소 x 를 스택에 추가
• pop(): 스택에 가장 나중에 저장된 데이터 원소를 제거
• top(), peek(): 스택에 가장 나중에 저장된 데이터 원소를 참조

활용

• 재귀 함수
• 후위표현 수식 및 계산