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..

문제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..

Baekjoon 2143문제숫자 T가 주어지고 배열 A와 B가 주어진다. 여기서 부 배열이라는 개념이 있는데 A[i], A[i+1], ..., A[j] 와 같이 연속된 배열을 부배열이라고 한다. A[13]까지라고 한다면 A[7], A[8], A[9], ... A[13] 도 가능하고 A[2], A[3]도 부 배열이라고 할 수 있다. 문제는 A의 부 배열과 B의 부 배열이 합해서 T가 되는 경우의 수를 구하는 것이다.예를 들어 본문의 내용과 같이 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인 경우, 부 배열 쌍의 개수는 다음의 7가지 경우가 있다.T(=5) = A[1] + B[1] + B[2] = A[1] + A[2] + B[1] = A[2] + B[3] = ..

Baekjoon 1806문제제목처럼 부분합을 구하는 문제이다.1,2,3,4 배열이 있을 때, 1 2 3 4 1 2 1 3 1 4 2 3 2 4 3 4 1 2 3 1 2 4 2 3 4 1 2 3 4와 같이 모든 조합이 가능 한 원소의 합이다.이 집합의 원소들의 합이 S 이상이 되는 것 중 원소가 연속되어 있고 짧은 것을 찾는 것이다.입력첫 번째 줄에 수열의 길이 N과 부분합 S가 주어진다. (10 ≤ N , 0 )두 번째 줄에 길이 N인 수열이 주어집니다. 수열의 각 원소는 10,000 이하의 자연수이다.출력합이 S 이상이 되는 가장 짧은 부분 수열의 길이를 출력합니다. 만약 그러한 부분 수열이 없다면 0을 출력한다.아이디어이 문제를 해결하기 위해 슬라이딩 윈도우(Sliding Window) 기법을 사용한..

https://www.acmicpc.net/problem/13913문제0 1 2 3 ... 100000 으로 이루어진 일자형 길에 x+1, x-1 2*x로 움직일 수 있다고 했을 때 목적까지 가는 최단 경로를 구하는 문제이다.아이디어단순 BFS문제이다. 하지만 visit으로 최단 경로보다 이후에 간 인덱스는 방문처리하여 다시 방문하지 않도록 한다. 여기까지는 스스로 짰지만 이후에도 메모리 초과가 걸렸다.왜냐하면 최단 경로를 vector를 사용하여 리스트처럼 저장을했는데이는 상당히 많은 배열을 큐에 저장하기 때문이다.단순하게 생각해보면 벡터의 크기가 1에서 100000까지인데 방문한 인덱스를 제외하면 최대 1에서 33333까지 3개씩 저장해 나갈 것이다.(1,2,2,2,3,3,3,4,4,4....) 그러면..

https://www.acmicpc.net/problem/9019문제원문에 나오는 D, S, L, R 연산을 구현하여 A, B입력 시 A→B가 될 때 까지 어떤 연산을 해야하는 지 출력해야 하는 문제이다.아이디어BFS를 통해 D, S, L, R, DD, DS, DL, DR, SD, SS, SL, SR, ...처럼 레벨 단위로 숫자를 확인한다. 여기까진 OK. 하지만 문자열의 제한이 없기 때문에 DSLDLSDRRSRSDSL... 같이 긴 숫자는 Queue에 메모리초과가 발생한다.숫자는 0~10000미만이다. 이것을 활용하여 10000까지 visit을 확인하여 이미 확인한 숫자는 확인하지 않는다. 또한 자료형에 대해서도 short로 바꿔줄 수 있다. int를 쓰면 틀리는 지는 확인해보지 않았지만 일단 sho..

https://www.acmicpc.net/problem/14502문제문제의 연구소에 벽(1)을 최대 3개 설치가 가능하고 바이러스(2)는 벽이 막혀있는 곳 까지 퍼질 수 있다. 이러한 조건에서 바이러스가 퍼졌을 때, 안전한 장소(0)를 얼만큼 확보할 수 있는 지 출력하는 문제이다.아이디어BFS를 통해 바이러스를 퍼뜨린다. 벽을 최대 3개 설치할 수 있는 로직은 행열 순으로 벽을 하나씩 설치했다가 해제했다가 순서대로 모든 경우의 수를 구한다. 바이러스가 퍼진 상태 + 벽이 최대 3개가 설치된 상태에서 최대 안전한 장소가 얼마나 확보됐는지 비교하며 max값을 구한다. 2 0 0 0 1 1 00 0 1 0 1 2 00 1 1 0 1 0 00 1 0 0 0 0 00 0 0 0 0 1 10 1 0 0 0 0 0..

https://www.acmicpc.net/problem/2206문제원문을 보면 알 수 있듯이, 왼쪽 위 기준에서 오른쪽 아래로 가는데 벽(1)을 한 번만 깰 수 있고 다음 부터는 깰 수 없다. 그러한 제약사항이 있는 상태에서 최단 거리를 구하면 된다.아이디어BFS를 이용하는데 Queue에 들어가는 정보가 (x,y)와 벽을 깬 적이 있는지에 대한 boolean이 들어가면 된다. code#include #include #include using namespace std;const int MAX = 1000; // 그리드 최대 크기// (-1, 0) (0, 1) (1, 0) (0, -1) 네 방향 이동int dx[] = {-1, 0, 1, 0}; // 방향 배열: x 좌표int dy[] = {0,..

https://www.acmicpc.net/problem/1987문제좌표의 크기가 주어지고, (1,1)부터 시작하는데 같은 알파벳을 만나면 안될때 까지 상하좌우로 움직일 시 최대한 많이 갈 수 있는 칸은 몇인지 찾는 문제이다.아이디어DFS와 백트래킹을 이용한다.인접한 상하좌우 좌표를 확인하여 기록된 알파벳이 없으면 DFS를 호출한다. 여기서 백트래킹을 추가하여 DFS를 통해 visited(알파벳)을 기록하는데 갈수 있는 곳 까지 간 후 다시 visited를 해제하는 방식을 이용한다.위 GIF는 문제의 예제로 백트래킹과 DFS가 어떻게 동작하는 지 그림판으로 나타내보았다. H-A에서H-A-D-G-J-FH-A-J-G-DH-A-J-F-D의 DFS가 적용되고 H-F에서H-F-J-A-D-GH-F-J-G-D-AH-..

https://www.acmicpc.net/problem/1707 문제이분 그래프란?그래프 이론에서 이분 그래프(二分graph, 영어: bipartite graph)란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다. 쉽게 말해서 어느 정점을 선택했을 때 간선을 통해 어디로 가든 RBRBRB...로 반복되어야 한다. (RED, BLUE) 이것을 풀어서 생각하면 두 집합으로 나눌 수 있는 그래프를 말한다. 즉 왼쪽이 있는 그래프를 모양만 좀 다르게 위치를 옮겨주면 오른쪽 그림이나 사실 똑같은 건데, 이런식으로 오른쪽 그림으로 만든 후 선 그어서 두 집합으로 나뉘어지면 그게 이분 그래프다. 아이디어BFS, DFS 방식으로 모두 풀이가 가능하다. ..

https://www.acmicpc.net/problem/16928스크래핑 문제로 open graph tag가 안뜸.문제글보단 그림으로 보면 편할 것이다. 1~100까지의 인덱스를 가진 Grid가 있지만 1차원인 배열로 봐도 상관없다. 뱀을 만나면 다시 내려가야 되고 사다리를 발견하면 껑충 뛰어넘어갈 수 있다.  아이디어①BFS1부터 1~6자리까지 모두 시행 후, BFS방식을 사용해 지름길을 통하거나 뱀을 피해 먼저 100에 도착하는 경우를 채택한다. visit[]을 통해 방문했던 인덱스인지 확인하고 아니라면 Queue에 push한다. queue에 들어간 좌표와 카운트는 level순으로 들어가고 순차적으로 빠질 수 있어 BFS가 된다. Code#include #include using namespace ..