본문 바로가기

알고리즘

 (12)
[스택] Monotonic Stack 👉 Monotonic Stack 이란? : 스택의 원소들을 오름차순 혹은 내림차순 상태로 유지하도록 하는 알고리즘 단조(monotonic)는 수학 함수에 사용되는 용어이다.함수 y = f(x)가 다음 조건을 따를 때 단조 증가 또는 단조 감소하는 것으로 간주됩니다x가 증가함에 따라 y도 항상 증가 -> 단조 증가 함수 x가 증가함에 따라 y가 항상 감소 -> 단조 감소 함수  ☑️ 2가지 상황에 사용 가능 -> 1) 배열 특정 위치에서 정렬된 숫자들만 보고 싶을 때 -> 2) 배열 특정 위치에서 바로 다음 큰 값(or 작은 값)을 보고 싶을 때  만약 브루트포스로 한다면 O(N^2)이 될 것이다. 하지만 모노토닉 스택을 사용한다면 O(N)으로 시간복잡도를 줄일 수 있다!  👉..
Chap 6-5. 힙 정렬(Heap Sort) 먼저, 힙이라는 자료구조에 대해서 알아보고 이를 이용한 정렬 방법에 대해 알아보자! 힙(Heap)을 공부할 때 항상 가수 마마무의 노래 중 힙(HIP)이 생각난다 ㅎㅎ 배경음악으로 틀고 공부해보자...ㅎ 😎힙(heap)이란? 힙 ("이진 힙"이라고도 한다)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위하여 고안된 완전 이진 트리(Complete Binary Tree)를 기본으로 한 자료구조이다. 힙이라고 하는 것은 우선순위큐를 구현하기 위해 만들어진 데이터 타입이라고 할 수 있다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.(빠르다니.. 완전 HIP한 Heap 이다.) ✔️힙 조건 : 각 노드의 우선 순위가 자식 노드의 우선순위보다 높거나 낮을 때 ✔️힙 종..
Chap 6-4. 쉘 정렬(Shell Sort) 🌈Shell 정렬이란? 쉘은 ‘Donald L. Shell’이 제안한 방법으로 “쉘 정렬”이라고 한다. 다른 정렬 방법들은 정렬 방식이 이름이지만 이것은 만든 사람의 이름이라는 점에서 차이가 있다. 여러 가지 정렬 방법들을 배우는데 이름과 방법이 매치가 되지 않는다. 그래서 본인은 정렬 방식이 이름에 표면적으로 드러날 수 있도록 “Gap 삽입 정렬”이라고 자의적으로 생각해봤다.(일명 뇌피셜이라 할 수 있다.. ㅎ) ✔️방법 : 전체 리스트를 일정 간격(gap)의 부분 리스트로 나눈다. -> 나누어진 각각의 부분 리스트를 insertion sort 수행한다. (부분 리스트 별로 sort를 수행한다) 🌈motivation ✔️버블 정렬이나 삽입 정렬이 수행되는 과정은 ”기껏해야” 이웃하는 원소의 자리바꾸는 ..
Chap 6. 정렬 알고리즘(sort) [ 정렬이란? ] 정렬은 물건을 크기 순으로 오름차순이나 내림차순으로 나열하는 것이다. 방대한 양의 데이터를 쉽고 빠르게 정보를 찾기 위해 컴퓨터를 사용한다 이를 위한 기본적이고 중요한 알고리즘이 정렬이라고 할수 있다. [ 정렬의 기준 ] 정렬은 여러 가지 기준으로 나눌 수 있다. (1) “효율적이지만 구현이 어려움 vs 비효율적이지만 구현 쉬움” 예를 들어, 퀵 정렬은 효율적이고 빠르지만 구현이 어렵다. 반면, 버블 정렬은 구현이 쉽지만 비효율적인 방법이고 느리다. (2) “안정성을 보장하는가” 안정성은 중복된 key값이 있다면 상대적인 순서가 보장되는 것이다. 예를 들어, 버블 정렬은 같은 "5"라는 숫자도 상대적인 순서를 구분해준다. 즉, 앞에 있는 5와 뒤에 있는 5를 구별한다. 하지만, 삽입정렬..
Chap 5-3. 편집거리 (Edit Distance) [편집거리 (Edit Distance)] = 삽입 (insert), 삭제 (delete), 대체 (substitute) 연산을 사용하여 스트링(문자열) S를 수정하여 다른 스트링 T로 변환하고자 할 때 필요한 최소의 편집 연산 횟수 즉, 3개의 연산(삽입, 삭제, 대체)을 통해 다른 문자열로 변환이 가능하다. [예시 strong -> stone] strong을 stone으로 바꿔보자 2가지 방법이 가능하다. 방법 1 ) 순서대로 s, t는 그대로 두고 o를 삽입하고 r, o를 삭제한다. n은 그대로 두고 g를 e로 바꾼다. ⇒ 총 4회의 편집 연산을 했다. 방법 2) ‘s’와 ‘t’는 그대로 사용한 후, ‘r’을 삭제하고, ‘o’와 ‘n’을 그대로 사용한 후, ‘g’를 ‘e’로 대체하여, 총 2회의 편집..
Chap 5-2.연속 행렬 곱셈 연속 행렬 곱셈(Chained Matrix Multiplication) 문제 = 연속된 행렬들의 곱셈에 필요한 원소 간의 최소 곱셈 횟수를 찾는 문제 행렬 곱셈 (1) 두 행렬의 곱셈이란? 두 행렬 A, B가 있다. A = 10 x 20 B = 20 x 5 라면 총 곱셈의 횟수 = 10 * 20 * 5 = 1000이다. (2) 3개의 행렬 곱셈 A = 10 x 20 B = 20 x 5 C = 5 x 15 행렬의 곱셈은 결합법칙 성립하므로 (A* B) * C , A * ( B * C) 이 둘 다 성립한다. 하지만 둘의 결과값는 같지만 곱셈의 횟수는 전자가 더 적다.(과정이 다르다) [ 행렬 곱셈의 주의점 ] 주어진 행렬의 순서를 지켜서 “반드시 이웃하는 행렬끼리” 곱해야 한다. 동적 알고리즘 적용 (1) ..
Chap 5. 동적 계획 알고리즘 Dynamic Programming(DP) 알고리즘 -입력 크기가 작은 부분 문제들을 해결한 후에 -그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결해어 -최종적으로 원래 주어진 입력의 문제를 해결 [문제] n개의 원소를 갖는 문제 같은 형태로 문제를 해결해나가지만 n개보다 작은 값으로 (작은 문제로 ) 만들어서 푸는 방법 (1) 최적의 하위구조 특성 k < n 인 k개의 원소를 갖는 문제를 정의하고 문제를 풀었더니 그것이 최적의 풀이법이고 점점점 작은 문제들을 결합해서 최종 풀이법이 완성되어지는 형태의 특성을 갖는 문제를 “최적의 하위구조 특성을 갖는 문제”라고 부른다. 예시) 두 도시를 자동차로 갈 수 있는 최단 경로 A도시 B도시 C도시가 있는데 A에서 C로 가기 위해서는 A-B의 최단 경로를..
Chap 4-7. 허프만 압축 파일을 저장할 때 최대한 작게 저장하는 것이 효율적일 것이다. 데이터 압축 문제는 데이터를 코드화하는 효율적인 방법을 찾는 것이다. (1) 허프만 코드라고 하는 코드화 방식 (2) 주어진 파일을 허프만 코드화하는 탐욕적인 알고리즘 파일은 기본적으로 이진코드를 사용해서 표현한다. 코드화 방식에서 각각의 문자는 코드워드라고 하는 유일한 이진 문자열로 각 문자를 표현한다. 이 중 길이가 고정된 이진 코드는 각각의 문자를 표현하는 bps가 일정하다. 예를 들어 a, b, c를 코드화한다. a : 00, b: 01, c:11 ababcbbbc ⇒ 000100011101010111 (18비트가 필요함) 그러나 길이가 변하는 이진 코드를 사용하면 좀 더 효율적인 코드화 방식을 사용할 수 있다. → 각 문자를 다른 길..
Chap4-4. 부분 배낭 문제 배낭 문제란? 배경 = 물건 n개의 집합 S = {1, 2, 3, 4, ..., n}이 있고 물건 무게 W = {W1, W2, W3..., Wn}, 물건을 팔았을 때의 가치(이윤) P = {P1, P2, P3, ..., Pn }가 있다고 하자. 조건 = W은 물건 무게 이므로 Wi > 0이어야 한다. P도 Pi > 0이어야 한다. 자신이 배낭에 물건을 가지고 가서 시장에서 판다고 가정하자 배낭에 넣을 수 있는 무게는 제한되었다. 최대 무게를 M이라고 하자 1 ~ n까지의 Wi * Xi ≤ M 이면서 (x= 물건의 개수) 1 ~ n 까지의 Pi * Xi 를 최대화하는 방향을 찾아야 한다. • n개의 물건이 각각 1개씩 있고, • 각 물건은 무게와 가치를 가지고 있으며, • 배낭이 한정된 무게의 물건들을 담..
Chap 4. 그리디 알고리즘 그리디 알고리즘 그리디 알고리즘은 "최적화 문제를 해결하는 알고리즘" 최적화 (optimization) 문제 가능한 해들 중에서 가장 좋은 (최대 또는 최소) 해를 찾는 문제 욕심쟁이 방법, 탐욕적 방법, 탐욕 알고리즘 등으로 불림 그리디 알고리즘은 (입력) 데이터 간의 관계를 고려하지 않고 수행 과정에서 매 순간 ‘욕심내어’ 최소값 또는 최대값을 가진 데이터를 선택 이러한 선택을 ‘근시안적’인 선택이라고 말하기도 함 전체를 끝까지 보는 것이 아니라 해당 시점에서 최적의 선택을 계속적으로 누적하여 마지막 결과까지 진행하는 방법이므로 "근시안적" 이라고 표현함 그리디 알고리즘 방법 = 근시안적인 선택으로 부분적인 최적해를 찾고, 이들을 모아서(축적하여) 문제의 최적해(전역 해)를 얻는다. [특징] (1) ..

티스토리툴바