import sys
input = sys.stdin.readline

value2id = {-1:0,0:1,1:2}

# ============== 1안 (시간초과) =============

from itertools import chain
mat_slice = lambda mat,r1,r2,c1,c2: list(map(lambda x: x[c1:c2], mat[r1:r2]))

def nona_comp(n, arr, answer):
    values = set(chain.from_iterable(arr))
    if len(values) == 1:
        answer[value2id[values.pop()]] += 1
        return
    div = n//3
    for i in range(3):
        for j in range(3):
            nona_comp(div, mat_slice(arr,div*i,div*(i+1),div*j,div*(j+1)), answer)

# =============== 2안 (통과) ===============

def nona_comp(n, arr, r, c, answer):
    start = arr[r][c]
    for row in range(r,r+n):
        for col in range(c,c+n):
            if arr[row][col] != start:
                div = n//3
                for i in range(3):
                    for j in range(3):
                        nona_comp(div, arr, r+div*i, c+div*j, answer)
                return
    answer[value2id[start]] += 1

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
answer = [0, 0, 0]
nona_comp(len(arr), arr, 0, 0, answer)

for num in answer:
    print(num)

[백준 1182] 부분수열의 합 (Python)

August 18, 2022

Algorithm, Baekjoon

Algorithm, Problem Solving, 백준, 백준 실버, Python, Brute Force

문제 링크 #

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

문제 해설 #

Idea #

Brute Force
전체 배열에서 1부터 N개의 부분 조합을 완전탐색하면서 합이 S와 같은 경우를 카운트하고 출력

Data Size #

N: 1 <= int <= 20
S: abs(int) <= 1,000,000
arr: int(100,000) * N

해설 코드 #

python

from itertools import combinations

N, S = map(int, input().split())
arr = list(map(int, input().split()))
count = 0

for i in range(1,N+1):
    comb = combinations(arr, i)
    count += sum(map(lambda x: sum(x)==S, comb))

print(count)

[백준 11725] 트리의 부모 찾기 (Python)

August 18, 2022

Algorithm, Baekjoon

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

문제 링크 #

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

문제 해설 #

Idea #

BFS
1번 노드부터 BFS를 수행하면서 다음 노드에 순차적으로 접근
다음 노드가 이미 방문한 노드의 경우 부모 노드라 판단하여 배열에 저장
부모 노드가 저장된 배열에 대해 2번 노드부터 순차적으로 부모 노드를 출력

Time Complexity #

O(N+E) = 200,000

Data Size #

N: 2 <= int <= 100,000

해설 코드 #

python

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

N = int(input())
graph = [[] for _ in range(N+1)]
visited = [False] * (N+1)
parents = [1] * (N+1)

for _ in range(N-1):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

queue = deque([1])
visited[1] = True
while queue:
    node = queue.popleft()
    for next in graph[node]:
        if not visited[next]:
            queue.append(next)
            visited[next] = True
        else:
            parents[node] = next

for parent in parents[2:]:
    print(parent)

[백준 1676] 팩토리얼 0의 개수 (Python)

August 16, 2022

Algorithm, Baekjoon

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

문제 링크 #

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

문제 해설 #

Idea #

Math
팩토리얼 수를 구하고 문자열로 변환해 연속되는 0의 개수를 출력

Data Size #

N: 0 <= int <= 500

해설 코드 #

python

from math import factorial
import re

N = int(input())
zeros = re.findall('0+', str(factorial(N)))
if zeros:
    print(len(zeros[-1]))
else:
    print(0)

[백준 1541] 잃어버린 괄호 (Python)

August 16, 2022

Algorithm, Baekjoon

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

문제 링크 #

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

문제 해설 #

Idea #

Greedy
최솟값을 만들기 위해서는 ‘-‘를 기준으로 괄호를 치는 것이 최선
‘-‘를 기준으로 식을 나누고 구분된 식을 계산하여 결과를 출력

Data Size #

arr: str(50)

해설 코드 #

python

arr = input().split('-')
answer = sum(map(int,arr[0].split('+')))
for i in arr[1:]:
  answer -= sum(map(int,i.split('+')))
print(answer)

[백준 1389] 케빈 베이컨의 6단계 법칙 (Python)

August 16, 2022

Algorithm, Baekjoon

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

문제 링크 #

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

문제 해설 #

Idea #

BFS
1부터 N까지의 번호에 대해 매번 BFS를 수행하면서 다른 모든 노드와의 거리를 파악
가장 작은 거리의 합을 가진 노드의 인덱스 번호를 출력

Time Complexity #

O(N^2+NM) = 510,000

Data Size #

N: 2 <= int <= 100
M: 1 <= int <= 5,000

해설 코드 #

python

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

def bfs(target, nodes):
    num = [0] * (N+1)
    queue = deque([target])
    visited = [False] * (N+1)
    visited[target] = True

    while queue:
        node = queue.popleft()
        for next in nodes[node]:
            if not visited[next]:
                num[next] = num[node]+1
                visited[next] = True
                queue.append(next)
    return sum(num)

N, M = map(int, input().split())
rels = [list() for _ in range(N+1)]
kevin = [0] * (N+1)

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

for i in range(1,N+1):
    kevin[i] = bfs(i, rels)

print(kevin.index(min(kevin[1:])))

[백준 5430] AC (Python)

August 15, 2022

Algorithm, Baekjoon

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

문제 링크 #

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

문제 해설 #

Idea #

Implementation, Deque
문제에서 주어진대로 매번 배열을 뒤집으면 O(N^2)의 시간 복잡도로 시간 초과가 발생
배열에 영향을 주지 않으면서 R 함수를 처리하기 위해 상태 변수를 정의하고,
D 함수가 호출될 경우 배열의 상태에 따라 첫 번째 수를 버릴지 마지막 수를 버릴지 결정
마지막에 배열의 상태를 업데이트하고 정해진 형태로 결과를 출력

Time Complexity #

O(N) = 100,000

Data Size #

T: 1 <= int <= 100
p: 1 <= int <= 100,000
n: 1 <= int <= 100,000
arr: int(100) * n (like [x_1,…,x_n])

해설 코드 #

python

from collections import deque

for _ in range(int(input())):
    p = input()
    n = int(input())
    arr = deque(eval(input()))
    forward = True

    try:
        for cmd in p:
            if cmd == 'R':
                forward = not forward
            elif cmd == 'D':
                if forward:
                    arr.popleft()
                else:
                    arr.pop()
        arr = map(str,arr) if forward else map(str,reversed(arr))
        print(f'[{",".join(map(str,arr))}]')
    except IndexError:
        print('error')

[백준 1463] 1로 만들기 (Python)

August 15, 2022

Algorithm, Baekjoon

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

문제 링크 #

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

문제 해설 #

Idea #

Dynamic Programming
N에 대해 조건을 만족하는 경우에서 3으로 나누기, 2로 나누기, 1을 빼는 연산을 반복 수행하고
각각의 연산횟수 별로 도출할 수 있는 값을 모두 저장
앞선 결과를 모두 활용해 다음 결과에 대한 모든 경우를 탐색하고 결과 집합에 1이 있을 시 탐색을 종료
1이 포함된 마지막 집합의 인덱스 번호를 최소 연산횟수로 출력

Data Size #

N: 1 <= int <= 10^6

해설 코드 #

python

N = int(input())
dp = [{N,}]
while 1 not in dp[-1]:
    dp.append(set())
    for n in dp[-2]:
        if n % 3 == 0:
            dp[-1].add(n//3)
        if n % 2 == 0:
            dp[-1].add(n//2)
        dp[-1].add(n-1)
print(len(dp)-1)

[백준 1697] 숨바꼭질 (Python)

August 15, 2022

Algorithm, Baekjoon

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

문제 링크 #

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

문제 해설 #

Idea #

BFS
N에서 시작해 K에 도달할 때까지 x-1, x+1, x*2에 대한 최단거리를 탐색
두 점이 위치할 수 있는 범위 내에서 가까운 거리의 점부터 탐색을 수행 K에 대한 거리를 출력
N이 K보다 클 경우 x-1 외에는 이동수단이 없기 때문에 시간 단축을 위해 예외로 처리

Time Complexity #

O(N) = 100,000

Data Size #

N: 0 <= int <= 100,000
K: 0 <= int <= 100,000

해설 코드 #

python

from collections import deque

def bfs(start, target):
    MAX = 10**5
    count = [0] * (MAX+1)
    queue = deque([start])

    while queue:
        x = queue.popleft()
        if x == target:
            return count[x]
        for nx in (x-1,x+1,x*2):
            if 0 <= nx <= MAX and not count[nx]:
                count[nx] = count[x] + 1
                queue.append(nx)

N, K = map(int, input().split())

if N >= K:
    print(N - K)
else:
    print(bfs(N, K))

[백준 20922] 겹치는 건 싫어 (Python)

August 15, 2022

Algorithm, Baekjoon

Algorithm, Problem Solving, 백준, 백준 실버, Python, Two Pointer

문제 링크 #

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

문제 해설 #

Idea #

Two Pointer
수열의 시작과 끝 지점에 대한 두 개의 포인터 지정
끝 지점에 대한 포인터를 확장하면서 탐색되는 원소의 수를 카운트
원소의 수가 K개와 같아지는 시점부터 시작 지점에 대한 포인터를 확장하여 범위 축소
최종적으로 두 포인터 간 거리의 최대치를 출력

Time Complexity #

O(N) = 200,000

Data Size #

N: 1 <= int <= 200,000
K: 1 <= int <= 100
a: int(100,000) * N

해설 코드 #

python

N, K = map(int, input().split())
a = list(map(int, input().split()))
answer = 0
start, end = 0, 0
counter = [0] * (max(a)+1)

while end < N:
    if counter[a[end]] < K:
        counter[a[end]] += 1
        end += 1
    else:
        counter[a[start]] -= 1
        start += 1
    answer = max(end-start, answer)

print(answer)