어디까지 갈 수 있을까?

목적 시작노드에서 각 노드까지 최단거리를 구하는 알고리즘 O(ElogV)의 시간 복잡도를 갖는다 우선순위 큐로 거리가 짧은 노드를 우선적으로 탐색한다 BFS는 가중치가 같은(없는) 그래프에서, 다익스트라는 가중치가 서로 다른 그래프에서 사용한다 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 import heapq import sys input = sys.stdin.readline INF = int(1e9) n, m = map(int, input().split()) start=int(input()) graph = [[] for i in range(n + 1)] ..

문제링크 https://programmers.co.kr/learn/courses/30/lessons/43164 [답코드] def dfs(cand, visit, target): global n, answer if len(visit) == n: answer.append(visit+[target]) return for i, v in enumerate(cand): if v[0] == target: dfs(cand[:i] + cand[i + 1:], visit + [v[0]], v[1]) def solution(tickets): global n, answer n = len(tickets) answer = [] for i, v in enumerate(tickets): if v[0] == "ICN": dfs(tick..

문제링크 programmers.co.kr/learn/courses/30/lessons/42579 1. sort() 활용 잘하기, -붙이면 reverse=True 와 같은 역할 함 [답코드] def solution(genres, plays): answer = [i for i in range(len(genres))] dict = {} for i in range(len(genres)): if genres[i] not in dict: dict[genres[i]] = plays[i] else: dict[genres[i]] += plays[i] answer.sort(key=lambda x: (-dict[genres[x]], -plays[x], x)) genre_dict = {} ret=[] for j in answ..

문제링크 programmers.co.kr/learn/courses/30/lessons/42890 [정리] 1. 전치행렬 만들기 list(map(list, zip(*relation))) 2. append는 ()안 요소 전체를 추가 하지만 extned는 ()안 요소 하나하나를 접근해 배열에 추가 3. set()으로 만들 값은 변형 불가능한 값이어야 하기 때문에 원소들을 tuple로 변형시킨다 4. 최소성 만족을 위해 set(j).issubset(i) ex) j=[1,2,2] i=[1,2,3] 일 때도 = (하위집합 j에 중복되는 원소가 있을 때도) 상위집합의 부분집합으로 인정하기 위해 set(j)를 붙여주는 걸로 추정 [답코드] from itertools import combinations def solut..

문제링크 programmers.co.kr/learn/courses/30/lessons/17679 1. 전치행렬을 만들어주기 위해 list(map(list, zip(*board))) 1-1. list를 unpacking 하기 위해 * 1-2. zip()은 tuple을 반환하는데 tuple은 값 변경이 안 되니 list로 바꿔줌 1-3. map()은 주소값을 반환하기 때문에 list()로 묶어줌 2. 중복되는 원소를 넣지 않기 위해 set() / set.add() [답코드] import copy def solution(m, n, board): answer = 0 board = list(map(list, zip(*board))) #*는 리스트를 unpacking 한다 while True: remove=set(..

문제링크 programmers.co.kr/learn/courses/30/lessons/17684 [답코드] def solution(msg): answer = [] dict={} for i in range(0, 26): dict[chr(ord('A')+i)]=i+1 i, num=0, 27 w='' while i

문제링크 programmers.co.kr/learn/courses/30/lessons/17683 [답코드] def change(note): note=note.replace('C#','c') note=note.replace('D#','d') note=note.replace('F#','f') note=note.replace('G#','g') note=note.replace('A#','a') return note def solution(m, musicinfos): arr=[] #[제목, 음표] m=change(m) for mm in musicinfos: start, end, title, sound=mm.split(',') sound=change(sound) start_hour, start_min, end_ho..

문제링크 programmers.co.kr/learn/courses/30/lessons/42578 [답코드] def solution(clothes): answer = 1 dict={} for c in clothes: if c[1] not in dict: dict[c[1]]=1 else: dict[c[1]]+=1 for k, v in dict.items(): answer*=(v+1) return answer-1 [풀이법] 해당 예시에서 생성되는 dict는 {'headgear': 2, 'eyewear': 1} 이다. 여기서 headgear를 안 쓰는 경우, 1번 headgear를 쓰는 경우, 2번 headger를 쓰는 경우 3가지가 있다 eyewear를 안 쓰는 경우, 1번 eyewear를 쓰는 경우 2가지가..