| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |
- 알고리즘 연습
- django ORM
- 알고리즘 풀이
- java
- js
- AWS
- API
- MAC
- c++
- DRF
- web
- form
- javascript
- django rest framework
- react
- django widget
- 파이썬
- 장고
- 파이썬 알고리즘
- 백준
- PYTHON
- HTML
- Git
- 알고리즘
- Baekjoon
- Django
- es6
- CSS
- 알고리즘 문제
- Algorithm
- Today
- Total
목록알고리즘/이론 (20)
수학과의 좌충우돌 프로그래밍
세그먼트 트리(Segment Tree)란? 배열에 부분 합을 구할 때 사용하는 개념입니다. 이 때 문제는 배열의 값이 지속적으로 바뀔 수 있기 때문에 매 순간 배열의 부분 길이 만큼, 즉 O(N) 만큼의 시간이 걸리기 때문에 이를 트리로 구현하여 O(logN) 의 시간으로 해결하는 방법입니다. 배열을 세그먼트 트리로 세그먼트 트리 를 사용하기 위해서는 주어진 배열을 이진 트리 구조로 만들어야 합니다. 이 때 트리를 구현하는 알고리즘은 다음과 같습니다. 부모노드의 값은 양 쪽 자식 노드 값의 합 배열의 요소들은 리프 노드에 위치 위 알고리즘을 통해 N = 10 일 때의 세그먼트 트리를 그리면 다음과 같습니다. 이 때 기존 데이터의 배열의 크기를 통해서 트리 배열의 최대 크기를 알 수 있습니다. 기존 데이터..
비트 마스크란? 비트마스크란 컴퓨터의 언어인 이진수를 활용하여 정수를 이진수 형태로 표현하여 비트연산을 활용하는 방법입니다. 기본적인 비트 연산 기본적인 비트연산들을 표로 정리해보았습니다. A B ~A A&B A|B A^B 0 0 1 0 0 0 0 1 1 0 1 1 1 0 0 0 1 1 1 1 0 1 1 0 not 연산을 할 경우 주의해야할 점이 자료형에 따라서 결과가 달라집니다. A = 83 = 1010011(2) 에 대하여 8비트 자료형의 경우 ~A = 10101100(2) 32비트 자료형인 경우 ~A = 11111111 11111111 11111111 10101100(2) 쉬프트 연산 쉬프트 연산은 다음과 같이 부등호 2개로 표현하며 A
유니온 파인드 알고리즘이란? 그래프 알고리즘의 일종으로서 상호 배타적 집합, Disjoint-set 이라고도 합니다. 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘입니다. 그러기 위해 두 가지 연산이 존재합니다. Find 노드 x 가 어느 집합에 포함되어 있는지 찾는 연산 Union 노드 x가 포함된 집합과 노드 y가 포함된 집합을 합치는 연산 유니온 파인드 구현 구현은 간단한 트리를 통해서 이루어집니다. parent[i] 를 i 노드의 부모 노드 라고 정의하고 초기화 해줍니다. parent[i] = i 인 경우, 루트노드 임을 의미합니다. int parent[MAX_SIZE]; for (int i=0; i
Divide and Conquer Divide and Conquer 는 분할정복 알고리즘이라고도 하며, 문제를 2개 또는 그 이상의 작은 부분 문제로 나눠서 문제를 해결하는 알고리즘을 말합니다. 경우에 따라서는 푼 다음에 다시 부분 문제들을 합쳐서 정답을 구할 때도 있으며 퀵 정렬, 병합정렬, 큰수곱셈, FFT 등 여러 분야에서 분할정복 알고리즘을 이용하여 문제를 해결하고 있습니다. Divide and Conquer VS danamic programming 분할정복 알고리즘과 다이나믹 프로그래밍은 문제를 해결하는 핵심적인 전략이 동일합니다. 바로 문제를 작은 부분 문제로 나눠서 해결한다는 점입니다. 하지만 둘은 결정적인 차이가 존재하는데 바로 memorization 입니다. 다이나믹 프로그래밍은 작은 부..
그리디 알고리즘은 한국어로 탐욕 알고리즘 이라고도 하며 결정해야 하는 순간 가장 좋다고 생각하는 것을 선택하면서 답을 찾아가는 알고리즘을 말합니다. 이 방식의 한계점은 그 순간에는 최적일지도 모르지만 최종적으로는 답이 아닐 수 있는 경우가 많기 때문에 그리디 알고리즘을 사용한 경우, 최적이라는 걸 입증하는게 쉽지 않습니다. 그래도 입증만 한다면 구현하는건 다른 알고리즘에 비해 쉬운 편입니다. 문제를 풀면서 이해해보도록 하겠습니다. BAEKJOON 동전 0 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. ..
이항 계수는 기본적으로 factorial 을 이용해서 계산하기 때문에 수가 클 경우 일반적인 방법으로 계산하기 쉽지 않습니다. 그래서 각 경우에 대해서 어떻게 구해야하는지 알아보도록 하겠습니다. 이항계수 1 https://www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net n 과 k 의 값이 10 이하의 수로 굉장히 작습니다. 그렇기 때문에 fac_list 에 factorial 값을 미리 계산해놓고 index 로 참조하여 이항계수를 빠르게 구할 수 있습니다. #include using namespace std; int fac_list[1..
피보나치 수는 일반적으로 재귀적으로 구할 수 있지만 이 경우 함수 호출이 많아져서 많은 시간이 소요되게 됩니다. n 의 값에 따라서 이에 대해서 어떻게 접근해야할지가 다릅니다. 여러 문제를 해결하며 이를 알아보도록 하겠습니다. BAEKJOON 247 피보나치 수 1 불러오는 중입니다... n 번째 피보나치 수를 구하는 문제입니다. n 의 범위가 45 보다 작거나 같기 때문에 int 자료형으로 해결이 가능합니다. #include using namespace std; int main(int argc, const char * argv[]) { int fibo[46]; fibo[0] = 0; fibo[1] = 1; for (int i=2;i> N; cout N; cout
a^b, a 제곱 b 는 일반적으로 다음과 같이 구현할 수 있습니다. int pow(int a,int b){ int result = 1; for (int i=0;i
KMP 알고리즘 에 이어서 문자열에서 검색에 위한 새로운 방법들을 알아보도록 하겠습니다. 이번에 알아볼 내용은 Trie 자료구조입니다. Trie 자료구조 문자열 집합, {AB, ACD, ACEF, ACEG, HB, HC} 에 대해 Trie 자료구조가 어떻게 그려지는지 살펴보도록 합시다. 시작 부분이 같은 단어끼리 부모를 공유한다면, 다음과 같은 트리 모양을 얻을 수 있습니다. 이 트리에 대하여 탐색을 진행할 경우, 트리의 시간 복잡도는 O(H) (H 는 트리의 높이) 가 될 것입니다. 그리고 트리의 높이는 문자열 집합 중 가장 긴 문자열의 길이와 동일하기 때문에 Trie 자료구조를 사용하면 가장 긴 문자열의 길이를 M 이라 했을 때, O(M) 만에 문자열 검색이 가능합니다. 언제 사용해야 하지? Trie..
한글, 워드 등의 에티터는 물론이고 웹페이지에서도 찾기 기능이 존재합니다. 본인이 원하는 단어나 음절이 있을 시에 이를 빠르게 찾아 줄 수 있는 기능이죠. KMP 는 바로 이 검색을 위한 알고리즘으로서 알고리즘을 만든 인물들, Knuth, Morris, Pratt 세 명의 이름을 따서 지었습니다. 이 알고리즘이 어떻게 동작하는지 함께 알아보도록 합시다. 단순한 문자열 검색 특별한 알고리즘 없이 문자열 검색을 구현한다면 아마 다음과 같이 생각하기 쉽습니다. 두 개의 문자열 P 와 T 에 대하여 문자열 P 가 문자열 T 에 몇 번이나 어느 위치에 있는지를 찾아야하는 문제입니다. 이 때 T의 길이를 n, P의 길이를 m 이라고 하면, 일반적으로 n>=m 이 성립합니다. n 0 && p[i] != p[j]) j..