[백준 22859] HTML 파싱 (Python)

August 15, 2022

Algorithm, Baekjoon

Algorithm, Problem Solving, 백준, 백준 골드, Python, String

문제 링크 #

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

문제 해설 #

Idea #

Implementation, String
,
,
태그 등을 구분
의 attribute인 title을 우선 출력하고 안에 있는
를 한 줄씩 출력
안에 있는 태그와 시작과 끝에 있는 공백을 지우고 2개 이상의 공백을 하나로 변경
제목은 무조건 존재하고 태그 사이에는 공백이 없으며 태그는 올바른 쌍으로만 주어짐을 보장
정규 표현식을 활용해 조건에 맞는 문장을 파싱하고 불필요한 문자를 제거해 출력

Data Size #

source: str(1,000,000)

해설 코드 #

python

import re

source = input()

main = re.findall('<main>(.*)</main>', source)[0]
div_list = re.findall('<div title="(.*?)">(.*?)</div>', main)

for title, paragraph in div_list:
    print('title :', title)
    p_list = re.findall('<p>(.*?)</p>', paragraph)
    for p in p_list:
        p = re.sub('(<.*?>)', '', p)
        p = re.sub('\s+', ' ', p.strip())
        print(p)

[백준 21318] 피아노 체조 (Python)

August 12, 2022

Algorithm, Baekjoon

Algorithm, Problem Solving, 백준, 백준 실버, Python, Prefix Sum

문제 링크 #

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

문제 해설 #

Idea #

Prefix Sum
실수한 곡에 대한 누적합을 구하고 인덱싱을 통해 특정 구간에 대한 누적합 출력
마지막 곡은 항상 성공하기 때문에 y에 대한 누적합과 y-1에 대한 누적합이 다르면 1 감소

Time Complexity #

Prefix Sum: O(N) = 100,000

Data Size #

N: 1 <= int <= 100,000
scores: int(10^9) * N
Q: 1 <= int <= 100,000

해설 코드 #

python

import sys
input = sys.stdin.readline

N = int(input())
scores = list(map(int, input().split()))
Q = int(input())

fails = [0]*(N+1)
for i in range(1,N+1):
    fails[i] = fails[i-1] + int(scores[i-1] > scores[min(i,N-1)])

for _ in range(Q):
    x, y = map(int, input().split())
    answer = fails[y] - fails[x-1]
    if fails[y] != fails[y-1]:
        answer -= 1
    print(answer)

[백준 16987] 계란으로 계란치기 (Python)

August 12, 2022

Algorithm, Baekjoon

Algorithm, Problem Solving, 백준, 백준 실버, Python, DFS

문제 링크 #

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

문제 해설 #

Idea #

Backtracking
0번째 계란부터 마지막 계란까지의 모든 경우의 수를 탐색
시간 단축을 위해 현재 계란이 깨진 경우 또는 나머지 모든 계란이 깨진 경우를 예외로 처리
한 번에 두 개 이상의 계란을 치는 경우를 방지하기 위해 계란을 친 후 원상복구 수행

Time Complexity #

Backtracking: O(N^N) = 16,777,216

Data Size #

N: 1 <= int <= 8
S, W: 1 <= int <= 300

해설 코드 #

python

N = int(input())
eggs = list()

for _ in range(N):
    eggs.append(list(map(int, input().split())))

answer = 0
def dfs(eggs, idx):
    global answer
    if idx == N:
        answer = max(answer, len([s for s,w in eggs if s < 1]))
        return

    if eggs[idx][0] < 1:
        dfs(eggs, idx+1)
        return

    if len([s for s,w in eggs if s < 1]) >= N-1:
        answer = max(answer, N-1)
        return

    for target in range(N):
        if target != idx and eggs[target][0] > 0:
            eggs[target][0] -= eggs[idx][1]
            eggs[idx][0] -= eggs[target][1]
            dfs(eggs, idx+1)
            eggs[target][0] += eggs[idx][1]
            eggs[idx][0] += eggs[target][1]

dfs(eggs, 0)
print(answer)

[백준 16918] 봄버맨 (Python)

August 11, 2022

Algorithm, Baekjoon

Algorithm, Problem Solving, 백준, 백준 실버, Python, Simulation

문제 링크 #

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

문제 해설 #

Idea #

Simulation (or BFS)
초기에 빈 칸(.)을 0, 폭탄이 있는 칸(O)을 1로 설정
처음에 폭탄이 있는 칸의 상태를 우선 1 증가시키고, 이후 모든 칸의 상태를 1씩 증가시키는 과정 반복
매번 각 칸의 상태를 점검하면서 3을 초과할 경우 해당 위치 및 이웃 위치를 폭발 대상에 추가
폭발 대상이 존재할 경우 격자의 범위를 벗어나지 않는 범위 내에서 상태를 0으로 변환
위 과정을 N초 동안 반복하고, 0은 빈칸으로, 나머지는 O로 표시하여 출력

Time Complexity #

Simulation: O(N^3) = 8,000,000

Data Size #

R, C, N: 1 <= int <= 200

해설 코드 #

python

import sys
input = sys.stdin.readline

R, C, N = map(int, input().split())

board = list()
char2id = lambda x: 0 if x == '.' else 1
id2char = lambda x: '.' if x == 0 else 'O'
for _ in range(R):
    board.append(list(map(char2id, input().strip())))

board = [[state+1 if state > 0 else 0 for state in row] for row in board]

for s in range(2,N+1):
    board = [[state+1 for state in row] for row in board]

    bomb = set()
    for i in range(R):
        for j in range(C):
            if board[i][j] > 3:
                neighbor = [(0,0),(1,0),(-1,0),(0,1),(0,-1)]
                [bomb.add((i+dy,j+dx)) for dy,dx in neighbor]

    for i,j in bomb:
        if 0 <= i < R and 0 <= j < C:
            board[i][j] = 0

for row in board:
    print(''.join(list(map(id2char, row))))

[백준 2302] 극장 좌석 (Python)

August 11, 2022

Algorithm, Baekjoon

Algorithm, Problem Solving, 백준, 백준 실버, Python, DP

문제 링크 #

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

문제 해설 #

Idea #

Dynamic Programming
자리를 옮길 수 있는 연속되는 좌석의 수는 피보나치 수열을 따름 (S[i] = F[i+1])
VIP 좌석 번호를 기준으로 연속되는 좌석의 수를 리스트로 저장
모든 연속되는 좌석 수에 대한 피보나치 수를 곱하고 출력

Sequence #

S2 (1,2) -> (1,2), (2,1) = 2(F3)
S3 (1,2,3) -> (1,2,3), (2,1,3), (1,3,2) = 3(F4)
S4 (1,2,3,4) -> (1,2,3,4), (2,1,3,4), (1,2,4,3), (1,3,2,4), (2,1,4,3) = 5(F5)
S5 (1,2,3,4,5) -> (1,2,3,4,5), (1,2,4,3,5), (1,2,3,5,4), (2,1,3,4,5), (2,1,4,3,5), (2,1,3,5,4), (1,3,2,4,5), (1,3,2,5,4) = 8(F6)
S6 (1,2,3,4,5,6) -> (1,2,3,4,5,6), (1,2,4,3,5,6), (1,2,3,5,4,6), (1,2,3,4,6,5), (1,2,4,3,6,5), …

[백준 18352] 특정 거리의 도시 찾기 (Python)

August 10, 2022

Algorithm, Baekjoon

Algorithm, Problem Solving, 백준, 백준 실버, Python, BFS

문제 링크 #

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

문제 해설 #

Idea #

BFS
시작 노드 X부터 연결된 노드를 순차적으로 방문하면서 X로부터 떨어진 거리를 기록
거리가 K와 같은 노드를 출력하고, 해당하는 노드가 없을 경우 -1을 출력
거리가 K를 넘어가지 않는 노드에 대해서만 탐색하여 시간 단축

Time Complexity #

BFS: O(N+M) = 1,300,000

Data Size #

N: 2 <= int <= 300,000
M: 1 <= int <= 1,000,000
K: 1 <= int <= 300,000
X: 1 <= int <= N
A, B: 1 <= int <= N

해설 코드 #

python

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

N, M, K, X = map(int, input().split())
nodes = [[] for _ in range(N+1)]
visited = [False] * (N+1)
dists = [0] * (N+1)

for _ in range(M):
    A, B = map(int, input().split())
    nodes[A].append(B)

queue = deque()
queue.append(X)
visited[X] = True

while queue:
    city = queue.popleft()

    for next in nodes[city]:
        if not visited[next] and dists[city] < K:
            queue.append(next)
            visited[next] = True
            dists[next] = dists[city]+1

targets = [i for i,d in enumerate(dists) if d==K]
if targets:
    for target in targets:
        print(target)
else:
    print(-1)

[백준 1495] 기타리스트 (Python)

August 10, 2022

Algorithm, Baekjoon

Algorithm, Problem Solving, 백준, 백준 실버, Python, DP

문제 링크 #

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

문제 해설 #

Idea #

Dynamic Programming
P[i] = max(P[i-1]+V[i-1],P[i-1]-V[i-1]), 0 <= P[i] <= M
모든 P[i-1]가 P[i+1]에 영향을 줄 수 있기 때문에 범위 내 모든 값을 집합에 저장
마지막 곡에 대한 P가 존재할 경우 최댓값을 출력하고, 없을 경우 -1을 출력

Time Complexity #

DP: O(NM) = 50,000

Data Size #

N: 1 <= int <= 50
M: 1 <= int <= 1,000
S: 0 <= int <= M
V: int * N

해설 코드 #

python

N, S, M = map(int, input().split())
V = list(map(int, input().split()))

P = [set() for _ in range(N+1)]
P[0] = {S,}

for i in range(1,N+1):
    for j in P[i-1]:
        if j+V[i-1] <= M:
            P[i].add(j+V[i-1])
        if j-V[i-1] >= 0:
            P[i].add(j-V[i-1])

if P[-1]:
    print(max(P[-1]))
else:
    print(-1)

[백준 2805] 나무 자르기 (PyPy3)

March 25, 2022

Algorithm, Baekjoon

Algorithm, Problem Solving, 백준, 백준 실버, Python, Binary Search

문제 링크 #

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

개요 #

이분 탐색으로 해결할 수 있는 문제이다.
Python3을 사용하면 시간초과가 발생하므로 PyPy3를 사용한다.

문제 조건 #

일정 높이에 대해 모든 나무를 잘랐을 때, 조건을 만족하는 절단기의 최대 높이(H)를 구하는 문제이다.
잘린 나무의 길이의 합은 상근이가 필요로 하는 나무의 길이(M)보다 크거나 같아야 한다.

문제 해설 #

나무의 수(N)의 최댓값이 1,000,000이므로 모든 범위에 대해 반복하는 순차 탐색을 이용할 경우 시간초과가 발생한다.
시간 복잡도가 O(log n)인 이분 탐색을 이용하면 시간 복잡도가 O(n)인 순차 탐색을 쓰는 것보다 훨씬 빠르다.
이분 탐색은 중간값(md)을 기준으로 시작하여 조건에 따라
최대/최솟값의 포인터(mx/mn)를 조정하는 탐색 알고리즘이다.
잘린 나무의 길이의 합(total)을 구할 때 잘리지 않은 나무에 대한 음수값을 포함하지 않도록 주의한다.
조건을 만족할 경우 최솟값(mn)을 중간값(md)보다 크게 맞추며,
반대의 경우 최댓값(mx)을 중간값(md)보다 작게 조정한다.
이분 탐색을 마치면 최댓값(mx)에 조건을 만족하는 최대 높이(H)의 값이 남게 된다.

시간 복잡도 #

시간 복잡도가 O(log N)인 이분 탐색의 매 반복마다 시간 복잡도가 O(n)인 for문을 실행하므로
시간 복잡도는 O(N log N) 이상이 된다.
N의 최댓값 1,000,000에 대해 20,000,000번이 넘는 연산이 실행되므로 Python3으로는 시간 제한 1초를 초과한다.
PyPy3에 대한 이해가 깊은 편이 아니라 자세한 설명은 어렵지만,
메모리를 더 사용하는 대신 코드를 캐싱하는 PyPy3를 사용하면 시간 제한 안에 해결할 수 있다.

해설 코드 #

python

N, M = map(int, input().split())
trees = list(map(int, input().split()))
mn, md, mx = 0, 0, max(trees)

while mn <= mx:
    md = (mx + mn) // 2
    total = 0
    for tree in trees:
        total += tree - md if tree > md else 0

    if total >= M:
        mn = md + 1
    else:
        mx = md - 1
print(mx)

[백준 11650] 좌표 정렬하기 (Python)

March 23, 2022

Algorithm, Baekjoon

Algorithm, Problem Solving, 백준, 백준 실버, Python, Sorting

문제 링크 #

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

개요 #

배열 형태의 자료들을 정렬하는 간단한 문제이다.
파이썬에서는 내장 함수 sort()를 사용하면 쉽게 풀 수 있다.

문제 해설 #

문제에서 요구하는 것은 x좌표 값과 y좌표 값으로 구성된 배열들의 리스트를 x 값, y 값 순으로 정렬하는 것이다.
배열의 자료구조는 인덱싱으로 접근이 가능한 것이면 아무거나 상관없기에 좌표 표현에 직관적인 튜플을 사용한다.
정렬의 기준이 반대였으면 람다 식을 써야겠지만 좌표의 위치가 곧 정렬 순서이기 때문에 Key값은 사용하지 않는다.

해설 코드 #

python

import sys

input = sys.stdin.readline
points = []

for _ in range(int(input())):
    points.append(tuple(map(int, input().split())))

for point in sorted(points):
    print(point[0], point[1])

[백준 4949] 균형잡힌 세상 (Python)

March 22, 2022

Algorithm, Baekjoon

Algorithm, Problem Solving, 백준, 백준 실버, Python, Stack

문제 링크 #

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

개요 #

스택을 이용하여 풀 수 있는 문제이다.
문자열 처리에 관한 능력이 추가로 요구된다.
최대 입력 크기가 정해지지 않았기에 시간 복잡도는 무시한다.

문제 해설 #

해당 문제에서 고려해야할 문자는 종료 조건인 점(’.’)을 제외하면 소괄호와 대괄호 뿐이다.
균형잡힌 문장의 구분 여부는 1. 닫힌 괄호가 열린 괄호보다 앞에 나온 경우 2. 열린 괄호가 안 닫힌 경우로 판단했다.
문자 하나하나마다 확인하며 괄호를 골라낼 수도 있지만 이번엔 정규식을 사용해본다.
우선 정규식 라이브러리인 re에 속한 sub 메서드를 사용해 괄호를 제외한 모든 문자를 제거한다.
나머지 문자에 대해 for문을 돌려 열린 괄호면 스택에 추가, 닫힌 괄호면 스택에 남은 값을 뺀다.
단, 닫힌 괄호의 경우 스택에 열린 괄호가 없거나 스택 맨 위의 값이 다른 종류의 괄호면 균형이 깨졌다 판단한다.
코드의 중복을 발생시키지 않기 위해 균형이 깨진 경우를 IndexError의 발생으로 통일하고
이 때 조건 변수를 재설정하고 반복문을 중지시킨다.
반복문이 종료된 후 스택과 조건 변수에 대한 NAND 결과를 통해 균형잡힌 문장의 여부를 판단하여 결과를 출력한다.

해설 코드 #

python

import re

match = {')': '(', ']': '['}

while True:
    balanced_stack = []
    unbalanced = False
    sentence = input()
    if sentence == '.':
        break

    sentence = re.sub('[^\(\)\[\]]+', '', sentence)
    for bracket in sentence:
        if bracket in {'(', '['}:
            balanced_stack.append(bracket)
        else:
            try:
                if balanced_stack[-1] == match[bracket]:
                    balanced_stack.pop()
                else:
                    raise IndexError
            except IndexError:
                unbalanced = True
                break
    
    if not(balanced_stack or unbalanced):
        print('yes')
    else:
        print('no')