| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |
- c++
- js
- Algorithm
- Baekjoon
- PYTHON
- MAC
- 알고리즘 문제
- django rest framework
- HTML
- 장고
- 파이썬 알고리즘
- 알고리즘 연습
- java
- javascript
- django ORM
- DRF
- CSS
- 백준
- AWS
- 파이썬
- react
- form
- Git
- django widget
- web
- 알고리즘 풀이
- API
- Django
- es6
- 알고리즘
- Today
- Total
목록알고리즘 (87)
수학과의 좌충우돌 프로그래밍
https://www.acmicpc.net/problem/2875 2875번: 대회 or 인턴 문제 백준대학교에서는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다. (왜인지는 총장님께 여쭈어보는 것이 좋겠다.) 백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다. 그런데 올해에는 대회에 참여하려는 학생들 중 K명을 반드시 인턴쉽 프로그램에 참여하라는 학교의 방침이 생기게 되었다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다. 백준대학교에서는 뛰어난 인재들이 많기 때문 www.acmicpc.net 그리디 알고리즘 을 이용해서 문제를 두 가지 방법으로 해결하였습니다. O(K) 남녀의 인원 수를 비교하며 팀의 개수를 최대로 할 ..
https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다. 예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열 www.acmicpc.net 그리디 알고리즘 을 이용해서 문제를 해결하였습니다. 합이 최대가 되기 위해서는 절대값이 큰 수끼리 묶어주어야 합니다. 양수에 대해서는 큰..
https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. www.acmicpc.net 그리디 알고리즘 을 이용해서 문제를 해결하였습니다. 식의 값이 최소가 되기 위해서는 - 가 나온 순간 괄호를 쳐서 그 이후에 나오는 + 들을 전부 음수로 바꿔주면 됩니다. 값을 담는 벡터와 부호를 담는 벡터를 선언하여 들어오는 값을 나누어 넣어준 후 하나씩 꺼내보면서 위의 과정을 실행하였습니다. #include #include usi..
어느 회의실을 선택할지에 대해서 그리디 알고리즘 을 통해 접근합니다. 현재 순간에 최선의 선택지를 고르는 것으로 말이죠. 그렇다면 현재 순간의 최선이라면 어떤 희의를 골라야할까요? 여러 가지 경우를 생각할 수 있습니다. 시작 시간이 가장 빠른 회의, 회의시간이 가장 짧은 회의 등등 여러 경우가 있지만 각각은 반례가 존재하고 정답은 종료시간이 가장 빠른 회의입니다. 언제 시작하더라도 얼마나 회의를 하더라도 가장 빠르게 종료한다면 다음 회의를 진행하는데 있어서 유리합니다. https://www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net #include #include #includ..
그리디 알고리즘은 한국어로 탐욕 알고리즘 이라고도 하며 결정해야 하는 순간 가장 좋다고 생각하는 것을 선택하면서 답을 찾아가는 알고리즘을 말합니다. 이 방식의 한계점은 그 순간에는 최적일지도 모르지만 최종적으로는 답이 아닐 수 있는 경우가 많기 때문에 그리디 알고리즘을 사용한 경우, 최적이라는 걸 입증하는게 쉽지 않습니다. 그래도 입증만 한다면 구현하는건 다른 알고리즘에 비해 쉬운 편입니다. 문제를 풀면서 이해해보도록 하겠습니다. 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..
https://www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개가 차례대로 주어진다. N과 M, 그리고 K는 100보다 작거나 같고, 행렬의 원소는 절댓값이 100보다 작거나 같은 정수이다. www.acmicpc.net 행렬을 제곱하는 문제입니다. B 범위가 100,000,000,000 까지 이기 때문에 곱셈을 여러 번 한다면 시간복잡도에 걸리게 됩니다. 따라서 행렬에 대해서 분할 정복을 통해서 제곱을 수행합니다. 그리고 행렬의 곱셈을 하는 함수 matrixMul와 단위..
피보나치 수는 일반적으로 재귀적으로 구할 수 있지만 이 경우 함수 호출이 많아져서 많은 시간이 소요되게 됩니다. 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
https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 단순히 사칙연산 처럼 보이는 문제입니다. 그렇게 때문에 19년 9월 8일 문제를 푼 시점에 정확도는 25%로 매우 낮지만 정확도 만큼 어려운 문제는 아니었습니다. 분할 정복을 이용한 a^b [Algorithm] 분할 정복을 이용한 a^b a^b, a 제곱 b 는 일반적으로 다음과 같이 구현할 수 있습니다. int pow(int a,int b){ int result = 1; for (int i=0;i> a >> b >> c; cout
