Algorithm (140) 썸네일형 리스트형 1이 될 때까지 문제 N이 1이될 때까지 1을빼거나 K로 나눈다. 이 때, 최소한의 연산으로 1을 만들어라. 유형파악 다른 알고리즘 연결이 안된다. 그리디 알고리즘이다. 아이디어 직관적으로 최대한 K로 나누는게 숫자 1을 만드는데 더 빨리 가까워진다. 나누어 떨어지면 K로 나누고 아니면 1을 뺸다. 정당성 직관적으로 나누는게 항상 1을 빼는거 보단 숫자가 더 빨리 작아지므로 정당하다고 볼 수 있다. 구현 - K로 나눠지는지 확인 - 나눠지면 K로 나눈다. 아니면 1을 뺀다 - 1이 될때까지 반복한다. 코드 n = int(input("입력 : ")) k = int(input("입력 : ")) count = 0 while n != 1: if n % k == 0: n /= k count += 1 else: n -= 1 cou.. 숫자 카드 게임 문제 - 여러개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한장을 뽑는다 - 카드는 행, 열로 구성되어 있다. - 찾는 순서는 행선택, 그 행에서 가장 숫자가 낮은 카드를 뽑는다. - 행을 선택할때 해당 행에서 가장 낮은 숫자를 뽑는 구조인데 이를 고려해, 행마다 가장 낮은 숫자 중 가장 높은 숫자를 뽑도록 해야한다. - 용량 : 128MB, 시간 : 1초 - 1 큰 수의 법칙 문제 큰수의 법칙 : N개의 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더해서 가장 큰 수를 만드는 법칙 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다. - 용량 : 128MB, 시간 : 1초 - 2 Greedy - Concept 해당 문제는 "이것이 코딩 테스트이다" 책을 참고하여 제작하였습니다. 알고리즘의 유형 중 그리디 유형에 대해서 알아보려고 한다. 기본적인 정의는 다음과 같다. "현재 상황에서 지금 당장 좋은 것만 고르는 방법" 이는 여러가지 알고리즘을 사용해 해결하는 유형이 아닌 단순히 창의력, 아이디어를 요구하는 유형을 의미한다. 즉, 어떠한 문제를 만났을 때, 현재 가장 좋아보이는 방법을 선택하는 유형이라고 볼 수 있다. HINT, 사용 상황 가장 큰 순서대로, 가장 작은 순서대로 다른 알고리즘을 생각해봐도 마땅히 연결되는 알고리즘이 없는 경우 보통 그리디 알고리즘은 정렬 알고리즘과 짝을 이루는 경우가 많다. 예시 문제 - 손님에게 거스름돈을 걸러줘야하는데, 500, 100, 50, 10원 단위의 동전이 있다. 이 .. 이전 1 ··· 15 16 17 18 다음
