본문 바로가기

TIL12

백준 11049. (PyPy3 1등 먹은 풀이!) 행렬체인곱셈 | Python 다이나믹 프로그래밍 🔔 문제 설명은 백준 문제 링크로 대신합니다 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 수많은 시도 끝에 성공한 행렬체인곱셈 문제.. CLRS 책을 한참 읽고서야 이해했고, 문제를 푸는 데도 한참이 걸렸던 문제다. 이 문제는 제대로 상세히 기록을 해 둬야 할 것 같다!! 처음에는 하향식 + 메모이제이션으로 풀었는데 계속해서 시간초과가 났다. 이 문제를 먼저 맞춘 팀원들은 다 상향식으로 풀었다고 해서 상향식으로 다시 풀었다. 사실 CLRS에서 상향식으로 푸는 부분은 도저히가 이해가 안가서 하향식.. 2022. 10. 19.
백준 11047. 동전 0 | Python | 그리디 🔔 문제 설명은 백준 문제 링크로 대신합니다. 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 특정 금액을 최소한의 동전 개수로 만들기 위해서는 단위가 큰 동전부터 최대한 많이 사용해야 한다. 큰 동전을 최대로 사용하고, 남은 나머지를 또 최대한으로 쓰고, 그 나머지를 또 최대한으로 쓰고... 이런 식으로 반복해나가다가 나머지가 0이 되는 시점이 오면 계산을 끝낸다. 예를 들어 1300원이 있고, 이를 500원, 100원, 50원짜리 동전을 '최소.. 2022. 10. 15.
백준 1904. 01타일 | Python | 메모이제이션 & 바텀엄(상향식) 접근 방식 풀이 🔔 문제 설명은 백준 문제 링크로 대신합니다 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 피보나치 수열이라 메모이제이션 방식과 바텀업 방식 둘 다로 풀어보았는데, 메모이제이션 방식은 재귀 깊이 설정(setrecursionlimit())을 안 하거나 충분한 깊이로 하지 않으면 RecursionError가 발생하고, 충분한 깊이로 하면 메모리 초과가 발생한다. 문제에서 N의 범위가 1 ≤ N ≤ 1,000,000 라고 해서 재귀 깊이를 10**7로 했더니 메모리가 초과되고, 줄였더니 런타임에러가 발생했다. 결국 메.. 2022. 10. 15.
백준 2748. 피보나치 수 2 | Python | 메모이제이션 & 바텀엄(상향식) 접근 방식 풀이 🔔 문제 설명은 백준 문제 링크로 대신합니다 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 피보나치 수열의 n번째 원소를 출력하는 문제이다. 이번 주 학습 주제인 동적프로그래밍과 그리디에 대해서 먼저 이론을 공부하고 문제를 풀었는데, 피보나치 수열은 동적프로그래밍의 너무나도 대표적인 예시라서 공부를 하는 과정 중에 먼저 코드를 이해할 수 있었고 문제를 금방 풀 수 있었다. 동적프로그래밍의 두 방식 메모이제이션(memoization)과 바텀업(bottom-up) 방식 모두로.. 2022. 10. 14.
[정글 TIL] 유클리드 호제법 , 재귀 알고리즘 오늘은 랜덤런치 날이라 다른 조원들과 함께 점심 식사를 했는데, 대부분 재귀함수에서 벗어나지 못하고 있었다. 나도 마찬가지라 (^.^) 재귀함수 문제 풀다가 도저히 공부없이는 해결을 못 할 것 같아서 교재를 펴서 재귀 알고리즘을 공부하기 시작했다. 재귀 알고리즘의 예제로 '유클리드 호제법'이 나왔는데 알고리즘은 고사하고 그냥 유클리드 호제법 자체가 이해가 안 가서 유클리드 호제법부터 공부했다. 어차피 이번주차 공부해야 할 내용중에 정수론도 있어서 겸사겸사 함께 공부! 유클리드 호제법은 youtube에서 쑤튜브 채널 영상을 참고해서 이해했다. 유클리드 호제법 유클리드 호제법은 A와 B의 최대공약수는 B와 A를 B로 나눈 나머지의 최대공약수와 같다는 것이다. 즉, A = qB + r 이라면 (q는 몫, r은.. 2022. 9. 26.
[정글 TIL] Week01 | 입출력, 산술연산자(/,//,%) 나의 TIL은 Today I Learned가 아닌 This week I Learned :-) 지난 기수 분들의 TIL을 보면, 대부분 10주차 정도까지만 TIL을 쓰시고 대부분 자취를 감추시더라. 하지만 정글에서 7일째를 보내고 있는 난 이제 알 것 같다. 그 분들이 초심을 잃거나 귀찮으셨던게 아니라 더이상 TIL을 쓸 시간조차 없으셨다는 것을..ㅎㅎ 나도 주차가 진행될 수록 바빠지겠지만 최대한 매주 배웠던 내용들을 정리하고 매 주마다의 깨달음과 마음가짐 등을 마지막 주차까지 꼭 적어보도록 노력해봐야지! 어쨌든 fresh한 마음으로 첫 TIL을 시작해본다! 이번 주부터 4주 간은 자료구조와 알고리즘에 대해 공부하고, python 언어로 백준 알고리즘 문제를 푼다. 나는 주로 javascript로 개발을 .. 2022. 9. 26.
반응형

티스토리툴바