트리
2021. 7. 20. 15:34
🕶 Algorithm/자료구조
트리 (Tree) 구조 트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 실제로 어디에 많이 사용되나? 트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨 알아둘 용어 Node : 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함) Root Node : 트리 맨 위에 있는 노드 Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node : 어떤 노드의 다음 레벨에 연결된 노드 Child Node : 어떤 노드의 상위 레벨에 연결된 노드 Leaf Node (Terminal Node) : Child No..
해쉬 테이블
2021. 7. 19. 17:20
🕶 Algorithm/자료구조
해쉬 구조 Hash Table: 키(Key)에 데이터(Value)를 저장하는 데이터 구조 Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐 파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예: Key를 가지고 바로 데이터(Value)를 꺼냄 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법) 단, 파이썬에서는 해쉬를 별도 구현할 이유가 없음 - 딕셔너리 타입을 사용하면 됨 알아둘 용어 해쉬(Hash) : 임의 값(방대한 데이터)을 고정 길이(ex. 256)로 변환하는 것 해쉬 테이블(Hash Table) : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 해싱 함수(Hashing Function) : Key(키를 ..
시간복잡도
2021. 7. 16. 18:55
🕶 Algorithm/자료구조
알고리즘 복잡도 계산이 필요한 이유 시간복잡도 : 알고리즘의 풀이 시간을 정략적으로 표기하는 방법 하나의 문제를 푸는 알고리즘은 다양할 수 있음. 즉, 풀이가 다양하다. 정수의 절대값 구하기 1, -1 ->> 1 방법1: 정수값을 제곱한 값에 다시 루트를 씌우기 방법2: 정수가 음수인지 확인해서, 음수일 때만, -1을 곱하기 다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해, 복잡도를 정의하고 계산함 알고리즘 복잡도 계산 항목 시간 복잡도: 알고리즘 실행 속도 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈 가장 중요한 시간 복잡도를 꼭 이해하고 계산할 수 있어야 함 알고리즘 시간 복잡도의 주요 요소 반복문을 가지고 시간복잡도를 계산한다. 시간이 어디에서 제일 많이 걸리느냐를 보면 반복문이다..
연결 리스트 (Linked List)
2021. 7. 16. 11:31
🕶 Algorithm/자료구조
연결 리스트(Linked List) Linked List 구조 연결 리스트라고도 함 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조 연결 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조 본래 C언어에서는 주요한 데이터 구조이지만, 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원 미리 데이터 크기를 예약해 놓지 않고, 필요할 때마다 추가추가 하는 것 : 배열의 단점을 극복한 구조 Linked List 기본 구조와 용어 노드(Node): 데이터 저장 단위 (데이터값, 포인터) 로 구성 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간 * 일반적인 링크드 리스트 형태 파이썬에서 링크드 리스트 구현시 class..
자료구조, 알고리즘, 배열, 스택, 큐
2021. 7. 15. 11:31
🕶 Algorithm/자료구조
자료구조 대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조를 의미 대표적인 자료구조 : 배열, 스택, 큐, 링크드 리스트, 해쉬 테이블, 힙 등 알고리즘 어떤 문제에 대해, 특정한 '입력'을 넣으면, 원하는 '출력'을 얻을 수 있도록 만드는 프로그래밍 얼마나 시간이 걸리느냐, 얼마나 메모리를 차지하느냐가 주 요소 따라서 코드를 짰을 때 얼마나 메모리를 차지하고 얼마나 시간이 걸렸는지 알고 있어야 한다. 자료구조와 알고리즘이 중요한 이유 어떤 자료구조와 알고리즘을 쓰느냐에 따라, 성능이 천지차이이다. 배열(Array) 데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조 유사한 데이터를 연결된 데이터 공간에 넣을 수 있다. 파이썬에서는 리스트 타입이 배열의 기능을 제공한다. 배열이..
NP hard
2020. 6. 21. 22:04
🕶 Algorithm/알고리즘
결정론적 튜링기계 : 한 방향으로 문제를 해결하는 기계 다항시간 : 다항식으로 표현될 수 있는 시간. 다항식안의 미지수 : 알고리즘의 입력 크기 4 2 3 1 -> 2 4 3 1 -> 2 3 4 1 -> 2 3 1 4 -> 2 3 1 4 -> 2 1 3 4 -> 2 1 3 4 -> 1 2 3 4 (n-1) + (n-2) + .. + 1 = (n-1)(n)/2 주어지는 숫자의 개수 : 입력 크기 P 문제 : 알고리즘 속도가 다항식으로 표현되는 문제들 (Polynomial) , 쉬운 문제 NP 문제 : 다항식으로 표현될 수 있는지 여부가 알려지지 않은 문제들 (Non-deterministic Polynomial), 어려운 문제 결정형 문제 결정형 문제(decision problem)란 그 답이 'yes’와 ..
Backtracking
2020. 6. 8. 17:32
🕶 Algorithm/알고리즘
체스판을 대각선 방향으로 놓지 않도록 모든 행마다 하나씩 놓는다. 앞으로 가다가 막히면 옆으로 가고 옆에도 막혀있으면 뒤로가는 방법. (2,4,1,3) 으로 표현할 수 있다. 트리 형태로 Backtracking(퇴각검색)을 설명할 수도 있다. 다 놓아보고 찾는게 아니라 하나씩 놓으면서 우회하는 방법이므로 시간을 절약할 수 있다. Pruning(가지치기) 라고도 한다. v = 스타트 노드 recursion으로 한다. queens를 recursion 한다. 위에서 배운 tree를 만드는 것은 아니다. column 이라는 그저 길이 4짜리 배열을 하나 만든다. (a) 1 / / / (b) 1 / 3 / / (c) 1 / 3 / x / x (d) 1 / 4 / / (e) 1 / 4 / 2 / promising(..
Greedy Algorithm
2020. 5. 18. 17:29
🕶 Algorithm/알고리즘
동적 프로그래밍과 함께 최적화 문제의 해결에 많이 사용된다. 문제 해결을 위해 데이터를 선택할 때, 그 순간에 가장 최고인 것을 선택한다. 지역적으로는 최적이지만 전체적인 최적은 확신할 수 없다. 알고리즘이 항상 최적해를 주는지 확인이 필요하다. Greedy Algorithm 적용 단계 선택 과정(Selction procdure) : 현재 상태에서 최선인 답을 찾아 해답에 포함한다. 적정성 검사(Feasibilty check) : 새로 결정된 해답들이 적정한지 검사한다. 해답 점검(Solution check) : 새로 얻은 해답들이 최적인지 검사한다. 배낭 문제 (Knapsack Problem) n개의 물건과 배낭이 있다고 가정하자. 각각의 물건에는 무게와 가치가 주어진다. 배낭에 물건을 넣을 때, 그 ..