출처 : 백준, https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net # 다음 세대 드래곤 커브 # 이전 세대 드래곤 커브의 끝 점을 기준으로 90도 시계 방향 회전 # 그것을 끝 점에 붙인 것임 # 격자 위에는 N개의 드래곤 커브가 존재 # x, y, d, g # 1x1 크기의 정사각형의 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수 더보기 먼저, 생각해야 할 부분 1. 꼬마신 신고 평행 이동과 회전 변환, 잊지 않..
출처 : 백준, https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net # 1번 1방향 # 2번 서로 반대 방향 # 3번 서로 직각 # 4번 3방향 # 5번 4방향 # CCTV는 벽을 넘을 수 없으나, CCTV는 넘을 수 있다. # 최소 사각지대의 개수 더보기 먼저, 생각해야 할 부분 1. 여러개의 CCTV가 바라볼 수 있는 모든 방향에 대한 조합을 어떻게 구할지 생각해본다. 풀이 모든 조합을 훑어 최소값을 알아보고 싶다면, 깊이 우선 탐색..
출처 : 백준, https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net # 한 칸에 한나라, 인구이동은 하루에 한 번 # 인구 이동이 발생하지 않을 때 까지 반복 # 두 나라 사이의 인구 차가 L 이상 R 이하이면, 국경선 OPEN # 국경선을 모두 연 다음에 인구 이동 시작 # 국경선이 열린 나라들끼리 연합 # 인구 이동 = 연합 인구 / 연합 이루는 나라 수 (소수점 버림) # 인구이동이 발생한 일자 더보기 먼저, 생각해야 할 부분 ..
출처 : 백준, https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net # 벽을 3개 세울 수 있다. # 바이러스는 상하좌우로 퍼져나간다 # 바이러스가 있는 칸은 연구소 내에 2개 이상 9개 이하이다. # 안전영역의 최댓값을 구하여라 더보기 먼저, 생각해야 할 부분 1. 어떻게 해야 벽을 세울 칸을 효율적으로 선택할 수 있을지 고민해보자. 아마.....없을 것이다. 벽을 세울 칸을 효율적으로 선택할 수 없다면...다 해봐야지 어쩌겠니... 2. 그렇다면 안전 영역..
출처 : 백준, https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 더보기 먼저, 생각해야 할 부분 1. 주사위를 굴리는 알고리즘 문제의 핵심은 주사위를 굴리는 알고리즘을 어떻게 구현할 것인가이다. 주사위의 면과 적혀있는 숫자를 매칭하는 것과, 실제 놓여진 주사위의 각 면의 방향과 주사위의 각 면을 매칭하는 것을 따로 생각해보자. 괜히 주사위의 각 면에 번호를 붙여준게 아니다. 풀이..
출처 : 백준, https://www.acmicpc.net/problem/3190 더보기 먼저, 생각해야 할 부분 1. 계속 움직이는 뱀이 차지하는 좌표들을 어떻게 관리하면 좋을까? 뱀이 자기자신에게 부딪혀도 게임 오버이기 때문에 지속적으로 뱀의 좌표를 관리해주어야한다. 뱀이 한 번 움직일 때마다 뱀이 차지하는 좌표들을 조회해야했기 때문에 빠르게 조회할 수 있는 자료형이 필요했고, 처음에는 좌표들을 set에 넣어서 관리하려고 했다. 이를 통해 새 좌표를 넣어주고, 꼬리를 제거하면서 필요 시 간편하게 조회할 수 있을 것이라 생각했다. 그러나 set은 성분의 순서를 보장하지 않기 때문에 뱀의 꼬리가 어디인지 알아낼 수 없었다. 이를 해결하기 위해 dictionary 자료형을 사용하도록 변경했다. (Pytho..
출처 : 백준, https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 더보기 먼저, 생각해야 할 부분 1. 1개를 골랐을 때 최대 m개라면, m개를 골랐을 때도 같은 값이 나온다. m개가 최댓값이라면 m개를 골랐을 때 최댓값이 나온다. 최대 m개를 골라야하지만, 어짜피 m개보다 작게 고른 경우의 수가 m개를 뽑았을 때도 포함되어 있으므로, 1~m개를 모두 계산하는게 아니라 m개를 고른 경우에 대해서만 계산하면 된다. 풀이 def..
이전에 조합(Combination)의 코드화에 대해서 글을 작성한 적이 있었다. 이번에는 순열의 코드화에 대해 글을 적어보려한다. 순열의 코드화는 조합의 코드화에서 약간만 추가하면 쉽게 만들 수 있다. [4, 3, 2, 1]에서 성분이 2개인 순열을 구하는 방식은 다음과 같다. 먼저 고정된 성분 4를 선택한다. 그 후, 고정된 성분 뒤의 배열에서 1개인 성분을 선택한다. 모두 돌았다면, 고정된 성분 4를 가장 뒤로 보낸다. 그 후 고정된 성분 3을 선택하고 위를 반복한다. 여기서 고정된 성분을 따로 떼어놓고 생각해보자. 고정된 성분 4를 제외하면, [3, 2, 1]에서 1개의 성분에 대한 순열을 구하는 것과 같다. 즉, list에서 성분이 n개인 순열을 구하는 방법은 고른 고정성분 앞의 배열을 고정 성분..
조합(Combination)의 코드화에 대해 글을 작성해보려한다. 조합을 코드화하기 위한 아이디어를 생각해보자. [4, 3, 2, 1]에서 성분이 2개인 조합을 구하는 방식은 다음과 같다. 먼저 4를 고정해놓고 뒤의 숫자를 1개 고른다. 그 후 4를 제외하고 3을 고정, 뒤의 숫자를 1개 고른다. 그런데 여기서 고정된 성분을 따로 떼어놓고 생각해보자. 고정된 성분 4를 제외하고 생각해보면, 이는 [3, 2, 1]이라는 배열에서 성분이 1개인 조합을 구한 것에 성분 4를 추가한 것과 같다. 이를 통해 list에서 n개의 조합을 구하는 알고리즘을 짜보자. 1. 고정할 성분을 선택 2. 이를 제외한 뒤의 배열에서 n-1개의 조합을 구함 3. 이 조합에 고정한 성분을 추가 4. 다음 고정 성분을 선택한 후 반복..
출처 : 백준, https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 더보기 먼저, 생각해야 할 부분 1. 문제를 단순하게 줄여보자 # 구름은 d방향으로 s칸만큼 이동 후 구름이 있는 칸의 물 + 1 => 구름 제거 # 물이 증가한 칸에 대각선 방향으로 거리가 1인 바구니 중 물이 있는 바구니 수만큼 바구니만큼 물 증가 # 1, N 경계는 취급 X # 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고 물의 양이 2가 줄어듬. # ..
출처 : 백준, https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 더보기 먼저, 생각해야 할 부분 1. 문제를 잘 이해하자. 문제가 너무 이상하지만 차근차근 읽어보면 해석이 된다. 문제에서 말하는 단계란 무엇일까? # 단계의 정의 -> 1~4까지가 1단계 # 1. 벨트를 움직인다. -> 로봇 내림 # 2. 로봇을 움직인다. -> 내구도 하락 및 로봇 내림 # 3. 로봇 올림 # 4. 내구도 k개인지 조사 이것이 문제에서 말하..
출처 : 백준, https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 더보기 먼저, 생각해야 할 부분 1. 보자마자 가장 쉬운 접근법이 떠올랐을텐데 그 풀이 방법이 통과 가능한지 검토해보자. 불가능하다는 말이 아니다. 2. 구현 문제는 놓치는 부분 없이 꼼꼼하게 풀어야한다. 조건을 놓치지 않게 조건을 잘 명시하는 의사코드를 대략적으로 적어보자 풀이 : Multiple Pointer import sys def solution(gears, rot_c..
