[WEEK04] DAY26 & TMI

1939 중량제한

코드

import sys
from collections import deque

# 최대 중량 찾기
# 최소, 최대에서 가능한 이분탐색
# bfs에서 중간값을 기준으로 
    

n,m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]

for _ in range(m):
    start, end, weight = map(int, sys.stdin.readline().split())
    graph[start].append([end, weight])
    graph[end].append([start, weight])

start_island, end_island = map(int, sys.stdin.readline().split())

min_weight , max_weight = 1, 10000000000

def bfs(mid_weight): 
    queue = deque()
    queue.append(start_island)
    visited = set()
    visited.add(start_island)

    while queue:
        start = queue.popleft()
        for end, weight in graph[start]:
            if end not in visited and weight >= mid_weight:
                visited.add(end)
                queue.append(end)

    if end_island in visited:
        return True
    else:
        return False

result = min_weight

while min_weight <= max_weight:
    mid_weight = (min_weight + max_weight)//2
    if bfs(mid_weight): 
        result = mid_weight
        min_weight = mid_weight+1
    else:
        max_weight = mid_weight-1

print(result)

DP

.

2746 피보나치 수 2 (DP)

코드

import sys
n = int(sys.stdin.readline())

dp = [0] * (n+1)
dp[1] = 1
for i in range(2, n+1):
    dp[i] = dp[i-2] + dp[i-1]

print(dp[n])

.

1904 01타일 (DP)

코드

import sys
n = int(sys.stdin.readline())
if n == 1:
    print(1)
elif n == 2:
    print(2)

else:
    dp = [0] * 1000001

    dp[0] = 1
    dp[1] = 2
    for i in range(2, n+1):
        dp[i] = (dp[i-1] + dp[i-2]) % 15746

    # result = dp[n-1] % 15746
    print(dp[n-1]%15746)

피보나치 수열 점화식을 이용했고,
처음에 속도가 너무 느리게 떠서 if n == 1일때와 n == 2 일 때를 추가해서 끊어주었다
.

4주차 시작

2021.11.26 FRI

이번 DP문제들은 지난번 11053 가장 긴 증가하는 부분 수열 문제를 응용해서 풀 수 있을 것 같은 문제들이 많은 것 같다

어떻게 응용을 하면 좋을지 낼 각잡고 고민해봐야 할 것 같다 인프런도 보고!

이전에 올렸었던 11053문제 DP 풀이버전 관련 끄적끄적들이다..
여기에 피보나치 수열 이야기가 쓰여있고, 11053 문제 자체도 다시 보면 좋을 것 같다

오늘의 이야기

처음 1, 2주차에는 다른 이과출신 사람들과의 이과적 사고흐름의 속도 차이를 보며
내가 코딩, 컴퓨터 공학 즉 개발이라는 분야를 너무 만만하게 생각한 건 아닐까 하는 생각에 두려웠다
나도 어느정도 논리적사고를 가지고 있다고 생각했는데 이공계를 전공으로 4년간 공부한 사람들과의 생각 차이는 매우 크게 느껴졌다
주어진 알고리즘 문제 속에서 자꾸만 마주치게 되는 수학영역의 장벽이 굉장히 크고 낯설었지만
그럼에도 불구하고 불안감 가질 필요 없다 생각하며 지금까지 우직하게 그냥 했다 나를 믿고
살면서 성취해온 크고 작은 나만의 업적들이 있기에 이번에도 나를 믿을 수 있었다

결론은 하니까 늘고있다
구조가 보이고 문제가 요구하는 사고의 흐름을 인식하기 시작했다
그리고 타인의 새로운 사고흐름을 인지하고 내것으로 만들고 있다
이대로라면 이전에 했던 걱정들은 이제 모두 좀 덜어도 괜찮을 것 같다는 생각이 든다

ㅎㅎ
화이팅