카운팅 정렬 (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..
가장 기본적인 다익스트라 알고리즘 문제이다. 다익스트라 알고리즘을 처음 접한다면 아래 글을 한번 읽어보는 것을 추천한다. 2023.06.26 - [자료구조_알고리즘/Algorithm] - [Algorithm] 다익스트라(dijkstra) 알고리즘 (최단거리, 가중치 그래프) 우선 Edge 클래스를 하나 만들어서 해당 edge가 가리키는 노드, 가중치를 저장한다. 출발 노드는 ArrayList의 index로 관리할 것이기 때문에 필요 없다. 그래프 정보를 저장할 ArrayList[ ] 배열과 최단거리 배열 int[ ] distance를 만들고, 초기화 한다. 각 Edge의 가중치가 작은 것 부터 poll() 할수 있는 우선순위 큐를 만들고 시작점을 먼저 넣는다. 이후 우선순위 큐에서 Edge를 하나씩 꺼내..
그리디 (greedy) 알고리즘 그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체에서 최선의 선택지라고 가정하는 알고리즘이다. 빠르게 근사치를 계산할 수 있지만, 결과적으로 전체 케이스 중 최적의 값이 아닐 수도 있다. 따라서 이 문제를 그리디 알고리즘으로 해결해도 될지 고민해 보는 것이 필요하다. 그리디 알고리즘 수행 과정 1. 해 선택 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다. 2. 적절성 검사 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다. 3. 해 검사 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 만약 전체 문제를 해결할 수 없다고 판단되면 다시 1번으로 돌아가 과정을 반복한다. 이처럼 그리디 알고리즘을 수행하는 과정은 ..
