※"이것이 코딩 테스트다"의 저자인 나동빈 님의 유튜브 강의를 보고 학습을 위해 정리한 글입니다. 예제 어떠한 수 N이 1이 될 때 까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다. N에서 1을 뺀다. N을 K로 나눈다. 예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 이경우 전체과정을 실행한 횟수는 3이된다. 이는 N을 1로 만드는 최소 횟수이다. N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야하는 최소 횟수를 구하는 프로그램을 작성하시오 입력조건 - 첫째줄에 N(2
Language/Coding Test
소수? 소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다. 소수 찾는 방법 1. n을 2부터 n-1로 나누었을 때 나누어지지 않으면 소수이다. 시간 복잡도 = $O(n)$ ※ 한개의 소수를 판단할 때의 시간 복잡도이다. for i in range(2, n-1): if n % i == 0: print("소수가 아닙니다.") break else: print("소수입니다.") 2. 1번 방법은 2부터 $\ n-1$ 까지의 수 대입으로 속도가 느리다. 약수의 특징을 통해 효율적으로 접근해보면 $\sqrt{n}$ 까지의 수만 대입해봐도 약수의 여부를 알 수 있다. 약수는 대칭적인 형태를 띄는 것이 초점 N의 약수는 무조건 $\sqrt{n}$의 범위에 존재한다. 시간복잡도 = $O(\sqrt{n}..
※"이것이 코딩 테스트다"의 저자인 나동빈 님의 유튜브 강의를 보고 학습을 위해 정리한 글입니다. 개요 그리디 알고리즘을 쉽게 생각해보면 현재 상황에서 가장 좋은 것만 고르는 방법을 뜻한다. 그리디 알고리즘의 정의는 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식이다. 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다고 한다. 그렇지만 코딩 테스트에서의 대부분의 그리디 문제는 그리디 알고리즘으로 얻은 해가 최적의 해가 되는 상황에서 이를 추론할 수 있어야 풀리도록 출제된다고 한다. - 동빈 나- 예제 그리디 알고리즘의 대표적인 예시로는 거스름돈 예제가 있다. 당신은 음식점에서 계산을..
