면접 예상 질문 목록2 (정렬,자료구조,알고리즘,디자인패턴)

면접 예상 질문 목록 정리2

정렬

• 선택 정렬(selection sort)

  선택 정렬은 앞쪽부터 정렬하는 방식이다. 주어진 배열에서 가장 작은 최소값을 찾고 배열의 맨 앞의 값과 위치를 바꾸면서 정렬한다. 선택 정렬은 배열의 최소값을 찾아 선택하여 정렬한다는 뜻에서 이름이 붙여졌다. 배열에서 최소값을 찾아야 하기 때문에 비교 횟수는 많지만 실제로 값을 바꾸는 교환 횟수가 적다는 것이 특징이다.

  1. 장점

     • 구현이 간단하다.
     • 데이터를 하나씩 비교하기 때문에 정밀한 비교가 가능하다.
     • 비교하는 횟수에 비해 교환하는 횟수가 적다

  2. 단점

     • 데이터 하니씩 비교하기 때문에 시간이 오래 걸린다.
     • 정렬된 상태에서 새로운 데이터가 추가되면 정렬 효율이 좋지 않다.

• 버블 정렬(bubble sort)

  버블 정렬은 첫번째 원소부터 인접한 원소와 비교하며 자리를 바꾸면서 맨 끝부터 정렬하는 방식이다. i번째 원소와 i+1번째 원소의 값을 비교하고 만약 i번째의 값이 i+1번째의 값보다 크다면 둘의 자리를 바꾸어 값이 큰 원소가 뒤에 위치하게 한다. 이를 반복해서 수행하면 가장 큰 값부터 뒤쪽에 쌓이게 된다. 즉 가장 큰값을 하나씩 뒤로 보내면서 뒤쪽부터 정렬한다. 버블 정렬은 정렬 방식이 마치 물속에서 올라오는 물방울과 같다고 하여 버블 정렬이라는 이름이 붙여졌다.

  1. 장점

     • 구현이 간단하다.
     • 데이터를 하나씩 비교하기 때문에 정밀한 비교가 가능하다.

  2. 단점

     • 데이터를 하나씩 비교하기 때문에 비교 횟수가 많아지므로 시간이 오래 걸린다.

• 삽입 정렬(insertion sort)

  삽입 정렬은 버블 정렬의 비효율성을 개선하기 위해 등장한 방법이다. 버블 정렬은 i번째와 i+1번째를 비교하며 위치를 바꾸었다면 삽입 정렬은 i번째 원소를 정렬된 상태의 앞부분과 비교하여 적절한 위치에 삽입하는 방식이다. i-1번째 원소까지는 모두 정렬된 상태여야 하며 i-1번째부터 0번째 원소와 i번째 원소를 각각 비교한다. 이때 i번째 원소보다 작은 값이 발견되면 그 위치에 i번째 원소를 삽입한다. 삽입 정렬은 버블 정렬의 비교 및 교환 횟수를 줄임으로써 높은 효율을 보여준다.

  1. 장점

     • 입력으로 들어오는 배열의 원소가 정렬되어 있을수록 속도가 빠르다.
     • 정렬된 값은 교환이 일어나지 않는다.

  2. 단점

     • 삽입을 구현해야 하므로 속도가 자료구조릐 영향을 많이 받는다.
     • 입력으로 들어오는 배열이 역순으로 정렬된 성능이 굉장히 좋지 않다.

• 병합 정렬(merge sort)

  병합 정렬은 배열을 작은 단위로 쪼개어 정렬한 결과를 합치면서 전체를 정렬하는 방식이다. 배열을 왼쪽 절반, 오른쪽 절반으로 분할하여 최소 단위로 쪼갠 후 정렬을 진행한다. 대부분의 경우 병합 정렬은 상당한 안정성을 가지기 때문에 좋은 성능을 보인다. 하지만 작은 단위로 쪼갠 배열을 저장할 공간을 사용하기 때문에 추가적인 메모리가 필요하다.

  1. 장점

     • 항상 일정한 시간 복잡도(O(NlogN))를 가진다.
     • 안정적이며 대부분의 경우에서 좋은 성능을 낸다.

  2. 단점

     • 추가 메모리 공간이 필요하다.

• 퀵 정렬(quick sort)

  퀵 정렬은 하나의 축을 정해서 이 축보다 작은 값은 왼쪽에 큰값은 오른쪽에 위치시킨다. 그리고 왼쪽과 오른쪽에 해당하는 원소들에 대해 다시 축을 각각 정하고 그 안에서 작은 값은 왼쪽에 큰 값은 오른쪽에 위치시킨다. 실제로 많이 사용하고 있는 정렬 알고리즘으로 알려져 있다. 일반적으로 준수한 효율을 보이지만 최악의 경우에는 훨씬 많은 시간이 소요되므로 안정성이 좋지 않다는 특징이 있다. 대부분의 내장 라이브러리에서 존재하는 정렬 함수는 퀵 정렬 알고리즘을 사용한다.

  1. 장점

     • 평균 실행 시간이 빠르다.

  2. 단점

     • 축을 어떻게 설정하느냐에 따라 성능의 차이가 심하다.
     • 안정성이 좋지 않다.

• 힙 정렬(heap sort)

  힙 정렬은 최대 힙 트리(Max Heap Tree)나 최소 힙 트리(Min Heap Tree)를 구성하여 정렬하는 방식이다. 여기서 ‘힙’이라는 자료구조가 사용되는데 힙은 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다. 여러 개의 값중에서 최댓값이나 최솟값을 빠르게 찾기 위해 사용된다. 최대 힙 트리는 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리이며 최소 힙 트리는 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리이다.

  힙 정렬을 통해 내림차순으로 정렬하기 위해서는 최대 힙 트리를 구성하고 오름차순으로 구성하기 위해서는 최소 힙 트리를 구현한다. 먼저 입력으로 들어오는 배열로 힙 트리를 만든다. 그 후 root 노드를 하나씩 꺼내어 배열의 뒤쪽부터 넣는다. 빈 root 노드 자리에는 힙 트리의 가장 뒤에 있는 원소가 들어가서 자기 자리를 찾아간다. 즉 힙 트리로 구한 최댓값 혹은 최솟값에 해당하는 root 노드를 빼내면서 정렬을 수행한다.

  1. 장점

     • 항상 같은 시간 복잡도를 가지기 때문에 성능이 준수하다.

  2. 단점

     • 같은 시간 복잡도를 가지는 다른 정렬 알고리즘과 비교하면 느린 편이다.

• 셸 정렬(shell sort)

  셸 정렬은 삽입 정렬의 문제점을 해결하기 위해 등장한 방법이다. 입력으로 들어온 배열을 간격이라고 하는 일정한 기준에 따라 분류한다. 이를 통해 연속적이지 않은 여러 개의 부분 배열을 생성한 후 각 배열을 삽입 정렬로 정렬한다. 모든 배열이 정렬되면 다시 전체 배열을 여러 개의 부분 배열로 나누는데 이때 간격을 전 단계보다 작게 설정하여 생성되는 부분 배열의 개수를 전 단계보다 적게 만든다. 그 후 부분 배열의 개수가 1이 될 때까지 앞의 과정을 반복한다.

  1. 장점

     • 삽입 정렬의 문제점을 해결함으로써 성능이 좋다.

  2. 단점

     • 설정한 간격에 따라 성능의 차이가 심하다.

• 위상 정렬(topological sort)

  위상 정렬은 위의 일정한 수의 배열을 정렬보다는 노드 사이에 방향성이 있는 간선이 있는 경우 사용됩니다. 그러므로 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해 주는 알고리즘입니다. 노드와 노드 간의 간선이 하나 이상씩 존재하게 된다면 여러개의 답이 존재할 수 있게 되고, 사이클이 없는 DAG에만 적용이 가능합니다. 구현 방법은 진입 차수가 0인 정점부터 큐에 삽입합니다. 큐에서 원소를 꺼내게 되면 연결된 모든 간선을 제거하고 정점과 진입차수의 정보가 저장되어 있는 배열의 진입차수를 갱신합니다. 다시 진입 차수가 0인 정점을 큐에 삽입하고 큐가 모두 빌 때까지 반복합니다. 이 때 큐에서 꺼낸 순서가 위상정렬의 결과입니다.

• 시간 복잡도(Big O)

  정렬	선택 정렬	버블 정렬	삽입 정렬	병합 정렬	퀵 정렬	힙 정렬	셸 정렬	위상 정렬
  평균	O(N^2)	O(N^2)	O(N^2)	O(NlogN)	O(NlogN)	O(NlogN)	O(N^1.5)	O(V+E)
  최선	O(N^2)	O(N)	O(N)	O(NlogN)	O(NlogN)	O(NlogN)	O(N)
  최악	O(N^2)	O(N^2)	O(N^2)	O(NlogN)	O(N^2)	O(NlogN)	O(N^2)
  공간	O(N^2)	O(N)	O(N^2)	O(NlogN)	O(NlogN)	O(NlogN)	O(N)

자료구조

• 배열(Array)

  배열은 가장 기본적인 자료 구조이다. 배열은 생성시 설정된 셀의 수가 고정되고, 각 셀에는 인덱스 번호가 부여된다. 배열을 활용시 부여된 인덱스를 통해 해당 셀 안에 있는 데이터에 접근 할 수 있다.

  1. 장점

     • 바로 만들어서 활용하기가 쉽다
     • 더 복잡한 자료 구조의 기초가 될 수 있다
     • 원하는 데이터를 효율적으로 탐색/가져올 수 있다
     • 정렬에 용이하다

  2. 단점

     • 데이터를 저장 할 수 있는 메모리 크기가 고정되어 있다
     • 데이터 추가 / 삭제 방법이 비효율적이다
     • 구조 재구성 시 정렬하는 방식이 비효율적이다

• 스택(Stack)

  스택은 순서가 보존되는 선형 데이터 구조 유형이다. 가장 마지막 요소 (가장 최근 요소)부터 처리하는 LIFO (Last In First Out) 메커니즘은 가지고 있다. 스택은 쌓여있는 접시 더미와 같이 작동한다. 새로운 접시가 쌓일 때도 맨 위에서 쌓이고, 접시를 가져갈 때도 맨 위에서 가지고 가는 것과 같다.

  1. 장점

     • 동적인 메모리 크기
     • 데이터를 받는 순서대로 정렬된다
     • 빠른 런타임 (runtime)

  2. 단점

     • 가장 최신 요소만 가져온다
     • 한번에 하나의 데이터만 처리 가능하다

• 큐(Queue)

  큐는 스택과 비슷하지만 가장 먼저 입력된 요소를 처리하는 FIFO (First In First Out) 메커니즘이다. 큐는 놀이공원에서 서는 줄과 같이 작동한다. 사람들이 맨 끝에 줄을 서고, 맨 앞에서부터 놀이기구에 탑승하는 것과 같다.

  1. 장점

     • 동적인 메모리 크기
     • 데이터를 받는 순서대로 정렬된다
     • 빠른 런타임 (runtime)

  2. 단점

     • 가장 오래된 요소만 가져온다
     • 한번에 하나의 데이터만 처리 가능하다

• 연결 리스트(Linked list)

  연결 리스트 구조는 앞에서 말한 세 가지 구조와 달리 메모리에 있는 데이터의 물리적 배치를 사용하지 않는 데이터 구조다. Index나 위치보다 참조 시스템을 사용한다. 각 요소는 노드라는 것에 저장되는데, 다음 노드 연결에 대한 포인터 또는 주소가 포함된 또 다른 노드에 저장된다. 모든 노드가 연결된 때까지 반복이 돼서 노드의 연결로 이루어진 자료 구조다. 그리고 이 구조는 데이터 추가 및 삭제 시 재구성이 필요 없어서 효율적이다.

  연결 리스트에는 단일 연결 리스트(Singly-Linked List), 이중 연결 리스트(Doubly-Linked List)등의 종류가 있다.

  1. 장점

     • 새로운 요소들의 추가 및 삭제가 용이하고 효율적이다
     • 배열처럼 메모리에 연속적으로 위치하지 않는다
     • 배열처럼 구조의 재구성이 필요없다
     • 동적인 메모리 크기
     • 메모리를 더 효율적으로 쓸 수 있기 때문에 대용량 데이터 처리 적합

  2. 단점

     • 배열보다 메모리를 더 사용한다
     • 처음부터 끝까지 순회하기 때문에 원하는 값을 비효율적으로 검색/가져온다
     • 노드를 반대 방향으로 검색할 때 비효율적이다 (이중 연결 리스트의 경우)

• 해시 테이블 (Hash tables / Hash map)

  해시 테이블은 대량의 정보를 저장하고 특정 요소를 효율적으로 검색할 수 있는 복잡한 데이터 구조다. 이 데이터 구조는 테이블 내에 더 작은 서브그룹인 버킷(bucket)에 키/값(key/value) 쌍(pair)을 저장한다. 해시 테이블은 키를 저장할 때에 메모리 공간을 덜 사용할 수 있도록, 키를 “해시 함수”(Hash function)라는 함수를 통해 해시(hash)라는 특정 숫자값으로 변환한다. 해시 테이블은 필요할 때에만 메모리 크기를 늘리고, 가능한 작은 크기를 유지한다.

  키(key)는 검색 시 사용되는 문자열이고 값(value)은 해당 키와 쌍을 이룬 데이터다. 검색된 각 키는 미리 정의된 해시함수(hash function)를 통해 해시(hash)값을 받고 버킷(bucket)을 가리킨다. 즉, 해시 숫자는 버킷의 index라는 뜻이다. 그리고 버킷에서 검색할 때 입력된 키를 찾고 해당 키와 관련된 값을 반환한다.

  1. 장점

     • 새로운 요소들의 추가/삭제가 용이하고 효율적이다
     • 원하는 값의 검색/가져오기가 빠르고 효율적이다
     • 동적인 메모리 크기 (그러나 직접 크기를 늘리거나 줄여야 한다)

  2. 단점

     • 충돌이 일어날 수 있다 (입력된 키의 해시값이 이미 데이터가 저장된 버킷을 가리킬 수 있다)
     • 충돌이 자주 일어날 수 있으며 해시함수의 정비가 필요한 경우가 많다.

• 그래프 (Graph)

  그래프는 단순히 nodes/vertices(노드) 사이에 edge(엣지)가 있는 collection이다. 그래프는 directed(방향) 또는 undirected(무방향)이 될 수 있다. Directed graph는 한쪽 방향 밖에 없어서 일방통행과 같고, undirected graph는 방향이 지정되지 않아서 양방향 도로와 같다. 하지만 그래프로 구성된 데이터 구성은 다양하다.

  그래프로 구조를 어떻게 설계 그리고 무엇을(검색, 추가, 삭제, 등) 하고 싶으냐에 따라 시간 복잡도가 달라진다.

  그래프가 리스트 형태로 설계 되어 있는 경우: N = node, E = edge

  1. 장점

     • 새로운 요소들의 추가/삭제가 용이하고 효율적이다
     • 구조의 응용이 가능하다

  2. 단점

     • 충돌이 일어날 수 있다 (입력된 키의 해시값이 이미 데이터가 저장된 버킷을 가리킬 수 있다)

• 트리(Tree)

  트리는 노드로 구성된 계층적 자료구조다. 최상위 노드(루트)를 만들고, 루트 노드의 child를 추가하고, 그 child에 또 child를 추가하는 방식으로 트리 구조를 구현할 수 있다.

  트리의 종류는 다양하다.

  트리 구조와 관련하여 반드시 알아야 할 개념들:

  • A, B, C, D 등 트리의 구성요소를 노드(node) 라고 한다.
  • 위 그림의 A처럼, 트리 구조에서 최상위에 존재하는 노드를 root라고 한다.
  • 루트를 기준으로, 다른 노드로의 접근하기 위한 거리를 depth 라고 한다.
  • 같은 부모를 가지면서 같은 depth에 존재하는 노드들은 sibling 관계에 있다.
  • 그림에서 A는 B와 C의 부모(parent) 이고, B와 C는 A의 자식(child)이다.
  • 노드와 노드를 잇는 선을 edge 라고 한다.
  • 자식이 없는 노드는 leaf 라고 한다.
    

• 복잡도

  자료구조	가져오기	추가하기	삭제하기
  배열	O(N)	O(N)	O(N)
  스택	O(N)	O(1)	O(1)
  큐	O(N)	O(1)	O(1)
  연결 리스트	O(N)	O(1)	O(1)
  해시 테이블	O(1)	O(1)	O(1)
  그래프	O(|N|+|E|)	O(1)	O(|N|+|E|) / O(|E|)
  트리(이진)	O(logN)	O(logN)	O(logN)

알고리즘

• 깊이 우선탐색(DFS)

  루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다. 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.

  로직은 stack을 통해 구현한다면, 시작점을 stack에 push합니다. 시작점을 방문 표시합니다. stack을 pop해서 나온 정점의 인접 정점을 stack에 다시 push합니다. 다시 pop을 하여 인접 정점을 push합니다. push를 하며 방문 표시를 합니다. 모든 정점을 방문하고 stack이 null이 될 때까지 진행합니다. 탐색 결과는 pop한 순서입니다.

  1. 장점

     • 단지 현 경로상의 노드들만을 기억하면 되므로 저장 공간의 수요가 비교적 적다.
     • 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

  2. 단점

     • 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제로는 미리 지정한 임의 깊이까지만 탐색하고 목표 노드를 발견하지 못하면 다음 경로를 따라 탐색하는 방법이 유용할 수 있다.
     • 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.

• 너비 우선 탐색(BFS)

  시작점에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 주로 두 정점 사이의 모든 정점을 탐색할 때 사용된다.

  로직은 queue를 통해 구현하면 되는데, 먼저 시작 정점을 queue에 enqueue한다. 방문 표시 후에 dequeue를 한다. 인접 정점을 모두 enqueue하고 방문 표시를 한다. 다시 dequeue를 하며 인접 정점을 찾는 것을 반복한다. 모든 정점을 방문하고 queue가 null이 될 때까지 반복한다. 결과는 dequeue한 순서이다.

  1. 장점

     • 최적해를 찾음을 보장한다.

  2. 단점

     • 최소 실행시간보다는 오래 걸린다는 것이 거의 확실하다.
     • 최악의 경우, 실행에 가장 긴 시간이 걸릴 수 있다.

• 최소 신장 트리(MST)

  spanning tree 중에서 사용된 간선들의 가중치 합이 최소인 트리이다. 간선의 가중치를 고려하여 최소 비용의 스패닝 트리를 선택하는 것이다. 일단 본래의 그래프의 모든 노드를 포함하여야 하고, 간선의 가중치의 합이 최소여야 한다. 모든 노드가 서로 연결되어 있고, 사이클이 생기면 안된다. 간선의 갯수는 n-1이여야 한다.

  • Kruskal

    크루스칼의 핵심은 모든 간선을 가중치 기준으로 오름차순으로 정렬하고, 이 간선들을 순서대로 모든 정점이 연결될 때까지 연결하는 것이다. Union-Find 알고리즘을 이용해서 구현할 수 있고, 이를 통해 사이클이 형성되지 않으면서 모든 정점을 연결할 수 있다.

    로직은 그래프의 간선들을 가중치 기중 오름차순으로 정렬한다. 정렬된 간선 리스트를 순서대로 선택하여, 간선의 정점들을 연결한다. 이때 정점을 연결하는 것은 union-find의 union으로 구현한다. 만약 간선의 두 정점이 이미 연결되어 있다면 스킵한다. 위 과정을 반복하여 최소 비용의 간선들만 이용하여 모든 정점이 연결된다.

  • Prim

    프림의 핵심은 트리 집합을 단계적으로 확장하는 것이고, 새로운 정점을 연결할 때마다 새로운 정점에서 갈 수 있는 아직 연결되지 않은 정점들에 대한 간선을 추가해줘야 한다.Priority Queue를 이용한 최소 힙으로 구현할 수 있고, 다익스트라 알고리즘과 구현 방식이 유사하다.

    로직은 임의의 정점을 시작점으로 선택하여, 시작점에서 갈 수 있는 정점 중 가장 가중치가 작은 정점을 연결한다. 시작점과 연결된 정점들의 집합에서 갈 수 있는 이 집합에 포함되어 있지 않은 가중치가 가장 작은 정점을 연결한다. 위 과정을 반복하여 모든 정점이 연결될 때까지 반복한다.

  • 특징

    둘다 MST를 구하는 알고리즘이지만 동작 방식이 다르기에 상황에 따라 잘 사용하여야 한다. 그래프의 간선이 많다면 프림 알고리즘이 유리하고, 간선이 적을 경우 크루스칼 알고리즘이 유리하다.

• Dijkstra

  다익스트라 알고리즘은 DP를 활용한 대표적인 최단 경로 알고리즘이다. 인공위성 GPS 소프트웨어 등에서 가장 많이 사용된다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줍니다.

  로직은 출발 정점을 기준으로 각 정점의 최소 비용을 저장한다. 방문하지 않은 정점 중에서 가장 비용이 적은 를 선택한다. 해당 정점를 거쳐서 특정한 정점으로 가는 경우를 찾아 최소 비용을 갱신한다. 위 과정을 반복한다. 위 과정을 모두 반복하면 정점과 모든 정점 사이의 최소 거리를 찾을 수 있게 된다.

  • 특징

    선형 탐색으로 찾도록 만들었을 경우 시간 복잡도가 O(N^2)이지만 더 빠르게 구동해야 하는 경우 힙을 활용하여 만들면 O(NlogN)으로 만들 수 있다. 선형 탐색으로 만들 경우 정점의 갯수가 많은데 간선이 적을 때 비효율적으로 작동한다. 힙 구조일 때는 정점과 간선의 갯수의 상관없이 안정적으로 처리할 수 있다.

• 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)

  다익스트라는 하나의 정점에서 다른 모든 정점까지의 거리를 구하는 알고리즘이었다면, 플로이드-워셜 알고리즘은 한 번 실행하여 모든 노드 간 최단 경로를 구할 수 있다. 다익스트라와는 다르게 음의 간선도 사용할 수 있다. 기본적으로 DP를 사용하여 구현할 수 있다.

  로직은 2차원 인접 행렬을 사용한다. 2차원의 인접 행렬 표를 이용하여 모든 정점과 정점 사이의 거리를 행렬로 채운다. 1번의 이동으로 갈 수 없는 부분은 무한으로 해놓고 진행한다. X에서 Y로 가는 최소 비용과 X에서 1로 가는 것과 1에서 Y로 가는 비용을 계산한다. 만약 X에서 1로 가는 것과 1에서 Y로 가는 것이 더 비용이 적다면, D[X,Y]는 D[X,1] + D[1,Y]로 교체하는 방식으로 1을 거쳐가는 경우를 모두 계산하여 표를 채운다. 위와 같은 방식으로 모든 정점의 최소 비용을 계산하면 된다.

  • 특징

    시간 복잡도는 O(V^3)으로 고정적이다. 그래프의 정점의 갯수만 알면 다익스트라에 비해 더 효율적일 수 있다.

• 동적 프로그래밍(DP)

  반복되는 작은 문제들의 변하지 않는 답을 통해 큰 문제의 정답을 구하는 방법이다. 하향식(메모제이션)과 상향식(타뷸레이션)이 있는데, 하향식은 하위 문제에 대한 정답을 계산했는지 확인해가며 문제를 자연스러운 방식으로 풀어 나가는 방법이다. 상향식은 더 작은 하위 문제부터 살펴본 다음 작은 문제의 정답을 이용해서 큰 문제의 정답을 풀어나가는 방법이다.

• 백트래킹

  백트래킹은 가능한 모든 방법을 탐색하는 알고리즘이다. 상태 공간을 트리로 나타낼 수 있을 때, 모든 경우의 수를 정부 고려하는 알고리즘이다. 유망하지 않다면 배제하고 부모 노드로 돌아가서 풀이 시간을 단축해 나간다.

• 재귀함수(Recursion)

  함수 안에서 자기 자신을 호출하는 함수로 반복문을 통해 구현한 코드보다 더 직관적일 수 있다. 하지만 스택 오버플로우가 발생할 수 있다.

• 탐욕법(Greedy)

  탐욕법은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 순간마다 선택은 최적이지만, 그 선택들을 수집하여 최종적인 해답을 구했을 때 최적이라는 보장은 없다. 탐욕법은 2가지 조건이 성립하여야 하는데 탐욕적 선택 속성은 앞의 선택이 이후의 선택에 영향을 주지 않아야한다. 최적 부분 구조는 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다. 이 두가지 조건이 성립하지 않는 경우에는 최적해를 찾지 못한다.

• 이진 탐색 트리(BST)

  이진 탐색 트리는 이진 트리의 구조를 갖으나, 자료의 검색,삭제,삽입,정렬 등에 효율적이게 한 트리 자료 구조입니다. 삽입하거나 삭제시에 올바른 위치를 찾아 곧바로 넣거나 뺄 수 있다. 삽입과 삭제 시에는 다시 정렬을 해야 이진 탐색이 가능하다. 최소값과 최대값을 찾는데 용이하다. 제일 위쪽에 루트 노드가 있고, 각 노드는 1개의 키값을 가진다. 각 노드는 자식 노드를 2개씩 갖는데, 왼쪽의 자식 노드는 자신보다 작은 수를 넣고 오른쪽에는 자신보다 큰 노드를 갖는다.

  구현시에는 삽입과 삭제, 검색을 모두 구현해야 한다. 먼저 자식 노드를 가지는 구조체를 만들어 관리하고, 노드를 삽입할 시에는 현재 노드와 크기를 비교하여 좌 우로 내려갈 지 정한 후에 자식 노드가 없는 곳에 삽입하면 된다. 노드의 삭제는 삭제하는 노드의 서브 트리에서 최소값을 삭제하는 노드에 덮어 씌우고, 이후에 나머지 값을 갱신하면 된다.

• 시간 복잡도

  DFS	BFS	Kruskal	Prim	Dijkstra	Floyd-Warshall Algorithm
  O(N^2)/O(N+E)	O(N^2)/O(N+E)	O(ElogE)	O(ElogV+VlogV)	O(|V|^2+|E|)	O(N^3)

  • BST

  종류	검색	삽입	삭제
  배열	O(logN)	O(N)	O(N)
  연결리스트	O(N)	O(N)	O(1)

디자인 패턴

• 생성 패턴(추상 객체 인스턴스화)

  
  

  • 추상 팩토리(Abstract Factory)

    구체적인 클래스에 의존하지 않고 서로 연관되거나 의존적인 객체들의 조합을 만드는 인터페이스를 제공하는 패턴으로 이 패턴을 통해 생성된 클래스에서는 사용자에게 인퍼레이스를 제공하고, 구체적인 구현은 Con-crete Product 클래스에서 이루어지는 특징을 갖는 디자인 패턴이다.

  
  

  • 팩토리(Factory Method)

    상위 클래스에서 객체를 생성하는 인터페이스를 정의하고, 하위 클래스에서 인스턴스를 생성하도록 하는 방식으로 상위 클래스에서 인스턴스를 만드는 방법만 결정하고, 하위 클래스에서 그 데이터의 생성을 책임지고 조작하는 함수들을 오버로딩하여 인터페이스와 실제 객체를 생성하는 클래스를 분리할 수 있는 특성을 갖는 디자인 패턴이다.

  
  

  • 빌더(Builder)

    복잡한 인스턴스를 조립하여 만드는 구조로, 복합 객체를 생성할 때 객체를 생성하는 방법과 객체를 구현하는 방법을 분리함으로써 동일한 생성 절차에서 서로 다른 표현 결과를 만들 수 있는 디자인 패턴이다.

  
  

  • 프로토타입(Prototype)

    처음으로 일반적인 원형을 만들어 놓고, 그것을 복사한 후 필요한 부분만 수정하여 사용하는 패턴으로, 생성할 객체의 원형을 제공하는 인스턴스에서 생성할 객체들의 타입이 결정되도록 설정하며 객체를 생성할 때 갖추어야 할 기본 형태가 있을 때 사용되는 패턴이다.

  
  

  • 싱글톤(Singleton)

    전역 변수를 사용하지 않고 객체를 하나만 생성하도록 하며, 생성된 객체를 어디에서든지 참조할 수 있도록 하는 디자인 패턴이다.

• 구조 패턴(객체 결합)

  
  

  • 어댑터(Adapter)

    기존에 생성된 클래스를 재사용할 수 있도록 중간에서 맞춰주는 역할을 하는 인터페이스를 만드는 패턴으로, 상속을 이용하는 클래스 패턴과 위임을 이용하는 인스턴스 패턴의 두 가지 형태로 사용되는 디자인 패턴이다.

  
  

  • 브리지(Brigde)

    기능의 클래스 계층과 구현의 클래스 계층을 연결하고, 구현부에서 추상 계층을 분리하여 추상화된 부분과 실제 구현 부분을 독립적으로 확장할 수 있는 디자인 패턴이다.

  
  

  • 컴포지트(Composite)

    객체들의 관계를 트리 구조로 구성하여 부분-전체 계층을 표현하는 패턴으로, 사용자가 단일 객체와 복합 객체 모두 동일하게 다루도록 하는 패턴이다.

  
  

  • 데코레이터(Decorator)

    기존에 구현되어 있는 클래스에 필요한 기능을 추가해 나가는 설계 패턴으로 기능 확장이 필요할 때 객체 간의 결합을 통해 기능을 동적으로 유연하게 확장할 수 있게 해주어 상속의 대안으로 사용되는 디자인 패턴이다.

  
  

  • 파사드(Facade)

    복잡한 시스텐에 대하여 단순한 인터페이스를 제공함으로써 사용자의 시스템 간 또는 여타 시스템과의 결합도를 낮추어 시스템 구조에 대한 파악을 쉽게 하는 패턴으로 오류에 대해서 단위별로 확인할 수 있게 하며, 사용자의 측면에서 단순한 인터페이스 제공을 통해 접근성을 높일 수 있는 디자인 패턴이다.

  
  

  • 플라이웨이트(Flyweight)

    다수의 객체로 생성될 경우 모두가 갖는 본질적인 요소를 클래스화 하여 공유함으로써 메모리를 절약하고, ‘클래스의 경량화’를 목적으로 하는 디자인 패턴이다.

  
  

  • 프록시(Proxy)

    실체 객체에 대한 대리 객체로 실체 객체에 대한 접근 이전에 필요한 행동을 취할 수 있게 만들며, 이 점을 이용해서 미리 할당하지 않아도 상관없는 것들을 실제 이용할 때 할당하게 하여 메모리 용량을 아낄 수 있으며, 실체 객체를 드러나지 않게 하여 정보은닉의 역할도 수행하는 디자인 패턴이다.

• 행위 패턴(객체 간 커뮤니케이션)

  
  

  • 책임 체인(Chain of Responsibility)

    정적으로 어떤 기능에 대한 처리의 연결이 하드 코딩 되어있을 때 기능 처리의 연결 변경이 불가능한데, 이를 동적으로 연결되어 있는 경우에 따라 다르게 처리될 수 있도록 연결한 디자인 패턴이다.

  
  

  • 커맨드(Command)

    실행될 기능을 캡슐화함으로써 주어진 여러 기능을 실행항 수 있는 재사용성이 높은 클래스를 설계하는 패턴으로 하나의 추상 클래스에 메서드를 만들어 각 명령이 들어오면 그에 맞는 서브 클래스가 선택되어 실행되는 특징을 갖는 디자인 패턴이다.

  
  

  • 인터프리터(Interpreter)

    언어의 다양한 해석, 구체적으로 구문을 나누고 그 분리된 구문의 해석을 맡는 클래스를 각각 작성하여 여러 형태의 언어 구문을 해석할 수 있게 만드는 디자인 패턴이다.

  
  

  • 반복자(iterator)

    컬렉션 구현 방법을 노출시키지 않으면서도 그 집합체 안에 들어있는 모든 항목에 접근할 방법을 제공하는 디자인 패턴이다.

  
  

  • 중재자(Mediator)

    객체지향 설계에서 객체의 수가 너무 많아지면 서로 간 통신을 위해 복잡해져서 객체지향에서 가장 중요한 느슨한 결합의 특성을 해칠 수 있기 때문에 이를 해결하는 방법으로 중간에 이를 통제하고 지시할 수 있는 역할을 하는 중재자를 두고, 중재자에게 모든 것을 요구하여 통신의 빈도수를 줄여 객체지향의 목표를 달성하게 해주는 디자인 패턴이다.

  
  

  • 메멘토(Memento)

    클래스 설계 관점에서 객체의 정보를 저장할 필요가 있을 때 정용하는 디자인 패턴으로 Undo 기능을 개발할 때 사용하는 디자인 패턴이다.

  
  

  • 옵저버(Observer)

    한 객체의 상태가 바뀌면 그 객체에 의존하는 다른 객체들에 연락이 가고 자동으로 내용이 갱신되는 방버으로 일대 다의 의존성을 가지며 상호작용하는 객체 사이에서는 가능하면 느슨하게 결합하는 디자인 패턴이다.

  
  

  • 상태(State)

    객체 상태를 캡슐화하여 클래스함으로써 그것을 참조하게 하는 방식으로 상태에 따라 다르게 처리할 수 있도록 행위 내용을 변경하여, 변경 시 원시코드의 수정을 최소화할 수 있고, 유지보수의 편의성도 갖는 디자인 패턴이다.

  
  

  • 전략(Strategy)

    알고리즘 군을 정의하고(추상 클래스) 같은 알고리즘을 각각 하나의 클래스로 캡슐화한 다음, 필요할 때 서로 교환해서 사용할 수 있게 하는 패턴으로, 행위 클래스로 캡슐화해 동적으로 행위를 자유롭게 바꿀 수 있게 해주는 디자인 패턴이다.

  
  

  • 템플릿 메소드(Template Method)

    어떤 작업을 처리하는 일부분을 서브 클래스로 캡슐화해서 전체 일을 수행하는 구조는 바꾸지 않으면서 특정 단계에서 수행하는 내역을 바꾸는 패턴으로 일반적으로 상위클래스(추상 클래스)에는 추상메서드를 통해 기능을 골격을 제공하고, 하위 클래스(구체 클래스)의 메서드에는 세부 처리를 구체화하는 방식으로 사용하며 코드 양을 줄이고 유지보수를 용이하게 만드는 특징을 갖는 디자인 패턴이다.

  
  

  • 방문자(Visitor)

    각 클래스 데이터 구조로부터 처리 기능을 분리하여 별도의 클래스를 만들어 놓고 해당 클래스의 메서드가 각 클래스를 돌아다니며 특정 작업을 수행하도록 만드는 패턴으로, 객체의 구조는 변경하지 않으면서 기능만 따로 추가하거나 확장할 때 사용하는 디자인 패턴이다.