본문 바로가기

Algorithm problems, coding test

 (19)
[이코테][Chapter 3][문제] 2. 큰 수의 법칙 큰 수의 법칙이란 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과해 더할 수는 없다. [입력] 배열의 크기 N, 숫자가 더해지는 횟수 M, 연속해서 숫자를 최대로 더할 수 있는 횟수 K [출력] 큰 수의 법칙에 따라 더해진 답 [예시] 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M=8, K=3이라고 가정하자. 특정한 인덱스의 수를 연속해서 3번까지 더할 수 있으므로 큰 수의 법칙에 따라 결과는 6+6+6+5+6+6+6+5=46이 된다. 다른 예시로 3, 4, 3, 4, 3으로 이루어진 배열이 있을 때 M=7, K=2라고 가정하면, 결과는 4+4+4+4+4+4+4=28이 된다..
[이코테][Chapter 3][문제] 1. 거스름돈 [문제] 당신은 음식점의 계산을 도와주는 점원입니다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한이 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다. [입력] 1260 [출력] 6 가장 대표적이고, 가장 간단한 그리디 알고리즘 문제이다. 접근법 : 제일 큰 동전부터 거슬러주면서, 갯수를 하나씩 센다. import time n = 1260 #거스름돈 count = 0 #동전의 개수 coin_types = [500,100,50,10] #동전의 종류 start_time = time.time() for coin in coin_types: count += ..
[이코테][Chapter 3] Greedy Algorithm Greedy Algorithm는 "탐욕법"으로 번역 되기도 한다. 사전적인 의미로는 "가장 좋아보이는 방법을 계속 택하는 방법"이라고 하는데, 사실 좀 더 실용적으로 얘기해보면 "동일한 규칙을 계속 반복하는 방법"이라고도 할 수 있다.

티스토리툴바