코드 링크https://www.acmicpc.net/problem/2294 TIL문제에서 요구하는 것이 사용한 동전의 최수 개수이므로 dp도 그걸 기준으로 저장해야됨!!!dp는 tabulation이 더 편하고 생각보다 느리지 않아서 그냥 써도 될 듯 ,,, 항상 edge case랑 변수 범위 생각 하기 !!!!!!!제발 기억해 (dp 최소값 구하는 방법 중 하나)dp[i] = min(dp[i], dp[i-coin]+1) [ 처음에 인덱스 에러난 코드 ]n, k = map(int, input().split())dp = [100001]*(k+1)coins = [int(input()) for _ in range(n)]for c in coins: dp[c] = 1for coin in coins: ..
(( 한 번 더 보기 )) 문제 링크https://www.acmicpc.net/problem/2293 TIL이렇게 문제에서 연속되지 않지만, 사용해야하는 원소가 주어지면 (이 문제에서는 가치가 다른 임의의 개수의 동전)for c in coin 과 같이 해당 원소를 기준으로 순회하는 방법을 떠올리기 !!dp에 저장하는 값은 문제에서 요구하는 값임 !!!!!!!!! 여기서는 만들 수 있는 경우의 수가 됨처음에 tabulation을 사용하기에 k의 범위가 크고, 물어보는 것이 딱 하나에 대한 결과여서 memoization을 생각함. (Top-down)시간제한이 0.5 초 (추가 시간 없음)인데 지금 코드는 O(nk)니까 최대 100,000번. 따라서 시간초과발생할거라 생각근데 일단 tabulation(bo..
(( 한 번 다시 봐도 좋을 문제 )) 문제 링크https://www.acmicpc.net/problem/12919 TIL반대로 생각해보는 연습하기 (거꾸로)문제에서 S에 1) 끝에 A를 추가하거나 2) 끝에 B를 추가한뒤 배열 뒤집기를 요구했으니반대로 T에서 1) 끝에서 A를 제거하거나 2) 배열을 뒤집고 B를 제거하는 것을 해볼 수 있음 !! 다만 전체 배열로 비교하는 것은 까다롭고, 비효율적이니 T의 마지막 문자를 기준으로 확인하는 게 좋음 재귀에서는 연속된 return 처리 필수 모든 경우의 수를 봐야하는 경우에는 꼭 이렇게 재귀형식으로 해야함처음 코드의 경우, 모든 경우의 수를 볼 수 없음 >> 틀린 이유 [ 처음 코드] - TC는 모두 돌아가나, 정답 제출 실패import copyS = l..
문제 링크https://www.acmicpc.net/problem/1931 TIL처음에는 key-value의 형태로 시간을 기록할까 했지만, 시간 범위가 2^31인걸보고 절대 안되겠다 싶어서 다른 방법 생각남은 방법은 주어진 회의들에 대해서 순회하면서 넣을까 말까 고민하는 것이었기에 빠른 회의 순으로 나열해야한다고 생각함나열한 미팅 리스트를 순회하며만약 다음 회의의 시작 시간이 현재 회의가 끝나는 시간보다 뒤면 가능 (cnt 추가하고 변수 업뎃)if me meetings[i][0]:중요한 거는 여기서 =을 꼭 붙여야한다는 점 !!!! 이거 안해서 처음에 틀림. 끝나는 것과 시작하는 것은 동일할 수 있음만약 다음 회의의 끝나는 시간이 현재 회의 끝나는 시간보다 작으면 변수만 업뎃 (더 짧으니까)두 개 ..
문제 링크https://www.acmicpc.net/problem/1541 TIL문제를 잃고 처음에는 어떻게 풀어야하나 고민했으나 '-'가 중요한 역할이라고 생각했다.-가 나오지 않는 이상 무조건 +이므로 다 더해질 것이고, -가 나오면 그 뒤에 오는 모든 숫자는 그 다음 -가 나오기 전까지 모두 더하는 것이 가장 큰 수를 뺄 수 있는 방법이라고 생각그래서 -를 기준으로 분할을 하고, 분할한 것들을 +를 기준으로 분할하여 숫자를 구했다파이썬의 매우 유용한 기능 split 사랑훼이 방법이 왜 그리디인지??그리디 알고리즘에서는 현재 상태에서 가장 좋은 선택을 계속해서 취하고 그 선택들이 합쳐져서 최적의 해를 만든다고 가정한다이 문제에서도 - 연산자를 기준으로 수식을 나누고, 나누어진 후에는 각각의 부분을..
문제 링크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,..
