DAMPER's 낙서장

출처: algospot.com/judge/problem/read/ASYMTILING algospot.com :: ASYMTILING 비대칭 타일링 문제 정보 문제 그림과 같이 2 * n 크기의 직사각형을 2 * 1 크기의 타일로 채우려고 합니다. 타일들은 서로 겹쳐서는 안 되고, 90도로 회전해서 쓸 수 있습니다. 단 이 타일링 방법은 algospot.com 타일링 (TILING) 문제에서 좌우 대칭인 경우의 수를 뺀 비대칭 타일링의 갯수를 구하는 문제이다. DP 문제들 중에서 제일 힘들었던 문제인 것 같다...ㅜ 위 문제를 해결하는 방법은 다음과 같다. 1. 대칭인 부분도 포함하여 구한 다음, 대칭인 부분을 빼는 방법. 2. 대칭인 부분을 처음부터 제외하고 구하는 방법. 두 방법 모두 상당한 사고력을 ..

출처 : algospot.com/judge/problem/read/SNAIL algospot.com :: SNAIL 달팽이 문제 정보 문제 깊이가 n 미터인 우물의 맨 밑바닥에 달팽이가 있습니다. 이 달팽이는 우물의 맨 위까지 기어올라가고 싶어하는데, 달팽이의 움직임은 그 날의 날씨에 좌우됩니다. 만약 algospot.com 깊이가 n 미터인 우물의 맨 밑바닥에 달팽이가 있습니다. 이 달팽이는 우물의 맨 위까지 기어올라가고 싶어하는데, 달팽이의 움직임은 그 날의 날씨에 좌우됩니다. 만약 비가 내리면 달팽이는 하루에 2미터를 기어올라갈 수 있지만, 날이 맑으면 1미터밖에 올라가지 못합니다. 여름 장마가 찾아와, 앞으로 m 일간 각 날짜에 비가 올 확률이 정확히 75%일 전망입니다. m 일 안에 달팽이가 우..

출처: algospot.com/judge/problem/read/WILDCARD algospot.com :: WILDCARD Wildcard 문제 정보 문제 와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만, * 나 ? 와 같은 특수 문자를 algospot.com 와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만, * 나 ? 와 같은 특수 문자를 포함한다. 와일드카드 문자열을 앞에서 한 글자씩 파일명과 비교해서, 모든 글자가 일치했을 때 해당 와일드카드 문자열이 파일명과 매치된다고 하자. 단, 와일드카드 문자열에 포함된 ? 는 어떤 글자와 비..

www.acmicpc.net/problem/5525 5525번: IOIOI 첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000) www.acmicpc.net 처음엔 그냥 naive하게 매번 부분 문자열을 만들어서 비교했더니 역시 시간초과.. O(n^2) 그래서 처음에 'I'를 찾은 다음, 2칸씩 보고 "OI"를 세면서 문자열 P를 찾는다. 이때 본 2칸은 다시보지 않는다. "OI"를 n개 찾으면 결과값 +1, 그리고 찾은 "OI"개수를 1개 빼고 다시 2칸씩 보면서 찾는다. 이런식으로 해결하면 O(n) 으로 해결할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1..

www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 알고리즘 문제해결전략 책에 소개된 알고스팟 문제와 유사한 문제이다. damper.tistory.com/4 [ALGOSPOT] QUADTREE 출처 : algospot.com/judge/problem/read/QUADTREE 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분.. damper.ti..

www.acmicpc.net/problem/1718 1718번: 암호 Vigenere cipher이라는 암호화 방법은 암호화하려는 문장 (평문)의 단어와 암호화 키를 숫자로 바꾼 다음, 평문의 단어에 해당하는 숫자에 암호 키에 해당하는 숫자를 더하는 방식이다. 이 방법을 변 www.acmicpc.net 문제에서 원하는 그대로 했다. 평문에다가 키의 알파벳 순서를 빼고 만약 'a' 밑으로 가면 알파벳 개수인 26을 더해줍니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include using namespace std; #define swap(a,b) (a)^=(b)^=(a)^=(b) #define endl '\n' typedef lo..