![]()
문제 풀이 무향 그래프에서 1번 노드에서 N번 노드로 가는 최단 경로를 구하는데, 특정 A 노드와 B 노드를 거쳐 가는 최단 경로를 구하는 문제이다. A 노드와 B노드 어느 것을 먼저 지나갈지는 상관이 없다. 따라서 1 -> A -> B -> N or 1 -> B -> A -> N 두 가지 모두 검사를 해보아야 한다. 다익스트라로 위 두 가지 경우를 검사하여 해결하였다. 코드 #include using namespace std; struct edge { int weight; int end; edge(int a, int b) : end(a), weight(b) {}; bool operator e.weight; } }; vector graph(801); bool visited[801]; int dijkstr..
문제 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. 1 X: 정수 X를 스택에 넣는다. (1 ≤ X ≤ 100,000) 2: 스택에 정수가 있다면 맨 위의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다. 3: 스택에 들어있는 정수의 개수를 출력한다. 4: 스택이 비어있으면 1, 아니면 0을 출력한다. 5: 스택에 정수가 있다면 맨 위의 정수를 출력한다. 없다면 -1을 대신 출력한다. 입력 첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 둘째 줄부터 N개 줄에 명령이 하나씩 주어진다. 출력을 요구하는 명령은 하나 이상 주어진다. 출력 출력을 요구하는 명령이 주어질 때마다 명령의 결과를 한 줄에 하나씩 ..
![]()
https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 알고리즘 분류 자료 구조 덱 문제 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다. 각 풍선 안에는 종이가 하나 들어있고, 종이에는 -N보다 크거나 같고, N보다 작거나 같은 정수가 하나 적혀있다. 이 풍선들을 다..
![]()
문제 https://www.acmicpc.net/problem/2257 2257번: 화학식량 첫째 줄에 화학식이 주어진다. 화학식은 H, C, O, (, ), 2, 3, 4, 5, 6, 7, 8, 9만으로 이루어진 문자열이며, 그 길이는 100을 넘지 않는다. www.acmicpc.net Algorithm stack을 이용하는 문제이고, 후위표기식 방식을 생각하면 쉽게 풀린다. 여는 괄호가 나오면 닫는 괄호가 나올때까지 해당 원소들의 질량을 모두 더해주고, 숫자가 나오면 해당 앞의 화학식량의 숫자배를 해주면 된다. 여는 괄호가 나오면 닫는 괄호가 나올때까지 stack에 질량을 넣어준다. 닫는 괄호가 나오면 여는 괄호가 나올때까지 stack에서 pop하여 다 더해준후 stack에 넣어준다. 숫자가 나오는 ..
2161번: 카드1 (acmicpc.net) 2161번: 카드1 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제유형 *큐 문제 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는..
![]()
문제 https://www.acmicpc.net/problem/24041 24041번: 성싶당 밀키트 첫 번째 줄에 $N, G, K$가 공백으로 구분되어 주어진다. 두 번째 줄부터 $N$ 개의 줄 중 $i$ 번째 줄에는 $i$ 번째 재료에 대한 정보인 부패 속도 $S_i$, 유통기한 $L_i$와 중요한 재료인지를 나타내는 www.acmicpc.net Algorithm i에 대한 모든 S_i의 합이 G 이하이므로 가장 큰 x는 2e9이다. x의 최솟값은 0으로 해서 이진탐색으로 x를 찾는다. x일 이후에도 밀키트를 먹을 수 있으면 최솟값을 증가시키고 없다면 최댓값을 감소시키면서 x를 찾는다. Code import sys input = sys.stdin.readline N, G, K = map(int, in..
https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제요약 K개의 랜선의 길이가 주어진다. 이를 가지고 같은크기로 잘라서 N개의 작은 랜선을 만든다. 이때 만들 수 있는 최대의 길이를 출력한다. 문제 해결 유의해야할 점 랜선의 길이가 2^32-1까지 가능하다. int는 4byte이므로 양수는 2^16-1까지 가능하므로 더 큰 자료형을 써야했다. unsigned int를 사용했다. 1~(입력받은 랜선중 최대길이) 중에 ..
https://www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 코드 #include #include #include #include #include #include #include #include #include #include #include #define LL long long using namespace std; int main() { vector arr; int n; int k; cin >> n >> k; int num; for (int i = ..
![]()
문제 https://www.acmicpc.net/problem/17390 17390번: 이건 꼭 풀어야 해! [2, 5, 1, 2, 3]을 비내림차순으로 정렬하면 [1, 2, 2, 3, 5]이다. www.acmicpc.net Algorithm 수열을 비내림차순으로 정렬 후에 문제에서 주어지는 구간의 합을 출력하면 되는 문제이다. 구간의 합을 출력하면 되므로 누적합을 사용하였고, 비내림차순으로 정렬하기위해 .sort()함수를 사용하였다. 누적합을 사용할 수 있으면 쉽게 풀리는 문제였던것 같다. Code input = __import__('sys').stdin.readline n,q = map(int,input().split()) arr = list(map(int,input().split())) arr.so..
1806번: 부분합 (acmicpc.net) 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제유형 *누적 합 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입출력 예제 (입력 1) 10 15 5 1 3 5 10 7 4 9 2 8 (출력 1) 2 풀이 1. N짜리 수열을 저장하는 arr배열과, 누적합을 저장하는 total배열을 만들어 준다. ..
문제 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액..
![]()
문제 설명 회의실 배정에서 좀 더 어려워진 유형의 욕심쟁이 기법 문제이다. 출력으로 모든 강의를 진행하는데 필요한 강의실의 개수와, 각 강의에 배정되는 강의실 번호를 출력하면 된다. 우선 모든 강의를 시작하는 시간 순서대로 오름차순으로 정렬한다. 그리고 강의가 끝나는 시간을 기준으로 최소 힙을 만들어 강의를 하나씩 집어 넣는데 아래 규칙을 따른다. 1. 최소 힙 루트 원소의 끝나는 시간이 현재 넣어야 하는 강의의 시작 시간보다 작거나 같다면 루트를 제거하고 현재 강의를 넣는다. (진행 중인 강의가 끝나고 같은 강의실에서 진행할 수 있음) 2. 최소 힙 루트 원소의 끝나는 시간이 현재 넣어야 하는 강의의 시작 시간보다 크다면 그냥 넣는다. (강의가 끝나지 않아 새로운 강의실을 만들어야 한다.) 모든 강의를..
