10866번: 덱

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지

www.acmicpc.net

 

 

<내 코드>

import sys

class Deque:
    def __init__(self):
        self.result = list()

    def push_front(self, num):
        self.result.insert(0, num)

    def push_back(self, num):
        self.result.append(num)

    def pop_front(self):
        if(self.empty()):
            return -1
        else:
            return self.result.pop(0)

    def pop_back(self):
        if(self.empty()):
            return -1
        else:
            return self.result.pop()

    def front(self):
        if(self.empty()):
            return -1
        else:
            return self.result[0]

    def back(self):
        if(self.empty()):
            return -1
        else:
            return self.result[-1]

    def size(self):
        return len(self.result)

    def empty(self):
        if(self.size() == 0):
            return 1
        else:
            return 0


N = int(sys.stdin.readline())
deque = Deque()

for _ in range(N):
    input_split = sys.stdin.readline().split()
    oper = input_split[0]

    if(oper == 'push_front'):
        deque.push_front(int(input_split[1]))
    elif(oper == 'push_back'):
        deque.push_back(int(input_split[1]))
    elif(oper == 'pop_front'):
        print(deque.pop_front())
    elif(oper == 'pop_back'):
        print(deque.pop_back())
    elif(oper == 'front'):
        print(deque.front())
    elif(oper == 'back'):
        print(deque.back())
    elif(oper == 'empty'):
        print(deque.empty())
    elif(oper == 'size'):
        print(deque.size())

 

반응형

 

 

7568번: 덩치

우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩

www.acmicpc.net

 

 

<내 코드>

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

counts = [1 for _ in range(n)]

for i in range(n):
    for j in range(n):
        if((arr[i][0] < arr[j][0]) and (arr[i][1] < arr[j][1])):
            counts[i] += 1

print(*counts)

 

자신보다 키, 몸무게 모두 큰 사람 수를 단순히 모두 비교하면 되는 문제다.

 

반응형

 

 

1992번: 쿼드트리

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는

www.acmicpc.net

 

 

<내 코드>

 

n = int(input())
video = [list(input()) for _ in range(n)]


def divide(x, y, n):
    ans = []
    check = True
    color = video[x][y]

    for i in range(x, x+n):
        if not check:
            break
        for j in range(y, y+n):
            if color != video[i][j]:
                check = False
                ans.append("(")
                ans.extend(divide(x, y, n//2))
                ans.extend(divide(x, y+n//2, n//2))
                ans.extend(divide(x+n//2, y, n//2))
                ans.extend(divide(x+n//2, y+n//2, n//2))
                ans.append(")")
                return ans
    return color


print("".join(divide(0, 0, n)))

 

list.append와 list.extend의 차이에 대해 알게 됐다.

a = [1, 2, 3]
b = [4, 5, 6]

a.append(b)
print(a) # [1, 2, 3, [4, 5, 6]]

a = [1, 2, 3]
b = [4, 5, 6]

a.extend(b)
print(a) # [1, 2, 3, 4, 5, 6]

append는 해당 리스트(b) 그 자체를 리스트(a) 끝에 넣어준다. 반면에 extend는 해당 리스트(b) 안의 요소들을 (a)리스트 끝에 넣어 확장시켜준다.

반응형

 

 

2630번: 색종이 만들기

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다.

www.acmicpc.net

 

 

<내 코드>

 

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

white, blue = 0, 0


def divide(x, y, n):
    global white, blue
    color = paper[x][y]
    check = True

    for i in range(x, x+n):
        if not check:
            break

        for j in range(y, y+n):
            if color != paper[i][j]:
                check = False
                divide(x, y, n//2)  # 1사분면
                divide(x, y+n//2, n//2)  # 2사분면
                divide(x+n//2, y, n//2)  # 3사분면
                divide(x+n//2, y+n//2, n//2)  # 4사분면
                break
    if check:
        if color:
            blue += 1
        else:
            white += 1


divide(0, 0, N)
print(white)
print(blue)

 

이 문제는 처음 접하는 개념인 '쿼드트리'를 만드는 것이었다. 트리의 자식노드가 4개씩 분할하는 방법이라고 한다.

여기서 분할 된 영역 안에서 같은 색인지 판단해 다르다면 또 다시 나누면서 찾아간다. 일반 동적 계획법과 다르게 분할 정복은 중복되는 하위 문제가 없다는 것이 차이다.

반응형

 

 

14889번: 스타트와 링크

예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.

www.acmicpc.net

 

 

<내 코드>

 

from itertools import combinations

N = int(input())
S = list(list(map(int, input().split())) for _ in range(N))
comb = combinations(range(N), N//2)  # 0 ~ N-1을 N/2 만큼 씩 조합
ans = float('inf')  # inf는 어떤 숫자와 비교해도 무조건 크다고 판정
# -inf는 어떤 수보다 무조건 작다

for c in comb:
    start_team = list(c)
    link_team = list(set(range(N)) - set(c))  # 차집합 후 리스트화

    start_ability, link_ability = 0, 0

    for i in range(N//2 - 1):
        for j in range(i+1, N//2):
            start_ability += S[start_team[i]][start_team[j]
                                              ] + S[start_team[j]][start_team[i]]
            link_ability += S[link_team[i]][link_team[j]] + \
                S[link_team[j]][link_team[i]]

    ans = min(ans, abs(start_ability - link_ability))

print(ans)

 

 

이번 문제는 백트래킹 문제지만 브루트포스로 풀었다. 다른 사람의 풀이를 참조하면서 새로운 개념들을 몇 가지 알게 됐다. 집합을 이용해 팀을 나누는 방법을 사용했다.

inf - 어떤 숫자와 비교해도 무조건 크다고 판정되는 파이썬 기능

-inf - 어떤 숫자와 비교해도 무조건 작다

 

반응형

 

 

14888번: 연산자 끼워넣기

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 

www.acmicpc.net

 

 

<내 코드>

 

N = int(input())
nums = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())

# 비교값
max_ = -1e9
min_ = 1e9


def dfs(cnt, res, add, sub, mul, div):
    global max_, min_
    # 재귀 탈출 조건
    if cnt == N:
        max_ = max(res, max_)
        min_ = min(res, min_)
        return

    if add:
        dfs(cnt+1, res+nums[cnt], add-1, sub, mul, div)
    if sub:
        dfs(cnt+1, res-nums[cnt], add, sub-1, mul, div)
    if mul:
        dfs(cnt+1, res*nums[cnt], add, sub, mul-1, div)
    if div:
        dfs(cnt+1, int(res/nums[cnt]), add, sub, mul, div-1)


dfs(1, nums[0], add, sub, mul, div)
print(max_)
print(min_)

 

백트래킹을 이용해 모든 경우를 다 탐색하는 방법이다. 아직까지 재귀와 백트래킹 개념이 어려운 것 같다..

반응형

 

 

15652번: N과 M (4)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

 

<내 코드>

 

import sys
N, M = map(int, sys.stdin.readline().split())
visited = [0 for _ in range(N)]
arr = []


def dfs(cnt):
    if cnt == M:
        print(*arr)
        return

    for i in range(N):
        if visited[i] == 0:
            arr.append(i+1)

            dfs(cnt+1)  # 다음 깊이 탐색
            visited[i] = 1

            arr.pop()  # 탐사한 내용 제거
            # 시작 탐색 값만 제외시키도록 나머진 초기화
            for j in range(i+1, N):
                visited[j] = 0


dfs(0)
반응형

 

 

15651번: N과 M (3)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

 

<내 코드>

 

N, M = map(int, input().split())
#visited = [0 for _ in range(N)]
arr = []


def dfs(cnt):
    if cnt == M:
        print(*arr)
        return

    for i in range(N):
        arr.append(i+1)
        dfs(cnt+1)  # 다음 깊이 탐색
        arr.pop()  # 탐사한 내용 제거


dfs(0)

 

앞의 (1), (2) 순열, 조합 문제랑은 다르게 같은 수 중복 제거가 없다. 중복이 허용되고 그냥 탐사한 내용만 제거해주면 간단하게 된다.

반응형

+ Recent posts