Algorithm

파이썬으로 구현하는 퀵 정렬(Qucik Sort)

Concept 병합 정렬(Merge Sort)과 마찬가지로, 퀵 정렬은 분할 정복(Divide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘으로, 시간복잡도는 $O(nlogn)$이다 하나의 리스트에서 피봇(pivot)이라고 불리는 임의의 기준값을 사용하여 pivot 값을 기준으로 pivot 보다 작은 값의 그룹과 큰값의 그룹으로 나눈다. 이 때 두 그룹의 각 요소들은 정렬된 상태는 아니지만, pivot은 정렬된 위치로 들어가게되며 이를 재귀호출을 통해 정렬하게 된다. 전체적인 동작 과정은 다음과 같다 구현 코드 (아래 코드는 pivot을 arr의 첫번째 요소로 잡은 코드입니다; pivot = arr[0]) 1) 정렬되지 않은 데이터 -> 리스트로 입력 받기 >>>3 2 4 6 9 1..

파이썬으로 구현하는 병합정렬(Merge Sort)

Concept 병합정렬은 분할 정복(Divide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘으로, 시간복잡도는 O(nlogn)이다 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻는 정렬방법이다. 이때 병합 정렬은 아래와 같은 분할 정복 메커니즘을 따르게 된다 - 분할(Divide): 입력 리스트를 같은 크기의 2개의 부분 리스트로 분할한다 - 정복(Conquer): 부분 리스트를 정렬한다 - 결합(Combine): 정렬된 부분 리스트를 하나의 리스트에 통합한다 *이 때 그림에서 표현은 생략되었으나 부분 리스트의 크기가 1이 될 때까지 분할 후 정렬 후 합병과정을 거치게 된다 구현 코..

[SWEA] 분할 정복(Divide and Conquer)

본 글은 [SW Expert Academy]의 파이썬 SW문제 해결 응용-구현2 분할 정복 강의를 보고 정리한 글입니다 https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYFsQq11kDFAVT SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 분할 정복(Divide and Conquer) 목차 01 분할 정복 기법 02 병합 정렬 03 퀵 정렬 04 이진 검색 05 분할 정복 사례 01 분할 정복 기법 분할 정복(DnQ)이란? 탑다운 접근(Top-down approac)으로, 문제..

[SWEA] 완전 검색(Brute-force search)

본 글은 [SW Expert Academy]의 파이썬 SW문제 해결 응용-구현2 완전 검색 강의를 보고 정리한 글입니다 https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYDrI61lYDFAVT# SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 완전 검색(Brute-force search, 브루트 포스 서치) 목차 01 완전 검색 기법 02 조합적 문제 01 완전 검색 기법 완전 검색(Brute-force search)이란? 문제의 해(Solution)를 얻기 위해 가능한 모든 경..

[그래프 이론] 플로이드-워셜(Floyd-Warshall) 알고리즘

플로이드-워셜(Floyd-Warshall) 알고리즘이란? 모든 두 노드 u,v 사이에서 가장 최단 거리를 찾는 알고리즘 시간복잡도 $O(n^3)$으로 그래프의 크기가 작을 때만 사용 가능 음의 에지(negative edge)가 있어도 계산이 가능한 알고리즘 단, 음의 사이클(negative cycle)이 있을 경우 불가능 기본 개념: $A^k$[i][j] 노드 i에서 j까지의 최단거리 비용에는 $index

파이썬으로 구현하는 덱(Deque)

덱(Deque)이란? double-ended queue로, 큐의 앞과 뒤 모두에서 삽입 및 삭제가 가능한 큐를 의미한다. 덱은 원형 큐(Circular Queue)를 확장하면 손쉽게 구현할 수 있다. 원형 큐 구현에 관해서는 해당 게시글을 참고하시면 좋습니다 https://codingsmu.tistory.com/123 파이썬으로 구현하는 원형 큐(Circular Queue) 원형 큐(Circular Queue)란? 배열로 구현 된 선형 큐(Linear Queue)의 경우 데이터의 삽입/삭제 시 데이터들을 앞으로/뒤로 당겨주는 과정이 필요해 최악의 경우 O(n)의 시간복잡도를 가지게 된다. 이러한 codingsmu.tistory.com 0. 멤버 변수&초기화 먼저 덱 클래스의 멤버 변수(member var..

파이썬으로 구현하는 원형 큐(Circular Queue)

원형 큐(Circular Queue)란? 배열로 구현 된 선형 큐(Linear Queue)의 경우 데이터의 삽입/삭제 시 데이터들을 앞으로/뒤로 당겨주는 과정이 필요해 최악의 경우 O(n)의 시간복잡도를 가지게 된다. 이러한 선형 큐의 단점을 극복한 구조가 원형 큐이다 0. 멤버 변수&초기화 먼저 원형 큐 클래스의 멤버 변수(member variable)화 초기화하는 과정을 살펴보자 class CircleQueue: rear = 0 front = 0 MAX_SIZE = 100 queue = list() def __init__(self): self.rear = 0 self.front = 0 self.queue = [0 for i in range(self.MAXSIZE)] 1. 공백 상태 원형큐가 비워져 있..

네트워크 플로우(Network Flow)

네트워크 플로우(Network Flow)란? 특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는가를 측정하는 알고리즘으로 네트워크 데이터 전송, 교통 체증 등 다양한 분야에서 활용되고 있음 최대 유량(Maximum Flow)이란? 최대 유량이란 가중치가 있는 방향그래프(Weighted Directed Graph) G와 시작 노드 S, 도착 노드E 가 주어졌을 때, 각 엣지의 용량(Capacity)를 고려하여 S에서 E로 흘려보낼 수 있는 유량의 최대값을 말하는 것이다. 이 때, G의 각 에지 가중치를 용량(capacity)라고 하며 (u,v)의 용량을 c(u,v)라고 쓴다. 예로, 아래와 같은 그래프 G가 있다고 할 때, A에서 D로 최대한 많은 유량을 보내려고 할 때 가장 합리적인 양은 가..