티스토리 뷰
자료구조와 알고리즘에 대해 설명하시오
자료구조는 데이터를 원하는 규칙, 목적에 맞게 저장하기 위한 구조이고
알고리즘은 자료구조에 쌓인 데이터를 활용해 어떠한 문제를 해결하기 위한 여러 동작들의 모임이다.
도서관에서 책장이 자료구조라면 특정 책을 찾는 방법이 알고리즘이다.
해시 테이블에 대해 설명하시오
해시 테이블은 자료를 쉽고 빠르게 저장할 수 있고 key-value를 대응시켜 자료를 얻을 수 잇다.
효율적인 탐색을 위한 자료구조이며 쉽게 접할 수 있는 예로는 자바스크립트의 객체, local, session Storage가 있다.
해시 테이블에서 가장 중요한 부분은 해시 함수인데 해시 함수는 특정 키를 자료를 저장하는 배열의 인덱스로 변환한다.
좋은 해시 함수가 되기 위해서는 결정성, 효율성, 균일한 분배가 필요하다.
해싱의 첫번째 기법은 해시 테이블의 인덱스의 개수를 소수로 결정하는 것이다.
이는 소수를 사용한 모듈러 나눗셈이 균일한 방식으로 배열 인덱스를 생성하기 때문이다.
같은 인덱스에 두 개 이상을 저장할 수 없기 때문에 충돌이 발생한다. 이때 충돌을 막기 위해서 탐사 해싱 기법을 사용한다.
대표적인 예로는 선형 탐사, 이차 탐사 등이 있다.
접근에는 평균 O(1)의 시간이지만 최악의 경우는 O(n)이 걸린다.
스택에 대해 설명하시오
스택은 자료구조의 일종으로, 후입선출(last in first out)이다. 즉 마지막에 삽입된 항목만을 제거하고 접근할 수 있다.
상자를 쌓고 상자를 뺀다고 생각하면 쉽다. 자스에서 배열로 만들수도 있고 LinkedList로 만들 수도 있다.
배열로 만들면 push, pop을 이용하면 된다. 스택도 마찬가지로 push, pop이란 메소드를 갖는다. DFS나 재귀에서 사용된다.
접근 O(n), 검색 O(n), 들여다보기(peek) O(1), 삽입 O(1), 삭제 O(n^3) (LinkedList로 만들면 O(1))
큐에 대해 설명하시오
큐는 자료구조의 일종으로, 선입선출(first in first out)이다. 즉 첫번째로 추가된 항목만을 제거할 수 있다.
가게에 줄을 서서 앞사람 붙터 물건을 산다고 생각하면 쉽다. 자스에서 배열로 만들수도 있고 LinkedList로 만들 수도 있다.
배열로 만들면 push, shift를 이용하면 된다. 큐는 enqueue, dequeue라는 메소드를 갖는다. BFS나 캐시를 구현할 때 사용한다.
접근 O(n), 검색 O(n), 들여다보기(peek) O(1), 삽입 O(1), 삭제 O(1)
?? pop은 O(1) shift는 O(n) 생각해보면 당연 shift는 인덱스를 수정하니
검색(탐색)에 대해 설명하시오
검색에는 크게 선형검색과 이진검색이 있다. 선형검색은 앞에서부터 차례대로 검색하는 방식으로 가장 기본적인 검색이다. 시간복잡도는 O(n)
이진검색은 정렬된 상태에서만 사용할 수 있다. 중간 인덱스를 확인해 절반씩 범위를 줄여가며 검색한다. 시간복잡도는 O(log(2) n)=O(logn)
정렬에 대해 설명하시오
정렬의 종류에는 버블정렬, 선택정렬, 삽입정렬, 병합정렬, 빠른정렬, 계수정렬 등이 있다.
버블정렬은 앞에서부터 두개씩 비교해서 왼쪽이 더 크다면 바꾼다. 이 방식을 반복해서 가장 큰 원소를 맨 오른쪽에 할당한다.
그리고 맨 오른쪽 원소를 제외한 배열에서 같은 작업을 반복하면 정렬이 된다. O(n^2)으로 최악이다.
선택정렬은 처음에 가장 작은 원소를 선택해서 첫번째 원소와 바꾼다. 그렇게 첫번째 원소는 정렬된 상태가 됬다.
이제 두번째 원소부터 마지막 원소중에서 가장 작은 원소를 선택해서 두번째 원소와 바꾼다. 이를 반복해서 정렬한다. O(n^2)으로 최악이야
삽입정렬은 배열을 순차적으로 검색하면서 정렬되지 않은 항목들을 배열의 왼쪽의 정렬된 부분으로 이동시키며 정렬한다.
즉 정렬된 부분의 배열 개수가 처음에는 1이 였을때, 정렬할 두번째 원소를 정렬된 부분으로 이동시키고 그 안에서 정렬한다.
이 경우 두번째 원소가 첫번째 원소보다 작은 경우 바꾼다. n번째 원소를 정렬된 부분으로 이동시킬때 왼쪽 정렬의 오른쪽부터 비교하면서 n번째 원소가
더 크다면 바꾸고 만약 더 작게 되는 경우에 멈추면 된다. 이렇게 하면 정렬이 된다. O(n^2)
병합정렬은 분할 정복이라는 알고리즘에 의해 만들어진 정렬이다. 배열들을 하나의 항목이 될때까지 계속 분할을 하고(n개에서 2/n개로) 병합하는 것이다.
O(nlog(2)n)=O(nlogn) 실제 정렬에서도 쓰이는 정렬방법이다.
빠른정렬은 너무 어렵다. O(nlogn)
1. 배열의 중간 지점에 위치한 원소(피봇)을 선택
2. 2개의 포인터를 생성. 피봇보다 더 큰 원소가 나올 때까지 좌측 포인터를 움직이고,
피봇보다 더 작은 원소가 나올 때까지 우측 포인터를 움직인 다음, 두 포인터에 해당하는 원소를 서로 교환한다.
이 과정을 좌측 포인터가 우측 포인터보다 더 커질 때까지 반복
이로써 피봇보다 작은 원소는 좌측에, 큰 원소는 우측에 나열
이걸 파티션이라 한다.
3. 피봇을 중심으로 나뉜 두 서브배열에 대해 정렬이 끝날 때까지 위 과정을 재귀적으로 반복
힙 정렬은 밑에 따로
계수 정렬은 숫자에 대해서만 동작, 특정 범위도 주어져야 한다. 각 항목의 등장 횟수를 센다. 객체(해시 테이블)를 이용한다. O(k+n)
LinkedList을 배열과 비교하여 설명하시오
LinkedList는 노드가 연결되어 있다. 단방향, 양방향 LinkedList가 있고 head, tail이 있다.
노드는 data와 next를 가진다. next는 다음 노드를 가리킨다.(prev는 생략 편의상)
LinkedList에서 특정 값에 접근을 하려면 head부터 차례대로 접근을 해야되기 때문에 O(n)이다.
반면 배열은 인덱스를 가지고 있기 때문에 O(1)로 접근이 가능하다.
LinkedList에서 삽입, 삭제를 하려면 O(1)인데 배열은 O(n)이다.
저장방식도 배열에서 요소들은 인접한 메모리 위치에 연이어 저장된다. 반면 LinkedList에서 새로운 element들은 memory 어딘가에 저장되어 되어지고
Linkedlist에서는 새로운 요소에 할당된 메모리 위치 주소가 linkedlist의 이전 요소에 저장된다.
배열에서 메모리는 선언 시 컴파일 타임에 할당이 된다.(정적 메모리 할당) 반면 Linkedlist에서는 새로운 요소가 추가될 때 런타임에 메모리를 할당한다.(동적 메모리 할당)
배열은 Stack 섹션에 메모리 할당이 이루어 진다. 반면 Linkedlist는 Heap 섹션에 메모리 할당이 이루어진다.
BinaryTree와 BinarySearchTree에 대해 설명하시오
이진탐색트리 BST(BinarySearchTree)는 이진 탐색과 연결 리스트를 결합한 자료구조이다.
이진 탐색의 효율적인 탐색능력을 유지하면서, 빈번한 자료 추가, 삭제가 가능하다.
이진 탐색 트리는 왼쪽 트리의 값이 부모 노드보다 작아야 하고, 오른쪽 트리의 값이 부모 노드보다 커야 한다.
탐색, 삽임, 삭제의 시간 복잡도는 O(h) 즉 트리의 높이이다.O(log(2)n) 최악의 경우 O(n)이다.
불균형인 경우 시간 복잡도가 높아지는데 이를 해결하기 위한 트리로 AVL트리가 있다.
힙에 대해 설명하시오
다른 자료 구조와 달리 힙은 자식에 대한 포인터를 갖는 대신에 배열을 사용해 자료를 저장한다.
배열에서 힙 노드의 자식 위치(인덱스)를 쉽게 계산할 수 있다.
힙을 사용하면 부모와 자식 간의 관계를 쉽게 정의할 수 있기 때문이다.
최대 힙의 경우 부모가 자식보다 크고 최소 힙의 경우 부모가 자식보다 작다.
우선순위 큐에 사용
그래프에 대해 설명하시오
비선형
그래프는 네트워크 구조를 추상화한 모델로, 간선(edge)으로 연결된 노드(node)(정점(vertex))의 집합이다.
페이스북, 트위터 등의 소셜 네트워크도 그래프로 표시할 수 있고 도로, 항로, 통신을 나타낼 때도 그래프가 활용된다.
너비우선검색(bfs)는 같은 단계(차수)에 있는 이웃 노드들을 우선 방문하면서 그래프를 순회한다. O(V+E)
깊이우선검색(dfs)은 한 노드와 연결된 노드를 깊이 방향으로 우선 방문하면서 그래프를 순회한다. O(V+E)
다익스트라의 알고리즘은 한 정점에서 나머지 정점들까지의 최단 경로를 찾는다.
다익스트라의 알고리즘은 목적지에 도달하기 위해 각 단계에서 최단 경로를 취하는 방식으로 동작한다.
처음에는 일부 노드에 도달할 수 없을 수도 있기 때문에 거리를 무한으로 표기한다.
그러고 나서 각 순회 반복 루프 때마다 각 노드에 대한 최단 경로를 선택한다.
최소 스패닝 트리 MST(Minimum Spanning Tree)는 그래프의 edge weight값이 최소인 스패닝 트리를 말한다.
스패닝 트리란 그래프의 모든 vertex가 cycle없이 연결된 상태이다.
n개의 vertext를 가지는 그래프에서 반드시 n-1개의 edge를 사용해야 하면 사이클이 형성되서는 안된다.
kruskal과 prim알고리즘을 통해 MST를 만들 수 있다.
크루스칼 알고리즘은 가중치를 기준으로 정렬한 후에 MST가 될때까지 간선을 하나씩 선택 또는 삭제해가는 방식이다.
사이클을 형성하는 간선은 추가하지 않고 간선의 수가 정점의 수보다 하나 작을 때 MST가 완성된다.(그리디 알고리즘 방식)
프림 알고리즘은 시작 정점부터 단계적으로 트리를 확장하는 방법이다.