코드 낙서장

문제 주소 : www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제 확인 간단하게 dfs 그래프 탐색으로 해결할 수 있는 문제 아래 그림과 같이 최대 4번의 깊이 탐색으로 해결 할 수 있습니다. ㅜ 형태의 모양은 dfs를 통해 탐색하기 까다로우므로 따로 함수를 만들어 탐색하도록 합니다. 풀이 처음 배열을 초기화 할 때 최대값을 미리 저장해두고 탐색 시 기대값 계산에 사용합니다. 이를 통하여 가지치기를 진행합니다. 탐색 시 이전 방향으로 돌아가는 것을 막기 위..

문제 주소 : www.acmicpc.net/problem/12094 12094번: 2048 (Hard) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 문제 확인 2048(easy) 문제와 같은 방식, 최대로 움직일 수 있는 횟수가 10번이다. 완전 탐색으로 구현을 하면 시간초과가 나기 때문에 탐색에서 가지치기를 해 주어야 한다. 풀이 가지치기 조건 1. 배열 값이 변화가 없는 경우 2. 현재 최대값 이상으로 변화할 수 없는 경우 앞으로 n번 움직일 수 있을 때 매번 합처지는 경우를 생각하면 기대값은 (2^n * 현재..

문제 주소 : www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 확인 전형적인 DFS, BFS 그레프 탐색 문제입니다. * 문제에 자세하게 나오지 않아 헷갈리는 부분이 있는데 같은 날에서 여러 개의 연합이 인구이동을 할 수 있고 이는 한 번으로 취급됩니다. 이 문제에서 해결해야 할 점은 2개입니다. 1. 조건에 맞춰 국가 연합 생성, 생성할 연합이 그 단계에 없다면 종료 2. 연합에 속해 있는 나라의 인구 변경 풀이 배열 초기화 시 배열 외..