이마닷의 블로그

0. 문제 https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 1. 문제분석 - 드래곤 커브를 그리기 위해서는, 직전 세대에 커브 그리기를 마친 점에서부터 시작해서, 이전 세대에서 그린 커브와 동일한 모양의 커브를 시계방향으로 90도를 회전시켜 그려야 한다. 이 때, 새로운 커브를 그릴 때는 이전 세대에서 커브를 그렸던 순서의 역순으로 다시 그려야 한다. 따라서 LIFO(Last In First Out)의 구조인 스택을 ..

0. 문제 https://www.acmicpc.net/problem/156834 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 1. 문제분석 - 주어진 사다리에서 추가로 가로줄을 그려서 사다리 타기의 시작점과 끝점이 모든 경우에 같도록 하는 경우를 찾는 문제이다. 최대 3개의 가로줄을 넣어보고, 그 때의 사다리 타기 결과가 조건을 만족하는 가로줄 개수의 최솟값을 구해야 하므로, 각각의 가로줄을 넣어보고 각 경우에 대해서 사다리 타기의 결과를 체크해 보아야 한다. 즉, 추가할 가로줄을 순차적으로 대입시켜보고,..

0. 문제 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 1. 문제분석 - 8개 이하의 cctv들이 만들어낼 수 있는 사각지대의 넓이를 구하기 위해서는, 각 cctv들이 감시할 수 있는 경우의 수를 모두 고려해 보아야 한다. 즉, 각 cctv들이 움직일 수 있는 경우의 수 대로 사각지대 넓이를 각각 구해보고 그 최솟값을 구해야 하므로, cctv들이 감시할 수 있는 영역을 순차적으로 대입시켜보고, 다시 원래 상태로 복구한 뒤에 새로운..

0. 문제https://www.acmicpc.net/problem/15998 15998번: 카카오머니만약 유효한 최소 충전 단위 M(1 ≤ M ≤ 9 * 1018)이 존재한다면, 첫 번째 줄에 M 을 출력한다. 가능한 값이 여러 가지 있다면, 그중 9 * 1018 이하인 것을 아무거나 하나 출력한다. 존재하지 않는다면www.acmicpc.net 1. 문제분석- 출금하는 금액에 따라 잔액이 음수가 될 때, 음의 값을 갖는 잔액을 양의 값으로 바꾸기 위해서는 최소금액 m을 적어도 1번 이상 채워야 한다. 즉, 잔액이 음수가 되었을 때, 이를 메우기 위해 더해지는 금액들은 모두 공통의 약수를 가지며, 더해지는 금액은 항상 잔액이 최소의 양수 값이 되게 하는 금액이므로 그 약수는 최대공약수가 된다. 따라서 최대..

0. 문제 https://www.acmicpc.net/problem/15954 15954번: 인형들 첫 번째부터 세 번째까지의 인형을 선택하면 표준편차는 2/3의 양의 제곱근이 되고, 이 때 표준편차가 최소가 된다. 두 번째부터 네 번째까지의 인형을 선택하는 경우와, 세 번째부터 다섯 번째 www.acmicpc.net 1. 문제분석 - 주어진 최소 개수 이상의 크기 만큼 순차적으로 표본집합을 만들어 분산 및 표준편차 값을 구하는 비교적 단순한 브루트 포스(Brute Force) 문제이다. 2. 주의할 점 - 값이 double 또는 float으로 이루어지다 보니, 소수점 이하의 값이 처리 도중 잘못 바뀌는 상황에 유의하며 문제를 풀어야 한다. 특히 위 수식 중 두번째 수식처럼 곱하기, 나누기의 연산이 더 ..

0. 문제 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 1. 문제분석 - 주어지는 노드들 전부 간의 관계가 주어지지 않고 일부 노드들간의 방향성있는 edge만 주어지면서 이러한 관계를 답으로 나타내야 하므로 위상정렬(topology sort) 문제임을 알 수 있다. 위상정렬은 대학에서의 선수과목을 예시로 들면 가장 이해하기 쉽다. 2. 주의할 점 - 역시나 출력이 잦으므로, StringBuilder를 쓰면 출..

0. 문제 https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 1. 문제분석 - 특정 위치에 1-9 중 하나의 숫자를 넣을 때에 스도쿠의 모든 조건을 만족하는지 여부를 판단해보아야 하고, 조건을 만족하는지 여부는 이전에 선택했던 결과들(현재 이전의 위치 중 비어있는 자리에 수를 넣은 것)이 영향을 미친다는 점에서 backtracking 방식으로 문제를 풀어야 함을 알 수 있다. - row[i][j], col[i][j], square[i][j]..

0. 문제 https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 1. 문제분석 - 비행기의 도킹은 가능한 가장 큰 번호의 게이트로 하는 것이 가장 효율적이라는 점과, 각 비행기에 주어진 도킹 가능 최대 게이트 값이 다른 비행기라도, 앞선 비행기들이 하나씩 게이트를 차지함에 따라실제로 도킹할 수 있는 게이트의 최대 번호(루트 노드)는 같아질 수 있다(같은 집합에 속한다)는 점에서 union-find 함수를 이용한 di..