문제 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음 www.acmicpc.net 풀이 입력 크기가 작고, 어떻게 구현해야하는지 거의 전부 설명이 되어있기 때문에, 정확하게 구현만 하면 되는 문제다. 코드
문제 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net 풀이 어려운 문제는 아니지만 실수하기 쉬운 문제다. 테트로미노의 경우의 수가 19개 있는데 햇갈리지 않고 정확하게 코딩하면 된..
문제 https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 풀이 만약 시험장에 있는 응시자의 수(x)가 총감독관이 관리 가능한 수(A) 보다 작거나 같다면, 시험장에는 총 감독관 1명이 필요할 것이다. 만약 크다면 2가지 경우가 있다. 1. x-A를 부감독관이 관리 가능한 수(B)로 나눴을 때 나머지가 0인경우 2. 나머지가 0 이상인 경우 나머지의 몪에 1의 경우 0, 2의 경우 1을 더한다..
알고리즘문제해결전략 p189 문제 울타리 잘라내기 (문제ID:FENCE, 난이도 중) 알고스팟 링크 풀이 개인적으로 분할정복 문제는 아직 어려워서 고생을 좀 했다. 분할정복 문제가 으레 그렇듯이 나누는 개념 자체는 어렵지 않다. 가운데를 자르고 앞의 절반의 최대값과 뒤의 절반의 최대값을 구해 비교한다. 물론 이 때 분할되는 부분을 처리해주어야 한다. 즉, 잘리는 부분의 울타리 2개를 포함하는 최대값을 구해서 같이 비교해 주어야 한다. 이 때, 이 가운데 부분을 처리하는 부분이 주된 문제인데 절반씩 줄어드므로 logN번 반복되는 연산으로 이 연산을 N시간에 해내야 NlogN으로 풀 수 있다. 내가 처리한 방법은 가운데 2개의 울타리에서 시작해서 좌우로 넓어지면서 최대값을 구하는 것이다. 이때 커지는 방향을..
알고리즘문제해결전략 p189 문제 쿼드 트리 뒤집기 (문제ID:QUADTREE, 난이도 하) 알고스팟 링크 풀이 분할 정복 카테고리에 있지만 문제의 내용 자체가 분할 정복의 원리를 사용한 것일 뿐이고 실제로 풀이는 그냥 stack을 사용해서 하면 된다. (DFS) 풀이의 아이디어는 상하를 뒤집는 방법에 있어서, x마다 하위의 노드들을 전부 앞뒤로 바꿔주면 전체적으로 상하로 뒤집은 결과가 된다는 것. 책의 그림 7.6과 그 밑에 개념적인 설명이 잘 되어있으니 잘 읽어보자 그걸 구현 하는 방법은 stack을 통해서 뒤집을게 모이면 계속 뒤집어 주면 된다. 단지 살짝 주의해야 하는 점은 뒤집은 직후에 그 뒤집었던 x를 루트로 하는 부분트리가 상위 x의 4번째 node였을 때 곧바로 한번 더 뒤집어야 한다는 점..
알고리즘문제해결전략 p168 문제 시계 맞추기 (문제ID:CLOCKSYNC, 난이도 중) 알고스팟 링크 풀이 이 문제는 완전탐색의 탈을 쓴 연립방정식 문제이다. 전체 경우의 수가 4^10이므로 완전탐색을 하라고 책에서는 말하지만 많은 사람들이 손으로 연립방정식을 풀고 그냥 옮겨 적어서 풀었다. 나도 상호 종속적인 몇 개의 버튼을 적당히 거르고 적당히 코드로도 검증을 해서 풀었다. 완전탐색으로 구현하고 싶다면 한 스위치를 4번 누르는것은 0번 누르는 것과 같다는 것만 명심하면 된다. 그래서 나온 경우의 수가 4^10으로 그냥 모든 버튼의 모든 경우의 수를 적당히 구하면 된다. 약 100만개 정도라서 아마 시간이 오래 걸릴 것 같지는 않다. 코드 이 코드는 AC를 받은 코드지만 별로 참고하기는 좋은 코드가 ..