| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 15 | 16 | 17 | 18 | 19 | 20 | 21 |
| 22 | 23 | 24 | 25 | 26 | 27 | 28 |
| 29 | 30 | 31 |
- 알고리즘 문제
- CSS
- Git
- js
- 알고리즘 풀이
- HTML
- MAC
- Algorithm
- 알고리즘 연습
- DRF
- Django
- API
- 알고리즘
- django rest framework
- AWS
- 장고
- c++
- java
- 파이썬 알고리즘
- 파이썬
- es6
- web
- react
- PYTHON
- javascript
- django ORM
- Baekjoon
- form
- 백준
- django widget
- Today
- Total
목록알고리즘/이론 (20)
수학과의 좌충우돌 프로그래밍
이번 포스팅에서는 Two Pointers에 대해서 알아보도록 하겠습니다. Two Pointers 는 1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 알고리즘입니다. 여기서 두 개의 포인터를 사용하여 기존의 방식보다 시간을 개선할 수 있습니다. Two Pointers 의 동작원리, 시간복잡도, C++로 구현한 코드를 보며 이해해보겠습니다. 동작 원리 적절한 예시를 위해 백준에서 Two Pointers 를 사용하는 문제의 에시를 사용하겠습니다. https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분..
이번 포스팅에서는 Counting Sort 에 대해서 알아보도록 하겠습니다. Counting Sort의 동작원리, 시간복잡도, C++로 구현한 코드를 보며 이해해보겠습니다. 동작원리 다음과 같이 origin이라는 배열을 Counting Sort를 통해서 정렬 해보도록 하겠습니다. int origin[] = {5, 3, 4, 5, 1, 0, 4, 1, 3, 0, 2, 4, 2, 3, 0}; Counting 첫 번째로 해야할 일은 각 숫자가 몇 번 나왔는지 세야합니다. origin 배열에 등장한 수와 그 수가 몇 번 나왔는지를 기재하였습니다. 수 0 1 2 3 4 5 나온 횟수 3 2 2 3 3 2 Counting Sum 다음으로는 각 수의 누적합을 구해줍니다. 누적합을 통해서 해당 숫자가 어느 인덱스에 위..
위상정렬이란? 위상 정렬은 순서가 정해져있는 작업 차례로 수행해야 할 때, 그 순서를 결정해주는 알고리즘입니다. 그림을 보며 이해해봅시다. 다음과 같은 그래프에서 앞선 작업 2,3이 끝나야 뒤 작업 4가 이루어질 수 있으며 이 때 둘 중 무엇을 먼저 끝내던 규칙에 위배 되지 않기 때문에 경로는 여러 개가 나올 수 있습니다. 단 위상정렬이 성립하기 위해서는 DAG여야 합니다. DAG란? Directed Acyclic Graph의 줄임말로 사이클이 존재하지 않는 방향 그래프입니다. 만일 위 그림에서 5이 1에 연결되었다면 시작점이 존재하지 않기 때문에 위상정렬이 성립할 수 없습니다. 위상 정렬 원리 위상 정렬이 어떤 원리로 동작하는지 살펴봅시다. 위상 정렬을 스택이나 큐를 사용하여 구현할 수 있지만 큐를 사..
규정 상의 이유로 출처와 문제는 밝힐 수 없지만 코딩테스트를 보다가 연속 구간의 최대 합을 구하는 문제를 접하게 되었습니다. 문제를 푸는 방법이 굉장히 다양하고 각 풀이 방법의 복잡도가 전부 다르기 때문에 이에 대해서 정리해보고자 합니다. 연속 구간의 합 우선 main 함수입니다. main 함수에서는 원소의 개수를 입력받고, 원소의 개수만큼 값들을 입력받아 배열에 저장합니다. #include #include #include using namespace std; int main() { int N; vector arr; cin >> N; for (int i=0;i> temp; arr.push_back(temp); } int result = brute_force(arr); cout
안정 정렬와 불안정 정렬 우선 안정정렬와불안정정렬이 무엇인지 알아봅시다. 안정정렬은 동일한 값에 대해 기존의 순서가 유지되는 정렬을 말하며 불안정정렬은 반대로 동일한 값에 대해 기존의 순서가 뒤바뀔 수 있는 정렬입니다. 아래 그림을 보며 이해를 해봅시다. 기존의 숫자배열은 스페이스 7, 하트 5, 하트 2, 스페이스 5로 구성되어 있습니다. 이를 숫자에 대하여 오름차순으로 정렬한다고 생각해봅시다. 이 때 안정정렬을 하게 되면 앞에 존재하던 하트 5와 뒤에 존재하던 스페이스 5의 순서는 바뀌지않음이 보장됩니다. 반대로 불안정정렬을 보도록 하겠습니다. 이 경우에는 하트 5와 스페이스 5의 순서가 바뀌었지만 불안정이라고 해서 항상 바뀌는 것은 아닙니다. 바뀔 수 도 있고 바뀌지 않을 수 도 있습니다. C++의..
그래프에서 정점끼리의 최단 경로를 구하는 방법은 여러가지가 있습니다. 플로이드 와샬 알고리즘에 대해서 알아보기 전에 이에 대해서 간단히 살펴보도록 하겠습니다. 하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제 single source and single destination shortest path problem 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제 single source shortest path problem 하나의 목적지로가는 모든 최단 경로를 구하는 문제 single destination shortest path problem 모든 최단 경로를 구하는 문제 all pairs shortest path problem Floyd-Warshall 알고리즘이란? Fl..
Bellman-Ford 알고리즘이란? Bellman-Ford 알고리즘이란, 한 노드에서 다른 노드까지의 최단거리를 구하는 알고리즘입니다. 벨만포드 알고리즘 외에 최단거리를 구하는 알고리즘은 여럿 있지만 벨만포드는 가중치가 음수 일 때도 사용이 가능합니다. 하지만 다익스트라 알고리즘에 비해 느리므로 가중치가 모두 양수일 경우에는 굳이 벨만포드 알고리즘을 사용할 필요가 없습니다. 음수간선 음수간선이 있을 경우 어떠한 문제가 생길지 알아보도록 하겠습니다. 아래 그래프에서 s 에서 출발하여 g 로 도착하는 경우를 생각해봅시다. s -> a -> b -> g 이 경우도 물론 음수간선이 존재합니다. 하지만 문제가 되는 경우는 없습니다. 3+(-4)+4 로 가중치 3으로 도착할 수 있습니다. s -> c -> d -..
Prim 알고리즘이란? Prim 알고리즘이란, 그래프에서 MST 를 찾는 알고리즘입니다. MST 가 무엇인지 모르신다면 아래 링크를 참고해주세요. Spanning Tree 와 MST [Algorithm] Spanning Tree 와 MST, 스패닝 트리와 최소 스패닝 트리 Spanning Tree 란? Spanning Tree 란 스패닝 트리라고 읽으며 다른 말로 신장트리 라고도 합니다. 이는 그래프 내의 모든 정점을 포함하는 트리를 말합니다. 그래프의 일부 간선을 이용해 만든 트리로서 항상 그래.. ssungkang.tistory.com 이 알고리즘은 MST 를 찾기 위해서 시작 정점에서부터 단계적으로 확장해나갑니다. 특이한 점은 MST 를 찾기위해서는 간선을 선택해야 하지만 Prim 은 정점 선택을 ..
Kruskal 알고리즘이란? Kruskal 알고리즘이란, 그래프에서 MST 를 찾는 알고리즘입니다. MST 가 무엇인지 모르신다면 아래 링크를 참고해주세요. Spanning Tree 와 MST [Algorithm] Spanning Tree 와 MST, 스패닝 트리와 최소 스패닝 트리 Spanning Tree 란? Spanning Tree 란 스패닝 트리라고 읽으며 다른 말로 신장트리 라고도 합니다. 이는 그래프 내의 모든 정점을 포함하는 트리를 말합니다. 그래프의 일부 간선을 이용해 만든 트리로서 항상 그래.. ssungkang.tistory.com 이 알고리즘은 MST 를 찾기 위해서 greedy 하게 접근합니다. greedy 하게 접근한다는 말은 현재 순간에 최적의 선택을 한다는 의미인데 최소 비용으..
Spanning Tree 란? Spanning Tree 란 스패닝 트리라고 읽으며 다른 말로 신장트리 라고도 합니다. 이는 그래프 내의 모든 정점을 포함하는 트리를 말합니다. 그래프의 일부 간선을 이용해 만든 트리로서 항상 그래프의 부분집합이 됩니다. Spanning Tree 의 특징 Spanning Tree 는 이름에서도 알 수 있듯이 트리 중 하나이기 때문에 트리의 특징은 모두 포함합니다. 하나의 그래프에는 여러 Spanning Tree 를 가질 수 있습니다. 모든 정점을 포함하고 사이클은 생기면 안되기 때문에 N 개의 노드에 대해서 정확하게 N-1 개의 엣지를 가지게 됩니다. MST 란? MST 란 Spanning Tree의 한 종류로서 사용되는 간선의 가중치 합이 최소인 트리를 말합니다. 이 때 ..