본문 바로가기

문제 풀이262

[Python] 백준 2294번 : 동전 2 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 💡 문제 풀이 DP 문제이다! DP 문제는 항상 3가지를 고려해준다. 1. 어떤 값을 memoization 할지 2. 어떻게 점화식을 세울지 3. 초기값을 어떤 값으로 둘지 이번 DP 배열에는 n을 만드는데 최소 동전 개수를 넣어주었다. 동전의 가치가 i 보다 크면 DP[i]와 DP[i-c] + 1을 비교해서 더 작은 값으로 최신화를 한다. 더 작은 값으로 최신화하기.. 2022. 7. 19.
[Python] 백준 2293번 : 동전 1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 💡 문제 풀이 DP 문제이다! 역시 점화식만 고민하면 되는 문제이다. 주어진 코인을 기준으로 연산을 실행하고 이전 경우를 따지면서 계산해주면 된다. 문제를 예로 들면, 1을 기준으로 시작한다. 2는 1을 만드는 방법에서 1만 추가해준 것이다. 또, 3은 2를 만드는 방법에서 1만 추가해준 것이다. 즉, 1원이 기준일 때는 경우의 수가 변화가 없다. 1만 추가하면 되기 때문이다. 2를 기준으로 잡았을.. 2022. 7. 18.
[Python] 백준 7576번 : 토마토 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 💡 문제 풀이 BFS 문제이다. BFS를 돌면서 가장 경우를 따져서 찾아내면 된다. 다 돌았는데 0이 있다면 -1을 출력하고 종료하면 되고 아니라면 가장 큰 값을 찾아서 출력하는데 1로 시작했으니 1을 빼줘야 한다. ✔️ 느낀 점 이번에 BFS/DFS를 구현하면서 많이 익숙해진 것 같다. 큰 틀 자체는 어렵지 않고 이제 어떤 방식으로 도출해 나갈지에 대해서만 생각을 하면될 것 같다.. 2022. 7. 17.
[Python] 백준 1927번 : 최소 힙 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 💡 문제 풀이 최소 힙 문제이다. 라이브러리를 불러와서 사용하면 된다. ✔️ 느낀 점 💻 코드 import heapq, sys input = sys.stdin.readline n = int(input()) q = [] for _ in range(n): tmp = int(input()) if not tmp: if not q: print(0) else: print(heapq.hea.. 2022. 7. 16.
[Python] 백준 12100번 : 2048 (Easy) https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 💡 문제 풀이 백트래킹 문제이다. 백트래킹 자체를 구현하는 것은 하나도 어렵지 않다. 5번까지 이동 가능하므로 5번 이동했을 때 (= cnt가 5일 때) 최대 크기의 블록을 찾아서 최신화만 해주면 된다. 이 문제가 어려운 점은 이동이다. 이동에서 주의할 점이 2가지가 있다. 1. 앞의 모든 칸이 비어있다면 끝까지 이동한다는 점 2. 합치는 것은 연속적으로 일어나지 않아.. 2022. 7. 16.
[Python] 백준 1068번 : 트리 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제 풀이 DFS 문제이다! 우선 입력받은 값들을 딕셔너리를 이용해서 그래프화 시킨다. 이미 값들은 그래프화 시켰기 때문에 지우는 것만 따지면 된다. 스택을 이용해서 DFS를 구현한다. 지울 노드를 스택에 넣고 그 자식들을 스택에 넣으면서 차근차근 지워주면 된다. 다 지웠다면 목표 노드의 부모 노드를 for문으로 찾아 리스트에서 지워주고 (N의 범위가 50까지라서 가능하다..!) 남아있는 딕.. 2022. 7. 15.

티스토리툴바