본문 바로가기
728x90

Python13

백준 9012 - 괄호( Python ) https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 아마 스택 기본 문제이지 않을까 싶다. 예제로도 많이 등장하는 괄호 문제 1차 답안 n = int(input()) for i in range(n): data = input() stack = [] result = 'YES' for i in data: if i == '(': stack.append(i) else: if i == ')' and len(stack) == 0:.. 2023. 3. 6.
백준 1049 - 기타줄( Python ) 1049번: 기타줄 (acmicpc.net) 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 백준 그리디 4실버 문제인데 반례를 생각하지 못해서 결국 도움을 받은 문제.. 아직 반례를 생각하는게 쉽지않다 조금 더 분기를 차근차근 나누는 연습이 필요할 듯 싶다. 처음에는 단순히 튜플로 패키지, 단품 가격 비교만 했는데 조금 더 자세한 비교가 필요했다. 총 4개의 케이스가 있으며 튜플로 비교하는 것보다 패키지 묶음, 단품 묶음으로 비교하는 것이 생각하는 것이 편하다 1. 6개 이하인 경우 낱개 가격만 비교 2.. 2023. 2. 22.
백준 16401 - 과자 나눠주기( Python ) https://www.acmicpc.net/problem/16401 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1, www.acmicpc.net 이진탐색으로 풀이가 가능한 파라메트릭 서치형식의 문제이다. 이진탐색으로 풀이를 생각하는 것은 어렵지 않았던 반면 과자하나를 어떻게 여러번 잘라야하나라는 생각이 쉽게 들지 않앗다. 나누기를 이용하면 되는 간단한 수준이였음에도 불구하고 아직 풀이 방향성을 잡는데 시간이 오래 걸린다. 풀이는 매우 간단하다 m,n = .. 2023. 2. 16.
최단 경로 알고리즘 - 플로이드 워셜 알고리즘 드디어 최단 경로 알고리즘! DFS/BFS의 벽이 너무 높았지만 내가 해냄 플로이드 워셜 알고리즘 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단경로를 구할때 사용하는 알고리즘이다. 단계마다 거쳐가는 노드를 기준으로 알고리즘을 수행한다. 이 때 점화식을 사용하게 되므로 일종의 다이나믹 프로그래밍이다. 노드의 개수가 n개 일때 n번의 단계를 수행하며 단계마다 n^2의 연산을 통해 모든 경로를 고려하게된다. 총 시간복잡도는 n^3이다. 시간복잡도가 큰 만큼 풀 수 있는 유형이 정해져있다. 풀이 순서 1. 2차원의 리스트를 무한의 값으로 채워 넣는다. 2. 자기자신에서 자기자신으로 가는 경우는 비용을 0으로 처리 3. 각 간선의 정보를 입력받아 초기화 한다. 4. 플로이드 워셜 알고리즘 수행.. 2023. 1. 24.
백준 16953 - A → B ( Python ) https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 그리디 알고리즘의 일종이라고도 볼 수 있는 것 같다 풀이 1. b가 짝수인 경우 2로 나눌 수 있음 2. 1로 끝나는 경우 1제거 3. 짝수이면서 1로 끝나는 경우는 없으므로 if ~ elif로 작성 풀이 방식을 떠올리는 건 어렵지 않았다. 하지만 1로 끝나는 경우 1제거하는 방식을 문자열로 치환후 slice하였는데 다른 사람 풀이를 확인해보니 10으로 나눈 나머지로 분기를 정할 수 있었다.. 문제의 전제가 숫자였으니 이런 방식도 떠올려야하는데 아직 알고리즘 풀이가 많이 부족하다ㅠ 힘내자... a, b = map(int,.. 2023. 1. 14.
백준 2512 - 예산 ( Python ) https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 이진 탐색으로 풀이가 가능하다 예산의 상한선을 구하는 문제다 예산의 상한선을 구하기 위해서는 총 예산의 최적의 합계가 필요하다. 이진 탐색의 중간값이 예산의 상한선이 되며 해당 상한선보다 예산이 큰 경우에는 상한선을 더하고 예산이 작거나 같은경우에는 해당 예산을 더한다 총 예산의 합이 지정된 예산값보다 작거나 같은 경우 상한선을 높이고 -> start값을 늘려줌 초과된 경우에는 상한선을 줄이.. 2023. 1. 10.
728x90
반응형

티스토리툴바