https://www.acmicpc.net/problem/11256 11256번: 사탕 당신은 사탕 공장의 주인이다. 날마다, 당신은 J개의 사탕을 가게에 보내기 위해 상자에 포장해야 한다. 당신은 크기가 다른 상자 N개를 가지고 있다. 당신은 편리를 위해 상자를 최소한으로 쓰 www.acmicpc.net 1. 문제풀이 그리디 알고리즘을 이용한 문제로, 상자를 최소한으로 사용하기 위해서 크기가 큰 상자부터 사탕을 담으면 된다. 입력받은 상자의 정보를 바탕으로 상자의 크기를 우선순위 큐에 저장하고, 사탕의 개수가 0이하가 될 때까지 반복문을 돌면서 우선순위가 높은 원소를 꺼내면서 상자의 개수를 1씩 증가시킨다. 2. C++ 코드 #include #include using namespace std; int ..
C++
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/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/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 1. 문제 후위 표기식과 각 피연산자에 대응하는 값들이 주어져 있을 때, 그 식을 계산하는 프로그램을 작성하시오. 2. 입력 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이는 100을 넘지 않는다) 그리고 셋째 줄부터 N+2번째 줄까지..
https://www.acmicpc.net/problem/2828 2828번: 사과 담기 게임 상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M screen >> basket; cin >> apple; int* arr = new int[apple]; int location; for (int i = 0; i > location; arr[i] = location; } int left = 0, right = basket - 1; int cost = 0; for (int i = 0; i < apple; ++i) { int dropIdx = arr[i] - 1; int dista..
https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 1. 문제 상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다. 각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다. 상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지,..
https://www.acmicpc.net/problem/10173 10173번: 니모를 찾아서 여러 문장이 각 줄로 입력되며, 입력의 마지막에는 "EOI" 입력된다. 한 줄은 최대 80개의 글자로 이루어져 있다. www.acmicpc.net 1. 문제 영어 문장속 숨어있는 니모(Nemo)를 찾아보자. 니모를 찾는데 있어서 대소문자는 중요하지 않다. 2. 입력 여러 문장이 각 줄로 입력되며, 입력의 마지막에는 "EOI" 입력된다. 한 줄은 최대 80개의 글자로 이루어져 있다. 3. 출력 숨겨진 니모를 찾으면 “Found”, 못찾으면 “Missing”를 각 줄에 맞게 출력하면 된다. 4. C++ 코드 #include #include using namespace std; int main() { ios::sy..
