Algorithm

소수값 구하기 - 에라토스테네스의 체

소수를 찾는 방법 중 에라토스테네스의 체 방법을 설명드리겠습니다. 시간복잡도: O(NloglogN) 에라토스테네스의 체 원리 1. 2부터 120(예시)까지 모든 숫자를 나열합니다. (1은 소수가 아니므로) 2. 숫자 하나씩 방문하면서 자기자신을 제외한 배수를 제거합니다. (2를 방문했다면 2를 제외한 배수 4부터 지우기) 3. bool함수를 이용해 전에 지웠던 숫자를 다시 방문하지 않게 합니다. 소수만 출력하는 코드 #include const int INF = 10001; int arr[INF]; bool primearray[INF]; void Eratos(int n) { if (n

동적 계획법, DP(Dynamic Programming) c++

동적 계획법( 다이나밍 프로그래밍 ) 이란? 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 먼저 입력 크기가 작은 부분 문제들(subproblems)을 모두 해결한 후, 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘 동적 계획법, 다이나믹 프로그래밍, DP 모두 같은 말이므로 쉽게 DP라고 통일하겠습니다! DP는 이전 부분 문제의 최적해를 기록해놓으므로 완전 탐색 알고리즘보다 빠릅니다. 하지만 해당하는 문제가 최적 부분 구조를 가져야만 DP 알고리즘을 적용할 수 있습니다. 최적 부분 구조는 무엇일까요? 최적 부분 구조(optimal substructure)란 다음과 같습니다. 큰 문제의 최적해에 작은 문제의 최적해가 포함 순환..

hash map - C++ STL

예시 #include #include int main() { std::unordered_map hashmap; //insert hashmap.insert({"key1","value1"}); hashmap.insert({"key2","value2"}); hashmap.insert({"key3","value3"}); //find std::cout first

BFS(너비 우선 탐색) 알고리즘

BFS(Breadth-First Search)란? 그래프 순회 방법이 대표적으로 DFS와 BFS가 있는데 이번 시간에는 BFS를 알아보도록 하겠다! BFS 알고리즘은 출발 노드로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 그래프 순회 문제 중 최단 경로를 구하는 문제에 많이 쓰이는 알고리즘이다. DFS 알고리즘은 다음 글을 참고하면 된다. https://yhoons.tistory.com/8 DFS(깊이 우선 탐색) 알고리즘 DFS(Depth-First Search)란?? DFS는 한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 정점으로 되돌아와서 다른 방향으로 진행하는 그래프 순회 방법이다. 그래프 순회 방법 yhoons.ti..

DFS(깊이 우선 탐색) 알고리즘

DFS(Depth-First Search)란?? DFS는 한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 정점으로 되돌아와서 다른 방향으로 진행하는 그래프 순회 방법이다. 그래프 순회 방법에는 대표적으로 DFS와 BFS가 있다. DFS 이해하기 DFS 알고리즘을 구현하는 방법에는 인접 리스트를 이용하는 방법, 인접 행렬을 이용한 방법이 있는데 각각 장단점이 존재한다. 인접리스트를 이용했을 때 장점: 모든 노드를 순환하려 할 때 O(N)시간 밖에 걸리지 않는다. 빈 공간이 생기지 않는다. 단점: 인접한 특정 노드를 알고싶을 때 리스트 안에 일일이 찾아봐야한다. 인접 행렬을 이용했을 때 장점: 인접한 특정 노드를 알고싶을 때 2차원 배열에 정보가 저장돼있기 때문에 한 번에 찾..

투포인터 알고리즘(Two Pointers Algorithm) - c++

투포인터 알고리즘이란? 두 개의 포인터를 각각 이동시키면서 1차원 배열 안 특정 조건에 해당하는 값을 구하는 알고리즘입니다. 알고리즘의 이해 1차원 배열이 있고, 합이 5인 연속적인 부분 수열의 개수를 구하는 문제라고 가정해보겠습니다. 처음 두 개의 포인터는 인덱스 0에 위치해 있고, 각각 start, end 로 구분합니다. ↓ : start ↓ : end ↓↓ 1 2 3 4 5 6 현재 두 포인터 모드 인덱스 0을 가리키고 있으므로 인덱스0부터 0까지의 합은 1입니다. 합을 5로 맞춰야하므로 end 포인터를 오른쪽으로 한 칸 이동시킵니다. ↓ ↓ 1 2 3 4 5 6 현재 start의 인덱스는 0, end는 1을 가리킵니다. 인덱스 0부터 1까지의 합은 3. end포인터를 오른쪽으로 이동 시킵니다. ↓..

다익스트라 알고리즘(Dijkstra algorithm) - c++

다익스트라 알고리즘이란? 더보기 : 그래프에서 엣지(노드) 간에 최단 거리(가중치 합 최소)를 구하는 알고리즘 그래프 알고리즘 문제에도 많이 쓰이는 알고리즘 중에 하나이며, 실생활에선 네비게이션 알고리즘에도 쓰여 알아두면 좋은 알고리즘이다. 알고리즘 이해 노드 간의 거리를 비교해 나가면서 최단 경로를 구해야하기 때문에 거리를 저장 시켜둘 필요가 있다. 노드 개수가 6개이므로 , 크기가 6인 1차원 배열을 2개 만들어 (거리 정보와 방문 여부)를 저장시켜준다. int distance[7]; bool visited[7] = {0,}; 배열은 인덱스 0번부터 시작하지만 쓴이는 인덱스 0번을 비우고 인덱스와 노드값을 동일하게 사용하려고 7개의 원소를 받는다고 하였다. 우리는 최종 거리에 대한 최솟값을 구해야하기..