IT-garden

문제

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력과 출력

알고리즘 분류

시뮬레이션

정답

from collections import deque

n,m=map(int, input().split())
a=list(map(int,input().split()))
c=0
de=deque([i for i in range(1,n+1)])

for i in a:
    while True:
        if de[0] == i:
            de.popleft()
            break

        else:
            if len(de) - de.index(i) > de.index(i):
                de.append(de.popleft())
            else:
                de.appendleft(de.pop())
                
            c += 1

print(c)

len(de) - de.index(i) > de.index(i)를 통해 왼쪽과 오른쪽 중 어느쪽과 가까운지 확인하여 2번이나 3번 연산을 수행합니다.

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

문제

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

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