| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 widget
- django ORM
- HTML
- 파이썬
- 알고리즘 풀이
- django rest framework
- js
- web
- 알고리즘
- CSS
- DRF
- API
- AWS
- es6
- Git
- react
- form
- 알고리즘 연습
- 장고
- javascript
- Django
- MAC
- PYTHON
- 알고리즘 문제
- Baekjoon
- 파이썬 알고리즘
- c++
- java
- Algorithm
- Today
- Total
목록알고리즘 (87)
수학과의 좌충우돌 프로그래밍
https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다. www.acmicpc.net 동적계획법 중 top-down 방식을 사용했습니다. dp[i][j] 는 i 부터 j 까지의 행렬을 곱하는 연산의 최솟값 으로 정의하였습니다. i, j 가 인접해있다면, 즉 1 차이가 난다면 두 행렬의 곱셈을 직접 계산해주고 인접해있지 않다면 부분으로 쪼개 각각을 계산해준 후, 계산한 결과인 두 개의 행렬의 곱셈은 직접 계산해주었습니다. #include #include using n..
https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 www.acmicpc.net 동적계획법을 사용하여 문제를 해결하였습니다 . 그 중에서도 top-down 방식입니다. dp[i][j] 는 i 부터 j 까지의 파..
https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지 www.acmicpc.net 동적계획법을 사용한 문제입니다. dp[i][j] 을 (i,j) 에서 시작해서 (N,M) 까지 가는 경로의 수 라고 정의하였습니다. 이 ..
https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 동적계획법을 활용한 문제입니다. dp[i] 를 i 원에 대해서 주어진 동전으로 만들 수 있는 경우의 수라고 정의했습니다. 처음에는 동전을 하나만 사용하여 계산할 수 있는 경우의 수를 채우고, 이를 활용하여 동전 2개를 사용했을 경우, 3개, 4개 … 다음과 같이 늘려나가게 됩니다. 주어진 문제의 예시 처럼 1,2,5 원으로 10원을 만들려고 한다면 10원을 만드는 경우의수 = 9원까지의 경우의 수(..
https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net 동적계획법으로 접근하였습니다. dp[i] 에 대해 i 번 째 포도주 까지에 대해 최대로 마실 수 있는 포도주의 양 이라고 정의했습니다..
https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하는 프로그램을 작성하시오. www.acmicpc.net 지난 포스팅에서는 팰린드롬인지 아닌지 판별하는 문제를 동적계획법을 이용해서 해결해보았습니다. 팰린드롬? [C++] BAEKJOON 10942 팰린드롬? https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으..
https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 일반적으로 팰린드롬을 판별하기 위해서는 맨 앞과 맨 뒤, 앞에서 두번째와 뒤에서 두번째 … 다음과 같이 비교해봐야 하므로 O(N) 의 시간복잡도가 걸립니다. 이 문제 같은 경우에는 질문이 M 개이므로 전체 시간복잡도는 O(MN) 이 됩니다. 이 때 M 의 범위가 1 ≤ M ≤ 1,000,000 이므로 시간초과에 걸리게 됩니다. 이를 해결하기 위해서 동적계획법 으로 접근하였습니다. 길이가 1 인 경우 길이가 1인 경우에는 앞에서 읽던 뒤..
https://www.acmicpc.net/problem/1890 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 www.acmicpc.net 처음에는 bfs 나 dfs 를 생각하기 쉬운 문제지만 dp 를 사용해서 해결해야하는 문제입니다. dp 배열을 생성하여 각 원소는 해당 지점까지..
5052번: 전화번호 목록 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다. 예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자 긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 www.acmicpc.net Trie 자료구조를 사용하는 문제였습니다. Trie 자료구조란? [Algorithm] Trie 자료구조 KMP 알고리즘 에 이어서 문자열에서 검색에 위한 새로운 방법들을 알아보도록 하겠습니다. 이번에..
KMP 알고리즘 에 이어서 문자열에서 검색에 위한 새로운 방법들을 알아보도록 하겠습니다. 이번에 알아볼 내용은 Trie 자료구조입니다. Trie 자료구조 문자열 집합, {AB, ACD, ACEF, ACEG, HB, HC} 에 대해 Trie 자료구조가 어떻게 그려지는지 살펴보도록 합시다. 시작 부분이 같은 단어끼리 부모를 공유한다면, 다음과 같은 트리 모양을 얻을 수 있습니다. 이 트리에 대하여 탐색을 진행할 경우, 트리의 시간 복잡도는 O(H) (H 는 트리의 높이) 가 될 것입니다. 그리고 트리의 높이는 문자열 집합 중 가장 긴 문자열의 길이와 동일하기 때문에 Trie 자료구조를 사용하면 가장 긴 문자열의 길이를 M 이라 했을 때, O(M) 만에 문자열 검색이 가능합니다. 언제 사용해야 하지? Trie..