문제준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.입력첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)풀이K보다는 작으면서 가장 큰 동전을 선택한 다음, 그 다음으로 큰 동전을 선택하면서 현재 채운 값과 사용한 동전 수를 업데이트하며 K를 모두 채웠을 때 출력한다.코드N, K = map(int, input().split())coins = [int(..
Koala - 16기/코딩테스트 심화 스터디
문제수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.입력첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.풀이N부터 시작하는 위치를 deque에 넣고, visited배열로 각 위치의 방문 여부(-1로 초기화)와 최소 시간을 업데이트 해나간..
문제 & 링크https://www.acmicpc.net/problem/1916 풀이1. 정점(도시)의 개수 n과 간선(버스)의 개수 m을 입력받는다.2. 그래프를 인접 리스트의 형태로 저장한다.3. 최단 거리 배열인 cost를 큰 값으로 초기화한다.4. 다익스트라 알고리즘을 사용하여 최단 거리를 탐색한다.5. 우선 순위 큐를 사용해서 최소 비용부터 탐색한다.6. 모든 인접 정점을 처리하며 최단거리를 갱신한다. 코드#include #include #include #include using namespace std;int cost[1001];vector> V[1001];void dijkstra(int a) { priority_queue, vector>, greater>> pq; pq.push(ma..
문제N×M크기의 배열로 표현되는 미로가 있다.101111101010101011111011미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.입력첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.출력첫째 줄에 지나야 하는 최소의 칸 ..
문제정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.입력입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.입력의 마지막 줄에는 0이 두 개 주어진다.출력각 테스트 케이스에 대해서, 섬의 개수를 출력한다.예제 입력 1..
문제신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출..
문제https://www.acmicpc.net/problem/17298자료구조, 스택 AlgorithmA[i] (입력 값) 리스트, NGE 리스트, stack 리스트를 준비인덱스를 스택으로 만들어서 각 인덱스의 오큰수를 찾아 졸업시키기졸업하지 못한 인덱스는 stack 리스트에 쌓임, 끝까지 졸업하지 못한다면 NGE 리스트에서 초기값 -1로 표현됨A[i] 리스트의 현재 비교값(A[i])와 졸업 대상 (A[stack[-1]])을 비교해 현재 비교값이 더 크면 오큰수를 발견한 것=> 오큰수를 해당 인덱스에 저장하고, 그 인덱스 값은 stack에서 pop되면서 졸업Coden = int(input())a_li = list(map(int, input().split()))NGE = [-1]*nstack_li = [0..
문제풀이디큐를 구현한 다음 가장 위에 있는 카드를 버리고 그 다음 맨 위 카드를 맨 아래로 옮기는 작업을 반복한다카드가 1장 남았을 때 남은 카드를 출력한다코드from collections import deque n = int(input()) lst = [i for i in range(1, n+1)] q = deque() for i in lst: q.append(i) while len(q) != 1: q.popleft() x = q.popleft() q.append(x) print(q[0])
문제평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다. 평석이가 '좋은 단어' 개수를 세는 것을 도와주자. 이 때 단어는 A또는 B로 이루어져 있다.입력첫째 줄에 단어의 수 N이 주어진다. (1 ≤ N ≤ 100)다음 N개 줄에는 A와 B로만 이루어진 단어가 한 줄에 하나씩 주어진다. 단어의 길이는 2와 100,000사이이며, 모든 단어 길이의 합은 1,000,000을 넘지 않는다.풀이스택을 이용한다. 단어의 왼쪽부터 시작해서 A바로 옆에 B가 있거나, B바로 옆에 A가 있으면 좋은 단어일 수 없기 때문에, 단어의 왼..
문제인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두근 설레서 시험 공부에 집중을 못 한다. 이번 중간고사에서도 역시 승환이는 설레는 가슴을 안고 간식을 받기 위해 미리 공지된 장소에 시간 맞춰 도착했다. 그런데 이게 무슨 날벼락인가! 그 곳에는 이미 모든 학생들이 모여있었고, 승환이는 마지막 번호표를 받게 되었다. 설상가상으로 몇몇 양심에 털이 난 학생들이 새치기를 거듭한 끝에 대기열의 순서마저 엉망이 되고 말았다. 간식을 나눠주고 있던 인규는 학우들의 터져 나오는 불만에 번호표 순서로만 간식을 줄 수 있다고 말했다. 그제야 학생들이 순서대로 줄을 서려고 했지만 공간이 ..
문제&링크https://www.acmicpc.net/problem/19951 풀이1. 연병장의 높이를 map 배열에 입력받는다.2. 조교의 지시를 받을 때 sum 배열에서 시작 점에 해당하는 인덱스에 조교가 지시한 높이 k를 입력하고, 끝 점 + 1에 -k를 입력한다. 이렇게 하면 어느 지점부터 어느 지점까지 조교의 지시대로 수행해야 하는지 확인할 수 있다.3. 모든 조교의 지시를 받고 난 후 map과 sum 배열을 처음부터 순회한다.4. sum 배열의 값을 변수 s에 더하고, 해당 변수를 연병장 map에 더한다. 이렇게 하여 조교의 지시를 매 순간 수행하는 것이 아니라, 한 번에 수행할 수 있게 된다. 코드#include using namespace std;int map[100001] = {0};int..
문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.입력첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.풀이dp배열을 이용한다. 이 때 dp[n]의 의미는 n번째 원소를 포함한 연속 부분합 중 최대값을 뜻한다. dp배열의 첫 번째 원소 값을 입력받은 수열의 첫 번째 값으로 설정하고,..
