| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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
- form
- java
- 알고리즘 풀이
- DRF
- Django
- PYTHON
- 백준
- js
- 알고리즘 연습
- django rest framework
- django widget
- c++
- 알고리즘 문제
- Algorithm
- 파이썬 알고리즘
- MAC
- javascript
- 파이썬
- Baekjoon
- es6
- API
- HTML
- web
- react
- AWS
- Git
- django ORM
- 알고리즘
- Today
- Total
목록c++ (12)
수학과의 좌충우돌 프로그래밍
위상정렬이란? 위상 정렬은 순서가 정해져있는 작업 차례로 수행해야 할 때, 그 순서를 결정해주는 알고리즘입니다. 그림을 보며 이해해봅시다. 다음과 같은 그래프에서 앞선 작업 2,3이 끝나야 뒤 작업 4가 이루어질 수 있으며 이 때 둘 중 무엇을 먼저 끝내던 규칙에 위배 되지 않기 때문에 경로는 여러 개가 나올 수 있습니다. 단 위상정렬이 성립하기 위해서는 DAG여야 합니다. DAG란? Directed Acyclic Graph의 줄임말로 사이클이 존재하지 않는 방향 그래프입니다. 만일 위 그림에서 5이 1에 연결되었다면 시작점이 존재하지 않기 때문에 위상정렬이 성립할 수 없습니다. 위상 정렬 원리 위상 정렬이 어떤 원리로 동작하는지 살펴봅시다. 위상 정렬을 스택이나 큐를 사용하여 구현할 수 있지만 큐를 사..
https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 문제는 아주 간단합니다. Combination을 계산하는 문제로, 파스칼 삼각형을 이용하여 문제를 해결하려 하였습니다. 그런데 n, m의 값이 커지면 unsigned long long으로도 데이터를 전부 표현할 수 가 없어 덧셈을 문자열로 구현하였습니다. #include #include using namespace std; // nCm : pascal[i][j] string pascal[101][101]; string add_string_num(string a, string b) { int aidx = a.siz..
규정 상의 이유로 출처와 문제는 밝힐 수 없지만 코딩테스트를 보다가 연속 구간의 최대 합을 구하는 문제를 접하게 되었습니다. 문제를 푸는 방법이 굉장히 다양하고 각 풀이 방법의 복잡도가 전부 다르기 때문에 이에 대해서 정리해보고자 합니다. 연속 구간의 합 우선 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
이번 포스팅에서는 C++ stl container인 set과 mutiset에 대해서 알아보도록 하겠습니다. set set 은 데이터를 저장할 수 있는 container입니다. 가장 기본적인 container와 다른 점은 자동으로 정렬이 된다는 점입니다. 새로운 값이 삽입, 삭제 될 때마다 이 정렬 상태를 유지하고 있어야 하므로 set 은 기본적으로 binary search tree로 구현이 되어 있습니다. set 선언 set 을 사용하기 위해서는 헤더 파일을 포함해야합니다. #include 그 후에는 보통 container들과 마찬가지로 다음과 같이 선언할 수 있습니다. set 이름; int 자료형을 저장할 s라는 이름의 set을 만들기 위해서는 다음과 같이 선언해줍니다. set s; 선언 시, 어떠한 ..
타 언어는 문자열을 나누는 split 함수가 존재하지만 c++은 존재하지 않습니다. 따라서 알고리즘 문제를 풀면서 이러한 부분을 직접 구현해서 사용하곤 하였는데 자주 사용하다보니 이를 정리해 놓을 필요성을 느꼈습니다. split 함수와 같은 기능을 수행하는 방법은 많지만 그 중에서 stringstream을 사용해보도록 하겠습니다. stringsteam 을 사용한 split #include #include #include using namespace std; vector split(string str, char delimiter); int main(){ string test = "min sung kang"; vector result = split(test, ' '); for (int i=0;i
https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. ( www.acmicpc.net dfs 를 이용해서 구현하였습니다. K 번 만큼 받은 좌표를 통해 board 를 완성한 후, 연결되는 구간이 몇 개인지 세주는 문제였..
a^b, a 제곱 b 는 일반적으로 다음과 같이 구현할 수 있습니다. int pow(int a,int b){ int result = 1; for (int i=0;i
한글, 워드 등의 에티터는 물론이고 웹페이지에서도 찾기 기능이 존재합니다. 본인이 원하는 단어나 음절이 있을 시에 이를 빠르게 찾아 줄 수 있는 기능이죠. KMP 는 바로 이 검색을 위한 알고리즘으로서 알고리즘을 만든 인물들, Knuth, Morris, Pratt 세 명의 이름을 따서 지었습니다. 이 알고리즘이 어떻게 동작하는지 함께 알아보도록 합시다. 단순한 문자열 검색 특별한 알고리즘 없이 문자열 검색을 구현한다면 아마 다음과 같이 생각하기 쉽습니다. 두 개의 문자열 P 와 T 에 대하여 문자열 P 가 문자열 T 에 몇 번이나 어느 위치에 있는지를 찾아야하는 문제입니다. 이 때 T의 길이를 n, P의 길이를 m 이라고 하면, 일반적으로 n>=m 이 성립합니다. n 0 && p[i] != p[j]) j..
문제보러가기 8901번: 화학 제품 문제 상근이는 각기 다른 병에 담긴 세 화학 물질 A, B, C를 가지고 있다. 두 화학 물질을 같은 양만큼 혼합하면, 화학 제품을 얻을 수 있다. A와 B를 혼합하면 AB가 되고, B와 C를 혼합하면 BC, C와 A를 혼합하면 CA가 된다. (A 하나와 B 하나를 혼합하면 AB 하나를 얻게 된다) AB, BC, CA의 가격은 모두 다르다. 따라서, 만드는 화학 제품에 따라서 얻는 이익은 달라진다. 항상 정수 단위 만큼 두 화학 물질을 혼합할 수 있다. www.acmicpc.net 입력으로 주어지는 모든 숫자는 1000이하이기 떄문에 다음과 같이 어렵지 않게 접근하였습니다. ab 혼합물의 수를 0부터 a,b의 갯수의 최소값까지 만들어준다. bc 혼합물의 수를 0 부터 ..
문제보러가기 8895번: 막대 배치 문제 높이가 1, 2, ..., n인 막대 n개가 일렬로 배치되어 있다. 막대를 왼쪽이나 오른쪽에서 보면, 큰 막대가 뒤에있는 작은 막대를 가리게 된다. 아래와 같이 4개의 막대로 이루어진 두 배치를 살펴보자. 위의 두 배치는 모두 왼쪽에서 봤을 때 막대가 한 개 보이고, 오른쪽에서 봤을 때는 막대가 두 개 보인다. 막대의 개수 n과 왼쪽에서 봤을 때 보이는 막대의 개수 l, 오른쪽에서 봤을 때 보이는 막대의 개수 r이 주어진다. 이때, 이러한 결과를 만 www.acmicpc.net 동적계획법을 사용한 문제였습니다. 먼저 점화식을 세워보도록 하겠습니다. dp[n][l][r] 를 n 개의 막대에 대해, 왼쪽에서 보이는 막대가 l 개, 오른쪽에서 보이는 막대가 r 개인 경..