O'bin and the Chocolate Factory

링크>https://www.acmicpc.net/problem/1753  sol1 )  다익스트라 알고리즘으로 최단경로 탐색123456789101112131415161718192021222324252627282930313233343536373839import sysimport heapqinput = sys.stdin.readline def dijkstra(s, dis):    dis[s] = 0    q = []    heapq.heappush(q, (0, s))    while q:        cur_dis, now = heapq.heappop(q)        if cur_dis > dis[now]:            continue        for n, weight in graph[now]:..

링크>https://www.acmicpc.net/problem/1158   sol1 ) deque을 이용한 풀이12345678910111213from collections import deque n, k = map(int, input().split())q1 = deque([i for i in range(1,n+1)])answer = [] for _ in range(n):    for _ in range(k-1):        q1.append(q1.popleft())    answer.append(q1.popleft()) print(',end='')print(*answer, sep=', ', end='>')cs deque를 이용한 직관적 풀이그러나 시간복잡도가 O(N*k)로, k 크기 증가하면 비효율적 ..

링크>https://www.acmicpc.net/problem/5397   sol1 ) stack을 이용한 풀이1234567891011121314151617181920212223import sysinput = sys.stdin.readline t = int(input()) for _ in range(t):    str1 = []    str2 = []    for i in input().rstrip():        if i == '-':            if str1:                str1.pop()        elif i == ':            if str1:                str2.append(str1.pop())        elif i == '>':    ..

링크>https://www.acmicpc.net/problem/13549   sol1 ) 나의 오답 - 메모리 초과1234567891011121314from collections import dequen, k = map(int, input().split())graph = deque([(n, 0)]) while True:    now, time = graph.popleft()        if now == k:        print(time)        break     graph.append((now * 2, time))    graph.append((now + 1, time + 1))    graph.append((now - 1, time + 1))cs 예제는 맞췄지만, 채점 시 메모리 초과 발생 ..

링크>https://www.acmicpc.net/problem/3273    sol 1 ) 배열에 인덱스 저장하고 값 비교해 계산 1234567891011121314n = int(input())arr = list(map(int, input().split()))x = int(input()) arr2 = [0] * 2000000for i in range(n):    arr2[arr[i]] = i cnt = 0for i in range(n):    if arr2[x - arr[i]] > i:        cnt += 1 print(cnt)cs 입력을 arr에 받고, 각 원소를 인덱스로 하는 arr2 배열에 인덱스를 저장했다.정답이었지만, 문제를 잘못 이해한 풀이고,메모리 사용(불필요하게 큰 arr2 배열) 측..

링크>https://www.acmicpc.net/problem/1068   sol ) dfs를 이용한 리프 노드 탐색12345678910111213141516171819202122232425262728293031323334import sysinput = sys.stdin.readline def dfs(node, tree, visited):    visited[node] = True    for i in range(len(tree)):        if tree[i] == node and not visited[i]:            dfs(i, tree, visited) n = int(input())tree = list(map(int, input().split()))del_node = int(input..

링크>https://www.acmicpc.net/problem/1991   sol ) 재귀를 이용한 트리 탐색123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051import sysinput = sys.stdin.readline class Node:    def __init__(self, item, left, right):        self.item = item        self.left = left        self.right = right def pre_order(node):    result.append(node.item)    if node.left != '.':       ..

링크>https://www.acmicpc.net/problem/9372  sol ) DFS로 국가(노드) 탐색하여 비행 횟수 구하기12345678910111213141516171819202122232425import sysinput = sys.stdin.readline def dfs(node, cnt):    visited[node] = True    for n in tree[node]:        if not visited[n]:            cnt = dfs(n, cnt+1)    return cnt t = int(input()) for _ in range(t):    n, m = map(int, input().split())    tree = [[] for _ in range(n+1)]  ..

링크>https://www.acmicpc.net/problem/1926  sol 1 ) deque를 이용한 BFS로 풀이123456789101112131415161718192021222324252627282930313233343536373839404142import sysfrom collections import deque input = sys.stdin.readline dx = [-1, 1, 0, 0]dy = [0, 0, -1, 1] def bfs(x, y):    q = deque([(x, y)])    visited[x][y] = True    size = 1     while q:        x, y = q.popleft()        for i in range(4):            nx..

링크>https://www.acmicpc.net/problem/5525 123456789101112131415161718192021import sysinput = sys.stdin.read N = int(input().strip())M = int(input().strip())S = input().strip() answer, i, count = 0, 0, 0 while i  (M - 2):    if S[i:i+3] == 'IOI':        i += 2        count += 1        if count == N:            answer += 1            count -= 1    else:        i += 1        count = 0 print(answer)cs