문제 실행시간 제한 : 30sec 요약하자면, start와 end를 입력받고 두 수에 존재하는 a=b+c인 경우의 수를 모두 찾아 개수를 구하는 문제이다. 입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초 당 반복문 수행 횟수가 1억(10^8)을 넘어가면 시간 제한을 초과할 가능성이 있다. 시간제한이 1초인 문제를 만났을 때, 일반적인 기준은 다음과 같습니다. 입력이 10,000,000 개의 경우: O(N) 알고리즘 입력이 50,000 개인 경우: O(N * log N) 알고리즘 입력이 10,000 개인 경우: O(N * N) 알고리즘 입력이 400개: O(N * N * N) 알고리즘 입력의 최댓값이 1,000,000 이기 때문에, O(n) 알고리즘의 경우 0.1 초가 걸릴것이고..

문제 설명 모험가 길드에서 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 위기 대처능력이 떨어집니다. 공포도가 X인 모험간는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있습니다. N 명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹의 최댓값을 구하는 프로그램을 작성하세요. # N = 5이고, 각 모험가의 공포도가 [ 2 3 1 2 2 ] 라면 그룹 1에 공포도가 1,2,3인 모험가를 넣고, 그룹 2에 공포도가 2, 2 인 모험가를 넣게 되면 2개의 그룹을 만들 수 있다. 모든 모험가를 특정한 그룹에 넣을 필요는 없다. 입력 예시 출력 예시 5 2 3 1 2 2 2 문제 해결 아이디어 오름 차순 정렬 후 공포도가 낮은 모험가 부터 확..

문제 설명 어떠한 수 N이 1이 될 때 까지 다음 두 과정 중 하나를 반복 선택 수행하려고 한다. 단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다. 1. N에서 1을 뺀다. 2. N을 K로 나눈다. 이때의 최소 수행 횟수를 구하기 풀이 1 : 긴시간이 걸림. O(N)의 시간 복잡도 count=0 def solution(k,n): global count while(n>=2): if n%k==0: n/=k else : n-=1 count+=1 print(count) solution(17,4) 풀이 2: 짧은 시간이 걸림 . O(logN)의 시간 복잡도 count=0 def solution(k,n): global count while True: # N이 K로 나누어 떨어지는 수가 될 때 까지..

그리디 알고리즘 : 현재 상황에서 지금 당장 좋은 것만 보르는 방법, 닫순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토하는 과정이 꼭 필요! 거스름돈 문제 카운터에는 거스름돈으로 사용할 500원, 100원, 50원 10원짜리 동전이 무한히 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단, N은 10의 배수 해결 방법 - 최적의 해를 빠르게 구하기 위해 가장 큰 화폐 단위부터 돈을 거슬러 준다. >> N원을 거슬러 줘야 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을만큼 거슬러주고 이후 단위도 똑같이 반복 - 최적의 해가 보장되는 이유 : 큰 단위가 항상 작은 단위의 배수이기 때문! >> 800원을 ..