전체 글
-
[이코테 # Greedy1] 거스름돈 문제 풀이Programming 기초/Coding Test 2023. 6. 2. 17:13
* Greedy Algorism " 현재 상황에서 지금 당장 좋은 것만 고르는 방법" * 거스름돈 문제 카운터에 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리의 동전이 무한히 존재한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수.(단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.) # 해설 보기 전 original 본인 답변 # 500원= Five_H, 100원= One_H, 50원 = Fifty , 10원 = Ten # 손님에게 거슬러줘야 할 돈 N = change # 상품 가격 : ProductPrice = 1350원 ProductPrice = 740 print("상품 가격 : %d" % ProductPrice) payment = int(input("..
-
[Python 자료구조 #고급정렬3] 기수 정렬(radix sort), 카운팅 정렬(counting sort), 팀 정렬(Timsort)Programming 기초/Python 2023. 6. 2. 02:35
* 기수 정렬(radix sort) 입력 데이터에 대해서 어떤 비교 연산도 실행하지 않고 데이터를 정렬할 수 있는 색다른 정렬 기법이다. 다른 방법들이 O(nlog_2 n)이라는 비교기반 정렬의 이론적인 하한선을 깰 수 없는데 비해 기수 정렬은 이 하한선을 깰 수 있다. 기수 정렬은 O(kn)의 시간 복잡도를 갖고 k에 비례한다. 대부분 k는 크지 않은 값(예: k
-
[Python 자료구조 #고급정렬2] 병합정렬(merge sort), 퀵 정렬(quick sort), 이중피벗 퀵 정렬(dual pivot quick sort)Programming 기초/Python 2023. 6. 1. 23:31
* 병합 정렬(merge sort) 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 리스트를 합하여 전체가 정렬된 리스트를 만드는 방법이다. 하나의 문제를 작은 2개의 문제로 분리하고 각각 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략인 분할 정복(divide and conquer) 기법에 바탕을 두고 있다. 추가적인 메모리가 필요하다는 단점이 있다. 병합단계에서 n번의 비교 연산이 필요하고, 병합 단계가 log_2 n번 필요하므로 비교 연산은 최대 O(n log_2 n)번 필요하다. 최악, 평균, 최선의 경우에도 모두 동일한 O(nlog_2 n)시간 복잡도를 갖는다. ▶ 병합 정렬의 주요 처리 과정 분할(Divide) : 입력 배열을 같은 크기의 2개의..
-
[Python 자료구조 #고급정렬1] 셸 정렬(shell sort), 힙 정렬(heap sort)Programming 기초/Python 2023. 6. 1. 00:09
* 다양한 정렬 알고리즘 선택 정렬 : 입력의 크기에 따라 자료 이동 횟수가 결정된다. 삽입 정렬 : 레코드의 많은 이동이 필요하지만 대부분의 레코드가 이미 정렬되어 있는 경우에는 비효율적이다. 버블 정렬 : 인접 요소를 교환하는 방식의 가장 간단한 알고리즘을 사용한다. 셸 정렬 : 삽입 정렬 개념을 개선한 방법 힙 정렬 : 추가적인 메모리 공간이 필요 없는 제자리 정렬로 구현하는 방법 병합 정렬 : 연속적인 분할과 병합을 이용하는 방법 퀵 정렬, 이중피벗 퀵 정렬 : 피벗을 이용한 정렬 방법으로 대표적인 효율적인 정렬 알고리즘 기수 정렬, 카운팅 정렬 : 항목의 비교를 사용하지 않고 분배를 이용해 정렬하는 방법이지만 적용할 수 있는 킷값에 제한이 있는 알고리즘 * 셸 정렬(shell sort) Dona..
-
[Python 자료구조 #가중치 그래프3] 최단 경로 알고리즘 - Dijkstra, FloydProgramming 기초/Python 2023. 5. 30. 23:09
* 최단 경로(shortest path) 최단 경로 문제는 가중치 그래프에서 두 정점을 연결하는 여러 경로들 중에서 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제이다. 간선의 가중치를 시간으로 하면 "최단시간 경로", 거리로 하면 "최단거리 경로"가 된다. 인접 행렬에서 두 정점 사이의 간선이 없으면 None이 아니라 무한대 값(INF)을 저장한다. 간선의 가중치는 반드시 양수이다. * Dijkstra의 최단 경로 알고리즘 하나의 시작 정점 v에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 만약 그래프의 모든 정점들 사이의 최단 경로를 구하려고 한다면 Dijkstra 알고리즘을 정점의 수만큼 반복하여 실행하면 된다. 하나의 정점에서 출발하여 모든 정점까지의 최단 경로를 찾는데 O(n^2)..
-
[Python 자료구조 #가중치 그래프2] 최소비용 신장 트리 - Kruskal의 MST 알고리즘, Prim의 MST 알고리즘Programming 기초/Python 2023. 5. 29. 18:12
* 최소비용 신장 트리(MST: minimum spanning tree) 통신망 도로망 유통망 등은 대개 길이, 구축비용, 전송 시간 등의 가중치를 간선에 할당한 가중치 그래프로 표현할 수 있다. 이러한 망을 가장 적은 비용으로 구축하는 문제를 생각해 보자. 조건은 다음과 같다. 그래프의 모든 정점들은 연결되어야 한다. 연결에 필요한 간선의 가중치 합(비용)이 최소가 되어야 한다. 사이클은 두 정점을 연결하는 두 가지 경로를 제공하므로 비용 측면에서 바람직하지 않다. 따라서 사이클이 없이 (n-1)개의 간선만을 사용해야 한다. → 결과적으로 '신장 트리' 최소비용 신장 트리는 그래프의 여러 가능한 신장 트리들 중에서 사용된 간선들의 가중치 합이 최소인 신장 트리를 말한다. 최소비용 신장 트리를 구하는 방..
-
[Python 자료구조 #가중치 그래프1] 인접행렬/인접리스트를 이용한 가중치 그래프 표현Programming 기초/Python 2023. 5. 27. 23:28
* 가중치 그래프(weighted graph) 간선에 비용이나 가중치가 할당된 그래프. 수학적으로 G = (V, E, w)와 같이 표현된다. V(G)는 그래프 G의 정점들의 집합 E(G)는 그래프 G의 간선들의 집합 w(e)는 간선 e의 강도(weight)로 비용(cost) 또는 길이(length)라고도 부른다. 어떤 가중치 그래프의 경로를 p = (v_0, v_1, ..., V_k)라고 한다면, 경로의 길이(또는 강도) w(p)는 다음과 같이 경로상의 모든 간선의 길이 합으로 표현된다. * 인접 행렬을 이용한 가중치 그래프 표현 ▶ 간선이 없느 것을 표기하는 방법 1. 무한대(INF) 2. None ▶ 인접 행렬에서의 가중치의 합 계산 # 인접 행렬에서의 가중치의 합 계산 # def weightSum(..
-
[Python 자료구조 #그래프3] 신장 트리Programming 기초/Python 2023. 5. 27. 20:13
* 신장 트리(spanning tree) 그래프내의 모든 정점을 포함하는 트리이다. 트리의 일종이므로 모든 정점들이 연결되어 있고 사이클이 없어야 하고, 그래프의 n개의 정점을 정확히 (n-1)개의 간선으로 연결해야 한다. 하나의 같은 그래프에 다양한 신장 트리가 가능하다. 신장 트리는 깊이우선이나 너비우선 탐색 도중에 사용된 간선들만 모으면 된다. # 너비우선탐색 함수 bfs를 수정한 코드 # 탐색 도중에 추가되는 간선을 순서대로 출력한 코드 import collections def bfsST(graph, start): visited = set([start])# 맨 처음에는 start만 방문한 정점임 queue = collections.deque([start])# 파이썬 컬렉션의 덱 생성(큐로 사용) ..