algorithm

오늘도 백준을 풀다가 새로운 알고리즘 발견..항상 새로운 알고리즘을 발견할 때마다 정리해두면 좋을 것 같아서 작성하는 글이다.

탐욕 알고리즘이라고도 말하는데, 이 단어에서도 유추할 수 있듯이 '욕심쟁이'의 성격을 띈다고 보아도 된다각 경우의 수를 찾아나서는 과정마다 가장 최적이라고 생각되는 것을 선택하는 방식을 사용해 최종적인 해답으로 도달하는 알고리즘이다.한 순간 순간마다 'local 최적'

Prefix Sum: 구간 합 📕 Prefix Sum을 사용해야하는 문제의 조건 💡 Prefix Sum의 장점 📝 Prefix Sum을 사용하는 문제의 예 c.f. Prefix Sum을 사용하면 안되는 문제의 예

Two pointer 리스트에 순차적으로 접근해야 할 때 두 개의 점 위치를 기록하는 알고리즘 이중 for문으로 O(N^2)에 처리되는 작업을 2개의 포인터(변수) 움직임으로 O(N)에 해결하는 알고리즘 > > 두개의 포인터를 어디에 설정하는 지가 문제의 관권 >> 합

BFS (Breadth First Search)너비 우선 탐색: 맹목적 탐색 방법 중 하나. 시작 정점 방문하고 찾고자 하는 값을 찾을 때까지 시작 노드와 인접한 노드들을 우선 방문하는 방법

DFS (Depth First Search) 깊이 우선 탐색 하나의 정점에서 시작하여 차례대로 연결된 모든 정점들을 한 번씩 방문하는 방법

Binary Search: 이진 탐색 / 이분 탐색 이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다.

DP (Dynamic Programming = 동적계획법) 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 기본적인 아이디어를 가지고 푸는 하나의 문제 해결 패러다임이다. DP의 특징 > 시간복잡도 O(f(N))

Divide and Conquer (분할 정복) 여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념이다 Divide를 제대로 나누

최단 경로 알고리즘그래프 상에서 노드 간의 탐색 비용을 최소화하는 알고리즘이다세 가지 최단 경로 알고리즘1\. 다익스트라2\. 벨만 포드3\. 플로이드 워셜그리디하게 최소 비용 경로를 찾아간다\-> 출발 노드에서만 연결된 노드를 반복적으로 탐색하여 -> 다른 모든 노드

크루스칼 알고리즘 (Kruskal Algorithm) >최소 비용 신장 부분 트리(MST)를 찾는 알고리즘이다 =>가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 예로, 여러 개의 도시가 있을 때 각 도시를 도로로 연결하고자 하면서 비용을 최소한으로 할