일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- backtracking
- acm
- BFS
- 백트래킹
- 알고리즘문제해결전략
- union-find
- 스택
- 그리디
- Algospot
- 문자열
- 이분탐색
- 다이나믹프로그래밍
- DP
- Greedy
- 알고스팟
- 분리집합
- 너비우선탐색
- 세그먼트트리
- 분할정복
- 동적계획법
- stack
- BOJ
- 백준
- DFS
- 누적합
- 종만북
- priority_queue
- 재귀
- 완전탐색
- 유니온파인드
- Today
- Total
목록Problem Solving/알고리즘 문제해결전략 (35)
DAMPER's 낙서장
algospot.com/judge/problem/read/PI algospot.com :: PI 원주율 외우기 문제 정보 문제 (주의: 이 문제는 TopCoder 의 번역 문제입니다.) 가끔 TV 에 보면 원주율을 몇만 자리까지 줄줄 외우는 신동들이 등장하곤 합니다. 이들이 이 수를 외우기 위해 사용�� algospot.com (주의: 이 문제는 TopCoder 의 번역 문제입니다.) 가끔 TV 에 보면 원주율을 몇만 자리까지 줄줄 외우는 신동들이 등장하곤 합니다. 이들이 이 수를 외우기 위해 사용하는 방법 중 하나로, 숫자를 몇 자리 이상 끊어 외우는 것이 있습니다. 이들은 숫자를 세 자리에서 다섯 자리까지로 끊어서 외우는데, 가능하면 55555 나 123 같이 외우기 쉬운 조각들이 많이 등장하는 방법..
algospot.com/judge/problem/read/JLIS algospot.com :: JLIS 합친 LIS 문제 정보 문제 어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 '4 7 6'은 '4 3 7 6 9'의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로 algospot.com 어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 '4 7 6'은 '4 3 7 6 9'의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로 정렬되어 있는 부분 수열들을 가리켜 증가 부분 수열이라고 부르지요. 예를 들어 '3 6 9'는 앞의 수열의 증가 부분 수열입니다. 두 개의 정수 수열 A 와 B 에서 각각 증가 부분 수..
algospot.com/judge/problem/read/LIS algospot.com :: LIS Longest Increasing Sequence 문제 정보 문제 어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. algospot.com 어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열의 순서와 다르므로 10 7 4 9 의 부분 수열이 아니다. 어떤 부분 수열이 순증가할 ..
다음은 책에서 제시하는 최적화 문제의 동적 계획법을 설계하기 위한 과정입니다. 이 과정이 모든 문제를 해결해주는 것은 아니지만, 동적 계획법에 익숙해지기 전에 대략적 지침은 될 것입니다. 1. 모든 답을 만들어 보고 그 중 최적해의 점수를 반환하는 완전탐색 알고리즘을 설계한다. 2. 전체 답의 점수를 반환하는 것이 아니라, 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분 문제의 정의를 바꾼다. 3. 재귀 호출의 입력에 이전의 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄인다. 문제에 최적 부분 구조가 성립할 경우, 이전 선택에 관련된 정보를 완전히 없앨 수도 있다. 여기서 우리의 목표는 가능한 한 중복되는 부분 문제를 많이 만드는 것. 입력의 종류가 줄어들면 줄어들수록 더 많은 부분 문제..
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. 메모이제이션할 공간을 ..