본문 바로가기

개인 공부185

[Python] 백준 2096번 : 내려가기 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 💡 문제 풀이 DP 문제이다. 메모리의 크기가 매우 작으므로 입력 값을 받는 동시에 최댓값과 최솟값을 따져준다. ✔️ 느낀 점 단순히 2차원 배열로 구현할 수 있다. 크게 어렵진 않지만 메모리 크기 때문에 조금 생각을 바꿀 필요가 있는 문제이다. 조금 바꾸는게 너무 어려웠다.. 💻 코드 import sys input = sys.stdin.readline n = int(input()) DP_max = [0] * .. 2022. 7. 22.
[Python] 백준 2225번 : 합분해 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 💡 문제 풀이 DP 문제이다. 항상 절차대로 접근하면 된다. DP에는 i개의 숫자로 숫자 n을 만드는 경우의 수를 저장한다. DP[0]에는 0부터 숫자를 사용할 수 있으므로 몇 개의 숫자를 쓰던 경우의 수는 1이다. 표를 통해서 이해해 보자. 2를 2개로 만드는 경우는 (0, 2), (1, 1), (2, 0) 3가지이다. 이 경우는 (0을 한 개만 사용) * (2를 한 개만 사용) + (2를 한 개만 사용) * (0를 한 개만 사용) + (1을 한 개만 사용) * (1를 한 개만 사용) 이렇게 3가지로 볼 수 있다. 숫자 .. 2022. 7. 21.
[Python] 백준 1764번 : 듣보잡 https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 💡 문제 풀이 자료구조 문제이다. set에 대한 개념을 알고 있는지 묻고 있다. ✔️ 느낀 점 💻 코드 import sys n, m = map(int, sys.stdin.readline().split()) a1 = set([sys.stdin.readline().strip() for _ in range(n)]) a2 = set([sys.stdin.readline().strip() for _ in .. 2022. 7. 19.
[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.
Today I Learned : 파이썬 (4) 🐍 파이썬 ✔️ 2차원 배열 max 값 ### 2차원 배열에서 최대값 찾기 feat. max() arr= [[1,2], [3,4]] max_ =max(max_, max(map(max, arr))) ✔️ 깊은 복사, 얕은 복사 파이썬에는 객체를 2가지로 분류할 수 있다. 바로 mutable과 immutable. list, dictionary, set 이렇게 3가지만 mutable하고 나머지는 모두 immutable이다. 차이는 변경이 가능한지인데, immutable은 값이 같으면 변수명만 다르고 같은 참조를 한다는 것이다. 깊은 복사와 얕은 복사를 이해하기 위해서 이 개념이 필요하다. 얕은 복사란, 변수를 복사했는데 같은 곳을 참조할 때를 말한다. 대입연산자('='), 슬라이싱([:]), copy(), c.. 2022. 7. 17.

티스토리툴바