본문 바로가기

전체 글239

점화식 이란? 알고리즘을 공부하다가 점화식이라는 키워드가 나와서 알아본 정보입니다. 점화식이란 ? 수열의 각 항 간에 관계를 (단순 나열이 아닌 규칙으로) 표현한 관계식을 의미합니다. 좀 더 쉽게 이야기하면? - 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것입니다. 다시 말해 재귀함수의 구조를 갖는 알고리즘만 점화식으로 표현할 수 있습니다. - 수열의 N 번째 항(일반항) 을, - 그 앞의 항들에 의해 규칙적(종속적)으로 표현한 관계식을 말합니다. 어떤 점화식 표현이있을까 ? 점화식 특징은 ? 등식 또는 관계식 형태를 갖고있습니다. (단, 문제 제시 때는 초기값 또는 경계값이 반드시 필요합니다) 점화식 자체는, 간접적이고 부분적인 정보만 주어, 따라서 일반항을 구할 필요 있습니다. 점화식의 점근.. 2022. 3. 16.
다이나믹 프로그래밍(Dynamic Programming) 이란? 동적계획법 (Dynamic Programming) 이란? 최적화 문제를 위해 고안된 기법으로 복잡한 문제보다 간단한 여러 개의 부분 문제로 나누어 해결합니다. 중요한 점은 한 번 계산된 부분 문제의 답을 저장해 두어 나중에 같은 부분 문제의 답을 원할 시, 반복되는 연산 없이 바로 저장해 둔 걸 꺼내 쓸 수 있도록 하는 것이 핵심입니다. 주로 중복되는 부분 문제(Overlapping Subproblem)와 최적 부분 구조 (Optimal Substructure)를 가지고 문제들을 풀 때 사용됩니다. 또한, 동적 계획법을 설계할 때는 가장 중요한 것이 현재 문제의 상태와 문제와 부분 문제 간의 관계 또는 전이를 파악하는 것입니다. 문제들 간의 관계 또는 전이를 정확하게 파악한다면 알고리즘의 정당성을 얻을 .. 2022. 3. 16.
정렬 알고리즘 비교 In-Place ? 입력리스트 내부에서 정렬이 이뤄지는 경우를 가리킵니다. 반대는 정렬 도중에 별도 저장공간을 필요로 하는 경우입니다. Stable ? Stable이란 같은 값의 위치가 정렬 과정에서 뒤바뀌지 않는 것을 뜻합니다. 버블 정렬 선택 정렬 삽입 정렬 셸 정렬 합병 정렬 퀵 정렬 힙 정렬 2022. 3. 13.
힙 정렬 (Heap Sort) 이란? 힙 정렬이란? 자료구조 힙(heap)을 구성하여 정렬하는 방법이다. 힙이란? 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이며 최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조 이다. 이진트리란? 컴퓨터 안에서 데이터를 표현할 때 데이터를 각(Node)에 담은 뒤 노드를 두 개씩 이어 붙이는 구조이다. 최대 힙트리나 최소 힙트리를 구성해서 정렬하는 방법이다. 내림차순 -> 최대 힙(부모노드가 자식 노드보다 큰 힙)으로 구성 오름차순 -> 최소 힙(자식노드가 부모노드보다 큰 힙)으로 구성 1. 정렬해야할 N 개의 요소들로 최대힙(완전 이진트리 형태)를 만든다. *최대힙이니, 내림차순 기준 2. 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 된다. 3. 삭제되는 요소들(최대값.. 2022. 3. 13.
퀵 정렬 (Quick Sort) 란? 퀵 정렬이란? 하나의 배열을 피벗(pivot) 을 기준으로 두 개의 비균등한 배열로 분할하고 분할된 부분 배열을 정렬한 다음 두 개의 정렬된 배열을 합하여 전체 정렬된 배열이 되게하는 방법이다. 퀵 정렬은 3단계로 이루어졌다. 분할 단계 : 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열로 분할한다. 피벗을 중심으로 왼쪽 : 피벗보다 작은 요소들 피벗을 중심으로 오른쪽 : 피벗보다 큰 요소들 정복 단계 : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 '순환 호출' 을 이용하여 다시 분할 정복 방법을 적용한다. 결합 단계 : 정렬된 부분 배열들을 하나의 배열로 합병한다. 퀵 정렬 장단점은 ? 속도가 빠르다는 장점을 갖고 있다. 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다. 또.. 2022. 3. 13.
합병 정렬 (Merge Sort) 란? 합병 정렬이란 ? 합병? 병합? 둘 다 사용해도 되는 정렬 이름이다. - 합병 : A와 B가 합쳐져서 C가 만들어진다. - 병합 : A가 B의 일부가 되거나? B가 A의 일부가 됨. 분할을 이용하는 분할 정복 알고리즘이다. 말 그대로인 배열을 쪼개서 길이가 1인 배열을 만들고, 그 이후 정렬하면서 합치는 정렬이다. 합병은 binary tree 형태로 쪼개지기 때문에 가질 수 있는 최대 깊이는 log N이 된다. 병합 정렬의 단계가 존재하는데, '분할, 정복, 결합' 3가지로 나누어 볼 수가 있다. 분할 단계 : 입력된 배열을 같은 크기의 2개의 부분 배열로 분할한다. 정복 단계 : 부분 배열을 정렬한다. (*여기서 부분 배열의 크기가 충분히 작지 않다면? '순환 호출'을 이용하여 다시 분할 정복법을 적용.. 2022. 3. 13.

티스토리툴바