목록주요 알고리즘 (14)
이호진
상하좌우 문제는 문제에서 요구하는 내용을 좌표상에서 표현하여 구현하는 문제이다. NxN 크기의 배열이 주어지고 [0,0]의 위치를 기준으로 L은 좌측, R은 우측, U는 위쪽, D는 아래쪽으로 이동한 값을 나타내는 문제이다. 이 때, 좌표 밖으로 벗어나는 경우는 제외한다. n = int(input()) 5 x,y=1,1 plans=input().split() R R R U D D dx = [-1,1,0,0] dy = [0,0,-1,1] move_type = ['U','D','L','R'] for plan in plans: for i in range(len(move_type)): if plan == move_type[i]: nx=x+dx[i] ny=y+dy[i] if nxn: continue x,y = n..
이 문제는 n과 k를 입력받아 n을 k로 나눌 수 있으면 나누고 나눌 수 없으면 1을 나눌 수 있을 때 까지 빼서 그 횟수를 출력하는 알고리즘이다. 예를 들어, n=25이고 k=2이면 25-1 = 24, 24/2 = 12, 12/2 = 6, 6/2 = 3, 3-1 = 2, 2/2 = 1로 횟수는 6회이다. 1이 될 때까지 숫자를 줄여나가야 하는데 2 이상의 수로 나누면 1을 빼는것보다 빠르기 때문에 나눌 수 있으면 나누는것이 더 빠르다. 간단하게 while문으로 구성하면, n,k=map(int,input().split()) 25 3 count=0 while n>=k: while n%k != 0: n-=1 count+=1 n=n/k n=int(n) count+=1 while n>1: n-=1 count+=..
큰 수의 법칙이란 그리디 알고리즘을 이용하여 풀 수 있는 문제이다. 예를 들어, 순서대로 2, 4, 5, 4, 6이 주어지고 M=8, k=3 일 때, 8자리를 나열하는데 가장 큰 수를 한 번에 3번까지 더하고 두번째로 큰 수를 더하고 다시 가장 큰 수를 더하는 방식으로 구한다. ex) M=8, k=3일 때, 6+6+6+5+6+6+6+5 =46 결국 가장 큰 수와 두번째로 큰 수를 이용하여 m과 k에 관한 식으로 나타내야한다. ex) M=8, k=3일 때, 6 6 6 5 6 6 6 5 M=8, k=4일 때, 6 6 6 6 5 6 6 6 M=8, k=5일 때, 6 6 6 6 6 5 6 6 이다. k=3인 경우에서 6 6 6 5 / 6 6 6 5 두 묶음으로 표현할 수 있다. 이 때, M을 (k+1)로 나눈 ..
그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 예를 들어, 거스름돈 문제에서 거스름돈으로 사용할 500원, 100원, 50원, 10원 동전이 있다고 가정할 때, 손님에게 거슬러줘야 할 돈이 N원이라면 거슬러 주어야 할 최소한의 동전 개수는 n=1260 count=0 array=[500,100,50,10] for coin in array: count+=n//coin n%=coin print(count) 이렇게 구할 수 있다. 이 문제에서 중요한 것은 모든 동전이 하위 동전의 배수라는 것이다. 예를 들어, 500원 400원 100원 동전이 존재할 때 800원을 거슬러주는 방법에서 최적의 방법은 400원짜리 동전 두 개를 거슬러 주는 것이지만 그리디알고리즘에선 500원 1개, ..