본문 바로가기

두두의 알고리즘/공부

 (21)
[자료구조/알고리즘] 주요 지식 1. 배열과 링크드 리스트의 장단점에 대해 간략히 설명해주세요 2. BST의 최악의 시간 복잡도와 최악의 시간이 걸리는 케이스에 대해 설명해주세요 3. 해쉬 테이블에 대해 설명해주세요 4. Fibonacci 공식을 recursive와 dynamic programming으로 구현시 차이점에 대해 설명해주세요 5. DFS와 BFS에 대해 간략히 설명해주세요
[알고리즘] 백 트랙킹(Back Tracking) - N Queen 문제 백 트래킹 (backtracking) 백트래킹 (backtracking) 또는 퇴각 검색 (backtrack)으로 부름 제약 조건 만족 문제 (Constraint Satisfaction Problem) 에서 해를 찾기 위한 전략** 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack (다시는 이 후보군을 체크하지 않을 것을 표기)하고, 바로 다른 후보군으로 넘어가며, 결국 최적의 해를 찾는 방법 실제 구현시, 고려할 수 있는 모든 경우의 수 (후보군)를 상태공간트리(State Space Tree)를 통해 표현** 각 후보군을 DFS 방식으로 확인** 상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 해의 후보가 될만한..
[자료구조] 힙(Heap) - 기본코드 / 라이브러리 1. 힙 (Heap) 이란? - 힙: 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) - 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 - 힙을 사용하는 이유 - 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n) 이 걸림 - 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면, $ O(log n) $ 이 걸림 - 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨 5. 힙 (Heap) 시간 복잡도 - depth (트리의 높이) 를 h라고 표기한다면, - n개의 노드를 가지는 heap 에 데이터 삽입 또는 삭제시, 최악의 경우 root 노드에서 le..
[자료구조] 트리(Tree) - 이진 탐색 트리 1. 트리 (Tree) 구조 - 트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 - 실제로 어디에 많이 사용되나? - 트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨 2. 알아둘 용어 - Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함) - Root Node: 트리 맨 위에 있는 노드 - Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 - Parent Node: 어떤 노드의 다음 레벨에 연결된 노드 - Child Node: 어떤 노드의 상위 레벨에 연결된 노드 - Leaf Node (Termin..
[자료구조/알고리즘] 연결 리스트(Linked List), 더블 연결 리스트(Double Linked List), 트라이 구조(Trie) 리스트란? 데이터를 인덱스 값에 따라 저장 대량의 데이터에서 추가와 삭제 시 성능이 저하된다. 연결 리스트란? 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 데이터를 저장하는 자료 구조 [링크드 리스트 (Linked List) 구조] * 연결 리스트라고도 함 * 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조 * 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조 본래 C언어에서는 주요한 데이터 구조이지만, 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원' [링크드 리스트 기본 구조와 용어] - 노드(Node): 데이터 저장 단위 (데이터값, 포인터) 로 구성 - 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보..
[자료구조 / 알고리즘] 개념, 연습 방법 자료구조란? 용어: 자료구조, 데이터 구조, data structure 대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조를 의미 현실세계 정보를 어떻게 데이터로 변환해서 구조를 만드느냐 코드상에서 효율적으로 데이터를 처리하기 위해, 데이터 특성에 따라, 체계적으로 데이터를 구조화해 야 함 어떤 데이터 구조를 사용하느냐에 따라, 코드 효율이 달라짐 [효율적으로 데이터를 관리하는 예] 우편번호: 5자리 우편번호로 국가의 기초구역을 제공 학생 관리: 학년, 반, 번호를 학생에게 부여해서, 학생부를 관리 [대표적인 자료구조] 배열, 스택, 큐, 링크드 리스트, 해쉬 테이블, 힙 등 현실 세계의 가장 대표적인 데이터 구조? - 사전 알고리즘이란? 용어: 알고리즘, algorithm 어떤 문제를 풀기 위한 ..
[알고리즘] BFS(넓이 우선 탐색) / DFS(깊이 우선 탐색) 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 간선 정보를 저장하기 위해 O(V^2)만큼의 메모리 공간 필요 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용 : O(1) V : 노드 0 1 2 #노드 번호 0 0 7 5 #거리 1 7 0 ~ 2 5 ~ 0 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식 간선 정보를 저장하기 위해 O(E)만큼의 메모리 공간 필요 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용 : O(V) E : 간선 graph = [[] for _ in range(노드개수)] graph[0].append((노드번호, 노드거리)) graph[0].append((노드번호, 노드거리)) graph[1].append((노드번호, 노드거리..
[알고리즘] 소수의 판별 / 투 포인터 / 구간 합 계산 / 순열과 조합 소수의 판별 [특정 숫자 소수 판별] 제곱근 사용. 시간 복잡도 : O(X^1/2) import math def is_prime_number(x): for i in range(2,int(math.sqrt(x))+1): if x%i==0: return False #소수 아님 return True #소수 is_prime_number(숫자) [특정 범위 소수 판별 (에라토스테네스의 체)] 시간 복잡도 : O(NloglogN). 메모리를 많이 필요하기 때문에 N이 1,000,000 이내여야 함 2부터 N까지의 모든 자연수를 나열한다. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다 남은 수 중에서 i의 배수를 모두 제거한다(i는 제거하지 않는다) 더 이상 반복할 수 없을 때까지 2번과 3번의 과정..
LIST

티스토리툴바