카운팅 정렬 (Counting sort) 카운팅 정렬은 정렬 시 데이터들의 개수를 세어 카운팅 배열에 저장하고 이후에 하나씩 꺼내오는 방식으로 정렬한다. 특정 조건이 부합할 때만 사용할 수 있지만, 데이터 수가 많더라도 중복된 값이 많이 분포되어 있는 배열을 정렬할 때 효과적이고 빠른 정렬 알고리즘이다. 시간복잡도는 O(N + k)이다. k는 컬렉션(카운팅배열) 내부의 최대 숫자이다. 따라서 최대값이 너무 큰 경우에는 시간복잡도가 매우 커질 수 있다. 카운팅 정렬의 조건 1. 데이터가 양의 정수인 경우 카운팅 정렬은 기본적으로 0~최댓값의 인덱스를 가지는 배열에 데이터 등장 횟수를 카운팅 하는 방식이다. 따라서 양의 정수만 가능하다. 2. 데이터의 크기 범위가 제한 된 경우 위에서 언급했듯이, 최대값이 ..
다이나믹 프로그래밍 (DP , 동적 계획법) 크고 복잡한 문제를 여러 개의 작고 간단한 문제들로 분리하여 문제를 해결하는 방법이다. 답을 찾아가는 과정에서 작은 문제들을 계산한 결과를 기록하고, 재활용하며 문제의 답을 구하는 방식이다. 중간 계산 결과를 기록하기 위한 메모리가 필요하다. 한번 계산한 부분을 기록해두기 때문에 다시 계산하지 않아서 속도가 빠르다. DP 핵심 원리 DP를 사용하려면 큰 문제를 작은 문제 여러개로 나눌 수 있어야 한다. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다. DP 구현 방법 메모이제이션(memoization) 방법 : 모든 작은 문제들을 한 번만 계산해서 DP 테이블에 저장하여, 그 값들을 재사용하는 방법 타뷸레이션(Tabulati..
퀵 정렬 (Quick sort) 퀵 정렬은 기준값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘이다. 시간복잡도가 비교적 빠르기 때문에 코딩테스트에서도 종종 응용한다. 평균 시간복잡도는 O(nlogn)이고, 최악은 O(n^2)이다. 이미 정렬돼 있는 배열에 적용할 때 최악의 시간복잡도를 가진다. 퀵 정렬(Quicksort)은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고, 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 또한 매 단계에..
플로이드 - 워셜(floyd - warshall) 알고리즘 플로이드 - 워셜 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다. 시작점을 정해놓고, 해당 시작점에서 다른 모든 노드로의 최단거리를 구하는 다익스트라, 벨만-포드 알고리즘과 다르게 각각의 모든 노드에 대하여 다른 모든 노드로의 최단거리를 구할 수 있는 알고리즘이다. 모든 노드 간에 최단 경로를 탐색할 수 있다. 음수 가중치 간선이 있어도 수행할 수 있다. 동적 계획법을 이용하여 코드가 비교적 간단하다. 다른 알고리즘과 다르게 모든 노드사이의 최단거리를 도출하는 알고리즘이기 때문에 3중 for문을 이용한다. 시간 복잡도는 O( N^ 3)이다. 플로이드 - 워셜 알고리즘 동작 원리 1. 핵심 이론 2차원 배열에 모든 노드에 대하여 다른 모든 ..
벨만-포드(bellman-ford-moore) 알고리즘벨만 - 포드 알고리즘은 그래프에서 음수 가중치를 가진 간선이 있을 때 최단거리를 구하는 알고리즘이다.다익스트라 알고리즘과 같이 특정 노드에서 다른 모든 노드까지의 최단 거리를 탐색한다.다익스트라 알고리즘과 다르게 음수 간선이 포함되어 있어도 최단 경로를 구할 수 있다.음수 사이클이 있을 경우 정상 동작하지 않는다.음수 사이클의 존재 여부를 파악할 수 있다.매번 모든 간선을 확인하기 때문에 다익스트라에 비해 느리다.시간복잡도 : O(VE) => Vertex * Edge벨만 - 포드 알고리즘 동작 원리1. Edge 리스트로 그래프를 구현하고 최단경로 배열 초기화 하기위에서 말했듯이 벨만 - 포드 알고리즘은 매번 모든 간선을 확인한다.따라서 Edge 클래..
다익스트라(dijkstra) 알고리즘 다익스트라 알고리즘은 그래프에서 최단거리를 구하는 알고리즘이다. 가중치 그래프 상에서 출발노드에서 목표노드까지 이동하는 가장 짧은 경로를 찾는 방법을 찾는다. 하나의 출발 노드에서 다른 모든 노드로의 최단 경로를 구할 수 있다. 에지(간선)은 모두 양수여야 한다. 시간 복잡도 : O(ElogV) 그리디와 DP의 특성을 갖고 있다. 다익스트라 알고리즘 동작 원리 1. 인접 리스트로 그래프를 구현한다. [1] ->[ 2, 8 ] 은 1에서 2로 가는 가중치가 8이라는 뜻이다. 실제로는 아래와 같이 Edge 클래스를 만들어서 Edge 형 ArrayList배열을 선언하여 구성하였다. ArrayList[] graph; class Node{ int to; //가리키는 노드 in..
그리디 (greedy) 알고리즘 그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체에서 최선의 선택지라고 가정하는 알고리즘이다. 빠르게 근사치를 계산할 수 있지만, 결과적으로 전체 케이스 중 최적의 값이 아닐 수도 있다. 따라서 이 문제를 그리디 알고리즘으로 해결해도 될지 고민해 보는 것이 필요하다. 그리디 알고리즘 수행 과정 1. 해 선택 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다. 2. 적절성 검사 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다. 3. 해 검사 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 만약 전체 문제를 해결할 수 없다고 판단되면 다시 1번으로 돌아가 과정을 반복한다. 이처럼 그리디 알고리즘을 수행하는 과정은 ..
BinarySearch : 이진탐색 (이분탐색) 이진탐색은 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘이다. 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는 방식이다. 크기가 100인 배열이 있고, 우리가 찾고자 하는 값이 99번째 인덱스에 들어있는 상황을 가정해 보자. 일반적인 반복문을 사용하여 1부터 100까지 반복하면 99번째 반복에서 찾고자 하는 값을 찾을 수 있다. 물론 이 경우 찾고자 하는 데이터가 앞쪽에 있다면 같은 데이터셋에 대하여 탐색 시간이 이분탐색을 이용했을 때보다 빠를 것이다. 그런데 만약 데이터의 크기가 1억 개이고, 운이 나쁘게도 우리가 찾고자 하는 값이 99,999,999 번째의 데이터인 경우에는 시간이 매우 오래 걸릴 ..
