문제 링크https://www.acmicpc.net/problem/1916 TIL다익스트라에서 최소 거리 계산할 때, 배열 사용 !!특히, 시작점을 기준으로 다익스트라 실행 (아래 코드처럼)시작점은 무조건 dist = 0으로 초기화하고, 거기서부터 순회 시작 !!! Codefrom collections import defaultdictimport heapqimport sysinput = sys.stdin.readlineN = int(input())M = int(input())routes = defaultdict(list)for i in range(M): s, e, c = map(int, input().split()) routes[s].append((e,c))S, E = map(int,..
문제 링크https://www.acmicpc.net/problem/1261 TIL조건에 따라 업데이트되는 dist가 다를 수도 있음이럴 경우 분기해서 처리해야 함항상 heappush 하기 전에 해당 dijk 먼저 업데이트하기 !! Codeimport heapqimport sysinput = sys.stdin.readlineM, N = map(int, input().split())graph = [list(map(int, list(input().strip()))) for _ in range(N)]dir = [(0,1), (1,0), (0,-1), (-1,0)]dijk = [[int(1e9)]*M for _ in range(N)]dijk[0][0] = 0q = [(dijk[0][0], 0, 0)] # ..
문제 링크https://www.acmicpc.net/problem/1504 TIL다익스트라 로직heappush 사용 !!! 중요 조건: 그래프는 양방향, 가중치는 양수양방향이면 그래프 업데이트하는 거 필수 !!! 처음 노드의 cost도 업데이트 필수불필요한 연산을 줄이기 위해 continue 필수 (방문 체크 겸) 현재 노드의 거리가 기존 값보다 더 크면 볼 필요없음 if dist > cost[node]: continue다음 노드를 기준으로 heappush 함 !!!! for next_node, next_cost in graph[node]: new_cost = dist + next_cost if cost[next_no..
문제 링크 https://www.acmicpc.net/problem/14888 TILcur *= -1 , cur //= numbers[n] , cur *= -1 >> 결국 음수 신경안쓰고 나누겠다는 의미int(cur//numbers[n]) 하는 거랑 동일 !!!!!!! 암기하기 Code import syssys.setrecursionlimit(10**5)input = sys.stdin.readlineN = int(input())numbers = list(map(int, input().split()))plus, minus, times, divide = map(int, input().split())operators = {"+":plus, "-":minus, "*":times, "/":divide..
(( 한 번 더 풀기 !!!!!!!!!!!!!!!!!!!! 무조건 )) 문제 링크https://www.acmicpc.net/problem/14889 백트래킹을 사용해서 풀 수 있는 문제라고 분류되어 있지만, 안써도 충분히 풀림그치만 백트래킹 풀이와 조합 풀이 둘 다 해보기 !! (itertools 사용 못 할 수도 있으니) TIL처음에 조합론을 생각함그치만 backtrack을 공부하고 있었기에 혹시 가능할까 싶어 풀어봄 ..결론은 조합론 + 백트래킹 or 조합론 정도가 적당할듯주어진 원소의 후보군을 다룰 땐, 원소 자체를 판별하는 것이 좋음 (격자 이런거 만들지 말고)반복되는 기능을 함수로 따로 뺄 때는 꼭 초기화 주의 !!!! [ 처음 코드 ] - 이미 팀에 들어간 사람을 고려하지 않아서 중복 문..
(( 한 번 더 풀기 & 외우기 )) 문제 링크https://www.acmicpc.net/problem/1182 TIL1차적으로 완전탐색 생각완전 탐색에서 가장 먼저 확인할 것 -> 시간제한 - N의 범위 통해서 확인 가능완전 탐색과 연관된 알고리즘 - 백트래킹 !!혹시나 가지치기가 되는지, 했다-안했다(선택, 미선택)로 선택가능한지가 중요 !! >> 백트래킹 해당 원소를 선택 (idx번째 현재 원소) / 해당 원소를 미선택 (idx번째 현재 원소)backtrack은 항상 base 조건 있어야 함 !!크기가 양수인 부분수열 중 !!!!! > 주의 Codeimport syssys.setrecursionlimit(10**6) input = sys.stdin.readline # 1차적으로 완전탐색..
