aeightchill

문제 모음 레포지토리 📁 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 개의 수를 사용하여..

[백준] 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..

[백준] 1946. 신입 사원 / 실버1코드 변수 정의applicants : 입력받은 지원자 정보를 저장하는 리스트max_new : 선발할 수 있는 신입사원의 최대 인원수b : 지원자의 면접 성적min_b : 현재 지원자까지의 최소 면접 성적   *초기 값은 무한대 값으로 초기화한다.Greedy시간복잡도 : O(N logN)def recruit(): N = int(input()) applicants = [list(map(int, input().split())) for _ in range(N)] # 지원자 정보 저장 리스트 applicants.sort() max_new = 0 # 선발 가능 최대 인원수 min_b = float('inf') # 최솟값을 무한대 값으로 초기화 ..

[백준] 17503. 맥주 축제 / 실버1코드 변수 정의N  :  선택해야 하는 맥주의 개수M  :  최소로 요구되는 선호도 합K  :  주어지는 전체 맥주의 개수beers  :  [선호도, 도수 레벨] 형태로 저장된 K개의 맥주 정보 리스트 pq  :  선택한 맥주의 선호도를 저장할 최소 힙preference  :  현재까지 선택한 맥주의 선호도 합Priority Queue시간복잡도 : O(KlogN)import heapqdef drink(): N, M, K = map(int, input().split()) beers = [list(map(int, input().split())) for _ in range(K)] # K개의 맥주 정보를 (선호도, 도수 레벨) 형태로 저장 beers.so..