Algorithm125 [코딩 + 알고리즘 완주반] 20일차. 탐욕 알고리즘 (Greedy algorithm) # 탐욕 알고리즘(Greedy Algorithm) 최적의 해에 가까운 값을 구하기 위해 사용 여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행 # 문제1 ) 동전 문제 지불해야 하는 값을 동전의 수가 가장 적게 지불하기 가장 큰 동전부터 최대한 지불해야하는 값을 채우는 방식 지불해야 하는 값 : 4720 1원, 50원, 100원, 500원 동전 coin_list = [500, 100, 50, 1] # 큰 동전부터 def min_coin_count(value, coin_list): total_coin_count = 0 details = list() coin_list.sort(reverse=True) for coin in coin_list: coin_num =.. 2021. 4. 6. [코딩 + 알고리즘 완주반] 19일차. 그래프 이해와 자료구조 # 그래프 실제 세계의 현상이나 사물을 정점( 또는 노드)와 간선으로 표현 # 그래프 관련 용어 노드 (Node) : 정점(Vertex) , 위치 간선 (Edge) : 위치 간의 관계를 표시한 선으로 노드를 연결한 선 (link 또는 branch) 인접 정점 (Adjacent Vertex) : 간선으로 직접 연결된 정점 (또는 노드) 정점의 차수(Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수(In-Degree) : 방향그래프에서 외부에서 오는 간선의 수 진출 차수(Out-Degree) : 방향 그래프에서 외부로 향하는 간선의 수 경로 길이 (Path Length) : 경로를 구성하기 위해 사용된 간선의 수 단순 경로(Simple Path) : 처음 정점과 끝 정점을 제외하.. 2021. 4. 5. [LEET CODE] 771. Jewels and Stones # Problem You're given strings jewels representing the types of stones that are jewels, and stones representing the stones you have. Each character in stones is a type of stone you have. You want to know how many of the stones you have are also jewels. Letters are case sensitive, so "a" is considered a different type of stone from "A". Constraints: 1 int: freqs = {} count = 0 # 돌(S)의 빈도 수 계산 for.. 2021. 4. 5. [코딩 + 알고리즘 완주반] 18일차. 병합정렬 (merge sort) # 병합 정렬 재귀 용법을 사용한 정렬 알고리즘 리스트를 반으로 잘라 나눈 후 재귀적으로 병합 정렬 부분 리스트를 다시 하나의 정렬된 리스트로 합병 # 알고리즘 구현 # 병합하기 def merge(left,right): lp = 0 rp = 0 merged=list() # left,right 둘다 데이터 있을 때 while len(left) >lp and len(right) >rp : if left[lp]>right[rp]: merged.append(right[rp]) rp+=1 else: merged.append(left[lp]) lp+=1 # left에만 데이터 남아있을 때 while len(left) > lp : merged.append(left[lp]) lp+=1 # right에만 데이터 남아있을.. 2021. 4. 4. [코딩 + 알고리즘 완주반] 18일차. 퀵 정렬 # 퀵 정렬 기준점을 정해서 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수 작성 각 왼쪽, 오른쪽은 재귀 용법을 사용해서 반복 return qsort(left) + [pivot] + qsort(right) #퀵 정렬 구현 def qsort(data): if len(data) data[index]: left.append(data[index]) else: right.append(data[index]) return qsort(left) + [pivot] + qsort(right) # 리스트 컴프리헨션 사용 def qsort(data): if len(data) item ] right = [ item for item in data[1:] if pivot 2021. 4. 4. [코딩 + 알고리즘 완주반] 17일차. 재귀용법, 동적계획법과 분할정복 # 재귀 용법 함수 안에서 동일한 함수를 호출 # 일반적인 형태 # 일반적인 형태1 def function(입력): if 입력 > 일정값: # 입력이 일정 값 이상이면 return function(입력 - 1) # 입력보다 작은 값 else: return 일정값, 입력값, 또는 특정값 # 재귀 호출 종료 # 일반적인 형태2 def function(입력): if 입력 2021. 3. 31. 이전 1 ··· 17 18 19 20 21 다음 반응형
