일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 백트래킹
- 분할정복
- DFS
- backtracking
- union-find
- 너비우선탐색
- 스택
- BOJ
- priority_queue
- 백준
- 알고스팟
- Algospot
- 완전탐색
- 동적계획법
- 다이나믹프로그래밍
- 누적합
- 알고리즘문제해결전략
- acm
- 이분탐색
- 분리집합
- stack
- 재귀
- 세그먼트트리
- BFS
- 문자열
- 종만북
- 그리디
- Greedy
- 유니온파인드
- DP
- Today
- Total
목록전체 글 (105)
DAMPER's blog
다음은 책에서 제시하는 최적화 문제의 동적 계획법을 설계하기 위한 과정입니다. 이 과정이 모든 문제를 해결해주는 것은 아니지만, 동적 계획법에 익숙해지기 전에 대략적 지침은 될 것입니다. 1. 모든 답을 만들어 보고 그 중 최적해의 점수를 반환하는 완전탐색 알고리즘을 설계한다. 2. 전체 답의 점수를 반환하는 것이 아니라, 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분 문제의 정의를 바꾼다. 3. 재귀 호출의 입력에 이전의 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄인다. 문제에 최적 부분 구조가 성립할 경우, 이전 선택에 관련된 정보를 완전히 없앨 수도 있다. 여기서 우리의 목표는 가능한 한 중복되는 부분 문제를 많이 만드는 것. 입력의 종류가 줄어들면 줄어들수록 더 많은 부분 문제..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/IVr9f/btqKXLRuGhj/v1lUdgHed3bDj84BNzW5pk/img.png)
algospot.com/judge/problem/read/TRIANGLEPATH algospot.com :: TRIANGLEPATH 삼각형 위의 최대 경로 문제 정보 문제 6 1 2 3 7 4 9 4 1 7 2 7 5 9 4 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 �� algospot.com 밑으로 1층씩 내려가면서 바로 밑 자리 최대값 갱신, 오른쪽 아래 최대값 갱신으로 저장. 아이디어 그대로 구현(?) 하면 된다. 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 32 33 34 35 36 37 38 #includ..
메모이제이션 구현 패턴 알고리즘 문제해결전략에서 제시하는 메모이제이션 구현 패턴이다. 1. 항상 기저 사례를 제일 먼저 처리한다. - 인덱스 오류를 줄일 수 있음. 잘못된 입력이 들어온 경우 처리가 가능함. 2. 메모이제이션할 공간을 모두 나올 수 없는 값으로 초기화를 한다. - 미리 계산된 반환값이 아님을 알 수 있음. 예를 들어, 모든 반환값이 0 이상으로 보장되는 상황이라면, 메모이제이션할 공간을 모두 -1로 초기화해둔다. 3. ret 변수를 두어, cache[a][b]에 대한 참조형(reference)으로 사용하자. - 매번 귀찮게 cache[a][b]를 쓰지말자. 이 방법은 특히 다차원 배열에 메모이제이션할 때 유용하다. 인덱스 오류 등 실수를 할 가능성을 없애준다. 4. 메모이제이션할 공간을 ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/b95ZQL/btqKVOBfNoc/P47DLPKwQKga2aFr8cSf6K/img.png)
ACM-ICPC 인터넷 예선 늦은 후기입니다. ACM-ICPC 인터넷 예선 3솔로 마무리했습니다... 마지막에 F번에서 좀 비벼봤지만 안타깝게도 맞지는 못했더라구요ㅠ 풀었던 순서대로 리뷰를 좀 해보려고 합니다. I. Project Teams www.acmicpc.net/problem/20044 20044번: Project Teams 입력은 표준입력을 사용한다. 입력의 첫 번째 행에는 팀 수를 나타내는 양의 정수 n(1 ≤ n ≤ 5,000)이 주어진다. 그 다음 행에 학생 si 의 코딩 역량 w(si)를 나타내는 2n개의 양의 정수가 공백으로 �� www.acmicpc.net 2*N명의 사람으로 N개의 팀을 꾸리기 위해 2명씩 짝지어야하는데, 팀원들의 코딩 역량의 합을 최대한 일정하게 유지한다는 문제. ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/5cV37/btqKuFZqymE/hU5WQDOTbo1fMLzH2ZAeb1/img.png)
출처 : algospot.com/judge/problem/read/JUMPGAME algospot.com :: JUMPGAME 외발 뛰기 문제 정보 문제 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상�� algospot.com 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상태로 시작합니다. 각 차례인 사람은 맨 왼쪽 윗 칸에서 시작해 외발로 뛰어서 오른쪽 아래 칸으로 내려가야 합니다. 이 때 각 칸에 적혀 있는 숫자만큼 오른쪽이나 아래 칸으로 움직일 수 있으며, 중간..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/blBs01/btqJWszwmmE/63LGuw6Q3mDfBzJ99Fayvk/img.png)
출처 : algospot.com/judge/problem/read/QUADTREE 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현하는 것입니다. 쿼드 트리는 2N × 2N 크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축합니다. 이 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 b가 됩니다. 이 그림의 모든 픽셀이 흰 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 w가 됩니다. ..