본문 바로가기

전체보기

 (448)
[432] 7주차 동적 계획법, 누적합 1. 동적 계획법(동적 프로그래밍, Dynamic Programming; DP)가. 개요동적 계획법은 복잡한 큰 문제를 간단한 작은 문제 여러 개로 나누어 푸는 아이디어를 말합니다.분할 정복과 차이는 간단한 작은 문제가 반복되어 나타나므로 답을 저장해놓고 재사용하는 데 있습니다.동적 계획법은 구체적인 알고리즘이 아닌, 알고리즘을 설계하기 위한 접근 방법을 지칭하는 용어입니다.(ex. 분할 정복, 그리디, 백트래킹 등)나. 동적 계획법을 사용하기 위한 조건1) 최적 부분 구조(Optimal Substructure)큰 문제를 작은 여러 문제(부분 문제)로 나누어 풀기 위해서는 작은 문제의 답을 통해 큰 문제의 답을 찾을 수 있어야 합니다.예를 들어 위와 같은 지도에서 서울에서 부산까지 가는 최단 경로를 찾는..
[431] 우선순위 큐(Priority Queue)와 힙(Heap) 1. 우선순위 큐우선순위 큐는 추상 자료형(abstract data type, ADT)으로 구현 방법이나 연산의 시간 복잡도 등을 정의하고 있지 않습니다.흔히 "우선순위 큐"는 "힙"이라고 오해하는 경우가 있으나 "힙"은 "우선순위 큐"라는 추상 자료형을 구현한 "자료구조"에 해당합니다. 우선순위 큐는 선입선출(Fisrt In First Out, FIFO)인 큐와 다르게 우선순위가 더 높은 원소가 먼저 나갑니다.예를 들어 크기가 큰 것이 높은 우선순위를 가지는 우선순위 큐가 있다고 해봅시다.1, 3, 2가 어떤 순서로 들어와도, 나갈 때는 우선순위가 높은 3, 2, 1 순으로 나가게 됩니다.그림에서는 우선순위 큐에 원소가 들어올때마다 정렬이 일어나는 것으로 보여주고 있습니다만,우선순위 큐에 들어올 때 ..
[430] 2주차 조건문, 반복문 모든 알고리즘은 "순차", "선택", "반복"이라는 세 가지 기본 제어 구조로 구성할 수 있다는 것이 수학적으로 증명되어 있습니다.그리고 이 증명은 현대 프로그래밍의 기초를 이루는 구조적 프로그래밍(Structured Programming)의 이론적 배경이 되었습니다.이번 글에서는 이 중 "선택"과 "반복"을 조건문과 반복문으로 어떻게 구현하는지 살펴보도록 하겠습니다. 1. 조건문조건문은 조건(참과 거짓)에 따라 서로 다른 동작을 수행하도록 하는 문장입니다.조건문은 파이썬에서 다음과 같이 사용합니다.apple = 5banana = 3if apple banana: print("바나나보다 사과가 더 많습니다.")else: print("사과와 바나나 수가 같습니다.") # 바나나보다 사과가 더 많습니다..
[429] 계수 정렬(Counting Sort) 1. 계수 정렬 개념배열에 존재하는 원소 중 최대값을 범위로 가지는 새로운 배열을 만들어, 각 원소의 개수를 기록해 놓음으로서 선형 시간 내에 정렬을 할 수 있습니다.계수 정렬을 안정적인 정렬로 이용하기 위해서 누적합을 계산하여 원소들의 위치를 지정합니다.기수 정렬과 마찬가지로 비교 기반 정렬 알고리즘이 아닙니다.원소의 범위가 넓을수록 원소의 개수를 관리할 배열의 크기가 커지므로, 원소의 범위가 좁은 특별한 상황에서 사용됩니다.2. 계수 정렬 예제4, 2, 2, 8, 3, 3, 1 을 정렬해봅시다.각 원소의 개수를 기록합니다.기록된 개수의 누적합을 계산합니다.누적합 결과는 각 원소의 정렬 후 위치가 될 것입니다.기존 배열의 뒤에서부터 원소를 새로운 자리에 위치시킵니다.새로운 자리의 위치는 누적합한 결과값..
[428] 기수 정렬(Radix Sort) 1. 기수 정렬 개념기수 정렬은 지금까지 살펴보았던 비교 기반 정렬 알고리즘이 아닌 분배 기반 정렬 알고리즘입니다.미리 데이터를 담을 공간을 마련해두고, 기준에 따라 데이터를 담았다 꺼내는 방식으로 정렬합니다. 우리가 흔히 엑셀에서 서로 다른 기준으로 정렬할 때 사용하는 방식과 비슷하게 진행됩니다.예를 들어 다음 그림과 같은 다섯 명의 사람이 있을 때, 남자를 앞에 여자를 뒤에(성별 기준), 그리고 가나다 순(이름 기준)으로 정렬하려면 어떻게 해야할까요?정답은 최우선 기준을 마지막에, 차선 기준을 먼저 정렬해야합니다.따라서 먼저 가나다 순(이름 기준)으로 정렬합니다.다음으로 상대적인 위치를 바꾸지 않으면서 남자와 여자로 정렬합니다.결과적으로 성별 기준을 우선으로, 그다음 이름(가나다 순)으로 정렬되었습니..
[427] 힙 정렬(Heap Sort) 1. 힙 정렬 개념힙 정렬은 영국의 컴퓨터 과학자 J. W. J. Williams가 1964년 고안한 정렬 알고리즘입니다.힙이라는 자료구조를 만들어 원소를 차례대로 정렬해 나가는 과정을 거칩니다. 힙은 완전이진트리를 이용하여 최대값이나 최소값을 쉽게 찾아내는 자료구조입니다.최대값을 쉽게 찾는 힙을 최대 힙, 최소값을 쉽게 찾는 힙을 최소 힙이라고 부릅니다.이런 특성 때문에 일반적으로 힙을 사용하여 (크기를 우선순위로 가지는) 우선순위 큐를 구현합니다. 힙 정렬은 두 단계를 거칩니다.먼저 모든 원소를 최대 힙으로 만듭니다.(힙 생성 단계, \(O(n)\))그 다음 최대 값을 하나 꺼내고, 나머지 부분을 힙으로 재구성하는 과정을 반복합니다.(정렬 단계, \(O(n\log{n})\)) 힙 정렬은 완전이진트리 ..
[426] 병합 정렬(Merge Sort) 1. 병합 정렬 개념존 폰 노이만이 1945년에 개발한 정렬 알고리즘입니다.분할 정복(Divide and Conquer) 기법을 사용한 알고리즘으로 시간 복잡도가 \(O(n\log{n})\)입니다. 주어진 배열을 n개의 부분 배열로 분할하여 재귀적으로 정렬하는 방식으로, 일반적으로 2개의 부분 배열로 나눕니다.이후 나누어진 부분 배열을 다시 합하는 과정에서 정렬된 배열을 임시로 저장할 메모리 공간이 필요하여 공간 복잡도는 \(O(n)\)입니다. 주어진 배열을 나누는 횟수는 (\(\log_2{n}\)) 번 일어나고, 병합될 때 정렬하는 과정에서 \(O(n)\)의 시간이 걸리므로 시간 복잡도는 항상 \(O(n\log{n})\)이 됩니다. https://ko.wikipedia.org/wiki/합병_정렬 합병 ..
[425] 퀵 정렬(Quick Sort) 1. 퀵 정렬 개념영국의 컴퓨터 과학자 토니 호어(Charles Antony Richard Hoare)가 1959년 고안한 정렬 알고리즘입니다.효율적인 알고리즘으로 빠르게 널리 사용되기 시작하였으며, 다양한 프로그래밍 언어와 시스템에서 기본 정렬 알고리즘으로 채택되었습니다. 퀵 정렬은 분할 정복(Divide and Conquer) 기법을 사용하여 배열을 정렬합니다.배열에서 한 원소를 선택합니다. 선택된 원소는 피벗(Pivot)이라고 부릅니다.피벗을 기준으로 피벗보다 작은 원소들은 왼쪽으로, 큰 원소들은 오른쪽으로 이동시킵니다.이 과정은 투포인터를 사용하여 해결할 수 있습니다.먼저 피벗을 제일 오른쪽 원소와 바꿉니다.(피벗을 제일 오른쪽에 위치시킵니다.)투포인터(i, j)를 첫 번째 자리에 위치시킵니다.한..

티스토리툴바