※ 문제https://www.acmicpc.net/problem/12865  ※ 문제 유형다이나믹 프로그래밍, 배낭 문제(GOLD_5) ※ 나의 풀이DP를 이용하여 문제 해결역순으로 DP값을 max로 비교 계산import sysN, K = map(int, sys.stdin.readline().split())dp = [0] * (K + 1)items = []for _ in range(N): items.append(list(map(int, sys.stdin.readline().split())))for W, V in items: # 역순으로 계산 for i in range(K, W - 1, -1): dp[i] = max(dp[i], dp[i-W] + V) print(d..

※ 문제https://www.acmicpc.net/problem/5567  ※ 문제 유형그래프 이론, 그래프 탐색, 너비 우선 탐색(SILVER_2)※ 나의 풀이그래프 활용 (인접 리스트)주어진 친구 관계를 그래프 형태로 저장각 노드는 사람을, 각 간선은 친구 관계상근이의 직접 친구 리스트(friend) 생성상근이(1번 노드)의 친구 목록을 graph[1]을 이용이를 기반으로 직접 친구 리스트 friend를 작성상근이의 친구의 친구 리스트(friend_2) 생성상근이의 직접 친구를 순회하며, 각 친구의 친구를 확인상근이 자신(1번)과 이미 직접 친구인 사람은 제외하고, 친구의 친구 리스트에 추가최종 결과 계산직접 친구와 친구의 친구 수를 합산하여 출력import sysN = int(sys.stdin.re..

※ 문제https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  ※ 문제 설명n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution..

※ 문제https://www.acmicpc.net/problem/21318 ※ 문제 유형다아니믹 프로그래밍 (SILVER_3)※ 나의 풀이다아니믹 프로그래밍 풀이2차원 DP각 피보나치 숫자를 구하는 과정에서 0 호출 횟수 와 1 호출 횟수를 저장피보나치 공식인 fibo(x) = fibo(x -2) + fibo(x - 1)를 이용해 호출 횟수를 누적 계산 DP 배열 구조 :  dp[i]  =  [0 호출 횟수, 1호출 횟수]import sysT = int(sys.stdin.readline())cases = []for _ in range(T): cases.append(int(sys.stdin.readline()))# dp = [[0, 0]] * (40 + 1) X # -> 가변 객체를 담을 경우 같은 ..

※ 문제https://www.acmicpc.net/problem/21318 ※ 문제 유형누적합 (SILVER_1)※ 나의 풀이슬라이싱을 활용한 풀이 -> 시간 초과누적합으로 해결실수 여부 판단 리스트 mistake 배열 생성누적합 배열 생성 (mistake 배열 활용)질문 Q 처리 import sysN = int(sys.stdin.readline())li = [0] + list(map(int, sys.stdin.readline().split()))# 실수 여부 판단 리스트 생성mistake = [0] * N # 0부터 시작, 길이는 Nfor i in range(1, N): # 인접한 요소 비교 if li[i] > li[i + 1]: mistake[i] = 1# 누적합 계산s_num ..

※ 문제https://www.acmicpc.net/problem/2805※ 문제 유형이분 탐색, 매개 변수 탐색 (SILVER_2)※ 나의 풀이이분 탐색으로 문제 해결N, M의 입력 제한이 범위가 크므로, 시간 복잡도 고려 필수import sysN, M = map(int, sys.stdin.readline().split())trees = list(map(int, sys.stdin.readline().split()))trees.sort()low, high = 1, trees[-1] #max(trees) - 시간 초과ans = 0while low mid: total += tree - mid if total >= M: ans = mid low = mid + ..

※ 문제https://www.acmicpc.net/problem/14916※ 문제 유형수학, 다이나믹 프로그래밍, 그리디 알고리즘(SILVER_5)※ 나의 풀이DP로 문제 해결import sys N = int(sys.stdin.readline())dp = [-1] * (N + 1)if N >= 2: dp[2] = 1if N >= 4: dp[4] = 2if N >= 5: dp[5] = 1# DP 계산for i in range(6, N + 1): if dp[i - 2] != -1: # 2원을 추가할 수 있는 경우 dp[i] = dp[i - 2] + 1 if dp[i - 5] != -1: # 5원을 추가할 수 있는 경우 if dp[i] == -1:..

※ 문제https://www.acmicpc.net/problem/9095※ 문제 유형다이나믹 프로그래밍 (SILVER_3)※ 나의 풀이DP로 문제 해결4를 1, 2, 3으로 표현하는 방법 7가지1 + 1 + 1 + 11 + 1 + 21 + 2 + 12 + 1 + 12 + 21 + 33 + 15를 1, 2, 3으로 표현하는 방법4에서 1을 더하는 방법(7가지)3에서 2를 더하는방법2에서 3을 더하는 방법6을 1, 2, 3으로 표현하는 방법5에서 1을 더하는 방법4에서 2를 더하는 방법3에서 3을 더하는 방법dp[N] = dp[N-1] + dp[N-2] + dp[N-3]import sysT = int(sys.stdin.readline())case = []for i in range(T): case.app..

※ 문제https://www.acmicpc.net/problem/1463※ 문제 유형다이나믹 프로그래밍 (SILVER_3)※ 나의 풀이DP로 문제 해결import sysN = int(sys.stdin.readline())dp = [0] * (N + 1)dp[1] = 0for i in range(2, N + 1): # 이전 index의 값 + 1(1을 뺀다는 규칙)으로 저장 dp[i] = 1 + dp[i - 1] # 3으로 나누어 떨어지면 3으로 나누고, dp[i] 중 최솟값으로 저장 if i % 3 == 0: dp[i] = min(dp[i], 1 + dp[i // 3]) # 2으로 나누어 떨어지면 2으로 나누고, dp[i] 중 최솟값으로 저장 if i % 2 ..

※ 문제https://www.acmicpc.net/problem/5525※ 문제 유형문자열 (SILVER_1)※ 나의 풀이시간 복잡도를 고려하지 않고, index slicing을 통해 문제 해결 하였을 시, 50점import sysN = int(sys.stdin.readline())M = int(sys.stdin.readline())S = sys.stdin.readline()find_s = 'IOI' + 'OI' * (N-1)ans = 0idx = 0while idx 시간 복잡도를 고려하여, 인덱스 슬라이싱을 진행할 때, 중복된 IOI를 체크해야 하는 과정을 줄이기 위하여 다른 방안 채택투 포인터 알고리즘 고려import sysN = int(sys.stdin.readline())M = int(sys.st..