Bull

3190: 뱀 10875: 뱀 (Advanced)문제보드 위에 뱀이 돌아 다닌다. 초기 길이가 1인데, 사과를 먹으면 길이가 늘어난다. 벽이나 자기 자신의 몸에 부딪치면 종료된다. 이 때 몇 번 움직였는지 출력하면 된다. 출발점은(1, 1)로 시작되며, 전체 좌표는 `1-based index`로 주어진다. 뱀은 회전할 수 있는데 x 번째에 `D`가 주어지면 오른쪽, `L`이 주어지면 왼쪽으로 90°돌릴 수 있다. 해당 포스트는 3190번 문제를 다루지만 비슷한 내용에 똑같은 제목으로 10875번도 있다. 10875번 문제는 단순 구현으로 하게 되면 `메모리 초과`가 나오므로 이 문제의 다음 단계로 풀면 좋을 것 같다.분석우선 이 문제는 구현만 하면 된다. 하지만 설계를 어떻게 할 지 잘 생각해야 한다. ..

12100: 2048_Easy문제이 게임은 $N \times N$ 크기 보드에 $2^k$으로 이루어진 블록들이 주어진다. 상, 하, 좌, 우로 움직일 수있으며, 한 턴마다 새로운 숫자 2가 생겨난다. 하지만 문제에서는 새로운 숫자가 생성되지 않음을 가정한다.이 임의 숫자가 들어간 보드 판에서 최대 5번 이동해서 만들 수 있는 가장 큰 블록 값을 구해야한다. 분석매 턴마다 이동할 수 있는 경우의 수는 상, 하, 좌, 우 4가지이다. 5번의 기회가 주어지니, $4^5=1024$의 경우의 수를 가진다. 대략적으로 모든 경우의 수의 보드를 계산했을 때, $4Byte \times (20 \times 20) \times 1024 = 1.6384\ MB$ 결과가 나오고 메모리 제한은 512MB이다.따라서 `Brute..

소개만든 사람의 이름 앞 글자를 따서 Knuth, Morris, Prett로 지었다. 해당 알고리즘은 문자열 A에서 문자열 B가 어디에 있는지 찾는 알고리즘이다. 이는 브루트포스를 통해서 모든 경우를 찾아도 되지만, O(NM) 시간복잡도를 가지기 때문에 해당 알고리즘을 사용하면 O(N+M)으로 단축시킬 수 있다.KMP 알고리즘 내에서는 LPS (Logest Prefix which is also Suffix) 알고리즘이 사용되는데, 이는 다른 글로 정리 하였다. [1]에 정리하였다. [1] LPS 정리도 [2] 자료를 통해서 정리를 하였는데, 해당 블로그 글을 작성하신 분이 정리를 참 잘해놓으셔서 이해하는데 큰 도움을 얻었다.원리[1] LPS를 설명할 때 패턴이 일치되는 부분의 접두사와 접미사를 각 문자..

소개패턴 매칭. 원래는 KMP 알고리즘을 알기 전에, 아호-코라식 알고리즘을 우선적으로 알게 되었다. 하고있는 프로젝트에서 문장을 가지고 특정 문자열이 포함되어 있는 찾아야 했다. 하지만, 일반적인 브루트 포스 방식으로 한다면 시간이 오래 걸릴 것이란 것을 알고 있다. 그래서 제미나이가 나에게 아호-코라식 알고리즘을 소개해주었다. 알아보니 아호-코라식 알고리즘을 알기전에 KMP 알고리즘이 사용되기 때문에 그것을 먼저 알 필요가 있었다.문자열 패턴 매칭은 다음과 같은 예시로 설명할 수 있다."The rain in Spain stays mainly in the plain" (영화 "마이 페어 레이디" 중)rain, Spain, mainly, plain 과 같이 ain 패턴이 많기 때문에, 단순 브루트 포스는..

학교에서 배운 힙소트 정리 코드 아카이브 용.이론을 안다는 전제하에 코드만 읽는다.def heapify(arr,n,i): key = i l = key*2+1 r = key*2+2 # 왼쪽 자식 노드 검사 if l arr[key]: largest = l else: largest = key # 오른쪽 자식 노드 검사 if r arr[largest]: largest = r # 바뀐 게 있다면 자식 노드와 값을 바꾸고 해당 자식 노드를 검사 if largest != key: temp = arr[largest] arr[largest] = arr[key] arr[key] = temp heapify(arr,n,largest)# 절반부터 하는 이유는 절반보다 위..

문제1019: 책 페이지N이 36이라면 1~36페이지까지 즉 1,2,3,...35,36에 나오는 모든 숫자를 다 세는 것이다.설명각 자리 수 마다 검사하여 모든 경우의 수를 구한다. 1234라는 N이 주어졌을 때 1,2,3,4 모두 검사하는 것이다.1의 자리 수를 검사할 때 1의 자리를 0~9까지 모두 바꿔보는 것이다. 그리고 일의 자리를 제외한 나머지 부분을 보는 것이다.주석을 보고 숫자 디버깅으로 이해하는 게 편할 것이니 포괄적인 설명은 포기한다. (포괄적으로 말하기가 어려워서)1204일 때 0104~1204 (0004는 불가, 다른 숫자 과정에서 겹침.)1214일 때 0014~12141224일 때 0024~12241234일 때 0034~1134 | 1230,1231,1232,1233,12341244..

오른쪽 1 제거// C++#include #include int main() { unsigned int num = 0xFFFFFFFF; while (num > 0) { std::cout (num) (num) num -= num & -num 혹은 num = num & (num - 1) 을 해주면 된다. # 결과1111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111001111111111111111111111111111100011111111111111111111111111110000111111111111111111111111111000001111111111111111..