11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 예제 9 ans : 55 문제를 처음 봤을 때 바로 dp로 풀어야겠다 생각한 건 아니고 완전 탐색으로 셀 수 있나 생각을 해 봤다. 타일을 완전 탐색으로 채우는 것 자체가 힘들어 보여서 일단 손으로 보드를 채워보면서 문제를 파악했다. 딱 정확히 이 사진의 흐름대로 2*3에서도 2*2와 2*1을 이용해서 채운 느낌이 들었고 2*4 블록을 채울 때 확신이 생겼다. 2*k 블럭을 예로 들자면, 세로로 긴 블록을 하나 먼저 세우면 나머지 k-1열 2*k-1 블록을 채우는 방법과 정확히 똑같다..

2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 9 3 1 3 3 3 2 2 2 1 1 ans : 1 1 1 3 3 3 2 2 2 빈도를 기준으로 정렬하되, 들어온 순서를 유지하면서 정렬해야 한다. 빈도만 기준이었다면 떠오르는 방법은 아래와 같다. 맵에 빈도를 key로 값을 value로 해서 삽입한다. pair vector에 빈도, 값으로 삽입을 한 뒤 빈도를 기준으로 sort를 한다. 두 방법에서 기존 입력의 순서를 유지할 방법을 생각해 봤는데, sort를 병합 정렬로 직접 구현하지 않는 이상 맵이나 벡터를 확장하는 방법이었다. 맵 2개 사용, 하나..

Merge Sort 먼저 구현부터 해보자. 재귀 형태로 구현했다. 함수 정의 void merge_sort(int start, int end) : start ~ end - 1까지 병합 정렬을 실행한다. base condition if(길이가 1) return; 재귀식 배열을 반으로 쪼개서 병합정렬을 한 후 merge 함수를 써서 병합하면 된다. merge 함수는 정렬된 두 배열을 병합하는 함수이다. 배열을 반으로 쪼개서 병합정렬을 한다는 건 귀납적 사고를 통해 재귀식을 구성했다고 생각하면 된다. 길이가 4인 배열을 병합정렬 할 수 있다고 가정하면 길이가 8인 배열은 길이가 4인 배열을 합치면 끝이다. 이런 느낌으로 구현해 보자. #include #include using namespace std; int ..

14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 예제 5 5 1 2 3 4 5 5 4 3 2 1 2 3 4 5 6 6 5 4 3 2 1 2 1 2 1 ans : 19 문제 분석부터 해보자. 테트로미노라는 블록을 보드에 넣는데, 블록이 들어가는 칸의 합이 가장 크게 되는 숫자를 찾으면 된다. 테트로미노는 총 5 종류고, 가장 먼저 떠오르는 방법은 모든 테트로미노를 하나하나 끼워 넣는 방법이다. 보드의 크기가 2500이고 블록 단 한 개만 넣으면 되므로 모든 테트로미노를 다 끼워보는 방법으로 구현해도 될 것 같다...

13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 문제 분석부터 해보자. N * M 크기 보드에 파란 구슬, 빨간 구슬이 하나씩 있고 상하좌우 기울여서 구슬이 구멍에 들어가는지 관찰하면 된다. 빨간색만 빠지면 성공이고 빨, 파 동시에 빠지거나 파란색만 빠지면 실패이다. 10번 이상 움직여도 실패이다. 문제를 보고 예제들을 한 번 훑어보면서 생각난 주의 사항은 다음과 같다. 공 하나가 구멍에 빠지는 경우를 주의하자. (예제 7) 움직일 때 두 공이 겹칠 수 없다. ..

14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 문제가 요구하는 내용들을 그대로 하나씩 구현하면 된다. 딱 봐도 디버깅이 매우 귀찮아 보인다. 천천히 실수가 없게끔 구현해 보자. 톱니바퀴가 4개 고정돼 있고, 최대 100번 회전한다. 한 번의 회전이 일어나면 4개 모두 회전할 수 있는데, 데이터가 매우 적어서 시간복잡도 계산도 안 하고 바로 완전탐색으로 구현했다. 문제의 요구사항은 다음과 같다. 회전시키기 k번째 톱니바퀴를 회전시키려면 그냥 새 배열을 만들어서 회전시킨 결과물을 저장하면 끝이다. 근처 톱니..