알고리듬

문제 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 예를 들어 ..

문제 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. 입력 첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다. 출력 첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다. 길이가 1인 오르막 수의 경우는 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 로 총 10개이다 dp[n][x]의 dp[n]을 길이가 n인 오르막 수로 설정하고, x의 범위를 0~9로 설정하여 n번째..

조합 nCm의 값 중 끝에 오는 0의 개수를 구하는 문제이다 nCm = n! / (n-m)!*m! 공식을 사용하여 팩토리얼을 계산하고 0의 개수를 세어줄 수 있겠지만 정수 n,m의 범위를 보았을 때 시간 초과가 날 것을 고려하여 소인수분해를 사용하였다 nCm을 소인수분해 하였을 때 2와 5가 한 쌍이 되어 하나의 0이 만들어지기에(2*5 = 10) 5의 개수가 더 작을 것이라 생각하고 5의 개수를 구하였다 5 = 5 25 = 5*5 125 = 5*5*5 와 같은 패턴을 적용하여 소인수분해 하고자 하는 limit내의 지수 5의 개수를 구하였다 제출 결과는 틀렸으며 지수 2의 개수가 5의 개수보다 적은 경우도 존재한다는 것을 알았다 지수 2와 5의 개수를 모두 구하기 위해 함수를 만들고 def CountZe..

문제 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다. 이 추측은 아직도 해결되지 않은 문제이다. 백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오. 입력 입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다. 각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ..

두 개의 자연수를 입력받고 최대 공약수와 최소 공배수를 출력하는 간단한 문제이다. 최대 공약수는 greatest common divisor의 약자를 사용해서 GCD로 줄여 부르며 최소 공배수는 largest common multiple로 LCM으로 줄여 부른다 GCD와 LCM을 구하는 방법은 다양하다 GCD를 구하는 직관적인 방법으로 1씩 증가시키며 두 수에 모두 나누어 떨어지는지 확인하여 가장 큰 수를 찾아내는 방법이 있다. for i in range(1,min(x,y)+1): if x%i==0 and y%i==0: res = i 이 방법은 O(n)의 시간복잡도를 갖는다 시간 복잡도 측면에서 효율적인 방법으로는 유클리드 호제법이 있다 x,y의 최대 공약수를 구할 때 유클리드 호제법을 사용하면 큰 수를 ..

문제 설명 스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다. 이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다. 맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다. 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다. 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다. 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다. 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다. 4..

import sys N = int(sys.stdin.readline().rstrip()) A = list(map(int,sys.stdin.readline().rsplit())) F = {} # 각 정수의 개수를 담을 딕셔너리 result = [-1 for i in range(N)] NGF = [] # 인덱스를 담을 스택 # 각 정수 개수 저장 for i in A: if i in F: F[i] += 1 else: F[i] = 1 for i in range(N): while NGF and F[A[i]] > F[A[NGF[-1]]]: result[NGF.pop()] = A[i] NGF.append(i) print(*result) 1. 리스트의 정수들을 카운트 2. 스택에 리스트 인덱스를 푸쉬 3. 스택의 to..

N = int(input("")) seq = list(map(int,input().split())) nge_index = [] L = len(seq) result = [-1 for i in range(L)] ### 시간 초과 ### # for i in range(L): # for j in range(i,L): # if(seq[i] seq[nge_index[-1]]): result[nge_index.pop()] = seq[i] nge_index.append(..