cloge 이야기

Sliding Window(슬라이딩 윈도우)란 수행 과정에서 필요한 전체 메모리를 할당하는 것이 아닌 매 수행마다 필요한 부분만큼만을 저장하여 사용함으로 메모리를 절약, 공간 복잡도를 낮추는 기법이다. 즉, 수행한 이후에 사용하지 않게 되는 기록을 버림으로 매 순간 필요한 정보들만을 저장, 이용한다. 이러한 형태가 실제로 필요한 메모리 할당들을 지정된 크기의 창문에 할당한 이후, 그 메모리를 창문으로 밀어넣음으로서 매 순간에는 창문 크기 내의 정보만을 이용하는 것과 같아 Sliding Window라고 불린다. 창문 창문에 밀어넣을 배열 창문과 배열에서 값의 이동 피보나치 함수를 예로 들어보자. Fn+1 = Fn + Fn - 1 (n > 2) , F2 = 1, F1 = 1 DP를 이용하여 임의의 N에 대해..

Codeforces TopCoder AtCoder SundayCoding Usaco 차근차근 작성할 예정이다.

STL - bitset http://neodreamer-dev.tistory.com/326 String http://blog.naver.com/hgt2768/220688873682

문제 세트를 올릴 때에는 그 세트의 모든 문제를 푼 후에 올리겠다고 생각했었는데, 그 동안 제대로 모두 푼 문제 세트가 없어서(...) 올리지 못했다. (최근에 하나 더 추가 되기는 했다 ^^;) 6/25일 아침에 시간잡고 푼 문제 셋 - 일본정보올림피아드 2010 예선 링크는 BOJ 기준이다. 1. 영수증 10권 중 나머지 9권의 가격의 합을 10권 전체 가격의 합에서 빼면 나머지 한 권의 가격이 나온다. 2. 주사위 게임 말판의 지시를 기록해놓고, 주사위 던지는대로 시뮬레이션하면 된다. 3. 결혼식 주어지는 친구 간선으로 그래프를 그린다. 이후 상근이를 기준으로 거리가 2인 친구들은 모두 초대할 수 있다. 이를 BFS를 통해 확인할 수 있다. O(M) 4. 카드놓기 카드를 모두 선택하는 경우의 수를 ..

BOJ - 잠수함 식별 잠수함은 물 속에서 소리를 낼 때 일정한 규칙성을 갖는 소리를 낸다. 0과 1로 구성되는 소리의 집합이 있을 때, 현 집합이 잠수함이 내는 소리인지 잡음인지를 판별해야 한다. 주어진 소리 집합이 잠수함이 내는 소리이려면 다음 패턴을 만족해야 한다. (100~1~|01) ~ 여기서 ~은 그 앞에 묶여있는 부분집합이 반복됨을 의미하며, a | b 는 a 또는 b 둘 중 하나가 해당되는 것을 의미한다.즉, 100~1~ 은 1 이후 0이 반복되고, 그 이후 1이 반복되는 패턴을 의미하며, (100~1~|01) ~ 는 (100~1~ 또는 01) 패턴이 반복됨을 의미한다. 이전에 문제를 풀었을 때에 먼저 떠오른 방법과, 며칠 전 문제를 풀었을 때에 먼저 떠오른 방법이 달랐었고, 둘 다 괜찮은..

BOJ - 주차장 IOI에 이런 문제가 나온줄 몰랐다. 이런 생각이 든다. 1. 그 당시 알고리즘이 많이 연구 & 알려지지 않았거나 (하지만 IOI 2009엔 Archery가 있는걸...)2. Problem Setter가 문제 내기 귀찮았거나3. 정말정말 문제 내기 귀찮았거나4. 빵점 방지용 ...2015 Boxes나 2011 Ricehub보다 훨씬 심하다. 2009 set을 오늘 처음 봤기에 (자랑인지는...) 이런 문제가 있으리라고는 생각 못했다... 해법을 작성하겠다. O(NM) 배열과 Queue의 관점으로 문제를 접근하면 쉽게 떠올릴 수 있다.차량이 들어오는 순서는 Queue와 같이 진행된다. 즉, 나중에 온 차가 먼저 주차되는 경우는 없다.차량이 들어올 때, 주차를 할 수 있다면 번호가 가장 작..

BOJ - 발리의 조각상 APIO 2015에 나온 문제이고, 몇몇은 여지껏 APIO에 나온 문제들 중 가장 쉬운 문제였다고 한다.(...)본인은....대회 때 손도 못댔기에 할 말이 없다...(당시에 결과가 논리연산이라는걸 보고 아무런 생각도 못했다.) 지금 보면 어렵지는 않지만, 아직도 쉬운 줄은 모르겠다....ㅇㅅㅇ;; KOI 2009 - 숫자 맞추기 (숫자 맞추기가 더 쉽다)IOI 2008 - Linear Garden (더 어려운 듯...)이런 느낌... 문제를 해결하기 위한 핵심은 최소의 아름다운 정도를 이진수로 나타냈을 때, 그 이진수에 2^k 꼴의 bit가 존재하는가? 를 판단해주면 된다.가장 큰 k부터 k를 줄여나가면서 현재의 2^k에 해당하는 값이 조각상을 분할 할 때 존재하지 않아도 된다..

BOJ - 굉장한 학생(Team) 한 학생이 3개의 시험에 대해 A, B, C 의 순위를 가지고 있다.이 때, 어떠한 학생들 중에서도 A'

일요일 아침의 데이트 BOJ 문제집에서 보게 된 문제. 1. Naive가장 간단하게 접근하는 방법은 Brute Force한 풀이법이다.시작점 F에서 모든 경로를 다 가보면서 S에 도달할 수 있는 모든 경우를 따진다.물론, 이와같이 짜면 시간초과가 날 것이 분명하다. 2. O(N^2M^2(N+M)) DP - 1가장 많이 쓰레기를 지나는 방법은 N+M-3개의 쓰레기를 지나는 방법이다. (시작점과 끝점이 대각선 끝에 위치하고 나머지 모든 지역이 쓰레기일 경우)또한, 가장 많이 돌아서 쓰레기 옆을 지나는 방법은 NM보다는 작다.이를 이용해 dp를 다음과 같이 세우자.dp[x][y][a][b] = { (x,y) 격자에 도달하는 경로 중, (쓰레기를 밟은 수, 쓰레기 옆을 지난 수) 가 (a,b) 인 경로가 존재하..

PS에 관련된 내용에 대해서는 존댓말을 빼고 작성하겠습니다...^^;; BOJ 좋은 수 (COCI) ...본 문제를 포스팅하는 이유는...처음에 보고는 다음 문제들 같다는 생각이 매우매우 강해서...너무 어렵다는 생각이 들었기 때문이다.... KOISTUDY 노안KOISTUDY 게으른 영롱이 (Canadian Computing Competition) KOI 짐정리KOISTUDY 케이크 (Usaco) 내가 느낀 위 문제들은....처음에는 쉬워보였지만...풀다보니 무척 어려웠다. (지극히 개인적으로는 말이다) 처음, 좋은 수 문제를 보고 나서도 별반 다르지 않은 느낌을 받았다. 보자마자 접근한 풀이는 N^3 brute force인데, 아무래도 선택 가능한 인자가 3개라는 것이 눈에 띄어서 그랬다.위 방법은 ..