DAMPER's 낙서장

메모이제이션 구현 패턴 알고리즘 문제해결전략에서 제시하는 메모이제이션 구현 패턴이다. 1. 항상 기저 사례를 제일 먼저 처리한다. - 인덱스 오류를 줄일 수 있음. 잘못된 입력이 들어온 경우 처리가 가능함. 2. 메모이제이션할 공간을 모두 나올 수 없는 값으로 초기화를 한다. - 미리 계산된 반환값이 아님을 알 수 있음. 예를 들어, 모든 반환값이 0 이상으로 보장되는 상황이라면, 메모이제이션할 공간을 모두 -1로 초기화해둔다. 3. ret 변수를 두어, cache[a][b]에 대한 참조형(reference)으로 사용하자. - 매번 귀찮게 cache[a][b]를 쓰지말자. 이 방법은 특히 다차원 배열에 메모이제이션할 때 유용하다. 인덱스 오류 등 실수를 할 가능성을 없애준다. 4. 메모이제이션할 공간을 ..

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명씩 짝지어야하는데, 팀원들의 코딩 역량의 합을 최대한 일정하게 유지한다는 문제. ..

출처 : algospot.com/judge/problem/read/JUMPGAME algospot.com :: JUMPGAME 외발 뛰기 문제 정보 문제 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상�� algospot.com 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상태로 시작합니다. 각 차례인 사람은 맨 왼쪽 윗 칸에서 시작해 외발로 뛰어서 오른쪽 아래 칸으로 내려가야 합니다. 이 때 각 칸에 적혀 있는 숫자만큼 오른쪽이나 아래 칸으로 움직일 수 있으며, 중간..

출처 : algospot.com/judge/problem/read/QUADTREE 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현하는 것입니다. 쿼드 트리는 2N × 2N 크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축합니다. 이 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 b가 됩니다. 이 그림의 모든 픽셀이 흰 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 w가 됩니다. ..

출처 : algospot.com/judge/problem/read/CLOCKSYNC algospot.com :: CLOCKSYNC Synchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 �� algospot.com 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 바꾸고 싶다. 시계의 시간을 조작하는 유일한 방법은 모두 10개 있는 스위치들을 조작하는 것으로, 각 스위치들은 모두 적게는 3개에서 많..

출처 : algospot.com/judge/problem/read/BOARDCOVER algospot.com :: BOARDCOVER 게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 �� algospot.com 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안 됩니다. 위 그림은 한 게임판과 이를 덮는 방법을 보여줍니다. 게임판..