알고리즘
1.[알고리즘] Algorithm
본 알고리즘 항목은 코딩 테스트를 위한 알고리즘 공부와, 개발하는 과정에서 문제해결능력을 함양하기 위해 새로 추가하였다.이 알고리즘 항목은 일별 공부한 항목을 따로 나누지 않고, 계속 이어가는 형식으로 기록하며 지금 공부하는 내용들이 계속 누적될 수 있도록 관리한다.알
2.[알고리즘] 정렬 알고리즘의 개요와 선택 정렬
알고리즘(문제를 해결하는 과정)의 효율성 차이에 대해 가장 빠르게 이해할 수 있는 수단 중 하나.말 그대로 data 혹은 숫자를 어떻게 구성하고 위치하는 지에 대해 정의하는 방법론이다.target data를 정한 후(정하는 방법은 여러가지가 있을 것임), target
3.[알고리즘] 버블정렬
data 정렬을 할 때, 특정 기준으로 바로 옆에 위치한 data를 비교하면서 정렬이 완료될때까지 수행하는 문제해결과정을 일컫는다.예를 들어 오름차순으로 data를 정리한다고 할 때, 최초 인덱스부터 마지막까지 계속 비교를 하면서 스와핑을 그때그때 진행한다.한 번의 순
4.[알고리즘] 삽입정렬
data 정렬시 앞의 data들은 이미 정렬이 완료되었다는 가정으로, 비교연산 등 순회과정을 진행할때마다 적당한 위치에 data를 정렬하는 방식이다.정렬이 되어있다고 가정하기 때문에 순회과정에서 특정 조건을 만족할 경우, 곧바로 순회를 종료한다. 이 관점에서 특정 조건
5.[알고리즘] 분할정복과 퀵정렬
분할정복을 활용하여 data를 정렬하는 알고리즘을 일컫는다.특정 값(pivot)을 기준으로 왼쪽에 pivot보다 작은 숫자(혹은 특정 기준을 만족하는 값들), 오른쪽에 pivot보다 큰 숫자(혹은 특정 기준을 만족하는 값들)를 위치해가며 data를 정렬해가는 방법을 의
6.[알고리즘] 병합정렬
5. 병합정렬 퀵정렬과 마찬가지로 분할정복을 사용하는 정렬이며, 시간복잡도 역시 O(N*logN)이다. 퀵정렬은 data정렬이 어느정도 되어있는 상태에서 활용할 경우 가장 빠르고 강력하지만, pivot 값이 달라짐에 따라 분할되는 부분집합도 달라지므로 pivot 편
7.[알고리즘] 힙정렬
6. 힙정렬 heap 구조를 이용하여 data를 정렬하는 방법으로, 병합/퀵정렬과 마찬가지로 시간복잡도가 O(N*logN)을 가지는 방법이다. 6-1. 이진트리 Binary Tree, 컴퓨터가 데이터를 표현할 때 데이터를 각 노드에 담은 후 해당 노드들을 이어붙이
8.[알고리즘] 계수정렬
## 7. 계수정렬 counting sort, 범위가 명확히 정해진 data들에 대해 크기(size 혹은 개수)를 기준으로 개수를 세고 이를 정렬하는 방법을 말한다. 퀵정렬, 병합정렬보다도 시간복잡도 관점에서 가장 강력한(O(N)) 정렬방법이지만, 반드시 특정한 범
9.[알고리즘] 파이썬 배열관련 메소드 (기본)
stack : last in - first outqueue : first in - first outappend : 배열 마지막 인덱스에 원소 추가 pop() : 배열 마지막 원소를 제거insert(0, x): 배열 처음 인덱스에 원소 추가pop(0) : 배열 처음 원소
10.[알고리즘] BFS(너비우선탐색), DFS(깊이우선탐색) 1
너비우선탐색, data 탐색을 할 때 너비를 기준(특정노드에 인접해있는 모든 노드들을 탐색대상으로 설정)으로 탐색을 하는 탐색방법의 일종이다.최단거리탐색 및 미로찾기 등 경로탐색에 사용할 수 있으며, Queue 자료구조를 이용하면, 자료구조의 특징을 이용하여 BFS를
11.[알고리즘] union find 연산 1
합집합 찾기, 동일 부모 노드를 보유하고 있는 요소를 찾기 위한 알고리즘으로 서로소 집합(연결관계가 없는 노드)을 탐색하기 위한 알고리즘이기도 하다.여러개의 노드가 존재할때, 두 노드를 선택해서 서로 같은 graph에 속하는지 판별한다.Strongly-connected
12.[알고리즘] 크루스칼 알고리즘
가장 적은 비용(간선연결)을 통해 모든 노드를 연결하는 방법을 도출하는 알고리즘이다.최적의 비용을 도출하는 알고리즘을 공부하는 것부터 시작한다.크루스칼 알고리즘을 구현할 때 만족해야하는 조건이 4가지 존재한다.모든 노드들은 연결되어있는 상태(하나의 graph로 구성)이
13.[알고리즘] 이진트리와 순회(개념)
선형자료구조는 말 그대로 data가 선형으로 구성되어있는 형태를 일컫는다.대표적인 형태로 배열, stack, queue 등이 존재한다.비선형자료구조 역시 말 그대로 data가 비선형으로 구성되어있는 형태를 말하는데, 쉽게 말하면 data들이 얽히고 설킨 구조를 의미한다
14.[알고리즘] 동적계획법(DP)과 memoization 1
Dynamic Programming, DP분할정복과 비슷한 개념이긴하지만 memoization(이전 결과값의 저장과 활용)이 추가된 알고리즘을 말한다.분할정복기법은 큰 문제를 반으로 나누어 잘게 쪼개고, 분할된 문제를 풀면서(혹은 정렬하면서) 큰 문제를 해결하는 과정을
15.[알고리즘] 에라토스테네스의 체
Sieve of Eratosthenes, 대량의 소수를 한꺼번에 판별 및 출력하는 알고리즘이다.소수(prime number)는 자기자신과 1을 약수를 가지는 수이며, 에라토스테네스의 체는 특정 범위까지 소수를 출력한다.1개의 수에 대한 소수여부를 파악하고자 하면, 수의
16.[알고리즘] 다익스트라(Dijkstra) 알고리즘 1
Dijkstra, 최단경로를 탐색하는 알고리즘으로 동적계획법을 활용한다.특정 노드에서 다른 모든 노드를 향하는 최단 경로를 구할수 있고, 음의간선이 존재하지 않을 경우 활용할 수 있는 알고리즘이다.정렬을 사용하여 그리디 알고리즘이라고도 일컫는다.기본적으로 동적계획법을
17.[알고리즘] 플로이드-와샬 알고리즘
floyd-warshall, 모든 노드를 출발점으로 지정하고, 모든 노드에 대한 최소비용 경우의 수를 구하는 알고리즘이다. 다익스트라가 특정 노드를 출발점으로 지정한다면, 플로이드는 존재하는 노드 모두 출발점으로 고려한다.플로이드-와샬 알고리즘은 기본적으로 2차원 배열
18.[알고리즘] 위상정렬
순서가 정해져있는 작업을 차례로 수행해야 할 때, 그 순서를 정렬하는 알고리즘을 일컫는다.위상정렬의 핵심은 조건(진입차수 및 간선배치)과 노드들의 선형정렬이다.이 선형정렬을 구성하기 위한 필요한 조건은 두가지이다.graph가 있을때 조건에 따른 한가지 경로를 도출할 수
19.[알고리즘] SCC/타잔알고리즘
Strongly Connected Component, 강한 결합 요소graph안에서 강하게 결합이 이루어진 정점들의 집합을 일컫는데, 쉽게 말하면 사이클(부모노드와 자식노드가 서로에게 도달이 가능한 상태)이 가능한 정점들을 SCC에 속한다고 한다.SCC는 방향이 있는
20.[알고리즘] 네트워크 플로우
특정 지점에서 다른 지점으로 데이터를 흘러보내려고 할때(네트워킹), 가능한 모든 경로를 다 찾고, 흘러보낼 수 있는 최대의 유량을 계산하고 흘러보내는 알고리즘을 의미한다.교통체증 및 네트워크 데이터 전송 등의 분야에서 활용가능한 알고리즘이다.노드를 이어주는 간선정보에
21.[알고리즘] 이분매칭
21. 이분매칭 Bipartite matching, 두 집단(집합) 간 1:1대응(혹은 조건 상 최대로 효율적인 연결관계)을 구현하는 알고리즘을 의미한다. 네트워크 플로우와 연계되는 개념이며, graph 상에서 같은 집합끼리는 연결되지 않은 상태에서 1:1대응하는 경
22.[알고리즘] 단순 문자열 매칭
특정한 글(문자열)이 있을때 그 글 안에서 하나의 문자열을 찾는 알고리즘이다.흔히 사용하는 탐색, ctrl+F와 같이 해당 문자열 내부에서 문자열이 있는지 탐색한다.말 그대로 단순하게 하나씩 문자열을 비교해가면서 확인한다.parent String(탐색 문자열) 내에서
23.[알고리즘] KMP 문자열 매칭 (**추가작성필요)
Knuth-Morris-Pratt Algorithm, 단순비교 문자열 매칭의 비효율성을 보완한 알고리즘으로 탐색알고리즘의 대표적인 알고리즘이다.단순 문자열 매칭에서 비효율적인 연산량, 특히 모든 경우에 대해 문자열을 비교해야한다는 점에서 단순 문자열 매칭은 사용하지 않
24.[알고리즘] 그리디 알고리즘 1
Greedy algorithm, 탐욕기법이라고도 하며 한가지 조건만을 기준으로 최적의 결과를 도출하는 과정을 의미한다.한가지 조건만을 기준으로 알고리즘을 진행하기 때문에 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적의 해에 근접한 형태를 찾을 수 있는 알
25.[알고리즘] 개념 및 문법 총정리(메소드 포함, for python)
시간복잡도 : 알고리즘의 수행시간공간복잡도 : 알고리즘의 메모리 사용량빅오표기법 : 알고리즘 수행능력을 입력받은 데이터 개수에 따른 연산량, 수행소요시간을 나타내는 방법이다. 시간소요량의 최대값(함수의 상한선)을 기준으로 나타낸다.※ 빅오표기법 - 데이터 개수가 늘어남
26.[알고리즘] 그리디 알고리즘 2
현재 상황에서 당장 좋은 것만 고르는, 특정 기준 하나만을 선택하여 기준대로 최적의 해를 구하는 방법이다.그리디 알고리즘의 핵심은 어떤 기준을 적용하고 적용할 것인지 판단하는 것이다.아래와 같은 graph가 있다고 하자.이때 노드의 값을 최대로 얻고자 할 때는 어떤 알
27.[알고리즘] 구현(시뮬레이션/완전탐색)
구현 자체는 문제에 대한 방안, 알고리즘을 실제 코드로 옮기는 과정을 의미한다.보통 모든 경우의 수를 생각하거나, 빠짐없이 상황을 탐색하고자 할 때를 의미하는데 알고리즘 구현은 곧 생각한 알고리즘을 실제로 구현하는 과정이 어려운 경우를 일컫는다.방안/알고리즘을 떠올리기
28.[알고리즘] stack과 queue
last in, first out의 자료구조로 DFS를 구현하기 위해 반드시 알아야하는 필수적인 자료구조이다.파이썬에서 제공하는 자료구조는 기본적으로 stack 형태이므로, append와 pop() 메소드를 이용하면 stack 자료구조를 그대로 활용할 수 있다.prin
29.[알고리즘] 재귀함수(recursion)
DFS 구현을 위해 queue 자료구조와 함께 반드시 알아야 하는 함수이다.파이썬은 디폴트로 재귀함수 호출 제한이 걸려있으므로, 내부적으로 호출제한을 풀어놓는 명령어를 작성해주어야 한다.재귀함수는 일종의 stack 자료구조 형식으로 구현된다.재귀함수를 무한으로 호출하기
30.[알고리즘] BFS(너비우선탐색), DFS(깊이우선탐색) 2
깊이우선탐색, 인접노드를 stack 자료구조에 넣는다는 것이 핵심.탐색노드를 stack에 넣은 후 추출하여 방문처리한다.이후 해당 탐색노드의 인접노드 중 방문하지 않은 노드만 stack에 넣는다.stack에 넣은 노드를 추출하여 방문처리, 그 노드의 인접노드 중 방문하
31.[알고리즘] 정렬 총정리
sort, 데이터를 특정 기준에 따라 나열하는 것.일반적으로 상황 및 조건에 따라 적절한 알고리즘이 공식처럼 사용된다.데이터 개수가 적을때데이터 개수가 많지만, 특정 범위로 한정되어 있을때이미 데이터가 거의 정렬되어있는 경우처리되지 않은 데이터 중, 가장 작은 데이터를
32.[알고리즘] 동적계획법(DP)과 memoization 2
1. 동적계획법 Dynamic Programming, 메모리를 누적하거나 적절히 활용하여, 알고리즘을 수행하는 시간을 최소화할 수 있는 알고리즘 기법이다. 프로그래밍 분야에서 Dynamic은 프로그램이 실행되는 도중을 의미하는데, DP에서의 Dynamic은 프로그래
33.[알고리즘] 다익스트라(Dijkstra) 알고리즘 2
특정노드에서 다른 노드로 향하는 가장 적은 비용, 최단 거리를 도출하는 알고리즘을 의미한다.최단경로를 도출하는 알고리즘을 활용할 수 있는 형태는 크게 3가지로 나뉘어져있다.한 지점에서 다른 한 지점으로 향하는 최단경로(최소비용)한 지점에서 모든 노드 지점까지 향하는 최
34.[알고리즘] 플로이드-와샬 알고리즘 2
## 1. 최단경로 알고리즘 특정노드에서 다른 노드로 향하는 가장 적은 비용, 최단 거리를 도출하는 알고리즘을 의미한다. 최단경로를 도출하는 알고리즘을 활용할 수 있는 형태는 크게 3가지로 나뉘어져있다. - 한 지점에서 다른 한 지점으로 향하는 최단경로(최소비용)
35.[알고리즘] 최단 경로 알고리즘의 구현
## 1. 도시 간 우편 보내기 N개의 도시가 있고, 각 도시는 다른 도시로 우편을 보내고자 한다. 단 X라는 도시에서 Y라는 도시로 전보를 보낸다고 할 때는 반드시 거쳐가는 통로가 존재해야 한다. 어느날 C라는 도시에서 위급상황이 발생하여, 최대한 많은 도시로 최대
36.[알고리즘] union find 연산 2
공통원소가 존재하지 않는 집합, 그러한 관계를 의미한다.이 서로소 집합에 대해 Union(개별적인 두 노드(원소)에 대해 동일한 부모노드를 설정하여 하나의 집합(합집합)으로 합치는 과정)연산을 거치면 동일한 하나의 집합으로 만들 수 있다.이 후 Find 연산으로, 각
37.[알고리즘] 신장트리(크루스칼 알고리즘)
Spanning Tree, 그래프가 모든 노드가 연결되어 있으면서 사이클이 존재하지 않는 그래프를 의미한다.모든 노드가 연결되어있지만 cycle이 존재하지 않는다는 점에서 tree라 명명하고, 전체 graph에서 부분적으로 신장트리를 도출해낼 수도 있다.이때 한 gra
38.[알고리즘] 위상정렬
사이클이 없는 방향 그래프에서, 모든 노드에 대해 방향을 거스르지 않으면서, 방향이 특정된 노드 순서대로 나열하는데 활용하는 알고리즘진입차수(Indegree) : 특정 노드로 들어오는 간선의 개수진출차수(Outdegree) : 특정 노드에서 나가는 간선의 개수위상정렬
39.[알고리즘] 소수 판별하기
1보다 큰 자연수 중에서 1과 자기자신을 제외한 자연수로 나누어떨어지지 않는 수를 의미한다.모든 수 N에 대하여 소수 여부를 확인하고자 할 떄는, 선형탐색(접근)보다는 경우의 수를 최대한 낮추어 알고리즘을 적용하는 것이 중요하다(선형탐색일 경우 시간복잡도가 그만큼 비례
40.[알고리즘] 투포인터 알고리즘
리스트에 접근할때, 두개의 포인터(노드, 점) 위치를 기록하면서 처리하는 방식을 의미한다.예를 들어, 2-3-4-5-6-7 의 학생을 지목할때 보통은 2번부터 7번까지의 학생으로 지칭하는 경우가 많은 것처럼, 리스트에 담긴 데이터에 접근할때 시작점과 끝점을 지정하고 이
41.[알고리즘] 접두사합(prefix sum) 알고리즘(구간의 합)
연속적으로 나열된 N개의 수가 있을때, 특정 구간 내 모든 수를 더하는 알고리즘에 대해 파악한다.다만, 단순히 1차원 리스트에서 선형탐색을 하며 합산하는 것이 아닌, 여러 정보와 구간이 제시될때 시간복잡도를 최소화하는 방안을 고민할 필요가 있다.N개의 정수로 구성된 수
42.[알고리즘] 벨만포드 알고리즘
음수 간선이 포함되어있는 상황에서 최단거리 혹은 최소비용을 도출하고자 할때 사용할 수 있다(\*다익스트라, 플로이드 와샬은 모두 간선이 양수).다익스트라를 통해 음수간선이 포함되어있는 상황에서 최단거리를 도출해낼 수는 있다. 단, 최단경로가 음의간선을 고려하였어도 양의
43.[알고리즘] 바이너리 인덱스 트리(BIT)
Binary Indexed Tree, BIT, 펜윅트리라고도 한다.데이터 업데이트가 가능한 상황에서의 구간합을 구할 때 사용하는 자료구조이다.일단 기본적으로 특정 수에 대한 negative값을 얻기 위해선, 2진수 비트에서 0과 1을 flip하고 마지막 비트에 +1을
44.[알고리즘] 최소공통조상(LCA)
1. 최소공통조상 LCA, Lowest common ancestor. 두 노드의 공통된 상위 부모노드(조상) 중에서, 가장 가까운 부모노드를 의미한다. 위 graph(tree)에서 8번노드와 15번노드의 LCA는 2번노드가 된다. 2. 해 도출 과정 모든 노드
45.[알고리즘] 방향/무방향 그래프에서의 최대 간선의 수
1. 개요 순환 구조를 가지는 그래프는 간선의 방향성 여부에 따라 무방향, 방향 그래프로 분류할 수 있다. 이때 방향 그래프와 무방향 그래프에서 노드의 개수가 N으로 주어졌을때 최대 간선의 개수를 구할 수 있다. 2. 방향 그래프에서의 최대 간선의 수 방향 그래