개발자 면접 질문 정리 - 알고리즘

알고리즘

정렬 알고리즘 (Sorting Algorithm)

[ Bubble Sort, Heap Sort, Merge Sort, Quick Sort, Insert Sort ]

Bubble Sort

서로 인접해 있는 두 원소를 비교하며 정렬하는 알고리즘이다. 0번 인덱스 부터 n-1번 인덱스까지 모든 인덱스를 비교하면 정렬 시간복잡도는 O(n^2)

Heap Sort

데이터를 바이너리 힙 자료구조에 담아서 최대값이나 최소값부터 하나씩 꺼내서 정렬하는 알고리즘이다. 시간 복잡도는 O(nlogn)

Merge Sort

Divide and conquer 의 원리로 원소 한개씩 나누어 결합(Combine) 과정에서 원소끼리 비교후 정렬되어 임시 배열에 저장하고, 정렬이 다되면 임시배열을 복사하여 결과 목록을 만든다. 시간복잡도는 Worst case에서도 O(nLogn) 를 가지는 장점이 있다.

Quick Sort

가장 빠른 기법이라고 하여 Quick 이름이 붙여졌지만 Worst Case 에서는 O(n^2) 이 나올수 있다. Merge Sort 와 같이 Divide and conquer 원리를 사용하고, Divide 과정에서 pivot 개념이 사용된다. pivot을 기준으로 좌,우측의 배열을 다시 재귀적으로 Quick Sort 하여 분할 하는 과정을 거친다. 시간 복잡도는 O(nlogn)

Insert Sort

두번째 값부터 시작하며, 그 앞에 있는 원소들과 비교하여 삽입할 위치를 찾아 삽입하며 정렬하는 알고리즘. 시간 복잡도는 O(n^2) 이며
Best Case는 O(n)이다.

동적 프로그래밍 (DP, Dynamic Programming)

동적 프로그래밍(Dynamic Programming)은 주어진 문제를 풀기 위해, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 결과를 결합하여 해결하는 방식. 동적 프로그래밍에서는 어떤 부분 문제가 다른 문제들을 해결하는데 사용될 수 있어, 답을 여러 번 계산하는 대신 한 번만 계산하고 그 결과를 재활용하는 메모이제이션(Memoization) 기법으로 속도를 향상 시킬 수 있다.

동적 프로그래밍의 조건

동적 프로그래밍(Dynamic Programming)으로 문제를 해결하기 위해서는 주어진 문제가 다음의 조건을 만족해야 한다.

Overlapping Subproblem(중복되는 부분문제): 주어진 문제는 같은 부분 문제가 여러번 재사용된다.
Optimal Substructure(최적 부분구조): 새로운 부분 문제의 정답을 다른 부분 문제의 정답으로부터 구할 수 있다.

탐색 알고리즘

DFS와 BFS

그래프 탐색에서 사용되는 탐색 기법

DFS는 (Depth First Search) 특정 노드에서 시작하여 해당 분기(Branch)를 끝까지 탐색한 이후 다음 분기로 이동하여 탐색하는 방법
자기 자신을 호출하는 순환 알고리즘 형태이며, 어떤 노드를 방문했었는지 방문 정보를 저장해야함 DFS는 스택이나 재귀호출을 사용하여 구현할 수 있다.

BFS는 (Breath First Search) 특정 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법. 최단 경로를 찾을 때 사용. 재귀적으로 동작하지 않고 DFS와 마찬가지로 방문 정보를 저장해야함. 큐(Queue)를 사용하여 구현할 수 있다.