코드 낙서장

문제 주소 : www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 문제 확인 간단한 시뮬레이션 문제입니다. 주어진대로 드래곤 커브 정보를 배열에 입력해둔 후 마지막에 정사각형 개수를 세면 됩니다. 풀이 드래곤 커브의 방향을 기록해야 다음 레벨의 드래곤 커브를 만들 수 있으므로 스택을 이용해서 기록합니다. 주의해야 할 점은 이전 단계 끝 지점에서 90도 방향으로 돌려야 하므로 스택에 저장된 정보를 top -> 0 순으로 읽어야 하며 모양..

문제 주소 : www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제 확인 모든 루프를 제거하고 조건식으로 풀 수 있는 문제이지만 이는 너무 시간이 많이 드는 작업이라 간단하게 dfs와 가지치기를 통해 풀었습니다. 조건식 풀이로 푼다면 시간과 메모리 모두 단축할 수 있습니다. 테트로미노는 최대 4개까지의 도형이므로 탐색이 깊지 않으므로 dfs로 풀어도 무방합니다. 주의해야 할 점은 다른 4가지의 테트로미노는 dfs로 풀 수 있지만 ㅜ 모양의 테트로미노는 dfs..

문제 주소 : www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 확인 bfs와 시뮬레이션 문제입니다. 배열 크기가 20x20으로 작기 때문에 가지치기 등을 이용하지 않고 문제를 풀 수 있습니다. 주의할 점은 먹이를 선정하는 기준이 아기 상어로부터의 거리, 거리가 같다면 위, 왼쪽 순으로 우선순위가 높습니다. 먹이를 먹으며 이동한 거리가 최종 결과가 됩니다. 풀이 큐를 통해서 bfs를 구현하고 visited 배열을 통해 여러 번 탐색하는 것을 방지합..

문제 주소 : www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net c언어 스타일로 벡터 등 컨테이너 없이 풀면 메모리는 적게 나오지만 가끔 0ms가 나오지만 보통 4ms가 나옵니다. 빈 배열과 나무 나이 등 조건이 더 많아지기 때문에 처리해야 할 조건문이 많아지기 때문인 것 같습니다. 문제 확인 따로 특별한 알고리즘이 필요하지 않습니다. 제한시간과 메모리 초과가 관건입니다. 문제 조건 봄 : 나이가 낮은 순 부터 나무가 땅의 양분을 먹고 나이가 ..

문제 주소 : www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 문제 확인 dfs 형태로 문제풀이 최소 개수를 찾는 문제이기 때문에 놓을 사다리 수를 0개부터 4개까지 순서대로 탐색합니다. 풀이 놓을 사다리 수를 0개부터 탐색하며 가능한 경우를 찾는 즉시 출력합니다. dfs, 의미없는 탐색을 줄이기 위해 세로 방향 탐색 시 의미가 중복되는 사다리는 넘어갑니다. //while(!a[i][j - 1] && !a[i][j + 1]) i++; 코드 1 2 3 4 5..

문제 주소 : 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. 연합에 속해 있는 나라의 인구 변경 풀이 배열 초기화 시 배열 외..