알고리즘

그리디 알고리즘(탐욕적 알고리즘)은 현재 상황에서 가장 좋아 보이는 선택을 반복하여 최적해를 구하는 알고리즘이다.각 단계마다 그 순간에 가장 큰 이득을 얻을 수 있는 선택을 하고, 그 선택들을 쌓아서 전체 문제의 해답이 된다고 가정을 하는 알고리즘 방식이다.가장 핵심은

DFS 알고리즘이란? DFS(Depth-First Search) 알고리즘은 깊이 우선 탐색 알고리즘으로 그래프를 탐색할 때 사용하는 알고리즘이다. 한 Node에서 시작하여 이와 인접한 Node들을 재귀적으로 탐색을 하며, 한 Node에서 가능한 깊숙이 들어간 뒤 더

Stack Stack이란? 스택이란 단어적인 뜻은 "쌓아놓은 더미"라는 뜻이다. 접시를 놓을 때는 제일 위에 놓고, 더미에서 꺼낼 때도 제일 위에 있는 접시를 꺼내는 것과 동일하게 생각하면 된다. 알고리즘에서도 동일하게 접시 -> 데이터만 바뀌고 동일하게 생각하면,

투 포인터 알고리즘은 리스트(배열)에서 두 개의 포인터를 사용해 연속된 구간을 다루면서 특정 조건을 만족하는 부분 구간을 효율적으로 탐색하는 알고리즘이며 주로 리스트(배열)가 정렬이 되어 있는 경우에 사용한다.주로 왼쪽(left)과 오른쪽(right) 포인터를 사용하고

Prefix Sum(누적 합) 알고리즘은 배열의 앞에서부터 차례대로 합을 미리 구해두고,이 누적된 합을 이용해서 어떤 구간의 합이든 빠르게 계산하는 방법이다.이 알고리즘의 가장 큰 장점은 누적 합을 만드는 데는 O(N) 한 번, 그 이후 구간 합을 구하는 질의는 각각

DP 알고리즘이란? DP(Dynamic Programming, 동적 계획법)는 큰 문제를 작은 부분 문제로 나누고, 그 부분 문제들의 정답을 미리 저장해두었다가 재사용하여 전체 문제를 효율적으로 푸는 알고리즘 기법이다. DP의 가장 큰 장점은 같은 계산을 여러 번 반

배낭 문제는 DP 알고리즘의 대표적인 문제로 DP를 이해하기에 좋은 예시이다.주어진 물건들 중에서 일부를 선택해 배낭에 담을 때, 주어진 무게를 넘지 않으면서 얻을수 있는 가장 최대의 가치를 구하는 문제이다.이 문제를 단순하게만 바라보면 어?? 최대 가치를 구하는 것이

우선순위 큐는 우리가 주로 많이 사용하는 큐와 다르게 들어온 순서에 따라 나가는게 아닌 우선순위에 따라 우선순위가 높은 데이터가 먼저 나오는 큐이다.일반적인 큐는 FIFO(선입선출)구조로 먼저 들어온 데이터가 먼저 나가지만, 우선순위 큐는 데이터에 우선순위를 매겨 높은

브루트포스(Brute Force) 알고리즘은 알고리즘 문제를 처음 접하는 순간 가장 먼저 마주하게 되는 방식이며, 이름처럼 모든 경우의 수를 전체 다 시도해 답을 찾는 방식이다.복잡한 최적화 기법이 없기에 구현도 단순하지만 입력값이 늘어날수록 시간복잡도가 기하급수적으로

다익스트라 알고리즘(Dijkstra’s Algorithm)은 가중치가 있는 그래프에서 하나의 시작 정점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이다.또한 여러 가지 최단 거리를 구하는 알고리즘이 있짐만 다익스트라 알고리즘은 간선의 가중치는 무조건 0이상

백트래킹 알고리즘은 모든 경우의 수를 탐색하지만, 답이 될 수 없는 경우는 더 깊게 들어가지 않고 되돌아오는(BackTrack) 탐색 기법이다.기본적인 형태는 DFS(깊이 우선 탐색)을 통해 완전 탐색을 하지만 중간중간 조건에 맞지 않는 경우는 가지치기를 하면서 탐색하

입력값들을 줄 단위로 받아 지금까지의 숫자들중에서 가장 중앙에 있는 값을 출력하는 문제이다.현재까지의 숫자의 갯수가 짝수인 경우는 중간에 있는 두개의 수 중에서 더 작은 값을 출력하면 된다.처음 이 문제를 보았을 때 그냥 ArrayList를 만들고 입력값을 받을 때마다