| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |
- API
- PYTHON
- Baekjoon
- 알고리즘
- javascript
- 알고리즘 문제
- MAC
- 알고리즘 연습
- Django
- 파이썬 알고리즘
- form
- Algorithm
- django widget
- CSS
- js
- DRF
- web
- Git
- HTML
- c++
- AWS
- 파이썬
- django ORM
- es6
- 백준
- 알고리즘 풀이
- java
- 장고
- django rest framework
- react
- Today
- Total
목록Algorithm (5)
수학과의 좌충우돌 프로그래밍
이번 포스팅에서는 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
한글, 워드 등의 에티터는 물론이고 웹페이지에서도 찾기 기능이 존재합니다. 본인이 원하는 단어나 음절이 있을 시에 이를 빠르게 찾아 줄 수 있는 기능이죠. KMP 는 바로 이 검색을 위한 알고리즘으로서 알고리즘을 만든 인물들, Knuth, Morris, Pratt 세 명의 이름을 따서 지었습니다. 이 알고리즘이 어떻게 동작하는지 함께 알아보도록 합시다. 단순한 문자열 검색 특별한 알고리즘 없이 문자열 검색을 구현한다면 아마 다음과 같이 생각하기 쉽습니다. 두 개의 문자열 P 와 T 에 대하여 문자열 P 가 문자열 T 에 몇 번이나 어느 위치에 있는지를 찾아야하는 문제입니다. 이 때 T의 길이를 n, P의 길이를 m 이라고 하면, 일반적으로 n>=m 이 성립합니다. n 0 && p[i] != p[j]) j..