그래프 탐색 문제로dfs, bfs 둘다 사용이 가능하여 다양한 풀이가 가능한 문제다. DFS: dictionary(인접리스트), 재귀 사용n = int(input()) # 컴퓨터의 수 (1~100 정수)m = int(input()) # 직접 연결되어있는 컴퓨터 쌍의 수graph = {i: [] for i in range(1, n + 1)} # 각 컴퓨터와 이어진 컴퓨터들을 저장할 그래프 초기화for _ in range(m): a, b = map(int, input().split()) # 직접 연결된 컴퓨터 쌍을 입력받음 graph[a].append(b) # a와 b를 연결하여 그래프에 추가 graph[b].append(a) # b와 a를 연결하여 그래프에 추가visited = ..
분류 전체보기
풀이 1: DP이 문제를 위한 가장 효율적인 방법은 DP를 사용하는 것이다. 초기값초기값 dp[1] = 1, dp[2] = 2, dp[3] = 4(dp[2]는 1+1, 2로 2가지, p[3]은 1+1+1, 1+2, 2+1, 3으로 4가지) 점화식4일 때 dp[3]+1, dp[2]+2, dp[1]+3와 같이 구할 수 있다. --> n은 dp[n-1]+3, dp[n-2]+2, dp[n-3]+3--> 방법의 수 dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 1, 2, 3의 합으로 나타내는 방법의 수에서 한 번 계산한 값을 재사용함으로써 중복 계산을 방지하고, 시간 복잡도를 줄일 수 있다.def count_ways(n): # n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 저장..
1. Basic인공지능 > 기계학습 > 딥러닝 > 트랜스포머Machine LearningSupervised Learning (Data-label)classification: 특정 클래스 예측regression: 수치 예측Unsupervised Learning (unlabled data)clustering - 특징 고려해서 묶음Reinforcement Learning: 두 가지 선택Exploration: 새로운 행동Exploitation: 기존 행동 중 가장 만족도 높은 것 선택 2. Machine Learning(개념)과 Data(종류, 모양)Datasettraining datavalidation datatest dataTargetPredictionmodel parametermodel hyperpar..
von Nuemann architectureassert 함수: 에러 검출. 특정 조건 거짓이면 프로그램 중단bus: Device controller와 memory를 연결하는 경로local buffer: 각 Device controller가 가지고 있는 버퍼IDT: 인터럽트를 받으면 이 테이블을 참조함Device driver: Device controller와 OS 간의 통신을 담당함kilo / mega / giga / tera: 용량 단위address space 구성: code, data, stack, heapprocess 5가지 상태: new, ready, running, blocked, exitfork 리턴 밸류:부모: 자식 PID자식: 0실패: -1zombie process: wait 호출하지 않고..
간단한 그리디 문제!입력 받는 것만 안 헷갈리면 될 것 같다. 11399번: ATMn = int(input())time = list(map(int, input().split()))time = sorted(time)lst = []cost = 0for i in range(len(time)): cost += time[i] lst.append(cost)print(sum(lst)) 11047번: 동전 0n, k = map(int, input().split())lst = [int(input()) for _ in range(n)]lst = sorted(lst, reverse=True)total = 0for i in range(n): if lst[i] lst[i] = 안 붙여서 처음에 틀렸다 ^^....
1. n, m, v 입력 받기 (띄어쓰기 입력)n, m, v = map(int, input().split())N(정점수), M(간선수), V(탐색 시작할 정점 번호) 2. 그래프 입력 받기 (노드 연결 정보) - 인접 행렬graph = [[0] * (n+1) for _ in range(n+1)]for i in range(m): a, b = map(int, input().split()) graph[a][b] = graph[b][a] = 1 정점 번호와 인덱스 일치시키기 위해 n+1로 초기화무방향 그래프이므로 graph[a][b] = graph[b][a] = 1 ** 그래프 출력하기def print_graph(graph): for row in graph[1:]: # 0번째 행과 열은 사용하..
subproblem 중복, 반복연산 많음 -> DP 풀이1 (Bottom-up)n = int(input())dp = [0] * (n+1)for i in range(2, n+1): dp[i] = dp[i-1] + 1 if i % 3 == 0: dp[i] = min(dp[i//3]+1, dp[i]) if i % 2 == 0: dp[i] = min(dp[i//2]+1, dp[i]) print(i, ": ", dp[i])if n 풀이2 (Top-Down) - Recursion Errordef min_operations(n, dp): if n 0: # 이미 계산된 값이 있다면 그 값을 반환 return dp[n] dp[n] = mi..
컴퓨터 과학에서는 알고리즘의 복잡도를 나타내는 데 $$T(n), O, \Theta, \Omega$$ 등의 표기법을 사용한다. 이러한 표기법은 알고리즘의 실행 시간이나 공간 요구사항의 상한, 하한, 또는 정확한 경계를 지정한다. 이러한 표기법을 빅 오 표기법이라고도 하며, 각각은 다음과 같은 의미를 가진다. Big O 표기법 (O): 함수의 상한을 설명한다. ( O(g(n)) )은 함수 ( f(n) )이 ( c \times g(n) )을 초과하지 않음을 의미한다. 이는 주로 최악의 경우 성능을 나타내는 데 사용된다. Theta 표기법 ((\Theta)): 함수의 정확한 성장률을 나타낸다. ( \Theta(g(n)) )은 ( f(n) )이 ( c_1 \times g(n) )과 ( c_2 \times g(..
겹치는 하위 문제(Subproblem)를 해결하고 그 결과를 저장해 나가는 방식으로 최적화 문제들 특징1. 작은 하위문제들이 반복적으로 발생하며, 이들의 해결 결과가 재활용될 수 있을 때 2. Optimal Substructure(최적부분구조)을 갖춘 문제. 큰 문제의 최적해가 작은 문제의 최적해를 통해 구할 수 있을 때 3. 중복된 계산을 최소화할 수 있는 구조. 같은 하위 문제를 반복해서 해결해야 할 때 하위문제가 독립적, 줄여가면서 해결 -> Divide & Conquer 하위문제가 중첩됨, 반복해야 함 -> Dynamic Programming DP로 해결하는 대표적인 문제들longest common subsequenceKnapsack problemRod cutting problemshortest ..
첫 번째 원소는 내림차순으로, 두 번째 원소는 오름차순으로, 세 번째 원소는 내림차순으로 정렬하는 예제 # 2차원 리스트 생성 two_dim_list = [ [3, 6, 9], [2, 5, 8], [3, 6, 7], [1, 4, 7], [2, 5, 10] ] # 우선순위에 따라 정렬하는 함수 정의 sorted_list = sorted(two_dim_list, key=lambda x: (-x[0], x[1], -x[2])) # 결과 출력 for item in sorted_list: print(item) 관련 문제 ) 백준 10825. 국영수 n = int(input()) students = [] for _ in range(n): name, kor, eng, math = input().split() stud..
