곽의 개발 blog

코드

import sys
input = sys.stdin.readline

n = int(input())
s = set()

def add(x):
    global s
    if x in s:
        return
    else:
        s.add(x)

def remove(x):
    global s
    if not x in s:
        return
    else:
        s.remove(x)

def check(x):
    global s
    if x in s:
        print(1)
    else:
        print(0)

def toggle(x):
    global s
    if x in s:
        s.remove(x)
    else:
        s.add(x)

for _ in range(n):
    temp = input().split()
    if len(temp) == 1:
        if temp[0] == "all":
            s = set(range(1, 21))
        else:
            s.clear()

    else:
        op, x = temp[0], temp[1]
        if op == "add":
            add(int(x))
        elif op == "remove":
            remove(int(x))
        elif op == "check":
            check(int(x))
        elif op == "toggle":
            toggle(int(x))

실수했던 부분

입력으로 받은 문자열을 비교하는 부분에서

temp == "all" 로 작성했다.

temp는 input().split() 을 통해 문자열을 분할한 리스트이기 때문에

문자열을 비교할 때는 temp[0] == "all"로 비교해야 한다.

remove 대신 discard를 써도 된다.

remove함수는 존재하지 않는 수를 제거하려고 하면 오류를 발생하지만

discard함수를 사용하면 오류 없이 정상적으로 종료된다.

문제

아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

 

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

 

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

 

코드

import sys
input = sys.stdin.readline

n = int(input())
matrix = [list(map(int, input().split())) for _ in range(n)]

white, blue = 0,0

def div_conq(x, y, N):
    global white, blue
    cnt = 0
    for i in range(x, x+N):
        for j in range(y, y+N):
            if matrix[i][j]:
                cnt += 1
    if not cnt:
        white += 1
    elif cnt == N*N:
        blue += 1
    else:
        div_conq(x, y, N//2)
        div_conq(x + N//2, y, N//2)
        div_conq(x, y + N//2, N//2)
        div_conq(x + N//2, y + N//2, N//2)
    return

div_conq(0, 0, n)
print(white)
print(blue)

분할 정복 (Divide and Conquer) 문제이다.

주어진 행렬을 재귀적으로 분할해가며, 각각의 영역이 모두 하얀색(0) 또는 모두 파란색(1)으로 이루어져 있는 지 확인한다.

div_conq 함수

행렬의 크기가 N일 때 주어진 위치 인덱스(x,y)에서 시작하여 N x N 크기의 영역을 탐색한다.

영역의 속하는 각 셀의 값이 0이면 white 값을 증가시키고, 1이면 blue 값을 증가시킨다.

만약 영역 내에 0과 1이 섞여 있는 경우에는 해당 영역을 더 작은 단위 (N//2 x N//2)의 영역으로 나누어 재귀적으로 탐색한다.

최종적으로 white와 blue 변수에는 각각 하얀색과 파란색으로 이루어진 영역의 개수가 저장되고, 이를 출력한다.

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = set()
b = set()

for _ in range(n):
    a.add(input().strip())

for _ in range(m):
    b.add(input().strip())

c = a.intersection(b)
sorted_list = sorted(c)

print(len(sorted_list))
for name in sorted_list:
    print(name)

집합을 이용해서 쉽게 구현했다.

뒤에 정리하겠지만 구현은 쉽게 해놓고 자질구레하게 여러 군데에서 틀렸다..ㅜ

파이썬에서 집합(set)은 고유한 원소들의 모음이다.

집합은 중복된 원소를 허용하지 않으며, 순서가 없다.

집합은 원소들 간의 유일성을 보장하고, 집합연산을 쉽게 수행할 수 있다.

union(), intersection(), difference() -> 합집합, 교집합, 차집합

add(), remove(), discard() -> 원소를 추가하거나 제거

오류

1. 문제를 제대로 읽자

• 출력할 때 명단을 사전순으로 출력하라는 조건을 놓쳤다.

2. sorted()

처음에 정렬문을 sorted(c) 이렇게만 썼다.

sorted() 함수는 리스트나 반복 가능한(iterable) 객체의 요소들을 정렬한 새로운 리스트를 반환한다.

원본 리스트를 변경하는 것이 아니라 새로운 정렬된 리스트를 반환하는 것이기 때문에 

sorted(c)를 썼더라도 c 집합이 정렬되지 않은 채로 출력된다.

따라서 정렬된 결과를 출력하기 위해서는 sorted() 함수의 반환 값을 다시 변수에 할당해야 한다.

sorted_list = sorted(c)

이번 문제에서는 해당되지 않지만,

정렬된 리스트를 원본 집합에 저장하려면 정렬된 리스트를 다시 집합으로 변환해야 한다.

여기서 집합은 중복된 요소를 허용하지 않으므로 정렬된 리스트를 집합으로 변환하면 중복된 요소가 제거될 수 있으니 주의해야 한다.

3. 출력 형식 오류

집합에 입력값을 추가하는 문장을 a.add(input()) 으로만 썼더니

출력될 때 문장들 사이에 공백 문장이 추가되는 오류가 떴다.

입력으로 받은 문자열에는 여전히 개행문자('\n')가 포함되어 있다.

그래서 출력할 때도 빈 문장이 같이 출력된 것

'.strip()' : 문자열의 양 끝에 있는 공백과 개행 문자 등을 제거한다.

'.rstrip()' : 오른쪽 끝에 있는 개행 문자를 제거한다.

코드

import sys
input = sys.stdin.readline

n = int(input())
arr = []

for _ in range(n):
    x = int(input())
    if x == 0:
        if not arr :
            print(0)
        else:
            print(min(arr))
            arr.remove(min(arr))
    else:
        arr.append(x)

요렇게 일반적인 배열구조로 짜봤더니 바로 시간초과가 나왔다.

제목에서부터 힙으로 구현하라고 써있으니 힙으로 다시 짜보았다.

import sys
import heapq
input = sys.stdin.readline

n = int(input())
heap = []

for _ in range(n):
    x = int(input())
    if x == 0:
        if not heap:
            print(0)
        else:
            print(heapq.heappop(heap))
    else:
        heapq.heappush(heap, x)

역시나 바로 정답이 나왔다.

x 가 0이고 힙이 비어있다면 0을 출력하고, 힙에 요소가 하나라도 존재한다면 최솟값을 출력하고 pop한다.

x가 0이 아닌 값이면 힙에 push한다.

New

<Heap>

힙은 완전 이진 트리(Complete Binary Tree)의 일종이다.

힙의 루트 노드는 항상 최솟값 또는 최댓값을 가진다.

완전 이진 트리의 형태를 가지며,

배열로 표현될 때 인덱스 i에 저장된 노드의 왼쪽 자식은 인덱스 (2i + 1)에, 오른쪽 자식은 (2i + 2)에 저장된다.

부모 노드의 인덱스는 (i-1)//2 이다.

파이썬에서 힙은 heapq 모듈을 통해 구현된다.

heapq 모듈은 최소 힙(Min Heap)을 기본적으로 제공한다.

이 모듈은 리스트를 힙으로 사용하고, 힙의 모든 연산을 제공한다.

heapq.heappush(heap, x) : 힙에 원소 'x' 추가

heapq.heappop(heap) : 힙에서 최솟값을 추출하고 반환

heapq.heapify(x) : 리스트 'x'를 힙으로 변환한다. 이때 시간 복잡도는 O(n)

heapq.heappushpop(heap, x) : heappush() -> heappop() 을 호출하는 것과 동일하지만, 한번의 연산으로 수행됨

힙은 주로 우선순위 큐(Priority Queue)를 구현하는 데 사용된다.

우선순위 큐는 가장 높은 또는 가장 낮은 우선순위를 가진 항목에 접근하고 수정할 수 있는 추상적인 자료구조이다.

최소 힙을 사용하면 최솟값을 O(1) 시간에 접근할 수 있다.

문제

https://www.acmicpc.net/problem/2579

 

2579번: 계단 오르기

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점

www.acmicpc.net

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

<그림 1>

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

<그림 2>

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

import sys
input = sys.stdin.readline

n = int(input())
stage = [0]*(n+1)
dp = [0]*(n+1)

for _ in range(1, n+1):
	stage[i] = int(input())

if n == 1:
	print(stage[1])
    exit()
elif n == 2:
	print(stage[1] + stage[2])
    exit()

dp[1] = stage[1]
dp[2] = stage[1] + stage[2]
for i in range(3, n+1):
	dp[i] = max(dp[i-3]+stage[i]+stage[i-1], dp[i-2]+stage[i])

print(dp[-1])

역시 동적 프로그래밍 문제이다.

i가 마지막 계단의 인덱스라고 할 때 경우의 수는 두 가지가 있다.

1. i-3번째 계단에서 두 계단을 오른 후 연속으로 i-1 계단 i계단을 밟은 경우

2. i-2번째 계단에서 두 계단을 올라 i계단을 밟은 경우

두 경우의 수 중에서 점수가 높은 경우의 수를 dp 배열에 저장하면 된다.

마지막 출력은 dp의 가장 마지막 인덱스이다.

코드

import sys
input = sys.stdin.readline

s = input().rstrip()

for i in range(len(s)):
    if s[i:] == s[i:][::-1]:
        print(len(s)+i)
        break

if s[i:] == s[i:][::-1] 문은 s[i:] 문자열이 팰린드롬인 지 확인하는 조건문이다.

즉 인덱스 i부터 시작하는 부분문자열을 거꾸로 해도 똑같다면 이 부분문자열은 팰린드롬이기 때문에

i 전의 문자열들을 맨 끝에 반대로 붙여주면 전체적으로 팰린드롬이 완성된다.

분명 저번에 팰린드롬 관련 문제를 풀어서 쉽게 풀릴 줄 알았는데

처음에 방향을 잘못 잡으니까 쉬운 문제임에도 불구하고 계속 헤맸다..ㅜ