2025-02월 Algoirthm

Baekjoon - 벡터 매칭(1007번)

결과적으로는 절반의 노드들은 더하고 절반의 노드들은 뺀 값이 벡터 값의 길이가 되는 것을 파악하는 것이 중요하였음.

N이 20까지 라는 비교적 적은 수였기 때문에 브루트 포스로 찾는 것이 가능한 것을 알아야 하는 문제 

추가적으로 Combination을 itertool이 아닌 직접 구현해 보는 것을 생각해보는 것도 좋은 문제

 

전체코드

import sys
from itertools import combinations
import math
T = int(sys.stdin.readline())

for _ in range(T):
    dot_n = int(sys.stdin.readline())
    node_l = []
    total_x = 0
    total_y = 0
    for _ in range(dot_n):
        x, y = map(int, sys.stdin.readline().split())
        node_l.append([x,y])
        total_x += x
        total_y += y
    cri = int(dot_n/2)

    comb = combinations(range(dot_n), cri)

    result = math.inf
    for cb in comb:
        sum_x = 0
        sum_y = 0
        for idx in cb:
            sum_x += node_l[idx][0]
            sum_y += node_l[idx][1]
        temp_x = total_x-2*sum_x
        temp_y = total_y-2*sum_y

        result = min(result, (temp_x**2+temp_y**2)**0.5)
    print(result)

 

---

Baekjoon - 불 켜기(11967번)

이것도 역시 발상의 전환이 필요한 문제였다...

bfs에서 stack에 데이터를 추가하는 시점이 일반적인 것과 많이 달랐던 문제....

 

전체 코드

import sys 
from collections import deque
N, M = map(int, sys.stdin.readline().split())
on_off_l = {}
for _ in range(M):
	x, y, a, b = map(int, sys.stdin.readline().split())
	if (x,y) not in on_off_l:
		on_off_l[(x,y)] = []
	on_off_l[(x,y)].append((a,b))

s = deque([[1,1]])
enable_in = {(1,1):True}
visited = {}

visited[(1,1)] = True
dx = [0,0,-1,1]
dy = [1,-1,0,0]

while s:
	c_x, c_y = s.popleft()
	
	if (c_x, c_y) in on_off_l:
		for o_x, o_y in on_off_l[(c_x,c_y)]:
			if (o_x, o_y) not in enable_in:
				enable_in[(o_x, o_y)] = True

				for i in range(4):
					n_x = o_x + dx[i]
					n_y = o_y + dy[i]
					if (n_x, n_y) in visited:
						s.append([o_x, o_y])
						visited[(o_x,o_y)] = True
						break
	for i in range(4):
		n_x = c_x + dx[i]
		n_y = c_y + dy[i]
		if 1<= n_x <= N and 1<= n_y <= N:
			if (n_x, n_y) in enable_in and (n_x, n_y) not in visited:
				s.append([n_x, n_y])
				visited[(n_x, n_y)] = True

print(len(enable_in))

 

 

---

Baekjoon - 책 페이지(1019번)

첫 시도에서는 DP와 비슷하게 처리하였고 메모리와 시간 측면에서 비효율적이었다.두번째 시도에서는 각 자릿수에서 0~9가 몇번 등장하는지 카운트 하는 방법을 사용하였다.

현재 자리수에서 0의 숫자를 셀때 처리가 중요하였고 left와 right가 의도와 다르게 현재 자리에서 왼쪽과 오른쪽의 자릿수를 보장하지 않는 경우에 대한 처리가 필요하였다.

 

전체 코드

import sys
from collections import deque
import copy
N = int(sys.stdin.readline())

### 1. 첫번째 접근 방법
# s = deque([])
# for i in range(9):
#     t = [0]*10
#     t[i+1] = 1
#     s.append([i+1, t])
# answer = [0]*10
# while s:
#     t = s.popleft()
#     if t[0] > N:
#         break
#
#     for i in range(10):
#         tt = copy.deepcopy(t[1])
#         tt[i] += 1
#         t_num = int(str(t[0]) + str(i))
#         s.append([t_num, tt])
#         answer[i] += t[1][i]
#
# for i in answer:
#     print(i, end=' ')


### 2. 두번째 접근 방법

num_len = len(str(N))

cur = N
num_cnt = {i:0 for i in range(10)}
for i in range(num_len):
    cur_n = cur % 10

    left = N // (10**(i+1))
    right = N % (10**(i))

    if i == 0:
        for j in range(cur_n+1):
            num_cnt[j] += left + 1
        for j in range(cur_n+1, 10):
            num_cnt[j] += left
        num_cnt[0] -= 1
    elif i == num_len-1:
        for j in range(1, cur_n):
            num_cnt[j] += 10**i
        num_cnt[cur_n] += right + 1
    else:
        if cur_n == 0:
            num_cnt[0] += (left-1)*(10**i) + right + 1
            for j in range(1, 10):
                num_cnt[j] += left *(10**i)
        else:
            for j in range(cur_n):
                num_cnt[j] += (left+1)* (10**i)
            num_cnt[0] -= 10**i
            num_cnt[cur_n] += left*(10**i) + right + 1
            for j in range(cur_n+1, 10):
                num_cnt[j] += left*(10**i)

    cur = cur//10


for i in range(10):
    print(num_cnt[i], end=' ')

 

 

---

Beakjoon - 타일 채우기(2718번)

시간이 오래 걸렸던 문제.... 

풀긴 했지만 아직도 완벽하게 그 흐름이 이해는 되지 않는다... 

dp를 이용하기 위해 특정 상태를 정의하고 그 상태를 계속 추적해 나가는데 특정 상태가 빠짐 없고 중복 없이 셀 수 있는 그 원리에 대해서는 아직 많이 부족한 상태... 

4가지 칸을 이진수로 보고 0~15 까지의 상태를 2진수로 가정 한 후 풀어낸다.

 

전체코드

 

import sys

T = int(sys.stdin.readline())

for _ in range(T):
    N = int(sys.stdin.readline())
    dp = [[0]*5 for _ in range(N+1)]

    dp[1][0] = 1
    if N>=2:
        dp[2][0] = 1
        dp[2][1] = 1
        dp[2][2] = 0
        dp[2][3] = 1
        dp[2][4] = 1
    if N == 1:
        print(1)
    elif N == 2:
        print(5)
    else:
        for i in range(2, len(dp)):
            dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][3] + dp[i-1][4] + dp[i-2][0]
            dp[i][1] = dp[i-1][0] + dp[i-1][4]
            dp[i][2] = dp[i-1][3]
            dp[i][3] = dp[i-1][0]+dp[i-1][2]
            dp[i][4] = dp[i-1][0] + dp[i-1][1]

        print(sum(dp[-1])-dp[-1][2]+dp[-2][0])

 

 

---

Baekjoon - 2048_Easy(12100)

현재 상태를 기록하고 업데이트 하는 특정 변수의 존재가 매우 중요 했던 문제... 그리고 변수들의 수정과 업데이트 시점이 매우 영향이 컸던 문제... 

 

전체 코드

import sys
import copy
N = int(sys.stdin.readline())
board = []

for _ in range(N):
    t = list(map(int, sys.stdin.readline().split()))
    board.append(t)


answer = 0
def move(bd, cnt):
    global answer
    if cnt == 5:
        for i in range(N):
            answer = max(answer, max(bd[i]))
        return
    for k in range(4):
        t_board = copy.deepcopy(bd)
        if k == 0: ## 위로 이동
            for j in range(N):
                cur = 0
                for i in range(1, N):
                    if t_board[i][j] != 0:
                        rec = t_board[i][j]
                        t_board[i][j] = 0
                        if t_board[cur][j] == 0:
                            t_board[cur][j] = rec
                        elif t_board[cur][j] == rec:
                            t_board[cur][j] *=2
                            cur += 1
                        else:
                            cur += 1
                            t_board[cur][j] = rec

        elif k == 1: ## 아래로 이동
            for j in range(N):
                cur = N-1
                for i in range(N-2, -1, -1):
                    if t_board[i][j] != 0:
                        rec = t_board[i][j]
                        t_board[i][j] = 0
                        if t_board[cur][j] == 0:
                            t_board[cur][j] = rec
                        elif t_board[cur][j] == rec:
                            t_board[cur][j] *=2
                            cur-= 1
                        else:
                            cur -=1
                            t_board[cur][j] = rec

        elif k == 2: ## 왼쪽으로 이동
            for i in range(N):
                cur = 0
                for j in range(1, N):
                    if t_board[i][j] != 0:
                        rec = t_board[i][j]
                        t_board[i][j] = 0
                        if t_board[i][cur] == 0:
                            t_board[i][cur] = rec
                        elif t_board[i][cur] == rec:
                            t_board[i][cur] *=2
                            cur += 1
                        else:
                            cur += 1
                            t_board[i][cur] = rec

        elif k == 3:    ## 오른쪽으로 이동
            for i in range(N):
                cur = N-1
                for j in range(N-2, -1, -1):
                    if t_board[i][j] != 0:
                        rec = t_board[i][j]
                        t_board[i][j] = 0
                        if t_board[i][cur] == 0:
                            t_board[i][cur] = rec
                        elif t_board[i][cur] == rec:
                            t_board[i][cur] *=2
                            cur -= 1
                        else:
                            cur -=1
                            t_board[i][cur] = rec

        move(t_board, cnt +1)
move(board, 0)
print(answer)

 

---

Baekjoon - 트리의 순회(2263)

inorder > 중위 순회, preorder > 전위 순회, postorder > 후위 순회

후위 순회의 마지막 원소는 루트 노드이다. 

중위 노드에서 루트 노드를 기반으로 왼쪽 트리와 오른 쪽 트리로 구분할 수 있다. 

왼쪽 트리의 개수로 후위 순회에서 왼쪽 트리에 대한 후위 순회 결과와 오른/쪽 트리에 대한 후위 순회 결과를 얻을 수 있다. 이렇게 분할된 왼쪽 트리와 오른쪽 트리를 다시 함수에 넣어서 최종적으로 전위 순회의 결과를 얻을 수 있다. 

시작과 끝점이 같을 때가 아닌, 시작점이 끝점보다 클때, 종료 조건이 되는 이유와 왼쪽 트리와 오른쪽 트리를 함수에 넣어주기 전에 루트를 출력하면 전위 순회가 되는 이유도 생각해보자.

 

import sys
sys.setrecursionlimit(10**8)
N = int(sys.stdin.readline())
in_order = list(map(int, sys.stdin.readline().split()))
post_order = list(map(int, sys.stdin.readline().split()))

in_value = {in_order[i]: i for i in range(N)}
def make_tree(in_s, in_e, post_s, post_e):
    if in_s > in_e or post_s > post_e:
        return

    root = post_order[post_e]
    root_idx = in_value[root]

    left_n = root_idx - in_s

    print(root, end=' ')
    make_tree(in_s, in_s+left_n-1, post_s, post_s+left_n-1)
    make_tree(in_s+left_n+1, in_e, post_s+left_n, post_e-1)

make_tree(0, N-1, 0, N-1)

---

Baekjoon - DSLR(9019)

12100번 문제와 비슷했지만 더 쉬웠던 문제.

지금까지 숫자의 자리수와 관련하여 str으로 변환후에 다루는 경우가 많았는데 10, 100, 1000 등을 이용하여 모듈러(%)와 목(//) 연산을 사용하는 방법을 사용하였다.

 

전체 코드

import sys
from collections import deque
import math
T = int(sys.stdin.readline())

cnt = 0
for _ in range(T):
    s_n , e_n = map(int, sys.stdin.readline().split())
    s = deque([[s_n, ""]])
    record = {s_n:True}
    answer = ""
    while True:
        t, cmd = s.popleft()
        if t == e_n:
            answer = cmd
            break
        for i in range(4):
            if i == 0:
                cur_t = (t*2)%10000
                c_cmd = "D"
            elif i == 1:
                cur_t = t-1 if t!= 0 else 9999
                c_cmd = "S"
            elif i == 2:
                cur_t = (t%1000)*10 + (t//1000)
                c_cmd = "L"
            elif i == 3:
                cur_t = (t%10)*1000 + (t//10)
                c_cmd = "R"

            if cur_t not in record:
                s.append([cur_t, cmd + c_cmd])
                record[cur_t] = True

    print(answer)

 

---

Baekjoon - 최소값 찾기(11003)

덱(Dequeue) 자료구조를 사용하는 것이 중요했던 문제. 

숫자의 인덱스와 값을 같이 덱에 저장하고 인덱스가 범위를 넘어나면 popleft로 제거해준다. 만약 현재 숫자보다 작은 숫자가 덱에 들어있다면 그 숫자를 제거해준다.

 

전체 코드

import sys 
from collections import deque
N, L = map(int, sys.stdin.readline().split())
a_list = list(map(int, sys.stdin.readline().split()))
dq = deque()
for i in range(N):
    if len(dq) > 0 and dq[0][0] <= i-L:
        dq.popleft()

    while len(dq) > 0 and dq[-1][1] > a_list[i]:
        dq.pop()
    
    dq.append([i, a_list[i]])

    print(dq[0][1], end = " ")

---

Beakjoon - 행성터널(2887)

최소 신장 트리(MST)를 프림 알고리즘을 통해 구하는 문제였다. 

x값의 차이, y값의 차이, z값의 차이중 최소값이 edge의 가중치가 되고 전체 노드 개수가 N개고 가능한 Edge의 개수가 N*(N-1)/2 개여서 Edge의 개수를 정렬을 통해 줄이는 발상이 중요했던 문제.

정렬이 되면 Edge의 개수를 줄일 수 있는 이유는 노드들을 이었을 때, x-y-z값들의 차이중 최소 값이 노드 간의 Edge가 되므로 한 노드에서 다른 노드로 가는 Edge는 x로 정렬했을 때, 인접한 노드이거나 y로 정렬했을 때, 인접한 노드이거나, z로 정렬했을 때 인접하느 노드가 되기 때문이다. 

또한 번외로 프림 알고리즘을 구현할때, cur 플래그를 사용한 방법은 테스트 케이스를 통과하지 못했는데 그 이유에 대해 한번 고찰해 보자.

 

 

전체 코드

import sys
import heapq
import math
import copy

N = int(sys.stdin.readline())
case_x = []
case_y = []
case_z = []

for i in range(N):
    x,y,z = map(int, sys.stdin.readline().split())
    case_x.append([x, i])
    case_y.append([y, i])
    case_z.append([z, i])
    if N == 1:
        print(min(x,y,z))
        sys.exit()

case_x = sorted(case_x, key = lambda x : x[0])
case_y = sorted(case_y, key = lambda x : x[0])
case_z = sorted(case_z, key = lambda x : x[0])
test = [case_x, case_y, case_z]
edges = {i: [] for i in range(N)}
for t in test:
    for i in range(N-1):
        heapq.heappush(edges[t[i][1]], [abs(t[i][0] - t[i + 1][0]), t[i+1][1]])
        heapq.heappush(edges[t[i+1][1]], [abs(t[i][0] - t[i + 1][0]), t[i][1]])
        

answer = 0
hq = edges[0]
visited = {0:True}
heapq.heapify(hq)
while hq:
    dist, node = heapq.heappop(hq)
    if node not in visited:
        visited[node] = True
        answer += dist
        for nn in edges[node]:
            if nn[1] not in visited:
                heapq.heappush(hq, nn)

print(answer)