Bull

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

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 방식으로 모두 풀이가 가능하다. ..