![]()
문제 https://www.acmicpc.net/problem/2548 2548번: 대표 자연수 첫째 줄에는 자연수의 개수 N이 입력된다. N은 1 이상 20,000 이하이다. 둘째 줄에는 N개의 자연수가 빈칸을 사이에 두고 입력되며, 이 수들은 모두 1 이상 10,000 이하이다. www.acmicpc.net Algorithm 주어진 모든 자연수들에 대하여 차이가 가장 작은 자연수를 대표자연수라고 하고, 이를 찾는 문제이다. 차이가 가장 작으려면 주어진 자연수들의 범위 내에서 대표자연수가 존재할 것이다. 주어진 자연수가 예제 처럼 4 3 2 2 9 10이라면 대표 자연수의 범위는 2 ~ 10이 될것이다. 그러므로 자연수들을 입력받은 후 최솟값과 최대값을 구해주고 그 안에서 브루트포스를 진행하면 된다. ..
https://www.acmicpc.net/problem/15810 문제 전북대학교 프로그래밍 경진 대회에서는 ACM-ICPC 스타일을 따라 문제를 해결한 팀에게 그 문제에 해당하는 풍선을 달아준다. 풍선을 담당하는 N명의 스태프가 있다. 스태프마다 폐활량이 다르기 때문에 하나의 풍선을 만드는 데 걸리는 시간은 다양하다. 대회가 시작되고 운영진으로부터 M개의 풍선을 만들어 달라는 의뢰가 들어왔다! 각 스태프가 풍선 하나를 만드는 시간(분) Ai를 알고 있을 때, 풍선 M개를 만들기 위해서 최소 몇 분이 걸릴까? 풍선을 만든 후에 문제를 표시할 것이기 때문에 풍선의 종류는 상관이 없다. 모든 스태프는 풍선을 만드는 데에 정확하게 자신이 말한 시간만큼 걸린다. 예를 들어 스태프 A가 풍선 하나를 만드는 데 ..
https://www.acmicpc.net/problem/11256 11256번: 사탕 당신은 사탕 공장의 주인이다. 날마다, 당신은 J개의 사탕을 가게에 보내기 위해 상자에 포장해야 한다. 당신은 크기가 다른 상자 N개를 가지고 있다. 당신은 편리를 위해 상자를 최소한으로 쓰 www.acmicpc.net 1. 문제풀이 그리디 알고리즘을 이용한 문제로, 상자를 최소한으로 사용하기 위해서 크기가 큰 상자부터 사탕을 담으면 된다. 입력받은 상자의 정보를 바탕으로 상자의 크기를 우선순위 큐에 저장하고, 사탕의 개수가 0이하가 될 때까지 반복문을 돌면서 우선순위가 높은 원소를 꺼내면서 상자의 개수를 1씩 증가시킨다. 2. C++ 코드 #include #include using namespace std; int ..
https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 1. 문제풀이 위치가 X일 때 X-1 또는 X+1로 이동하거나 2*X의 위치로 순간이동할 경우 1초가 소모된다. 이동 방법은 3가지임을 알 수 있으며 동일한 시간이 소모됨을 확인할 수 있다. 각 방법에 대하여 시간이 1초가 소모되는 가중치가 동일한 상황이므로 너비 우선 탐색을 시행하여 최단 시간을 구한다. 현재 위치에서 각 방법으로 이동 한 결과를 큐에 넣은 ..
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 1. 문제풀이 네트워크 연결 상태를 확인 후, 1번 컴퓨터가 바이러스에 걸렸을 때 전파될 수 있는 컴퓨터의 수를 구하는 탐색 문제이다. 깊이 우선 탐색 문제 중 하나로, 네트워크 연결 상태를 입력받은 후 인접 리스트의 형태로 그래프 정보를 저장한 후, 1번 컴퓨터를 매개변수로 하여 깊이 우선 탐색을 진행하였다. 다른 컴퓨터를 방문할 때마다 바이러스에 걸린 컴퓨터의 수를 1씩 증가시킨다. 2. C++ 코..
https://www.acmicpc.net/problem/12789 12789번: 도키도키 간식드리미 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두 www.acmicpc.net 1. 문제풀이 대기줄에서 한 명씩만 설 수 있는 공간을 거쳐서 간식을 받을 수 있는 방법으로 구현하였다. 모든 사람들이 처음에 대기열에서 다른 대기 공간으로 간다. 다른 공간을 스택으로 구현하여, 순번에 맞는 사람이 대기열에 존재할 때까지 다른 공간에 일렬로 서게 된다. 해당 스택의 마지막으로 들어온 사람의 값이 간식을 받을 차례가 아닌 경우 문제 조건에 어긋나므로 Sad를 출력하고 종료하고, ..
https://www.acmicpc.net/problem/16713 16713번: Generic Queries 첫째 줄에는 $N, Q$가 공백을 사이에 두고 주어진다. ($1 \le N \le 10^6$, $1 \le Q \le 3 \cdot 10^6$) 둘째 줄에는 $a_1, a_2, \cdots a_N$이 공백을 사이에 두고 주어진다. ($0 \le a_i \le 10^9$) 그 후, $Q$개의 줄에 걸 www.acmicpc.net 1. 문제풀이 누적합 문제를 XOR 연산을 적용하여 만든 문제이다. XOR 연산은 교환법칙과 결합법칙이 성립한다. 양수 A가 있을 때 XOR 연산은 다음이 성립한다. 1. A XOR 0 = A (0은 항등원) 2. A XOR A = 0 (A는 역원) 위 식이 성립할 때, ..
![]()
문제 https://www.acmicpc.net/problem/27278 27278번: 영내순환버스 첫 번째 줄에 승하차 지점 수 $N$과 병사 수 $M$이 공백으로 구분되어 주어진다. $(2 \leq N \leq 100\,000;$ $1 \leq M \leq 100\,000)$ 두 번째 줄에 $i$번 지점에서 $i+1$번 지점으로 갈 때 걸리는 시간 $t_i$가 공 www.acmicpc.net Algorithm 운전병이 운전 업무를 마친 시간을 구하라고 했으므로 가장 마지막에 내린 병사가 언제내렸는지를 구하면 되는 문제이다. 문제에서 주어지는 거는 각 정류장 사이의 거리와 병사가 출발정거장에서 기다리기 시작한 시간이다. 그러면 우리가 따져주어야 하는 것은 다음과 같다. 병사가 탑승한 시간 병사가 내린 ..
https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 1. 문제풀이 0은 빈 칸, 1은 집, 2는 치킨집이다. 최대 M개의 치킨집을 제외하고 나머지 치킨집은 폐업시켜야 한다. 치킨집의 개수가 최대일 때, 도시의 치킨 거리가 최솟값인 것은 자명하다. 도시에서 M개의 치킨집을 정하여, 각 집마다 거리의 합을 구하여, 최솟값을 갱신하면 된다. 도시에서 치킨집을 고르는 것은 조합인 것을 확인하고, 깊이 우선 탐색 방법으로 구현하였다. ..
https://www.acmicpc.net/problem/15624 15624번: 피보나치 수 7 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다. www.acmicpc.net 1. 문제풀이 피보나치 수열은 다음과 같이 수식으로 표현하면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일 때까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 주어진 문제에서 n의 범위는 0 ≤ n ≤ 1,000,000이다. n의 범위가 크므로, n번째 피보나치 수를 구하기 위하여 재귀함수가 아닌 다이나믹 프로그래밍으로 접근하였다. n번째 피보나치 수를 1,00..
https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 1. 문제 풀이 집합 S에 존재하는 로또 번호 중 6개의 번호를 선택하여 나열하는 모든 순열의 수를 완전 탐색을 이용하여 구하였다. 집합 S에서 6개의 원소를 선택하여 나열하기 위해, 집합 S의 개수만큼 0으로 채워진 벡터 V를 만들고, 0부터 5번째 인덱스까지 1을 채운다. 그 후, algorithm 헤더 파일의 prev_permutation 함수를 사용하여 벡터 V의 모든 순열의 수..
![]()
문제 https://www.acmicpc.net/problem/3474 3474번: 교수가 된 현우 첫째 줄에 테스트 케이스의 개수 T가 주어지고, 이어서 T개의 줄에 정수 N이 주어진다(1
