백준 알고리즘) Silver 2 문제 랜덤 풀이

[11279] 최대 힙

import sys
input = sys.stdin.readline
import heapq

n = int(input())
q = []
for _ in range(n):
    num = int(input())

    if num==0:
        if len(q)>0:
            print(abs(heapq.heappop(q)))
        else:
            print(0)
    else:
        heapq.heappush(q, num*-1)

 

파이썬에서 제공하는 힙 자료구조는 최소힙만 가능하기 때문에

heappush를 해줄 때 -1을 곱해서 넣어주고 heappop을 할 때는 다시 -1을 곱하거나 절댓값 처리를 해준다.

 

---

[1182] 부분수열의 합

import sys
input = sys.stdin.readline

def dfs(n, lst):
    global count
    if n==N:
        if len(lst)>0 and sum(lst)==S:
            count+=1
        return
    
    # 원소 포함
    dfs(n+1, lst+[nums[n]])
    # 원소 미포함
    dfs(n+1, lst)
    
N, S = map(int, input().split())
nums = list(map(int, input().split()))
count = 0

dfs(0, [])

print(count)

 

백트래킹, DFS를 이용해서 풀었다. 기본적인 백트래킹 문제라서 쉽게 풀 수 있었다.

(n은 nums에서 사용할 원소의 인덱스를 의미)

 

---

[2630] 색종이 만들기

import sys
input = sys.stdin.readline

def divide(x, y, N):
    global white, blue
    color = arr[x][y]
    
    for i in range(x, x+N):
        for j in range(y, y+N):
            if color != arr[i][j]:
                divide(x, y, N//2)
                divide(x, y+N//2, N//2)
                divide(x+N//2, y, N//2)
                divide(x+N//2, y+N//2, N//2)
                return
    if color == 0:
        white+=1
    else:
        blue+=1

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

for _ in range(n):
    arr.append(list(map(int, input().split())))
    
white, blue = 0, 0
divide(0, 0, n)
print(white)
print(blue)

나눠진 칸의 숫자가 모두 0이거나 1일 때 흰색 or 파란색 색종이의 개수를 센다.

만약 위 조건을 만족하지 않는다면 4분할을 해서 다시 조건을 확인해야 한다. (재귀, 분할)

4분할 할 때 각각의 x좌표, y좌표를 넣어주어 재귀를 총 4번 반복한다.

 

---

[1780] 종이의 개수

import sys
input = sys.stdin.readline

def divide(x, y, N):
    global zero, one, mone
    
    kind = paper[x][y]
    for i in range(x, x+N):
        for j in range(y, y+N):
            if kind != paper[i][j]:
                divide(x, y, N//3)
                divide(x, y+N//3, N//3)
                divide(x, y+2*(N//3), N//3)
                divide(x+N//3, y, N//3)
                divide(x+N//3, y+N//3, N//3)
                divide(x+N//3, y+2*(N//3), N//3)
                divide(x+2*(N//3), y, N//3)
                divide(x+2*(N//3), y+N//3, N//3)
                divide(x+2*(N//3), y+2*(N//3), N//3)
                return
    
    if kind == 0:
        zero += 1
    elif kind == 1:
        one += 1
    else:
        mone += 1
        
    return

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

zero, one, mone = 0, 0, 0
divide(0, 0, n)

print(mone)
print(zero)
print(one)

위 문제와 마찬가지로 재귀, 분할 정복 이용해서 풀기!

이번에는 9칸으로 분리하기 때문에 재귀를 9번씩 한다.

 

---

[11055] 가장 큰 증가하는 부분 수열

import sys
input = sys.stdin.readline

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

dp = [0]*n
dp[0] = nums[0]
for i in range(1, n):
    for j in range(i):
        if nums[j]<nums[i]:
            dp[i] = max(dp[i], dp[j])
    dp[i] += nums[i]
    
print(max(dp))

 

---

[1406] 에디터

import sys
input = sys.stdin.readline
from collections import deque

left = list(input().rstrip())
right = deque()

n = int(input())

for _ in range(n):
    command = list(input().split())
    
    if command[0] == 'L':
        # 커서 왼쪽으로 한 칸 옮기기
        if left:
            right.appendleft(left.pop())
    elif command[0] == 'D':
        # 커서를 오른쪽으로 한 칸 옮기기
        if right:
            left.append(right.popleft())
    elif command[0] == 'B':
        # 커서 왼쪽 문자 삭제
        if left:
            left.pop()
    else:
        # 커서 왼쪽에 문자 추가
        left.append(command[1])
    
answer = left + list(right)
print(''.join(answer))

 

 

처음에는 cursor 변수를 통해서 문자열이 담긴 리스트의 index를 이용해서 pop, insert해줬는데

시간초과가 떴다. 다양하게 코드를 바꿔봤는데도 계속 시간초과,,,,

해결법은 스택, 큐를 이용해서 커서 기준 왼쪽, 오른쪽 데이터를 나누는 방법이었다.

---

[1541] 잃어버린 괄호

import sys
input = sys.stdin.readline

nums = input().rstrip()
minus  = list(map(str, nums.split('-')))
plus = []

for idx, m in enumerate(minus):
    if m.count('+')>0:
        plus = list(map(str, m.split('+')))
        total = 0
        for p in plus:
            total += int(p)
        minus[idx] = total  # 덧셈 결과로 업데이트
    else:
        minus[idx] = int(m) # int형으로 변환

result = minus[0]
for i in range(1, len(minus)):
    result -= minus[i]
    
print(result)

 

 

숫자, 연산자의 순서는 바뀌지 않고 괄호만 추가해서 값이 최솟값이 되는 경우를 구해야 한다.

1. -를 기준으로 나누기

2. +가 존재하는 경우 계산 결과로 값 업데이트

3. 계산하기

 

55-50+40을 입력값이라고 치면,

- 를 기준으로 나눈 minus = [ '50', '50+40' ]이 된다.

minus의 요소들을 하나 하나 살펴보며 +가 있다면 해당 문자열을 계산한다.

+가 없다면 int형으로 변환을 시켜준다.

 

minus = [50, 90]이 된다.

이제 - 연산만 수행하면 된다. minus의 첫 번째 값을 result에 넣어두고

이후 인덱스부터 - 연산을 해주면 된다.

 

55 - 90 = -35

 

---

[11051] 이항계수

이항계수 구하는 법

import sys
input = sys.stdin.readline

def factorial(n):
    result = 1
    for i in range(1, n+1):
        result*=i
    return result
    
n, k = map(int, input().split())

answer = factorial(n)//(factorial(k)*factorial(n-k))
print(answer%10007)

 

---

[11722] 가장 긴 감소하는 부분 수열

import sys
input = sys.stdin.readline

n = int(input())
nums = list(map(int, input().split()))
dp = [1 for i in range(n)]

for i in range(n):
    for j in range(i):
        if nums[j] > nums[i]:
            dp[i] = max(dp[i], dp[j]+1)
print(max(dp))