Algorithm44 Chapter 18. 탐욕 알고리즘의 이해 탐욕 알고리즘의 이해 1. 탐욕 알고리즘 이란? Greedy algorithm 또는 탐욕 알고리즘 이라고 불리움 최적의 해에 가까운 값을 구하기 위해 사용됨 여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종적인 값을 구하는 방식 2. 탐욕 알고리즘 예 문제1: 동전 문제 지불해야 하는 값이 4720원 일 때 1원 50원 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오. 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 가능 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨 coin_list = [1, 100, 50, 500] print (coin_list) coin_list.sort(reverse=Tr.. 2020. 7. 22. Chapter 17-2. 너비우선탐색(BFS) 너비 우선 탐색 (Breadth-First Search) 1. BFS 와 DFS 란? 대표적인 그래프 탐색 알고리즘 너비 우선 탐색 (Breadth First Search): 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식 깊이 우선 탐색 (Depth First Search): 정점의 자식들을 먼저 탐색하는 방식 BFS/DFS 방식 이해를 위한 예제 BFS 방식: A - B - C - D - G - H - I - E - F - J 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 순회함 DFS 방식: A - B - D - E - F - C - G - H - I - J 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타.. 2020. 7. 22. Chapter 17-1. 깊이우선탐색(DFS) 깊이 우선 탐색 (Depth-First Search) 1. BFS 와 DFS 란? 대표적인 그래프 탐색 알고리즘 너비 우선 탐색 (Breadth First Search): 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식 깊이 우선 탐색 (Depth First Search): 정점의 자식들을 먼저 탐색하는 방식 BFS/DFS 방식 이해를 위한 예제 BFS 방식: A - B - C - D - G - H - I - E - F - J 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 순회함 DFS 방식: A - B - D - E - F - C - G - H - I - J 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 .. 2020. 7. 22. Chapter 16. 그래프 이해 그래프 이해 1. 그래프 (Graph) 란? 그래프는 실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node) 와 간선(Edge)로 표현하기 위해 사용 예제 집에서 회사로 가는 경로를 그래프로 표현한 예 2. 그래프 (Graph) 관련 용어 노드 (Node): 위치를 말함, 정점(Vertex)라고도 함 간선 (Edge): 위치 간의 관계를 표시한 선으로 노드를 연결한 선이라고 보면 됨 (link 또는 branch 라고도 함) 인접 정점 (Adjacent Vertex) : 간선으로 직접 연결된 정점(또는 노드) 참고 용어 정점의 차수 (Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수 (In-Degree): 방향 그래프에서 외부에서 오는 간선의 수 진출 차수 (Out.. 2020. 7. 22. Chapter 15-2. 이진 탐색 탐색 알고리즘2: 이진 탐색 (Binary Search) 1. 이진 탐색 (Binary Search) 이란? 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법 다음 문제를 먼저 생각해보자 이진 탐색의 이해 (순차 탐색과 비교하며 이해하기) [저작자] by penjee.com 이미지 출처 2. 분할 정복 알고리즘과 이진 탐색 분할 정복 알고리즘 (Divide and Conquer) Divide: 문제를 하나 또는 둘 이상으로 나눈다. Conquer: 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다. 이진 탐색 Divide: 리스트를 두 개의 서브 리스트로 나눈다. Comquer 검색할 숫자 (search) > 중간값 이면, 뒷 부분의 서브 리스트에서 .. 2020. 7. 22. Chapter 15-1. 순차 탐색 (Sequential Search) 탐색 알고리즘1: 순차 탐색 (Sequential Search) 1. 순차 탐색 (Sequential Search) 이란? 탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것을 의미 데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법 프로그래밍 연습 임의 리스트가 다음과 같이 rand_data_list로 있을 때, 원하는 데이터의 위치를 리턴하는 순차탐색 알고리즘 작성해보기 가장 기본적인 방법이므로, 직접 작성해보겠습니다. - 원하는 데이터가 리스트에 없을 경우 -1을 리턴 데이터 준비: data_list 10개 만들기 from random import * rand_data_list = list() for num in range(10): rand_data_list.appe.. 2020. 7. 20. Chapter 14-2. 퀵 정렬 (quick sort) 대표적인 정렬5: 퀵 정렬 (quick sort) 1. 퀵 정렬 (quick sort) 이란? 정렬 알고리즘의 꽃 기준점(pivot 이라고 부름)을 정해서, 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right) 으로 모으는 함수를 작성함 각 왼쪽(left), 오른쪽(right)은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복함 함수는 왼쪽(left) + 기준점(pivot) + 오른쪽(right) 을 리턴함 2. 어떻게 코드로 만들까? 퀵소트 알고리즘에 대해서는 위에서 언급이 되었으므로, 이를 구현하기 위한 세부 코드에 대해 연습을 통해 이해합니다. 프로그래밍 연습 다음 리스트를 리스트 슬라이싱(예 [:2])을 이용해서 세 개로 짤라서 각 리스트 변수에 넣고 출력해보기.. 2020. 7. 20. Chapter 14-1. 병합 정렬 (merge sort) 대표적인 정렬4: 병합 정렬 (merge sort) 1. 병합 정렬 (merge sort) 재귀용법을 활용한 정렬 알고리즘 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 직접 눈으로 보면 더 이해가 쉽다: https://visualgo.net/en/sorting 출처: 위키피디아 2. 알고리즘 이해 데이터가 네 개 일때 (데이터 갯수에 따라 복잡도가 떨어지는 것은 아니므로, 네 개로 바로 로직을 이해해보자.) 예: data_list = [1, 9, 3, 2] 먼저 [1, 9], [3, 2] 로 나누고 다시 앞 부분은 [1], [9] 로 나누고 다시 정렬해서 합친다. [1,.. 2020. 7. 20. Chapter 13. 동적 계획법(Dynamic Programming)과 분할 정복 (Divide and Conquer) 동적 계획법 (Dynamic Programming)과 분할 정복 (Divide and Conquer) 1. 정의 동적계획법 (DP 라고 많이 부름) 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식 Memoization 기법을 사용함 Memoization (메모이제이션) 이란: 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술 문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용됨 예: 피보나치 수열 분할 정복 문제를 나눌 수.. 2020. 7. 20. Chapter 12. 재귀 용법(recursive call, 재귀 호출) 재귀 용법 (recursive call, 재귀 호출) 고급 정렬 알고리즘엥서 재귀 용법을 사용하므로, 고급 정렬 알고리즘을 익히기 전에 재귀 용법을 먼저 익히기로 합니다. 1. 재귀 용법 (recursive call, 재귀 호출) 함수 안에서 동일한 함수를 호출하는 형태 여러 알고리즘 작성시 사용되므로, 익숙해져야 함 2. 재귀 용법 이해 예제를 풀어보며, 재귀 용법을 이해해보기 예제 팩토리얼을 구하는 알고리즘을 Recursive Call 을 활용해서 알고리즘 작성하기 예제 - 분석하기 간단한 경우부터 생각해보기 2! = 1 X 2 3! = 1 X 2 X 3 4! = 1 X 2 X 3 X 4 = 4 X 3! 규칙이 보임: n! = n X (n - 1)! 함수를 하나 만든다. 함수(n) 은 n > 1 이면.. 2020. 7. 20. Chapter 11-3 선택 정렬 (selection sort) 대표적인 정렬3: 선택 정렬 (selection sort) 1. 선택 정렬 (selection sort) 란? 다음과 같은 순서를 반복하며 정렬하는 알고리즘 주어진 데이터 중, 최소값을 찾음 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함 직접 눈으로 보면 더 이해가 쉽다: https://visualgo.net/en/sorting 출처: https://en.wikipedia.org/wiki/Selection_sort 2. 어떻게 코드로 만들까? 데이터가 두 개 일때 예: dataList = [9, 1] data_list[0] > data_list[1] 이므로 data_list[0] 값과 data_ list[1] 값을 교환 데이터가 세 개 일때 .. 2020. 7. 20. Chapter 11-2 삽입 정렬 (insertion sort) 대표적인 정렬2: 삽입 정렬 (insertion sort) 1. 삽입 정렬 (insertion sort) 란? 삽입 정렬은 두 번째 인덱스부터 시작 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사 이를 key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동 직접 눈으로 보면 더 이해가 쉽다: https://visualgo.net/en/sorting 출처: https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif for index in range(10, 1, -1): print (index) output: 10 9 8 7 6 5 4 .. 2020. 7. 20. Chapter 11-1 버블정렬(Bubble sort) 대표적인 정렬1: 버블 정렬 (bubble sort) 0. 알고리즘 연습 방법 알고리즘을 잘 작성하기 위해서는 잘 작성된 알고리즘을 이해하고, 스스로 만들어봐야 함 모사! 그림을 잘 그리기 위해서는 잘 그린 그림을 모방하는 것부터 시작 이번 챕터부터 알고리즘 시작입니다.! 1. 연습장과 펜을 준비하자. 2. 알고리즘 문제를 읽고 분석한 후에, 3. 간단하게 테스트용으로 매우 간단한 경우부터 복잡한 경우 순서대로 생각해보면서, 연습장과 펜을 이용하여 알고리즘을 생각해본다. 4. 가능한 알고리즘이 보인다면, 구현할 알고리즘을 세부 항목으로 나누고, 문장으로 세부 항목을 나누어서 적어본다. 5. 코드화하기 위해, 데이터 구조 또는 사용할 변수를 정리하고, 6. 각 문장을 코드 레벨로 적는다. 7. 데이터 구조.. 2020. 7. 20. Chapter 11. 공간복잡도 참고: 공간 복잡도 알고리즘 계산 복잡도는 다음 두 가지 척도로 표현될 수 있음 시간 복잡도: 얼마나 빠르게 실행되는지 공간 복잡도: 얼마나 많은 저장 공간이 필요한지 좋은 알고리즘은 실행 시간도 짧고, 저장 공간도 적게 쓰는 알고리즘 통상 둘 다를 만족시키기는 어려움 시간과 공간은 반비례적 경향이 있음 최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선 그래서! 알고리즘은 시간 복잡도가 중심 공간 복잡도 대략적인 계산은 필요함 기존 알고리즘 문제는 예전에 공간 복잡도도 고려되어야할 때 만들어진 경우가 많음 그래서 기존 알고리즘 문제에 시간 복잡도뿐만 아니라, 공간 복잡도 제약 사항이 있는 경우가 있음 또한, 기존 알고리즘 문제에 영향을 받아서, 면접시에도 공간 복잡도를 묻는 경우도.. 2020. 7. 20. Chapter 10. 힙(Heap) 대표적인 데이터 구조8: 힙 1. 힙 (Heap) 이란? 힙: 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 힙을 사용하는 이유 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n) 이 걸림 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면, $ O(log n) $ 이 걸림 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨 2. 힙 (Heap) 구조 힙은 최대값을 구하기 위한 구조 (최대 힙, Max Heap) 와, 최소값을 구하기 위한 구조 (최소 힙, Min Heap) 로 분류할 수 있음 힙은 다.. 2020. 7. 20. Chapter 09. 트리(Tree) 대표적인 데이터 구조7: 트리 1. 트리 (Tree) 구조 트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 실제로 어디에 많이 사용되나? 트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨 2. 알아둘 용어 Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함) Root Node: 트리 맨 위에 있는 노드 Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node: 어떤 노드의 다음 레벨에 연결된 노드 Child Node: 어떤 노드의 상위 레벨에 연결된 노드 Leaf Node (Termina.. 2020. 7. 20. Chapter 08. 해쉬 테이블(Hash Table) 대표적인 데이터 구조6: 해쉬 테이블 (Hash Table) 1. 해쉬 구조 Hash Table: 키(Key)에 데이터(Value)를 저장하는 데이터 구조 Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐 파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예: Key를 가지고 바로 데이터(Value)를 꺼냄 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법) 단, 파이썬에서는 해쉬를 별도 구현할 이유가 없음 - 딕셔너리 타입을 사용하면 됨 2. 알아둘 용어 해쉬(Hash): 임의 값을 고정 길이로 변환하는 것 해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 해싱 함수(Hashing.. 2020. 7. 20. Chapter 07. 시간 복잡도 알고리즘 복잡도 표현 방법 1. 알고리즘 복잡도 계산이 필요한 이유 하나의 문제를 푸는 알고리즘은 다양할 수 있음 정수의 절대값 구하기 1, -1 ->> 1 방법1: 정수값을 제곱한 값에 다시 루트를 씌우기 방법2: 정수가 음수인지 확인해서, 음수일 때만, -1을 곱하기 다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해, 복잡도를 정의하고 계산함 2. 알고리즘 복잡도 계산 항목 시간 복잡도: 알고리즘 실행 속도 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈 가장 중요한 시간 복잡도를 꼭 이해하고 계산할 수 있어야 함 알고리즘 시간 복잡도의 주요 요소 반복문이 지배합니다. 생각해보기: 자동차로 서울에서 부산을 가기 위해, 다음과 같이 항목을 나누었을 때, 가장 총 시간에 영향을 많이 미칠 것.. 2020. 7. 20. Chapter 06. 링크드 리스트(Linked List) 대표적인 데이터 구조: 링크드 리스트 (Linked List) 1. 링크드 리스트 (Linked List) 구조 연결 리스트라고도 함 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조 본래 C언어에서는 주요한 데이터 구조이지만, 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원 링크드 리스트 기본 구조와 용어 노드(Node): 데이터 저장 단위 (데이터값, 포인터) 로 구성 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간 * 일반적인 링크드 리스트 형태 (출처: wikipedia, https://en.wikipedia.org/wiki/Linked\_l.. 2020. 7. 20. Chapter 05. 스택(Stack) 꼭 알아둬야 할 자료 구조: 스택 (Stack) 데이터를 제한적으로 접근할 수 있는 구조 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조 큐: FIFO 정책 스택: LIFO 정책 1. 스택 구조 스택은 LIFO(Last In, Fisrt Out) 또는 FILO(First In, Last Out) 데이터 관리 방식을 따름 LIFO: 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책 FILO: 처음에 넣은 데이터를 가장 마지막에 추출하는 데이터 관리 정책 대표적인 스택의 활용 컴퓨터 내부의 프로세스 구조의 함수 동작 방식 주요 기능 push(): 데이터를 스택에 넣기 pop(): 데이터를 스택에서 꺼내기 Visualgo 사이트에서 시연.. 2020. 7. 20. 이전 1 2 3 다음 728x90 반응형
