본문 바로가기

분류 전체보기91

백준 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.
[📚누구나 자료구조와 알고리즘] 12-1. 동적 프로그래밍 - 불필요한 재귀 호출 줄이기 재귀는 때로 O(2^N)과 같이 느린 빅오의 원인이 된다. 배열의 최댓값을 구하는 예제 코드로 재귀가 때로 얼마나 많은 비효율적인 호출을 만들어보는지 확인해볼 수 있겠다. def get_max_value(arr): if len(arr) ==1 : # 만약에 인수로 들어온 배열 원소의 갯수가 1개라면 return arr[0] # 최댓값은 해당 원소일 것이다 if arr[0] > get_max_value(arr[1:]) : # 만약 배열의 첫 원소가 나머지 모든 원소들의 최댓값보다 크다면 return arr[0] # 최댓값은 배열의 첫 원소일 것이다. else: # 만약 배열의 첫 원소가 나머지 원소들의 최댓값 보다 작다면 return get_max_value(arr[1:]) # 나머지 원소들 중의 최댓값이.. 2022. 10. 14.
Week02-03. 정말 최선을 다하고 있나. Week02 회고를 쓰지 못했다. Week02를 시작하고 Week03이 끝난 오늘까지도 회고 쓸 시간이 없었다. 정확히는 시간이 없었던 게 아니라 회고를 쓸 마음의 여유가 없었다. 2-3주차 모두 나보다 실력이 뛰어난 팀원들과 함께 팀을 이뤘는데, 팀원들과 속도를 맞춰야 한다는 부담감이 있었다. 정글의 알고리즘 주차에서는 중간 중간 팀원들과 코드 리뷰를 하는데 상대적으로 문제를 푸는 속도 느린 나는 코드 리뷰 속도를 맞추기 위해 매일 매일이 조급했다. 2주차에는 27문제, 3주차에는 23문제를 풀었어야 했는데 2-3주차 모두 4문제를 풀지 못했다. 이 블로그를 보시는 분들이 오해하실까봐 덧붙이자면, 정글에서 제공하는 문제를 오롯이 자기의 힘으로만 풀어야 하는 것은 아니다. 인터넷에서 답을 찾아봐도 되고,.. 2022. 10. 14.
Week01. 알고리즘 파티 + 최적의 공부 방법을 찾아서 Week01 금요일에 처음 백준 문제를 풀기 시작했는데 수요일에 6일만에 백준 실버가 되었다. (그 3일 뒤에 실버4로 또 레벨업ㅎ) 여러분 정글이 이렇게 무서운 곳입니다… 알고리즘을 많이 접해본 사람이라면 더 빠르게 레벨업할 수도 있겠지만, 나의 경우 알고리즘 경험이 거의 없어 하루에 13시간씩 풀었어야했다. 우리 조 모두 비슷한 실력이어서 첫 날에 input() 받는 것 조차 구글링을 하는 단계였는데, 하루하루 하면서 다들 조금씩 실력이 늘어가는 게 눈에 보였다. 알고리즘 커리큘럼을 좀 설명하자면 정글 Week01 부터는 4주동안 자료구조/알고리즘 주차이다. 이 주차들을 거치며 '어떻게 컴퓨터에게 일을 시킬 것인가'를 익히게 된다. WEEK01: 배열, 문자열, 반복문과 재귀함수, 계산복잡도, 정렬,.. 2022. 10. 3.
반응형

티스토리툴바