| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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++
- Git
- es6
- 파이썬
- 장고
- Algorithm
- java
- js
- PYTHON
- API
- DRF
- 파이썬 알고리즘
- django widget
- AWS
- web
- Django
- 알고리즘 연습
- javascript
- CSS
- Baekjoon
- 알고리즘
- 알고리즘 문제
- MAC
- django rest framework
- 백준
- form
- react
- django ORM
- HTML
- Today
- Total
목록알고리즘/C++ (56)
수학과의 좌충우돌 프로그래밍
https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으 www.acmicpc.net 분할정복 을 사용하여 문제를 해결하였습니다. 문제를 해결하는 핵심 함수 check 와 배열의 원소들이 같은지 확인하는 same 함수를..
https://www.acmicpc.net/problem/11728 merge sort 에서 나눠진 배열을 합치는 과정과 같습니다. 두 배열을 계속 비교하며 작은 값을 새로운 배열에 넣어주고, 한 쪽 배열의 수들이 끝났으면 남은 배열의 값들을 그대로 복사해서 뒤에 추가해주도록 합니다. #include #include using namespace std; int a[1000001]; int b[1000001]; int c[2000002]; int main(int argc, const char * argv[]) { cin.tie(0); ios::sync_with_stdio(false); int N,M; cin >> N >> M; for (int i=0;i> a[i]; } for (int i=0;i> b[i]..
https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5 www.acmicpc.net 기본적인 하노이탑 구현 문제입니다. #include using namespace std; void hanoi(int n,..
https://www.acmicpc.net/problem/2873 2873번: 롤러코스터 문제 상근이는 우리나라에서 가장 유명한 놀이 공원을 운영하고 있다. 이 놀이 공원은 야외에 있고, 다양한 롤러코스터가 많이 있다. 어느 날 벤치에 앉아있던 상근이는 커다란 황금을 발견한 기분이 들었다. 자신의 눈 앞에 보이는 이 부지를 구매해서 롤러코스터를 만든다면, 세상에서 가장 재미있는 롤러코스터를 만들 수 있다고 생각했다. 이 부지는 직사각형 모양이고, 상근이는 R행 C열의 표 모양으로 나누었다. 롤러코스터는 가장 왼쪽 위 칸에서 시작할 것이고, 가 www.acmicpc.net 그리디 알고리즘 을 사용하여 문제를 해결하였습니다. 가로와 세로의 길이에 따라서 갈 수 있는 경로가 다릅니다. 가로와 세로의 길이 중 ..
https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 그리디 알고리즘 을 사용하여 문제를 해결하였습니다. 세로에 대해서는 세로길이-2 까지, 가로에 대해서는 가로길이-2 까지 순회를 하며 행렬을 뒤집을지 말지 결정해주었습니다. (0,0) 부분에 대해서 영향을 미치는 경우는 좌측 상단 모서리에 위치한 3*3 부분 행렬을 뒤집을 때 뿐이고 이 연산을 수행한 후, (0,1) 부분에 영향을 미치는 경우는 (0,1) 부터 시작하는 3*3 부분 행렬을 뒤집을 때 뿐입니다. ..
https://www.acmicpc.net/problem/10610 10610번: 30 문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. 입력 N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 출력 미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는 www.acmicpc.net 그리디 알고리즘을 사용하여 문제를 해결하였습니다. 30의 배수인지 확인하기 위해서 두 가지를 검사해주었습니다. 3의 배수이기 위해서는 각..
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..