[백준] 1541번 잃어버린 괄호 파이썬 풀이
https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 1. 접근 방식 먼저 입력 받은 식을 파싱하자. split()을 사용하면 구분자인 +, -가 사라지기 때문에 for문으로 하나씩 접근해서 파싱한다. 파싱 결과는 후처리가 수월하도록 리스트 형태로 한다. 최소값을 만드는 방법은 덧셈 부분을 최대한 합치는 것이다. 따라서 파싱한 결과를 순회하면서 위 그림과 같은 리스트가 나오도록 덧셈 부분을 모두 더한다. 이후 위 리스트를 식으로 생각하여 계산하..
[백준] 2491번 수열 파이썬 풀이
https://www.acmicpc.net/problem/2491 2491번: 수열 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾 www.acmicpc.net 1. 접근 풀이 연속해서 커지는/작아지는 수열 개수를 저장할 increase / decrease 리스트 2개가 필요하다. 각 리스트에 연속해서 커지고 / 작아지고 있는 수열의 개수를 누적해서 저장한다. 예를 들어 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾아내는 과정은 이러하다. 입력 받은 수열의 첫 번째 숫자인 4는 일단 1개로 카운트한다. 두 번째 숫자 1은 4보다 작으므로..
[백준] 14916번 거스름돈 파이썬 풀이
https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 1. 접근 방식 다이나믹 프로그래밍과 그리디, 2가지 버전으로 접근했다. 다이나믹 프로그래밍 문제를 연습하고자 카테고리를 타고 들어온 문제였기 때문에 dp 테이블을 사용하는 다이나믹 프로그래밍 기법에 맞춰 풀이하고자 노력했다. 이후엔 그리디로도 문제를 해결해보았다. 이 문제는 dp 방식보다 그리디 방식이 더욱 빠르고 간단하다. 그리디로 작성한 코드는 3번에서 확인할 수 있다. 2원과 5원 동전만 거슬러 줄 수 있으므로, dp 테이블의 5번 인덱스까지 미리 초기화해두자. dp 리스트에 1원 ~ 5원을 받았을 때 거슬러..
[백준] 1991번 트리 순회 파이썬 풀이
https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 1. 접근 방식 왼쪽 자식, 오른쪽 자식을 가지는 Node 클래스를 구현하자. 배열로 이진 트리를 표현하는 것보단 실제 이진 트리와 비슷하게 구현하는 편이 더 수월할 것이라고 생각했다. 따라서 실제 이진 트리의 노드처럼 왼쪽 자식, 오른쪽 자식을 갖는 Node 클래스를 작성했다. 딕셔너리로 트리를 표현하자. key는 해당 노드의 value, value는 해당 노드 인스턴스를 저장한다. ..