넘치게 채우기

https://www.acmicpc.net/problem/10972BOJ - 다음 순열문제 유형: 수학, 조합론문제 난이도: Silver III시간 제한: 1초메모리 제한: 256MB 문제1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.1, 2, 31, 3, 22, 1, 32, 3, 13, 1, 23, 2, 1 입력첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다. 출력첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. ..

https://www.acmicpc.net/problem/2097BOJ - 조약돌문제 유형: 수학, 기하학, 사칙연산문제 난이도: Silver V시간 제한: 1초메모리 제한: 128MB 문제당신은 N개의 조약돌을 가지고 있다. 이 조약돌을 좌표평면의 격자점 위에 아무렇게나 떨어뜨렸다. 격자점이란, x좌표와 y좌표 모두가 정수인 지점을 말한다. 이를테면 (1, 1)이나 (0, -9)는 격자점이며, (-2, 3.5)이나 (π, 7.14)는 격자점이 아니다.모든 조약돌을 포함하는 가장 작은 직사각형을 생각할 수 있다. 예를 들어 세 개의 조약돌을 (2,4), (4, 8), (5,5)에 떨어뜨렸다면, 이 세 조약돌을 모두 포함하는 가장 작은 직사각형은 가로 3, 세로 4인 직사각형이다. 이 경우 직사각형의 둘레..

https://www.acmicpc.net/problem/20923BOJ - 숫자 할리갈리 게임문제 유형: 시뮬레이션, 덱, 구현문제 난이도: Silver I시간 제한: 1초메모리 제한: 1024MB 문제인간이 가장 심심함을 느낀다는 오후 1시 22분, 도도와 수연이는 숫자 할리 갈리 게임을 하려 한다. 숫자 할리 갈리 게임의 규칙은 다음과 같다.[숫자 할리 갈리 게임의 규칙]도도와 수연이는 각각 N장의 카드로 이루어진 덱을 배분받는다. 게임 시작 시 그라운드는 비어있는 상태이다.덱은 숫자가 보이지 않게 카드를 뒤집어 쌓아 놓은 카드 더미를 의미한다. 도도와 수연이는 자신의 덱을 가지고 게임을 진행하게 된다.그라운드는 카드를 내려놓게 되는 땅을 의미한다. 그라운드에 카드를 내려놓을 때는 자신의 그라운드에..

https://www.acmicpc.net/problem/6597BOJ - 트리 복구문제 유형: 트리, 재귀, 분할 정복, 그래프문제 난이도: Gold III시간 제한: 1초메모리 제한: 128MB 문제창영이는 바이너리 트리를 매우 좋아한다. 그가 가장 좋아하는 게임은 바이너리 트리를 만들고, 노드에 알파벳 대문자를 하나씩 쓰는 것이다. 같은 알파벳을 여러 노드에 쓰지 않는다.아래는 창영이가 만든 한 바이너리 트리이다. D / \ / \ ..

https://www.acmicpc.net/problem/14556BOJ - Balance문제 유형: 수학, 조합론문제 난이도: Gold II시간 제한: 1초메모리 제한: 256MB 문제리유나는 양팔저울을 가지고 놀고 있다. 무게가 2^1, 2^2, ⋯, 2^N인 N개의 추가 있고, 적당한 순서로 서로 다른 N개의 추를 하나씩 놓는 동안, 왼쪽의 무게가 오른쪽의 무게를 넘지 않도록 하고 싶다. 추를 놓는 순서의 경우의 수를 구하여라. 입력첫째 줄에는, N이 주어진다. (1≤N≤50000) 출력첫째 줄에, 추를 놓는 순서의 경우의 수를 구하여라. 단, 답이 매우 클 수 있으니, 1000000009 (=10^9+9) 로 나눈 나머지를 구하여라. 풀이f(n)를 n개의 추를 놓기 위한 방법의 수라 하자.2^N짜..

https://www.acmicpc.net/problem/12912BOJ - 트리 수정문제 유형: 트리, 그래프, 트리의 지름문제 난이도: Gold I시간 제한: 2초메모리 제한: 512MB 문제N개의 정점으로 이루어진 트리 T가 있다. 트리의 각 정점은 0번부터 N-1번까지 번호가 매겨져 있다.트리에서 임의의 두 정점을 연결하는 단순 경로의 개수는 1개이다.두 정점사이의 거리는 두 정점을 연결하는 단순 경로상에 있는 간선의 가중치의 합이다.트리의 지름은 트리에 존재하는 모든 경로 중에서 가장 긴 것이다.홍준이는 T에서 간선을 하나 제거하고, 간선을 하나 추가하려고 한다. 이때, 추가하는 간선의 가중치는 제거한 간선의 가중치와 같아야 하며, 간선을 추가한 이후에도 트리를 유지해야 한다.이때, 홍준이가 만..

https://www.acmicpc.net/problem/1463BOJ - 1로 만들기문제 유형: 다이나믹 프로그래밍문제 난이도: Silver III시간 제한: 0.15초메모리 제한: 128MB 문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 풀이dp[i] = 1로 만들기위한 최소연산횟수로 한다.dp[1] = 0에서 시작해서, dp..

https://www.acmicpc.net/problem/2668BOJ - 숫자고르기문제 유형: 그래프, dfs/bfs, 위상정렬문제 난이도: Gold V시간 제한: 1초메모리 제한: 128MB 문제세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래와 같이 표가 주어졌다고 하자.이 경우에는 첫째 줄에서 ..

https://www.acmicpc.net/problem/7662BOJ - 이중 우선순위 큐문제 유형: 우선순위 큐, 해시문제 난이도: Gold IV시간 제한: 6초메모리 제한: 256MB 문제이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위..

https://www.acmicpc.net/problem/1003BOJ - 피보나치 함수문제 유형: 다이나믹 프로그래밍문제 난이도: Silver III시간 제한: 0.25초메모리 제한: 128MB 문제다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); }}fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.fibonacci(3)은 fib..