aeightchill

🗂️   문제 11657. 타임머신  📌   PointBellman-Ford Algorithm벨만-포드 알고리즘은 단일 출발점 최단 경로(SSSP, Single Source Shortest Path)를 구하는 알고리즘다익스트라와 달리 음의 가중치를 포함한 그래프에서도 사용 가능. 기본 코드def bellman_ford(V, edges, start): # 거리 배열 초기화 (무한대) INF = float('inf') dist = [INF] * V dist[start] = 0 # 시작 정점 거리 = 0 # (V-1)번 모든 간선 확인 for _ in range(V - 1): for u, v, w in edges: if dist[u] !=..

🗂️   문제 문자열 내 p와 y의 개수  📌   Point문자열(String) 자료형문자열의 count 연산으로 문자열 내 문자의 개수를 구한다.# 문자열 count 연산string = "hello worLd"l_count = string.count("l") '''문자열.count("개수를 구하고자 하는 문자")'''print(l_count)# result2count 연산을 할 때 소문자와 대문자를 구분하여 개수가 구해진다.따라서, 위에서 소문자 "l"을 count 하였으므로 hello에 들어간 l의 개수만 구해진다. 📄   코드def solution(s): p_cnt, y_cnt = s.count('p') + s.count('P'), s.count('y') + s.count('Y') ..

문제 모음 레포지토리 📁 https://github.com/ahyun39/99club_5_codingtest_study GitHub - ahyun39/99club_5_codingtest_study: [항해99] 99클럽 코딩테스트 스터디 5기 문제 모음[항해99] 99클럽 코딩테스트 스터디 5기 문제 모음. Contribute to ahyun39/99club_5_codingtest_study development by creating an account on GitHub.github.com [항해99] 99클럽 코딩 테스트 스터디 5기 🔥 스터디 참여 계기한창 동기들과 알고리즘 스터디를 진행할 때 기업 코테 문제를 거의 다 풀 정도로 실력이 쌓였었다. 6개월 동안 여러 알고리즘을 보다보니 문..

[백준] 1351. 무한 수열 / 골드5Dynamic Programming시간복잡도 : O(logN) def f(): N, P, Q = map(int, input().split()) dp = {0:1} # 딕셔너리 기반 메모이제이션 # dp[0] = 1 def memo(n): if n in dp: # 이미 계산된 값이면 그대로 반환 return dp[n] dp[n] = memo(n // P) + memo(n // Q) return dp[n] print(memo(N))f()   풀이 방식dp 초기화dp = {0: 1} : dp [0]은 문제의 기본 조건으로 1로 초기화한다.재귀 함수 memo(n) 정의메모이제이션 활용dp[..

[백준] 2225. 합분해 / 골드5Dynamic Programming시간복잡도 : O(NK) def f(): N, K = map(int, input().split()) dp = [[0] * (N + 1) for _ in range(K + 1)] dp[0][0] = 1 # DP 계산 for k in range(1, K + 1): dp[k][0] = 1 for n in range(1, N + 1): dp[k][n] = (dp[k][n-1] + dp[k-1][n]) % 1000000000 print(dp[K][N])f()  풀이 방식dp 배열을 (K+1) X (N+1) 크기로 초기화한다.dp[k][n]  :  k 개의 수를 사용하여..

🗂️  문제[SQL50] 1193. Monthly Transactions I (AGGREGATE)✍🏻  풀이 문제 해석주어진 Transactions 테이블에서 월별, 국가별로 각 query_name에 대해 다음을 계산하는 문제trans_count전체 거래 수approved_count승인된 거래 수state = 'approved'인 거래 수만 counttrans_total_amount전체 거래 금액 합approved_total_amountstate = 'approved'인 거래 금액 합  코드WITH all_trans AS ( -- 모든 거래에 대한 집계 SELECT country, SUM(1) AS all_trans_cnt, SUM(amount) ..

[백준] 9251. LCS / 골드5Dynamic Programming시간복잡도 : O(N X M)       *N : length s1,   M : length s2 def find_lis(): s1 = "0" + str(input()) s2 = "0" + str(input()) dp = [[0]*(len(s2)) for _ in range(len(s1))] for i in range(1, len(s1)): for j in range(1, len(s2)): if s1[i] == s2[j]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = ma..

[백준] 11053. 가장 긴 증가하는 부분 수열 / 실버2Dynamic Programming시간복잡도 : O(N^2)  코드 변수 정의l : 수열의 길이A : 정수로 이루어진 수열def lis(l, A): # dp[i]: A[i]를 마지막 원소로 가지는 최장 증가 부분 수열의 길이 dp = [1] * l # 모든 원소는 최소 1개의 길이를 가짐 # 모든 i에 대해 이전 원소들과 비교 for i in range(1, l): for j in range(i): # A[j]가 A[i]보다 작다면, A[i]를 A[j] 뒤에 붙일 수 있음 if A[i] > A[j]: dp[i] = max(dp[i], dp[j] ..

[백준] 1003. 피보나치 함수 / 실버3Dynamic Programming시간복잡도 : O(N)  코드 변수 정의dp : 한 번 계산한 값을 저장하여 재사용하기 위한 dp 테이블 생성def main(): T = int(input()) dp = [(1, 0), (0, 1)] + [(0, 0)] * 39 # N은 최대 40을 갖음 # dp 초기화 # fibo(n-1) + fibo(n-2) 로 0, 1 반환 count 구하는 코드로 구현 for i in range(2, 41): dp[i] = (dp[i-1][0] + dp[i-2][0], dp[i-1][1] + dp[i-2][1]) for _ in range(T): N = int(input..

[백준] 19598. 최소 회의실 개수 / 골드5코드 변수 정의meetings : 각 회의의 시작 시간과 종료 시간을 담은 리스트pq : 우선순위 큐start, end : 회의 시작 시간, 회의 종료 시간Priority Queue시간복잡도 : O(N logN)import heapqdef meeting_room(): N = int(input()) meetings = [list(map(int, input().split())) for _ in range(N)] meetings.sort() # 회의 시작 시간을 기준으로 정렬 pq = [] # 우선순위 큐 생성 heapq.heappush(pq, meetings[0][1]) # 1번째 회의 종료 시간을 힙에 push f..