| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |
- 알고리즘
- django ORM
- 알고리즘 풀이
- django rest framework
- Baekjoon
- 파이썬 알고리즘
- API
- javascript
- react
- web
- CSS
- 파이썬
- Django
- java
- PYTHON
- 알고리즘 연습
- es6
- MAC
- js
- AWS
- c++
- 장고
- Algorithm
- HTML
- django widget
- form
- Git
- DRF
- 알고리즘 문제
- 백준
- Today
- Total
목록알고리즘/C++ (56)
수학과의 좌충우돌 프로그래밍
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..
이번 포스팅에서는 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/17968 17968번: Fire on Field We define A as a sequence of positive integers like the following. Let A[0] = 1, A[1] = 1. For a positive integer i ≥ 2, A[i] is the smallest positive integer under the condition that no three terms A[i − 2k], A[i − k], and A[i] form an arithmetic progress www.acmicpc.net 2019 acm icpc Seoul A번 입니다. 해당 대회의 문제 중에 제일 쉬운 문제로 단순 구현 문제입니다. #..
https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다. 시작 www.acmicpc.net 전형적인 플로이드 와샬 알고리즘을 사용하여 해결하는 문제였습니다. 플로이드 와샬 알고리즘이란? [Algorithm] 플로이드 와샬(F..
https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 현재 주어진 상황에서 몇연쇄가 되는지 출력하라. (하나도 터지지 않는다면 0을 출력하면 된다.) www.acmicpc.net dfs 를 사용하여 문제를 해결하였습니다. 사실 dfs 를 이용한 접근보다 구현 쪽에 치중되어 있는 문제입니다. dfs 를 사용하여 같은 상하좌우 붙어있는 같은 색상을 찾아 해당 좌표를 v vector 에 넣어주었습니다. v vector 의 크기가 4 이상이면 삭제가 가능한 블록이므로 v_total vector 에 넣어주었습니다. 바로 삭제하지 않고 한 번에 모아서 삭제하는 이유는 동시에 깨지는 블록들의 경우에는 별도의 갯수로 세지 않기 때문입니다. v_total vector 가 비..
https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지 www.acmicpc.net dfs 를 이용하여 문제를 해결하였습니다. 매 년 마다 dfs 를 순회하여 빙산을 없애줍니다. 빙산을 한 번에 없애면 같은 년도에 먼저 없어..
https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다. www.acmicpc.net bfs 를 이용하여 문제를 해결하였습니다. 인접리스트를 이용하여 각 유저간의 연결 관계를 표시합니다. for (int i=0;i> n1 >> n2..
https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 문제 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서 www.acmicpc.net BFS 를 이용하여 문제를 해결하였습니다. 건물이 층, 폭, 너비 3차원이기 때문에 3차원 배열과 각 좌표를 담을 수 있는 pair3 ..
https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다. 이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북 www.acmicpc.net dfs 와 bfs, 두 방법을 사용하여 문제를 해결하였습니다. dfs 를 사용하여 각 섬을 구분지어주었습니다. 1110000222 1..