알고리즘

[알고리즘] 만들 수 없는 금액

문제 (이코테 P. 314) 동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요. 예를 들어, N=5 이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리(화폐 단위) 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원입니다. 또 다른 예시로, N=3이고, 각 동전이 각각 3원, 5원, 7원 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 1원입니다. 입력 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어진다. (1 > 소유가능 금액 갱신 else: possessed += new print(find_impossibl..

[알고리즘] 시간 복잡도

코딩 테스트에서 일반적인 시간 제한은 1~5초 정도이고, 그러므로 연산의 횟수가 10억을 넘어가게 되면 일반적으로 오답 판정을 받는다. 그래서 일반적으로는 O(N^3)을 넘어가면 문제 풀이에서 사용하기 어렵다. 아래를 보면 알 수 있듯이 N이 1000일때, 아래로 갈수록 연산 횟수가 지수적으로 증가하는것을 확인할 수 있다. 그러나, 무조건적으로 O(N^3)의 복잡도를 지양해야하는것은 아니다. 입력값의 크기에 따라서 O(N^3)을 사용해도되는 문제들이 있다. 예를들어, 전체 명령의 갯수가 1000개 이하이고 문제의 시간제한이 5초라면 O(N^3)을 사용해도 문제가 되지 않는다. 2020 KAKAO BLIND RECRUITMENT 의 '기둥과 보 설치' 문제가 그런 경우다. https://school.pro..