[면접대비] 알고리즘
본문 로딩 중...
댓글 0
댓글을 작성하려면 로그인이 필요합니다.
아직 댓글이 없습니다. 첫 번째 댓글을 작성해보세요.
인접한 두 원소를 비교해 순서가 잘못되어 있으면 교환하는 과정을 반복합니다. 한번 순회할 때마다 가장 큰 값이 뒤쪽으로 이동하며 시간 폭잡도는 평균과 최악의 경우 O(N²)입니다.
정렬되지 않은 영역에서 가장 작은 값을 찾아 현재 위치의 값과 교환하는 과정을 반복하는 알고리즘입니다
항상 전체 미정렬 영역을 탐색하기 때문에 시간 복잡도는 O(N²)입니다
앞부분을 정렬된 영영으로 유지하면서 새로운 원소를 적절한 위치에 삽입하는 방식입니다.
이미 정렬된 경우 O(N)까지 빨라질 수 있습니다
Pivot을 하나 선택하고 Pivot보다 작은 값과 큰 값을 나누어 배치한 뒤, 나누어진 영역에 같은 과정을 재귀적으로 수행하는 분할 정복 정렬입니다.
평균 시간 복잡도는 O(NlogN)이고 최악의 경우 O(N²)입니다
Pivot이 계속 최솟값이나 최댓값으로 선택되어 배열이 0:N-1처럼 극단적으로 불균형하게 분할되는 경우입니다
Pivot은 배열을 두 영역으로 분할하기 위한 기준값입니다. Pivot 보다 작은 값은 앞으로, 큰 값은 뒤로 배치하여 각각을 다시 정렬합니다
배열을 절반씩 나누어 원소가 하나가 될 때까지 분할할 뒤, 나누어진 배열을 정렬하면서 다시 합치는 분할 정복 알고리즘입니
둘 다 분할 정복 방식이며 평균적으로 O(N log N)이지만, 퀵 정렬은 Pivot을 기준으로 분할하고 일반적인 배열 구현에서는 추가 메모리가 적은 반면 최악의 경우 O(N²)이 될 수 있습니다. 병합 정렬은 항상 O(N log N)을 보장하지만 배열 기준으로 병합 과정에 O(N)의 추가 메모리가 필요합니다
동일한 값을 가진 원소들의 기존 상대적인 순서가 정렬 후에도 유지되는 정렬입니다
삽입 정렬이 유리할 수 있습니다. 시간 복잡도가 O(N)에 가까워지기 때문입니다.
데이터의 처음부터 끝까지 순차적으로 확인하며 원하는 값을 찾는 탐색 방법입니다.
정렬된 데이터에서 중간값과 찾는 값을 비교하여 탐색 범위를 절반씩 줄여나가는 알고리즘입니다
정렬된 데이터에서 Lower Bound는 특정 값 이상이 처음 등장하는 위치, Upper bound는 특정 값을 초과하는 값이 처음 등장하는 위치를 찾는 방법입니다.
자기 자신을 다시 호출하여 문제를 더 작은 문제로 나누어 해결하는 방식입니다. 무한 호출을 방지하기 위해 종료 조건이 필요합니다
반복문은 하나의 함수 안에서 반복하지만 재귀는 자기 자신을 호출하며 각 호출 정보가 Call Stack에 쌓입니다.
코드가 간결하고 직관적이지만 함수 호출 비용과 스택 메모리가 필요하여 스택 오버플로우가 발생할 수 있습니다.
재귀 호출 등이 지나치게 많이 발생하면 함수의 지역 변수, 반환 주소 등의 호출 정보가 Call Stack에 쌓입니다. 이 크기가 스택의 허용 범위를 초과하면 Stack Overflow가 발생합니다
큰 문제를 여러 개의 작은 문제로 나누어 각각 해결한 뒤 그 결과를 결합하여 원래 큰 문제를 해결하는 알고리즘입니다.
퀵 정렬, 병합 정렬, 이진 탐색 등이 있습니다.
여러 개의 정점과 정점 사이의 관계를 나타내는 간선으로 구성된 자료구조입니다. 길 찾기, 네트워크, 관계 표현 등에 사용됩니다
하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘입니다. 음수 가중치가 있으면 사용할 수 없습니다.
시작 정점의 거리를 0으로 설정하고 현재까지 거리가 가장 짧은 정점을 선택해 인접 정점들의 최단 거리를 갱신하는 과정을 반복합니다. 우선 순위 큐를 사용하며 O((V+E) log V) 시간 복잡도를 가집니다
음수 간선이 존재하면 나중에 다른 경로를 통해 이미 확정한 거리가 더 작아질 수 있어 전제가 깨집니다
하나의 시작 정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘으로 모든 간선을 반복적으로 확인하여 거리를 갱신합니다. 음수 간선을 처리할 수 있고 음수 사이클도 판별할 수 있습니다.
다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하고, 플로이드 워셜은 모든 정점 쌍 사이의 최단 경로를 구합니다.
가중치가 있는 연결 무방향 그래프에서 모든 정점을 연결하면서 간선 가중치의 합이 최소가 되는 트리입니다.
간선을 가중치가 작은 순서대로 선택하면서 사이클이 발생하지 않도록 연결하여 MST를 만드는 알고리즘입니다. Union-Find를 사용하며 O(E log E)의 시간 복잡도를 가집니다
하나의 정점에서 시작해 현재 만들어진 트리와 연결할 수 있는 간선 중 가중치가 가장 작은 간선을 계속 선택하여 MST를 만드는 알고리즘입니다. 우선순위 큐를 이용해 구현할 수 있습니다
정점 사이에 선후 관계가 있는 그래프에서 모든 간선의 방향을 지키도록 정점을 순서대로 나열하는 알고리즘입니다.
DAG처럼 방향성이 있으면서 사이클이 없는 그래프에서 사용할 수 있습니다.
시작점에서 현재 위치까지 실제 비용 g(n)과 목표까지의 예상 비용 h(n)을 합한 값을 이용하여 목표 지점까지의 최단 경로를 탐색하는 알고리즘입니다.
다익스트라는 시작점으로부터의 실제 비용을 기준으로 모든 방향을 탐색하지만, A*는 여기에 목표까지의 예상 비용인 휴리스틱을 추가해 목표 방향을 우선 탐색합니다.
현재 위치에서 목표 지점까지 남은 비용을 추정하는 함수입니다.
맨해튼 거리는 가로와 세로 이동 거리의 합을 계산하며
유클리드 거리는 두 점 사이의 직선 거리로 계산합니다.
타일이나 Grid 기반 게임에서 NPC나 몬스터가 장애물을 피해 플레이어나 목표 위치까지 이동할 경로를 찾는데 사용할 수 있습니다
BFS는 목표의 방향을 고려하지 않고 주변을 넓게 탐색하지만 A*는 휴리스틱을 이용해 목표 방향의 노드를 우선 탐색합니다. 따라서 큰 맵에서는 탐색해야 하는 노드 수를 줄일 수 있어 효율적일 수 있습니다
현재 상황에서 가장 최선이라고 판단되는 선택을 반복하는 알고리즘입니다
하나의 선택을 하기 때문에 구현이 단순하고 빠르지만 전체 최적해를 보장하지 못할 수 있습니다
현재 단계에서 가장 좋은 선택이 이후 선택까지 고려한 전체적인 최적 선택과 항상 일치하지 않기 때문입니다
현재 선택이 전체 최적해에도 포함되는 탐욕적 선택 속성과 부분 문제의 최적해로 전체 문제의 최적해를 구할 수 있는 최적 부분 구조를 만족해야합니다
큰 문제를 부분 문제로 나누어 해결하고, 이미 계산한 결과를 저장하여 같은 문제를 다시 계산하지 않는 알고리즘 설계 기법입니다
동일한 작은 문제가 반복해서 등장하는 중복 부분 문제와 부분 문제의 최적해를 이용해 전체 문제의 최적해를 구할 수 있는 최적 부분 구조를 가지는 문제에 적합합니다.
한번 계산한 결과를 배열이나 딕셔너리에 저장해두고 같은 문제가 다시 등장하면 계싼하지 않고 저장된 결과를 사용하는 기법입니다
DP는 여러 선택의 결과를 비교하면서 부분 문제의 결과를 저장하여 전체 최적해를 구하는 방식이고, 그리디는 각 단계에서 현재 가장 좋은 선택 하나를 즉시 선택합니다.
가능한 경우를 탐색하다가 현재 경로가 정답이 될 수 없다고 판단하면 이전 상태로 돌아가 다른 경우를 탐색하는 알고리즘입니다.
모든 경우의 수를 직접 확인하여 정답을 찾는 완전 탐색 방식입니다
탐색 과정에서 현재 경로가 정답이 될 가능성이 없다고 판단되면 이후 탐색을 생략하는 기법입니다
배열이나 리스트에서 두 개의 인덱스를 이동시키면서 원하는 조건을 만족하는 구간이나 값을 찾는 기법입니다
일정한 범위의 구간을 유지하면서 구간을 한 칸씩 이동해 필요한 값을 계산하는 기법입니다
배열의 처음부터 각 위치까지의 합을 미리 계산해 저장하는 방법입니다
여러 원소가 같은 집합에 속하는지 확인하고 서로 다른 두 집합을 합치는 자료구조이자 알고리즘입니다.
Find로 대표 원소를 찾고 Union으로 두 집합을 합치며 크루스칼의 사이클 판별 등에 사용됩니다
Union-Find의 Find 과정에서 방문한 노드들을 집합의 대표 노드에 직접 연결하여 이후 탐색을 빠르게 만드는 최적화 기법입니다
정수의 각 비트를 하나의 상태로 사용하여 여러 개의 Boolean 상태를 하나의 정수로 표현하고 비트 연산으로 관리하는 기법입니다
객체지향 면접대비
그래픽스 면접 대비
네트워크 면접 대비