저장소

1. 순차 탐색(Sequential Search) 탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것을 의미 데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법 1. 이진 탐색(Binary Search) 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방 1-1. 이진 탐색과 순차 탐색의 비교 2. 분할 정복 알고리즘과 이진 탐색 분할 정복 알고리즘 divide : 문제를 하나 또는 둘 이상으로 나눔 conquer : 나눠진 문제가 충분히 작고 해결이 가능하면 해결하고, 그렇지 않으면 다시 나눔 이진 탐색 divide : 리스트를 두 개의 서브 리스트로 나눔 conquer : 검색할 숫자 > 증가값 : 뒷 부분의 서브 리스트에서 검색힐 숫자를 찾음 검색할 ..

1. 분할 정복(Division Conquer) 문제를 나눌 수 없을 떄까지 나누어서 각각을 풀면서 다시 병합하여 문제의 답을 얻는 알고리즘 하향식 접근방법으로 상위의 해당을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식(재귀함구로 구현) 문제를 잘게 쪼갤때 부분 문제는 서로 중복되지 않음 Memorization 기법을 사용하지 않음 2. 대표적인 분할 정복 알고리즘 : 퀵 정렬(quick sort 정렬 알고리즘의 꽃(고급 알고리즘) 기준점(pivot)을 정해서 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 작성 각 왼쪽, 오른쪽은 재귀용법으로 사용해 다시 동일 함수로 호출하여 위 작업을 반복함 2-1. 퀵 정렬 알고리즘 구현 리스트 개수가 1개면 해당 리스트를 리턴 리..

1. 동적 계획법(Dynamic Programming) 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분의 값을 활용해서 보다 큰 크기의 부분 문제를 해결함 상향식 접근법(최하위 해답을 구한 후 해당 결과를 이용해서 상위 문제를 풀어가는 방식) 프로그램 실행 시 이전의 계산한 값을 저장하여 다시 계산하지 않도록 전체 실행 속도를 빠르게 하는 기술(메모이제이션 : Memoization)을 사용 문제를 잘게 쪼갤 때, 부분 문제는 중복되기 때문에 재활용 2. 동적 계획법 알고리즘 피보나치 수열 n을 입력받아서 아래와 같이 계산 피보나치 수열 함수흫 '피보나치' fibonacci(0) : 0 fibonacci(1) : 1 fibonacci(2) : 1 fibonacci(3) : 2 fibonacci(4)..

1. 재귀호출(recusive call) 함수 안에서 동일한 함수를 호출하는 형태 여러 알고리즘, 고급 정렬 알고히즘 작성시 자주 사용됨 1-1. 재귀 호출 분석 2! = 1 * 2 3! = 1 * 2 * 3 4! = 1 * 2 * 3 * 4 = 3! * 4 1-2. 규칙 n! = n * (n-1)! 함수로 만들어 보자 함수(n)은 n=1 함수(n)은 n>1 이면 return n*함수(n-1) 1-3. 검증 2! 함수(2)이면 2>1 이므로 2 * 함수(1) 함수(1)은 1이므로 return 2 * 1, 답은 2 3! 함수(3)이면 3>1 이므로 3 * 함수(2) 함수(2)는 위 계산에 의해 2! 이므로 return 2*1 = 2 3 * 함수(2) = 3 * 2 = 3 * 2 * 1, 답은 6 4! 함수..

1. 정렬 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것 프로그램 개발 시 빈번하게 정렬을 필요로 함 다양한 알고리즘이 고안되었으며 알고리즘 학습의 필수사항 2. 버블 정렬(bubble sort) 두 인접한 데이터를 비교해서 앞에있는 데이터가 뒤에 있는 데이터보다 크면 (작으면) 자리를 바꾸는 정렬 알고리즘 3. 삽입 정렬(insertion sort) 인덱스(key)앞에 있는 데이터(A)부터 비교해서 key가 더 작으면(크면) 데이터(A)값을 뒤 인덱스로 복사 key가 더 큰 데이터를 만날 때까지 반복 큰 데이터를 만난 위치 바로 뒤에 key를 이동 4. 선택 정렬(selection sort) 주어진 데이터 중, 최소값을 찾음 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함 맨 앞의 위..

1. 알고리즘 복잡도 표현방법 1-1. 알고리즘 복잡도 계산이 필요한 이유 하나의 문제를 푸는 알고리즘은 다양함 * 정수의 절대값을 구하는 방법 * 방법1 : 값이 음수인지 확인해서 0보다 작은 음수일 때 -1을 곱하기 * 방법2 : 정수값을 재곱한 값에 루트를 씌우기 디양한 알고리즘 중 어떤 알고리즘이 더 좋은지 분석하기 위해 복잡도를 정의하고 계산함 1-2. 알고리즘 복잡도 계산 항목 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈 시간 복잡도 : 알고리즘 실행 속도 1-3. 알고리즘 성능 표기법 오메가 표기법 알고리즘 최상의 실행 시간을 표기 세타 표기법 알고리즘 평균 실행시간을 표기 빅오 표기법 최악의 실행 시간을 표기 아무리 최악의 상황이라도 이 정도의 성능은 보장함을 의미 가장 많이 사용 1..

1. 힙(Heap) 1-1. 힙 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 완전 이진 트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 1-2. 힙을 사용하는 이유 배열에 데이터를 넣고 최대값, 최소값을 찾으려면 시간이 많이 걸릴 수 있음 힙에 데이터를 넣고 최대값, 최소값을 찾으면 시간이 적게 소모됨 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현등에 활용됨 2. 힙(Heap) 구조 힙은 최대값을 구하기 위한 구조(최대힙, Max Heap)와 최소값을 구하기 위한 구조(최소 힙, Min Heap)로 분류할 수 있음 힙은 아래와 같이 두가지 조건을 가지고 있는 자료구조 각 노드의..

1. 트리(Tree) Node와 Branch를 이용해서 사이클을 이루지 않도록 구성한 데이터 구조 트리중 이진 트리(Binary Tree)형태의 구조로 탐색(검색)알고리즘을 구현을 위해 많이 사용됨 2. 알아둘 용어 Node: 트리에서 데이터를 저장하는 기본 요소(데이터와 다른 연결된 노드에 대한 Branch 정보를 포함) Root Node: 트리 맨 위에 있는 노드 Level: 최상위 노드를 Level 0으로 했을 때 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node: 어떤 노드의 상위 레벨에 연결된 노드 Child Node: 어떤 노드의 하위 레벨에 연결된 노드 Leaf Node: Child Node가 하나도 없는 노드 Sibling Node: 동일한 Parent Node를 가진 ..

1. 해쉬 테이블(Hash Table) 키(key)에 데이터(value)를 저장하는 데이터 구조 파이썬에서는 딕셔너리(dick)타입이 해쉬 테이블의 예 key를 통해 데이터를 바로 찾을 수 있으므로 검색 속도가 빠름 보통 배열로 미리 Hash Table 사이즈 만큼 생성 후에 사용 2. 알아둘 용어 해쉬(Hash) : 임의의 값을 고정 길이로 변환하는 것 해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 해쉬 함수(Hashing Function) : key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수 해쉬 값(Hash Values) 또는 해쉬 주소(Hash Address) : key를 해싱 하무로 연산해서 해쉬 값을 알아내고 이를 기반으로 해쉬 테이..

1. 더블 링크드 리스트(Doubly Linked List) 양뱡향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능 class Node: def __init__(self, data, prev=None, next=None): self.prev = prev self.data = data self.next = next class NodeMgmt: def __init__(self,data): self.head = Node(data) self.tail = self.head def insert(self,data): if self.head == None: self.head = Node(data) self.tail = self.head else: node = self.head while node.next: node..

1. 링크드리스트(Linked List) 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 구조 데이터의 삽입과 삭제가 매우 빠름 C언어에서는 중요한 자료구조지만, 파이썬에서는 리스트 타입이 링크드 리스트 역할도 모구 지원 1-1. 링크드 리스트의 용어 노드(node) : 데이터 저장 단위(데이터, 포인터)로 구성 포인터(pointer) : 각 노드 안에서 다음이나 이전의 노드와의 연결정보를 가지고 있는 공간 1-2. 링크드 리스트로 데이터 추가하기 1-3. 링크드 리스트 데이터 출력하기 문제 데이터 30과 40 사이에 35를 삽입하는 코드를 작성해보자 2. 객체지향 프로그래밍으로 링크드 리스트를 구현 추가 삭제

1. 스택(stack) 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 구조 LIFO(Last Input First Out) 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조 1-1. 스택의 구조 스택은 LIFO 또는 FILO 데이터 관리 방식 스택의 활용 : 컴퓨터 내부의 프로세스 구조의 함수 동작 방식 기능 push() : 데이터를 스택에 쌓기 pop() : 데이터를 스택에서 꺼내기 1-2. 스택의 장점 구조가 단순해서 이해와 구조가 쉬움 데이터 저장/읽기 속도가 빠름 데이터 최대 개수를 미리 정해야 함(파이썬의 쟝우 재귀함수는 1000번까지만 호출이 가능) 저장 공간의 낭비가 발생할 수 있음(미리 최대 개수만큼 저장공간을 미리 확보하기 때문) 스택은 단순하고 빠른 성능을 위해 사용하므로 보통 배열 ..

1. 큐(Queue) 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조 FIFO(First-In, First-out) 줄을 서는 행위와 유사 1-1. 큐의 사용 멀티테스킹을 위한 프로세스 스케쥴링 방식을 구현(운영체제) 푸시메세지 1-2. 큐의 용어 Enqueue : 큐에 데이터를 넣는 기능 Dequeue : 큐에 데이터를 꺼내는 기능 비쥬얼고 [https://visualgo.net/en/list?slide=1] 1-3. queue 라이브러리 활용 Queue(): 가장 일반적인 큐 자료구조를 생성 LifeQueue() : 나중에 입력된 데이터가 먼저 출력되는 구조(스택) PriorityQueue() : 데이터마다 우선순위를 넣어서 우선순위가 높은 순으로 데이터를 출력 ✔ 일반적인 Queue ✔ Pr..

1. 배열 데이터를 나열하고 각 데이터를 인덱스에 대응하도록 구성한 자료구조 파이썬 리스트 타입은 배열 기능을 제공 1-1. 배열이 필요한 이유 같은 종류의 데이터를 효율적으로 관리하기 위해 사용 같은 종류의 데이터를 순차적으로 저장 빠른 접근이 가능(인덱스 번호로 접근시) 1-2. 배열의 단점 데이터의 추가/삭제가 어렵다 미리 최대 길이를 설정해야 함 문제 dataset 배열에서 전체 이름안에 'M'이 몇번 나왔는지 빈도수를 출력해보자 dataset = ['Braund, Mr. Owen Harris', 'Cumings, Mrs. John Bradley (Florence Briggs Thayer)', 'Heikkinen, Miss. Laina', 'Futrelle, Mrs. Jacques Heath (L..

파이썬으로 자료구조와 알고리즘을 공부하기로 하였다. 1. 자료구조(data structure) 코드상에서 효율적으로 데이터를 처리하기 위해 데이터의 특징에 따라 체계적으로 구조화하여 저장 대표적인 자료구조는 배열, 스택, 링크드리스트, 해쉬테이블, 힙 등.... 2. 알고리즘(algorithm) 어떤 문제를 풀기 위한 절차 및 방법 입력을 넣으면 원하는 출력을 얻을 수 있도록 만든 프로그램 3. 자료구조와 알고리즘을 배우는 이유 어떤 자료구조와 알고리즘을 사용하느냐에 따라 프로그램의 성능 차이가 큼 4. 파이썬을 활용한 자료구조와 알고리즘 어떤 언어로든 자료구조와 알고리즘은 공부할 수 있음 예전에는 C언어 또는 C++로 작성하는 경우가 많았음 최근에는 언어로 인한 제약/평가는 없어짐 가장 쉽고 빠르게 자..