DFS/BFS 유형문제로 나는 BFS를 사용하여 풀어보았다. BFS구현을 위해 deque를 사용하였다. 처음에는 입출력이 이해가 되질 않았다. 왜 "dot"을 거치는지 이해가 되질 않았는데 (사실 아직도 이해되지않는다..) 다른 블로그들을 참고하여, 문제를 풀기위한 방법으로 이해한 것은 한 번에 "한 개의 알파벳만 바꿀 수 있다" = "한개씩만 바꿀 수 있는경우 바꿔야한다." 라고 이해했다. 그리고 이 조건은 check 함수를 만들어서 조건으로 확인하였다. queue에 들어가는 값은 단어와 변환횟수(cnt)를 담았고, 결국 target과 start가 일치 할 때, 현재 cnt에 + 1 을 반환하였다. from collections import deque def check(word, target): cnt..
BFS를 활용하여 문제를 풀어보았다. 다른 문제를 풀 때, 거리가 필요하다면 거리정보를 담는 리스트를 따로 만들었을텐데, 이번에는 굳이 만들 필요가 없을 것이라고 생각했고, visited에 갱신된 적이 없을 경우, 1씩 더해가는 방법으로 답을 구했다. from collections import deque def solution(n, edge): graph = [[] for _ in range(n+1)] # 방문 및 거리 갱신 visited = [0] * (n+1) # 그래프 갱신 for a, b in edge: graph[a].append(b) graph[b].append(a) visited[1] = 1 queue = deque([1]) while queue: now = queue.popleft() fo..
나는 제한사항의 n과, 경기 결과 수가 많지 않은것을보고 모든 경우를 확인해보기로 하였다. 모든 경우의 수를 확인할 때에는, 중복을 피하기 위해 set을 사용하였고, 데이터 취합에는 dict를 사용하였다. 이번 문제에서 내게 문제였던 부분은, a와 b의 경기에서 a가 이기면 b가 이긴 사람은 모두 a가 이긴다는 것 그리고 a가 진사람은 b도 모두 진다는 것이였다. 생각은 했는데, 이게 코드로 작성이 안되더라.. 공책에 적어가면서 정리하니 풀 수 있었다. from collections import defaultdict def solution(n, results): answer = 0 game_win = defaultdict(set) game_lose = defaultdict(set) for win, los..
나는 먼저, 문제 풀이를 하는데 필요한 조건을 생각해보았다. 각 원소의 합이 S가 존재하지 않는 경우 어떻게하면 값이 최대가 되는지 def solution(n, s): answer = [] if n > s: return [-1] a, b = divmod(s, n) answer = [a] * n for i in range(b): answer[i] += 1 return sorted(answer) 첫번째 경우는 n이 s보다 커질 경우 최고의 집합이 존재 할 수 없었다. 두번째 경우는 어떻게하면 최대가 될까를 생각해 보았는데, s를 표현한 n개의 숫자 값들의 차이가 적을 때(어디에 치우치지않을 때), 그 값들의 곱이 가장 크게 나왔다. 그리하여 값이 중심에 올 방법을 생각한 것이 몫 이였다. 나머지가 발생할 경..
