기술면접 | 알고리즘

Bubble Sort는 정렬 알고리즘으로, 서로 인접한 원소를 비교하여 크기의 순서에 맞게 정렬을 수행하는 알고리즘입니다. 배열의 크기가 n일때, 0번 index부터 n-1번 index까지 모든 index를 순차적으로 비교하면서 정렬합니다. 매 회전마다 가장 큰 원소가

in-place sorting, 최솟값입력 배열 이외에 추가 메모리를 요구하지 않는 in-place sorting(제자리 정렬) 알고리즘 중 하나로, O(n^2)의 시간복잡도를 가지는 정렬 알고리즘입니다. 선택 정렬은 첫번째 index부터 해당 index를 기준으로 이

key, in-place sorting, 앞 배열 정렬삽입 정렬은 추가적인 메모리 공간을 필요로 하지 않는 in-place 정렬(제자리 정렬) 알고리즘 중 하나로, 매 회전 마다 새로운 원소가 이미 정렬이 되어있는 앞의 배열에서 어느 위치에 들어갈지 계산하여 삽입하는

분할 정복, 분할, 재귀, 합병합병 정렬은 분할 정복 알고리즘을 기반으로 한 정렬 알고리즘으로, 입력 배열을 같은 크기의 2개의 부분 배열로 분할하고 부분 배열을 정렬하는데, 이 때 부분 배열의 크기가 최소가 될 때까지 재귀적으로 반복합니다. 그리고 정렬된 부분 배열을

heap,Heap Sort는 heap 자료구조를 기반으로 정렬을 수행하는 알고리즘입니다. 내림차순 정렬을 위해서는 최대 힙, 오름차순을 위해서는 최소 힙 자료구조를 사용할 수 있습니다. 주어진 배열의 n개의 요소를 Heap에 삽입하고, 하나씩 삭제하면서 이를 새로운 배

평균,최악,pivot퀵 정렬은 평균적으로 O(NlogN)의 시간복잡도를 가지는 정렬이며, 같은 시간복잡도의 다른 정렬 알고리즘보다 일반적으로 빠른 정렬 알고리즘입니다. 이는 퀵 정렬의 특성상 매 단계에서 적어도 1개의 원소가 자신의 자리를 찾게 되기 때문에, 단계를 거

자리수, 메모리, 비교 연산기수 정렬은 낮은 자리수부터 비교하며 정렬을 수행하는 알고리즘입니다. 비교 연산을 수행하지 않기 때문에 정렬 속도가 빠르지만, 추가적인 메모리 공간을 필요로 합니다. 또 부동 소수점과 같이 자릿수가 없는 것은 정렬할 수 없습니다.동작원리를 간

counting,메모리 공간, 수의 범위계수 정렬은 주어진 배열에서 특정 숫자가 몇 번 등장했는지 counting하여 정렬을 수행하는 기법입니다. 숫자간 비교 없이 단순히 배열을 순회하고, 이후에 개수가 기록된 테이블을 순회하기 때문에, 시간복잡도는 O(n+k)입니다.

모든 노드 간의, 음의 간선, 인접 행렬, 중간 노드모든 노드 간의 최단거리를 구하는 문제가 있을 때, 플로이드-워셜 알고리즘을 사용합니다. 다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 (Single Source Shortest Path) 알고

다익스트라 알고리즘처럼, 특정 정점에서 각 노드로의 최단 거리를 구할 수 있는 알고리즘입니다. 하지만 다익스트라와 다른 것은 음의 간선이 존재하는 경우에도 적용 가능한 알고리즘이라는 것입니다. 또 구현 상에서 다익스트라와 다른 것은, 다익스트라는 간선을 기준으로, 현재

A\* 알고리즘은 가중치 그래프에서 특정 노드와 특정 노드 간의 최단 경로를 파악할 수 있는 그리디 알고리즘입니다. 먼저, 시작 노드부터 현재 노드까지의 비용을 G(n), 현재 노드에서 목표 노드까지의 예상 비용을 H(n)이라고 할 때, 이 두 값을 더한 F(n)을 최

큰 문제, 작은 문제, 겹치는 부분 문제, 최적 부분 구조, Top-Down, Bottom-up, Memoization, TabulationDP는 큰 문제를 작은 문제로 쪼개서 문제를 해결하는 일종의 패러다임입니다. DP를 사용하기 위해서는 2가지 조건을 만족해야 하는

부분 수열, 불연속, 문자열, 연속, DP, 2차원 배열, 점화식, 문자간 비교, 왼쪽 대각 먼저 subsequence와 substring의 차이를 말씀드리면, subsequence는 부분수열로, 연속되지 않은 문자열도 고려하지만 substring은 문자열로, 연속된

DP, 오름차순, 부분 수열, 이분 탐색LIS 문제는 DP를 이용해 빠르게 해결할 수 있는 대표적인 문제입니다. 특정 수열이 주어졌을때, 해당 수열의 부분 수열 중 오름차순으로 이루어진 부분 수열들이 있습니다. 그 중에서 가장 긴 부분 수열을 찾는 것이 이 문제의 목표

전체문제, 서브문제, 독립적분할정복은 전체 문제를 서브 문제들로 나누어서 문제를 해결하고 이를 합쳐 전체 문제를 해결하는 전략입니다. 분할정복 기법을 적용하기 위해서는 몇가지 조건이 필요합니다. 먼저, 큰 문제와 작은 문제의 구조가 동일해야 합니다. 즉, 큰 문제를 작

매 선택의 순간, 최적, 지역 최적해, 전역 최적해, 매트로이드Greedy 기법은 매 선택의 순간마다, 그 순간에 최적의 상황으로 나아가며 최종적인 해를 구하는 기법입니다. 항상 최적해를 구하는 것이 아닌, 최적해에 빠르게 근사하는 기법이라고 할 수 있습니다. 그래서

정렬된 배열, 하한값, 상한값, 중간값이진 탐색은 정렬된 배열에서 특정한 값을 빠르게 찾아내는 알고리즘입니다. 매번 하한값과 상한값 사이의 중간값에 접근하여, 목표하는 값과의 비교를 통해 하한과 상한의 격차를 줄여나가며, O(logN)의 시간복잡도로 탐색을 수행할 수