일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 알고스팟
- union-find
- acm
- Algospot
- 종만북
- BOJ
- Greedy
- 이분탐색
- 동적계획법
- 백트래킹
- stack
- 완전탐색
- DP
- 누적합
- 분리집합
- 그리디
- 문자열
- backtracking
- 분할정복
- 다이나믹프로그래밍
- BFS
- 유니온파인드
- 알고리즘문제해결전략
- 스택
- 백준
- priority_queue
- 재귀
- 세그먼트트리
- 너비우선탐색
- DFS
- Today
- Total
목록Problem Solving/BOJ 문제풀이 (34)
DAMPER's blog
https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 수열의 최대 크기가 1,000,000 인 LIS 문제이다. LIS 의 크기만 구하는 문제가 아닌, 정답이 될 수 있는 LIS 하나 출력하는 문제. \( O(NlogN) \) LIS 알고리즘 (이분탐색) + 넣을 때마다 인덱싱 저장으로 문제를 해결할 수 있었음. /* 수정 중 */ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2..
https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 부분수열의 합 1 문제에서 사이즈만 다른 문제. 부분수열의 합 1 문제에서는 \( 1 second; return; } dfsR(pos+1, sum+v[pos], v, mp); dfsR(pos+1, sum, v, mp); } int32_t main() { cin.sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL); c..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/3Uary/btrcGT2yc26/iAaau6YoHRpHR0lvO5y3q1/img.png)
https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net Dynamic Programmming 기본 문제들 중 하나이다. LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 이 때, 이문제는 LCS의 길이만을 출력하는 것이 아닌, 해당 부분 문자열을 찾는 문제이다. LCS를 찾는 점화..
https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 온라인게임으로 했던 2048 게임을 구현하는 문제이다. https://play2048.co/ 2048 Join the numbers and get to the 2048 tile! Careful: this game is extremely addictive! play2048.co 5번까지 움직여서 나오는 최대 숫자는 무언인지 출력하는 문제. 4방향을 움직여야하는데, 방향마..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/VdbWI/btrcb9MsqO0/FaEuHq00eNxd9TFDFI2WW0/img.png)
https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 가지고 있는 열쇠와 빌딩 바닥에 놓인 열쇠를 가지고 잠긴 문을 열어 가져울 수 있는 문서의 최대 개수를 구하는 문제. 처음에 헷갈렸던 점은 우리가 찾아야할 것이 문서의 최대 개수라는 것이다. 문서를 가져오는데 걸리는 시간이 아니라. 문서를 모두 가져오는데 걸리는 시간이라고 문제에 적혀있지도 않은데 자연스럽게 그렇게 생각했다. 이런 비슷한 문제를 풀어봤다는 생각에 문제를 대충읽은 것이다. 그러다 다시 제대로 이..
https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 두 용액의 특성도 합이 0이 되도록 하는 문제의 업그레이드 버전이다. 서로다른 세 용액을 합쳐 특성도가 0이 가깝도록 만드는 문제이다. N의 최대가 5000이라 서로다른 두 용액의 특성도를 합친 합배열을 만들어서(N^2) 특성도의 합과 인덱스를 같이 저장한다. 그리고 용액배열 N개를 돌면서 합배열에서 이분탐색으로 0에 가장 가까운 세 용액을 찾으려했다. 하지만 이렇게 할 경우..