문제 링크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차적으로 완전탐색..
(( 시간 효율 지키면서 서브트리 구별하는 방법 외우기 )) 문제 링크https://www.acmicpc.net/problem/15681 TIL2 ≤ N ≤ 100,000 , 1 ≤ R ≤ N, 1 ≤ Q ≤ 100,000이렇게 입력이 10만을 초과하는 경우 무조건 sys.stdin으로 input 받기 !!!!!!!그냥 input()으로 받으면 100% 시간 초과 발생 [ 처음 코드 ] - 시간 초과from collections import deque, defaultdictN, R, Q = map(int, input().split())# Level Tree 만들기dd = defaultdict(list)level = [-1]*(N+1)level[R] = 0for i in range(N-1): u..
