목록패스트캠퍼스 (9)
차밍이
[알고리즘] 패스트캠퍼스 알고리즘 학습 - 병합 정렬(Merge Sort)
1. 정의 재귀 용법을 활용한 정렬 알고리즘 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 2. 알고리즘 이해 이해를 돕기위한 예시 쪼개는 단계 [1, 9, 3, 2] > [1, 9] , [3, 2] > [1], [9], [3], [2] 더 이상 쪼갤 수 없으면 합병을 진행 작은 데이터를 앞에 큰 데이터를 뒤로 가도록 병합한다. [1], [9], [3], [2] > [1, 9], [2, 3] > [1, 2, 3, 9] 왼쪽 index 번호와, 오른쪽 index 번호를 활용해서 값을 비교해서 넣어가는 방식으로 진행하면 된다. 3. 코드 작성 데이터를 나누는 부분 & 데이터를..
[알고리즘] 패스트캠퍼스 알고리즘 학습 - 퀵 정렬(Quick Sort)
목차 1. 퀵 정렬 (Quick Sort) 이란? 정렬 알고리즘의 꽃 기준점(pivot이라 부름)을 정해서, 기준점보다 작은 데이터는 왼쪽, 크면 오른쪽으로 모으는 함수를 작성한다. 왼쪽과 오른쪽은 재귀 용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복한다. 함수는 왼쪽 + pivot + 오른쪽 을 출력한다. 분할 정복에 속하는 정렬이라고 할 수 있다. 2. 퀵 정렬 코드 작성 소스코드 data_list = [49, 97, 53, 5, 33, 65, 62, 51] def quick_sort(num_list): if len(num_list) >> [5, 33, 49, 51, 53, 62, 65, 97] 알고리즘 구현 및 풀이 quicksort 함수 만들기 만약 리스트 개수가 한 개이면 해당 리스트..
[알고리즘] 패스트캠퍼스 알고리즘 학습 - 동적 계획법과 분할 정복 with 피보나치
목차 1. 정의 동적계획법(Dynamic Programming) "DP"라고 많이 부름 큰 문제를 해결하기 위해, 작은 문제를 부분 부분 해결하여 저장해놓고 사용한다. 상향식 접근법으로 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과를 이용해서 상위 문제를 해결한다. Memoization 기법을 사용한다. 문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용된다. ex) 피보나치 수열 분할 정복(Divide and Conquer) 문제를 나눌 수 없을 때까지 나누어서 각각 문제를 풀면서 다시 합병하여 문제의 해답을 찾는다. 다시 합병한다. 하양식 접근법, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식 일반적으로 재귀 함수로 구현 문제를 잘게 쪼갤 때, 부분 문제는 서로..
[알고리즘] 패스트캠퍼스 알고리즘 학습 - 선택 정렬(Selection Sort)
1. 선택 정렬 이란? 주어진 데이터 중, 최솟값을 찾는다. 해당 최소값을 가장 맨 앞의 데이터의 위차와 교체한다. 맨 앞의 최소값 데이터를 제외한 나머지 데이터를 대상으로 동일한 방법을 반복한다. 2. 예제 코드 import random data_list = random.sample(range(100), 10) print(data_list, end="\n\n") for i in range(len(data_list)-1): index = i for j in range(len(data_list)-i): if data_list[index] > data_list[j+i]: index = j+i data_list[index], data_list[i] = data_list[i], data_list[index] p..
[알고리즘] 패스트캠퍼스 알고리즘 학습 - 버블정렬
버블 정렬 두 인접한 원소를 검사하면서 정렬하는 방법 앞에서부터 두 개의 데이터를 비교하면서 정렬한다. 한 번 실행하면 가장 큰 값이 가장 뒤로 정렬되는 방식이다. 두 번째 실행하면 그다음 큰 값이 가장 뒤에서 한번 전까지 데이터를 비교하며 정렬하게 된다. 시간 복잡도가 에 해당되므로 느리지만, 단순하다. data_list = [9, 7, 5, 3, 1] def bubbleSort(data_list): for i in range(len(data_list)): swap = False for j in range(len(data_list)-1-i): if data_list[j] > data_list[j+1]: swap = True data_list[j], data_list[j+1] = data_list[j+1..
목차 1. 삽입 정렬 방식 두 번째 인덱스에서부터 시작하여 데이터를 확인한다. 앞에 있는 데이터들과 하나씩 비교하면서 자신의 자리를 찾아나간다. 가장 작은 값이면 맨 앞까지 계속 이동한다. 혹은 자기보다 작은 데이터가 앞에 있으면 그 뒤쪽으로 데이터를 삽입한다. 2. 소스 코드 import random data_list = random.sample(range(100), 10) print(data_list) >>> [24, 62, 17, 81, 74, 55, 92, 93, 82, 53] 랜덤으로 정렬하기 위한 숫자 데이터 리스트를 생성한다. for i in range(1, len(data_list)): for j in range(i-1,-1,-1): if data_list[j] > data_list[j+1..
[알고리즘] 패스트캠퍼스 알고리즘 학습 정리 - 더블 링크드 리스트(Double Linked List)
목차 다양한 링크드 리스트 구조 1. 더블 링크드 리스트 (Doubly linked list) 더블 링크드 리스트 기본 구조 이중 연결 리스트라고도 함 단방향 링크드리스트인 경우 가장 끝 노드를 찾기 위해서는 처음부터 끝까지 모든 노드를 지나서 검색해야하는 한계가 있다. 데이터가 뒷쪽에 더 가깝다는 것을 안다면 뒤에서부터 검색하면 더 빠르게 접근할 수 있다. 장점 : 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능 단점 : 앞쪽 주소와 뒷쪽 주소를 모두 저장해야함. 저장 효율이 낮아진다.  (출처: wikipedia, https://en.wikipedia.org/wiki/Linked\..
[알고리즘] 패스트캠퍼스 알고리즘 학습 정리 - 링크드 리스트(Linked List)
목차 대표적인 데이터 구조: 링크드 리스트 (Linked List) 1. 링크드 리스트 (Linked List) 구조 연결 리스트라고도 함 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조 본래 C언어에서는 주요한 데이터 구조이지만, 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원 링크드 리스트 기본 구조와 용어 노드(Node): 데이터 저장 단위 (데이터 값, 포인터)로 구성 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간 배열의 단점 배열의 경우 미리 데이터의 길이를 선언해야한다. 선언한 길이만큼 공간을 미리 차지하고 있다. 데이터가 인덱스에 따..
[알고리즘] 패스트캠퍼스 알고리즘 학습 정리 - 자료구조란?
목차 자료구조란? 자료의 구조, 데이터의 구조 대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조를 의미한다. 코드상으로 얼마나 효율적으로 데이터를 처리하기위해 구조적으로작성하는가를 논하는 것 알고리즘이란? 어떤 문제를 풀기 위한 절차나 방법 자료구조와 알고리즘이 중요한 이유? 어떤 자료구조와 알고리즘을 쓰냐에 따라, 성능이 매우 크게 차이가 발생된다. 프로그래밍을 잘 할 수 있는 기술과 역량을 검증하는 척도로 사용된다. 배열 배열의 장점 데이터의 시작점만 알면 내부의 데이터들의 순서를 바로 알 수 있다. 순차적인 데이터를 손쉽게 다룰 수 있다. 빠르게 데이터에 접근 가능하다. 배열의 단점 데이터가 가변적인 경우 추가나 삭제가 쉽지 않음 최대 길이를 미리 지정해야함 큐 (Queue) 큐의 구조 FI..