![]()
문제 풀이 무향 그래프에서 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/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 코드 from itertools import combinations as cb n,m=map(int,input().split()) nlist=list(map(int,input().split())) ans=0 for i in range(n): for t in cb(nlist,i+1): #print(t,sum(t),end=" ") if sum(t)==m: an..
![]()
문제 https://www.acmicpc.net/problem/5533 5533번: 유니크 첫째 줄에 참가자의 수 N이 주어진다. (2 ≤ N ≤ 200) 둘째 줄부터 N개 줄에는 각 플레이어가 1번째, 2번째, 3번째 게임에서 쓴 수가 공백으로 구분되어 주어진다. www.acmicpc.net 코드 n=int(input()) alist=[] blist=[] dlist=[] #ex)처음 플레이어의 숫자가 주어진다 플레이어 수는 5명이라고 하자 for i in range(n): gamelist=list(map(int,input().split())) #점수를 입력한다 #5명이 3번의 게임당 얻은 점수 """ 1번째 2번째 3번째 100 99 98 1번째사람이 3번게임해서 얻은점수 100 97 92 2번째사람이..
![]()
문제 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/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 문제 도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오. 국어 점수가 감소하는 순서로 국어 점수가 같으면 영어 점수가 증가하는 순서로 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소..
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~(입력받은 랜선중 최대길이) 중에 ..
![]()
문제 n진수는 base가 n인 수를 말한다. 예를 들어 십진수는 base가 10인 수이다. n진수의 수 AmAm-1Am-2…A1A0를 n진수로 표현해보면 AmAm-1Am-2…A1A0 = Am × nm + Am-1 × nm–1 + Am-2 × nm–2 + … + A1 × n1 + A0 × n0이다. 예를 들면, 12468은 12468 = 1 × 104 + 2 × 103 + 4 × 102 + 6 × 101 + 8 × 100로 표현할 수 있다. 회문(Palindrome)이란 앞으로 읽으나 뒤로 읽으나 같은 글을 말한다. 예를 들면, madam, level, 12321은 회문이다. 반면에, Chung-ang이나 university, 54899는 회문이 아니다. 어떤 십진수의 수 A가 주어졌을 때, 이를 n진수로..
