yeony's story

문제 이해를 못해서 한참 헤맸던 문제 ㅠ..ㅠ 부피가 A,B,C 리터인 물통 3개가 있다. 처음에는 C 리터인 물통만 가득 채워져있다. 물을 옮길땐 조건이 있다. 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 사실 위 문장을 제대로 파악하지 않고 넘어가서 정말 헤맸던 문제다. 예시를 들어서 설명해보면 8,9,10 리터인 물통 3개가 있다고 가정한다. C물통에서 A물통으로 물을 옮기려면 A물통을 가득채우거나 또는 C물통이 빌때까지 부어야하는데 A물통이 C물통보다 용량이 작으므로 이때는 C물통에서 A물통으로 8리터를 옮긴다. 그러면 C리터에는 2리터의 물만이 남게 된다. 만약 B물통에 5리터, C 3리터가 남아있다고 가정한다. B물통를 가득채우려면 4리터가 필요하다. 그러나 C물통..

 dfs, bfs 두 방식 모두 풀 수 있었던 문제! 처음엔 dfs를 총 2번 돌려서 촌수를 더하는 방식으로 계산하려고 했으나 너무 비효율적인 것 같아서 패쓰.. 이 촌수 그래프는 무방향 그래프이니까 array[자식]=부모 array[부모]=자식 이런식으로 양쪽의 값을 각각 넣어줘야한다. import sys sys.setrecursionlimit(300000) n=int(input()) yeon,kim=map(int,input().split()) m=int(input()) array=[[] for _ in range(n+1)] visited=[0 for _ in range(n+1)] for _ in range(m): p,c=map(int,input().split()) array[p].append(c) ..

오랜만에 bfs 문제를 접했다..! 역시나 오늘도 헤맸다 !.! 문제 해석하기 1 4 2 2 1 (시작점 idx 2 ) 2 -> 왼쪽 1 o -> 오른쪽 4 o -> x -> 오른쪽 1 o -> 왼쪽 2 o -> 왼쪽 4 o o의 개수 = 5개 from collections import deque n = int(input()) array = list(map(int, input().split())) start = int(input()) - 1 visited = [0] * n result = 0 def bfs(start): # start=idx global result queue = deque() queue.append(start) visited[start] = 1 result+=1 while queue: ..

(처음 든 생각) BFS 같다.. 느낌이 1번 도시에서 2번, 3번 도시를 가야하고? 2번 도시에서 갈 수 있는 곳이 있는지, 조건을 부합하는 지 확인한 뒤 3번 도시도 확인해야 하니까!! (처음 푼 풀이) : BFS 처음에 이 문제도 EOFError를 사용해야 하는 줄 알고 좀 헤맸다. 문제 좀 잘 읽어볼 것.. BFS 알고리즘이니까, 큐를 이용해서 풀어야한다. 위 예제를 생각해보면, k=2 이다. (거리정보) 1번 도시에서 갈 수 있는 도시는 2번, 3번 따라서 큐에 2번, 3번을 넣고 방문처리를 해준다. 이때 방문처리 리스트를 통해 답을 구할 것이다. 처음엔 set()을 이용했는데, 시간초과가 떠서 ㅠㅠ popleft로 큐에서 데이터를 꺼내온다. (2번) 2번에서 갈 수 있는 도시는 3번, 4번 하..

1. 스택과 큐 (1) 스택 - 후입선출 - 삽입은 append(n) , 삭제는 pop() (2) 큐 - 선입선출 - 파이썬에선 큐 구현을 위해 deque 라이브러리를 사용한다. - 삽입 append(n), 삭제 popleft() - queue 라이브러리 대신 deque 라이브러리를 사용하는 이유? (from collections import deque) >> deque는 스택과 큐의 장점을 모두 채택한 것이라서 데이터를 넣고 빼는 속도가 훨씬 빠르기 때문! >> 코테에서는 collections 모듈과 같은 기본 라이브러리 사용을 허용함 : 코테 라이브러리에 대한 내용이 자세히 잘 나와있어서 주소 첨부! https://velog.io/@koyo/python-docs-6 [내가 보려고 적는 파이썬] 주요 ..