알고리즘 (2) 썸네일형 리스트형 [그래프] 프로그래머스 타겟 넘버 파이썬 프로그래머스 코딩테스트 연습의 '타겟 넘버' 문제입니다. 깊이/너비 우선 탐색으로 분류 되어있으며, 재귀적으로 풀어볼 수 있습니다. [문제] 문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/43165 [풀이] numbers의 길이는 최대 20 입니다. 재귀적인 트리구조를 생각해볼 수 있습니다. number의 첫번째 number가 -일 때와 +일 때를 각각 트리의 루트로 두고, 자식 노드도 마찬가지로, 다음 number가 -일 때 +일 때로 두고 지금까지 거친 노드의 합을 구해나갑니다. 그럼 마지막의 여러 리프노드에서 합이 target 값인지 아닌지 확인해 볼 수 있습니다. numbers = [4,1,2,1], target = 4 인 경우를 도식화 .. [dp] 백준 14916 파이썬 백준 14916번 거스름돈 dp 풀이입니다. greedy 알고리즘으로 푸는 방법도 있지만, dp로도 분류되어 있어서 dp로 간단하게 풀어보았습니다. [문제] [과정] 처음엔 5로 나누어 떨어질 때, 2로 나누어 떨어질 때 등의 상황을 if문으로 적절하게 구성해서 구현해보려 했습니다. 점점 greedy 알고리즘으로 구현하게 되어, 이전 index에 저장될 값을 어떻게 이용해볼까 생각하다가 그냥 경우의 수를 쭉 작성해보았습니다. [풀이] 2원짜리 동전은 최대한 적게 사용해야 하고, 5원짜리 동전은 최대한 많이 사용해야 합니다. 작성하다 보면 2원짜리 동전은 5개 이상은 사용할 필요가 없다는 걸 알 수 있습니다. 또 추가적으로 답이 -1인 경우는 n이 1일 때와 n이 3일 때밖에 존재하지 않습니다. 간단히 생.. 이전 1 다음
