모각코 2회차

목표 : 이것이 코딩테스트다. with Python 그리디 알고리즘 예제문제를 풀어보자.

1. 거스름돈
   ![]

문제풀이

거슬러야할 돈이 항상 10의 배수이고 거스름돈으로 사용할 금액이 500, 100, 50, 10원이므로 동전의 최소개수를 구하기 위해서는 큰 금액부터 나누어 가면서 개수를 세야 한다.

1. 거슬러야할 돈을 입력받는다.
2. 500, 100, 50, 10을 하나의 리스트로 저장한다.
3. 값을 거스름돈 목록에 있는 순서대로 나누어가며 나머지를 새로운 값으로 최신화하고 몫은 동전의 개수이므로 이를 누적하여 더한다.

Code

2. 큰 수의 법칙

문제풀이
정작 필요로 하는 것은 리스트 목록 중 가장 큰 값과 두번째로 큰 값이다. 최대 반복횟수가 k이므로 k번 반복 후에는 반드시 다음번째는 다른 값이 있어야한다. 따라서 k+1을 하나의 묶음으로 보고 묶음의 개수에서 k를 곱하면 가장 큰 값이 몇 번 나오는 지 알 수 있다. 물론 이는 N % (k+1) = 0 인 경우이다. 이 외의 경우는 나머지만큼 가장 큰 값이 더 나오므로 이 또한 고려해야한다.
따라서 가장 큰 값의 빈도수는 int((m/(k+1)) * k + m % (k+1)) 와 같다.

1. 값들을 입력받은 후 리스트 목록을 정렬한다.
2. 가장 큰 값과 두번째로 큰 값을 새로운 변수로 만들어 저장한다.
3. 가장 큰 값의 빈도수와 두번째로 큰 값의 빈도수를 표현한다.
4. 이를 각자 곱하여 더한다.

Code

3. 숫자 카드 게임

문제풀이
각 행들의 최소값들 중 최대값을 출력하는 문제이다.

1. 행과 열 크기를 입력받는다.
2. 2차원 배열을 만들어 0으로 초기화한다.
3. 2차원 배열에 값들을 저장하며 각 행의 최소값을 새로운 리스트에 저장한다.
4. 각 행의 최소값을 담은 리스트의 최대값을 출력한다.

Code

4. 1이 될 때까지

문제풀이
1로 만들기 위해 할 수 있는 과정으로 1을 빼거나 k로 나누는 두 가지 방법이 있다. 입력조건에 K가 2보다 크므로 1을 빼는 과정보다 나누는 과정이 더 수를 크게 줄일 수 있다. 따라서 N이 1이 아니라면 N % k == 0인지 확인하고 아니라면 1을 빼는 과정을 반복한다. 한 과정을 할 때마다 횟수를 1 증가시킨다. 반복문이 종료하면 횟수를 출력하도록 한다.

Code

이상이다.