[백준] 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는 해당 노드 인스턴스를 저장한다. ..
[백준] 16925번 배열 돌리기 1 파이썬 풀이
https://www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 1. 접근 방식 deque()를 사용해서 배열을 line으로 접근하자. 위 그림처럼 배열을 line으로 접근한다. 사각형 한 줄이 하나의 line인 것이다. line을 만들기 위해서는 인덱스 처리를 통해 for문으로 배열을 색깔별로 접근하면 된다. 하나의 라인을 만들기 위해 4개의 방향으로 접근한다. 각..
[백준] 16935번 배열 돌리기 3 파이썬 풀이
https://www.acmicpc.net/problem/16935 16935번: 배열 돌리기 3 크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다. 1번 연산은 배열을 상하 반전시키는 연산이다. 1 6 2 9 8 4 → 4 2 9 3 1 8 7 2 6 9 8 2 → 9 2 3 6 1 5 1 8 3 4 2 9 → www.acmicpc.net 1. 접근 방식 각 연산을 처리하는 함수를 구현하자. 각 함수는 인자로 기존 배열을 받고, 연산을 적용한 결과(배열)을 반환한다. 함수 내부에서 일어나는 일이 외부에 영향을 끼치고 싶지 않았기 때문에 이와 같이 배열을 인자로 받고, 새 배열을 반환하는 방식으로 구현하고자 한다. 인덱싱과 리스트 comprehension을 ..