IT-garden

문제

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

• add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
• remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
• check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
• toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
• all: S를 {1, 2, ..., 20} 으로 바꾼다.
• empty: S를 공집합으로 바꾼다.

입력

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

출력

check 연산이 주어질때마다, 결과를 출력한다.

예제 입력과 출력

정답

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

m=int(input())
s=[]
for i in range(m):
    a=input().split()

    if a[0] == 'all':
        s.clear()
        s=[i for i in range(1,21)]
        continue
    elif a[0] == 'empty':
        s.clear()
        continue

    num=int(a[1])
    if a[0] == 'add':
        if num not in s:
            s.append(num)
    elif a[0] == 'remove':
        if num in s:
            s.remove(num)
    elif a[0] == 'check':
        if num in s:
            print(1)
        else:
            print(0)
    elif a[0] == 'toggle':
        if num in s:
            s.remove(num)
        else:
            s.append(num)

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

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

예제 입력과 출력

정답

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

n=int(input())
w=[list(map(int,input().split())) for i in range(n)]
a=[i for i in range(n)]

r=10000000

def _10971(li):
    s=0
    
    for j in range(n-1):
        if w[li[j]][li[j+1]] != 0:
            s += w[li[j]][li[j+1]]
        else:
            return -1

    if w[li[-1]][li[0]] == 0:
        return -1
    else:
        s += w[li[-1]][li[0]]
    return s

for li in permutations(a):
    print(li)
    c= _10971(li)
    if c != -1:
        r=min(r,c)

print(r)

파이썬 시간초과로 PyPy3로 제출했습니다.

순열을 이용해 모든 가능한 경우를 확인합니다.
각 도시를 이동하는 비용을 더하는데 비용이 0인 경우는 이동할 수 없으니까 불가능한 경우라고 생각합니다.
또한 마지막 도시에서 여행을 출발했던 도시로 돌아올 때도 비용이 0이면 불가능한 경우라고 생각합니다.
가능한 경우 중 가장 적은 비용을 출력합니다.

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

문제

N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

입력

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

예제 입력과 출력

정답

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

n=int(input())
a=list(map(int,input().split()))

p=list(permutations(a,n))
r=0

for i in p:
    s=0
    li=list(i)
    for j in range(1,n):
        s += abs(li[j]-li[j-1])
    r=max(r,s)

print(r)

배열 a의 모든 경우의 수를 생각합니다.
순열을 이용해 각각 배열의 경우에 대한 합을 구하고 최댓값을 출력합니다.

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

문제

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

• 정사각형은 서로 겹치면 안 된다.
• 도형은 모두 연결되어 있어야 한다.
• 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

입력

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)

둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

출력

첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.

예제 입력과 출력

알고리즘 분류

브루트 포스

정답

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

n,m =map(int,input().split())
a = [list(map(int,input().split())) for i in range(n)]
b = [
    [(0,1), (1,0), (1,1)],
    [(0,1), (0,2), (0,3)],
    [(1,0), (2,0), (3,0)],
    [(0,1), (0,2), (1,0)],
    [(0,1), (0,2), (-1,2)],
    [(1,0), (1,1), (1,2)],
    [(0,1), (0,2), (1,2)],
    [(1,0), (2,0), (2,1)],
    [(0,1), (1,1), (2,1)],
    [(0,1), (1,0), (2,0)],
    [(1,0), (2,0), (2,-1)],
    [(1,0), (1,1), (2,1)],
    [(0,1), (1,0), (-1,1)],
    [(0,1), (1,0), (1,-1)],
    [(0,1), (1,1), (1,2)],
    [(0,1), (0,2), (1,1)],
    [(1,0), (1,1), (1,-1)],
    [(1,0), (2,0), (1,-1)],
    [(1,0), (1,1), (2,0)]
]

def countt(x, y):
    global r
    
    for i in range(19):
        c=a[x][y]
        for j in range(3):
            nx = x + b[i][j][0]
            ny = y + b[i][j][1]
            
            if 0 <= nx < n and 0 <= ny <m:
                c += a[nx][ny]
            else:
                break
        
        r=max(r,c)

r=0
for i in range(n):
    for j in range(m):
        countt(i, j)

print(r)

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

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M*N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8*8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8*8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

출력

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

예제 입력과 출력

알고리즘 분류

브루트 포스
시뮬레이션

정답

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

n,m=map(int,input().split()) # n 세로 ,m 가로
a=[list(input()) for i in range(n)]
min_c = 50*50

def white(ch):
    global min_c
    con = 0
    for i in range(8):
        for j in range(8):
            if i % 2 == 0 and j % 2 == 0 and ch[i][j] != 'W':
                con += 1
            elif i % 2 == 0 and j % 2 == 1 and ch[i][j] != 'B':
                    con += 1
            elif i % 2 == 1 and j % 2 == 0 and ch[i][j] != 'B':
                    con += 1
            elif i % 2 == 1 and j % 2 == 1 and ch[i][j] != 'W':
                    con += 1

    if min_c > con:
        min_c = con
            
def black(ch):
    global min_c
    con = 0
    for i in range(8):
        for j in range(8):
            if i % 2 == 0 and j % 2 == 0 and ch[i][j] != 'B':
                con += 1
            elif i % 2 == 0 and j % 2 == 1 and ch[i][j] != 'W':
                    con += 1
            elif i % 2 == 1 and j % 2 == 0 and ch[i][j] != 'W':
                    con += 1
            elif i % 2 == 1 and j % 2 == 1 and ch[i][j] != 'B':
                    con += 1

    if min_c > con:
        min_c = con

bb=0
cc=0
r=0
s=0

while True:
    li=[]
    
    for j in range(8): 
        li.append(a[bb][cc:cc+8])
        bb += 1
    
    white(li)
    black(li)
    r += 1

    if (n-7)*(m-7)== r:
        break
    
    if cc+8 == m:
        s += 1
        bb = s
        cc =0
        
    elif cc+8 < m:
        cc += 1
        bb = 0 + s
        
print(min_c)

1. 입력받은 보드를 8*8로 나눌 수 있는 경우의 수에 따라 나눕니다.
2. 맨 왼쪽 위 칸이 흰색인 경우와 검은색인 경우에 다시 칠해야 하는 정사각형의 최소 개수를 구합니다.

입력받은 보드를 8*8로 나누는 것이 어려웠습니다.

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

n,m=map(int,input().split()) # n 세로 ,m 가로
a=[list(input()) for i in range(n)]
min_c = 50*50

def white(ch):
    global min_c
    
    con = 0
    for i in range(8):
        for j in range(8):
            if i % 2 == 0 and j % 2 == 0 and ch[i][j] != 'W':
                con += 1
            elif i % 2 == 0 and j % 2 == 1 and ch[i][j] != 'B':
                    con += 1
            elif i % 2 == 1 and j % 2 == 0 and ch[i][j] != 'B':
                    con += 1
            elif i % 2 == 1 and j % 2 == 1 and ch[i][j] != 'W':
                    con += 1

    if min_c > con:
        min_c = con
            
def black(ch):
    global min_c
    con = 0
    for i in range(8):
        for j in range(8):
            if i % 2 == 0 and j % 2 == 0 and ch[i][j] != 'B':
                con += 1
            elif i % 2 == 0 and j % 2 == 1 and ch[i][j] != 'W':
                    con += 1
            elif i % 2 == 1 and j % 2 == 0 and ch[i][j] != 'W':
                    con += 1
            elif i % 2 == 1 and j % 2 == 1 and ch[i][j] != 'B':
                    con += 1

    if min_c > con:
        min_c = con

for i in range(n-7):
    for j in range(m-7):
        t = [z[(0+j):(8+j)] for z in a[(0+i):(8+i)]]
        white(t)
        black(t)

print(min_c)

입력받은 보드를 좀 더 간편하게 나눈 방법입니다.

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

문제

상근이는 어렸을 적에 "봄보니 (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