Total
[10799] 쇠막대기 (스택)
10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 풀이 """ 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다. 1. 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다. 2. 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다. 3. 레이저는 어떤 쇠막대기의 ..
[1935] 후위표기식2 (후위표기식 연산, 스택)
1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 풀이 """ 후위 표기식과 각 피연산자에 대응하는 값들이 주어져 있을 때, 그 식을 계산하는 프로그램을 작성하시오. 5 ABC*+DE/- 1 2 3 4 5 """ n=int(input()) arr=input() nList=[] # 피연산자 for _ in range(n): nList.append(int(input())) stack=[] for x in arr: if x.isalpha(): num=nList[ord(x)-ord('A')] stack.ap..
[1918] 후위표기식 (중위표기식 변환, 스택)
1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 풀이 """ 중위 표기식을 후위 표기식으로 변환 우선 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다. 그런 다음에 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다. 예를 들어 a+b*c는 (a+(b*c))의 식과 같게 된다. 그 다음에 안에 있는 괄호의 연산자 *를 괄호 밖으로 꺼내게 되면 (a+bc*)가 된다. 마지막으로 또 +를 괄호의 오른쪽으로 고치면 abc*+가 되게 된다. 표기식은 알파벳 대문자와 +, -, *, /, (, ) A..
[2812] 크게만들기 (스택)
2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 """ N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 첫째 줄에 N과 K가 주어진다. (1 ≤ K 0 and stack[-1]
[1744] 수 묶기 ( 수를 묶어서 최댓값 만들기, 우선순위 큐)
1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 분석 양수 : 가능한 큰 수들끼리 묶음 음수: 음수끼리 곱해서 양수로 더함 0 : 음수가 남는경우 0을 곱함 1 : 다 더함 풀이 import sys input=sys.stdin.readline from queue import PriorityQueue pq = PriorityQueue() # 양수처리 mq = PriorityQueue() # 음수처리 one=0 zero=0 n=int(input()) for _ in range(n): data=int(input(..
[1715] 카드 정렬하기 (우선순위 큐)
1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net """ 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 10장, 20장, 40장의 묶음 10+20, 40 => 30, 40 : (10 + 20) + (30 + 40) = 100번의 비교 10+40, 20 => 50, 20 : (10 + 40) + (50 + 20) = 120번의 비교 N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최..
[2294] 동전 2 (동전 개수 최소값)
2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 분석 동전 교환 (DP) 분석 더보기 karla.tistory.com 풀이 """ n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 ..
[2293] 동전 1 (경우의 수 구하기)
2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 분석 [2624] 동전 바꿔주기 (DP) 2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방 karla.tistory.com 풀이 """ n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각..
동전 문제 유형 정리 (greedy, DFS, DP)
1. 여러 단위 동전, 무수히 많을 때, 교환 최소 개수 출력 2023.04.27 - [Algorithm PS/Search] - 동전 교환(DFS) 2023.05.19 - [Algorithm PS/DP] - 동전 교환 (DP) 2023.06.01 - [Algorithm PS/DP] - [2294] 동전 2 (동전 개수 최소값) 2.여러 단위 동전, 무수히 많을 때, 교환 방법 경우의 수 출력 2023.06.01 - [Algorithm PS/DP] - [2293] 동전 1 (경우의 수 구하기) 3.여러 단위 동전, 정해진 갯수, 교환 방법 경우의 수 출력 2023.05.03 - [Algorithm PS/Search] - 동전 바꿔주기 (DFS) 2023.05.03 - [Algorithm PS/DP] - [..
[11047] 동전0 (동전개수의 최솟값 구하기)
11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net """ 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값 출력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) """ import sys input=sys.stdin.readline n,m=map(int,input().split()) a=[] for _..