IT-garden

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

예제 입력과 출력

정답

from collections import deque

n,k=map(int, input().split())
de=deque([i for i in range(1,n+1)])
r=[]

while len(de) != 1:
    for i in range(k-1):
        de.append(de.popleft())
    r.append(de.popleft())
    
r.append(de[0])

print('<'+ ', '.join(map(str,r)) +'>')

백준 알고리즘 11866번 : https://www.acmicpc.net/problem/11866

문제

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(1≤N≤500,000)이 주어진다.

출력

첫째 줄에 남게 되는 카드의 번호를 출력한다.

예제 입력과 출력

알고리즘 분류

시뮬레이션 

정답

from collections import deque

de=deque()
n=int(input())

for i in range(1,n+1):
    de.append(i)

while len(de) != 1:
    de.popleft()
    de.append(de.popleft())

print(de[0])

백준 알고리즘 2164번 : https://www.acmicpc.net/problem/2164

문제

상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)

다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.

사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

출력

첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

예제 입력과 출력

알고리즘 분류

브루트 포스 

정답

import sys
input= lambda : sys.stdin.readline().strip()

n=int(input())
a=[list(input()) for i in range(n)]
r=0

def width():
    global r
    
    for i in range(n):
        c=1  
        for j in range(1,n):
            if a[i][j] == a[i][j-1]:
                c += 1
            else:
                if r < c:
                    r=c
                c=1
                
        if r < c: # 한줄이 모두 같은 경우 처리
            r=c

def height():
    global r
    
    for i in range(n):
        c=1
        for j in range(1,n):
            if a[j][i] == a[j-1][i]:
                c += 1
            else:
                if r < c:
                    r=c
                c=1
                
        if r < c:
            r=c

for i in range(n):
    for j in range(1,n):
        a[i][j],a[i][j-1] = a[i][j-1], a[i][j] # 사탕 교환
        width()
        height() 
        a[i][j],a[i][j-1] = a[i][j-1], a[i][j] # 교환한 것을 원래대로

for i in range(n):
    for j in range(1,n):
        a[j][i],a[j-1][i] = a[j-1][i], a[j][i] # 사탕 교환
        width()
        height()
        a[j][i],a[j-1][i] = a[j-1][i], a[j][i] # 교환한 것을 원래대로

print(r)

1. 인접한 두 칸을 골라 사탕을 교환하고 전체 보드를 탐색하여 같은 색으로 이루어진 사탕 개수를 확인합니다.
2. 사탕의 최대 개수 r보다 구한 사탕 개수 c가 더 크면 r를 c로 바꿉니다.
3. 교환한 사탕을 원래대로 돌려 놓습니다.
4. 1, 2, 3의 과정을 사탕을 교환하는 모든 경우에 실행합니다.
5. 사탕의 최대 개수 r을 출력합니다.

백준 알고리즘 3085번 : https://www.acmicpc.net/problem/3085

문제

삼각수 Tn(n ≥ 1)는 [그림]에서와 같이 기하학적으로 일정한 모양의 규칙을 갖는 점들의 모음으로 표현될 수 있다.

자연수 n에 대해 n ≥ 1의 삼각수Tn는 명백한 공식이 있다.

Tn = 1 + 2 + 3 + ... + n = n(n+1)/2

1796년, 가우스는 모든 자연수가 최대 3개의 삼각수의 합으로 표현될 수 있다고 증명하였다. 예를 들어,

• 4 = T1 + T2
• 5 = T1 + T1 + T2
• 6 = T2 + T2 or 6 = T3
• 10 = T1 + T2 + T3 or 10 = T4

이 결과는 증명을 기념하기 위해 그의 다이어리에 “Eureka! num = Δ + Δ + Δ” 라고 적은것에서 유레카 이론으로 알려졌다. 꿍은 몇몇 자연수가 정확히 3개의 삼각수의 합으로 표현될 수 있는지 궁금해졌다. 위의 예시에서, 5와 10은 정확히 3개의 삼각수의 합으로 표현될 수 있지만 4와 6은 그렇지 않다.

자연수가 주어졌을 때, 그 정수가 정확히 3개의 삼각수의 합으로 표현될 수 있는지 없는지를 판단해주는 프로그램을 만들어라. 단, 3개의 삼각수가 모두 달라야 할 필요는 없다.

입력

프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어있다.

출력

프로그램은 표준출력을 사용한다. 각 테스트케이스에대해 정확히 한 라인을 출력한다. 만약 K가 정확히 3개의 삼각수의 합으로 표현될수 있다면 1을, 그렇지 않다면 0을 출력한다.

예제 입력과 출력

알고리즘 분류

브루트 포스 

정답

from itertools import combinations_with_replacement
import sys
input = lambda: sys.stdin.readline().strip()

n=int(input())
a=[int(input()) for i in range(n)]

for i in a:
    t=[]
    z=0
    
    for j in range(1,i+1):
        if (j*(j+1))//2 > i:
            break
        
        t.append((j*(j+1))//2)

    com=list(combinations_with_replacement(t,3))

    for k in com:
        if sum(k) == i:
            z=1
            break

    print(z)

입력받은 k에 대한 삼각수 공식을 만들어 리스트 t에 넣습니다.
리스트 t의 요소 중 3개를 뽑아 반복 가능한 조합을 만듭니다.
조합들의 합 중 k와 같은 값이 있으면 1을 출력하고 없으면 0을 출력합니다.

백준 알고리즘 10448번 : https://www.acmicpc.net/problem/10448

문제

준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다.

지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19)

우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다.

예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 되면 16 16 16이 아니라 1 16 16이 된다. 이유는 1 ≤ E ≤ 15 라서 범위를 넘어가기 때문이다.

E, S, M이 주어졌고, 1년이 준규가 사는 나라에서 1 1 1일때, 준규가 사는 나라에서 E S M이 우리가 알고 있는 연도로 몇 년인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 수 E, S, M이 주어진다. 문제에 나와있는 범위를 지키는 입력만 주어진다.

출력

첫째 줄에 E S M으로 표시되는 가장 빠른 연도를 출력한다. 1 1 1은 항상 1이기 때문에, 정답이 음수가 나오는 경우는 없다.

예제 입력과 출력

알고리즘 분류

수학
중국인의 나머지 정리

정답

e, s, m= map(int, input().split())
c=1

while True:
    if (c-e) % 15 == 0 and (c-s) % 28 == 0 and (c-m) % 19 == 0:
        print(c)
        break
    c += 1

백준 알고리즘 1476번 : https://www.acmicpc.net/problem/1476

문제

KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.

예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신을 한다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신을 하지 못한다.

탑들의 개수 N과 탑들의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 알아내는 프로그램을 작성하라.

입력

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.

출력

첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.

예제 입력과 출력

알고리즘 분류

스택

정답

from collections import deque

n=int(input())
a=list(map(int,input().split()))
li=deque()
r=[]

for i in range(n):
    while li:
        if li[-1][1] > a[i]:
            r.append(li[-1][0] + 1)
            break
        li.pop()

    if not li:
        r.append(0)

    li.append([i, a[i]])
    
for i in range(n):
    print(r[i], end=' ')

백준 알고리즘 2493번 : https://www.acmicpc.net/problem/2493