BOJ-2110 공유기 설치
https://www.acmicpc.net/problem/2110 문제 소개 집 N개가 수직선 위에 있을 때, 공유기 C개를 적당히 설치하려고 한다. N과 C, 그리고 집들의 좌표가 주어졌을 때 가장 인접한 두 공유기 사이의 최대 거리를 구한다. 문제 풀이 매개 변수 탐색 (parametric search) 을 이용하여 풀이하였다. 이진 탐...
https://www.acmicpc.net/problem/2110 문제 소개 집 N개가 수직선 위에 있을 때, 공유기 C개를 적당히 설치하려고 한다. N과 C, 그리고 집들의 좌표가 주어졌을 때 가장 인접한 두 공유기 사이의 최대 거리를 구한다. 문제 풀이 매개 변수 탐색 (parametric search) 을 이용하여 풀이하였다. 이진 탐...
https://www.acmicpc.net/problem/13335 문제 소개 강을 가로지르는 다리를 n개의 트럭이 건너가려고 한다. 다리 위에는 w개의 트럭만 동시에 올라갈 수 있으며, 다리 위에 올라간 트럭들의 무게의 합은 l보다 작거나 같아야 한다. 각 트럭은 하나의 단위시간에 하나의 단위길이만큼만 이동할 수 있으며, 트럭의 순서는 바뀌지 ...
https://www.acmicpc.net/problem/1629 문제 소개 자연수 A를 B번 곱한 수를 C로 나눈 나머지를 구한다. 문제 풀이 분할 정복을 이용한 거듭제곱을 사용하였다. a의 n제곱은 아래와 같이 나타낼 수 있다. [a ^ n = \begin{cases} 1 & if \;\; n == 0 (a ^ \...
https://www.acmicpc.net/problem/1107 문제 소개 이동하고자 하는 채널과 고장난 버튼에 대한 정보가 주어졌을 때 버튼을 누르는 최소 횟수를 구한다. 버튼은 0부터 9까지의 숫자 버튼과 +, - 버튼이 있다. + 버튼과 - 버튼은 누를 시 각각 채널을 1씩 +/-로 이동시킨다. 시작 채널은 100번이다. 문제 풀이 ...
https://www.acmicpc.net/problem/1389 문제 소개 케빈 베이컨 수는 케빈 베이컨 게임을 했을 때 나오는 단계의 합이다. BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구한다. 문제 풀이 bfs를 이용하여 풀이하였다. 함수 bfs는 큐에 정점을 삽입할 때 몇 단계를 거쳐...
https://www.acmicpc.net/problem/17626 문제 소개 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있으며, 어떤 자연수를 복수의 방법으로 표현된다. 자연수 n이 주어질 때, 합이 n과 같게 되는 제곱수들의 최소 개수를 구한다. 문제 풀이 dp로 풀이하였다. dp[x]는 자연수 x를 표현하는 제곱수들의 ...
https://www.acmicpc.net/problem/11286 문제 소개 절댓값 힙은 아래와 같은 연산을 지원하는 자료구조이다. 배열에 정수 $x (x != 0)$ 를 넣는다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출...
https://www.acmicpc.net/problem/1992 문제 소개 쿼드 트리는 흑백 영상을 압축하여 표현하는 데이터 구조이다. 주어진 영상이 모두 0/1으로 되어 있으면 압축 결과는 0/1이 된다. 0과 1이 영상에 섞여 있다면 영상을 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래로 나누어 압축하게 되며 그 결과는 괄호로 묶어서 표...
https://www.acmicpc.net/problem/5525 문제 소개 N + 1개의 I와 N개의 O로 이루어진, I와 O가 교대로 나오는 문자열을 $P_N$이라고 한다. ex) $P_2$ = IOIOI I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 $P_N$이 몇 군데 포함되어 있는지 구한다. 문제 풀이 먼저 찾고...
https://www.acmicpc.net/problem/10158 문제 소개 격자 공간의 크기와 개미의 시작 위치가 주어졌을 때, 주어진 시간동안 개미가 움직인 후 개미의 위치를 구한다. 개미가 공간의 경계면에 부딪히는 경우 반사되어 움직인다. 문제 풀이 개미의 x좌표와 y좌표 모두 1시간에 1씩 변화하며, 경계면에 부딪히는 경우 증가에서 ...