10. 최단경로 알고리즘(벨만포트, 다익스트라)
최단 경로 알고리즘아주 중요한 그래프 문제.엣지에 가중치가 부여된 상황에서 특정 노드에서 다른 노드로 가는 최적의 경로를 찾는 문제. 특징 노드 s에서 v까지 최단 경로 중 엣지(u, v)가 포함되면, 이 경로에서 s부터 u까지 부분도 역시 최단 경로다.M(v)를 s에서 v까지 최단 경로라고 길이라고 하면,M(V) = M(u)+min(u,v)
Category: Data Structure
9. 그래프
그래프G = (V, E)V = vertex set, E = edge set동그라미가 버택스(혹은 노드), 버택스를 잇는 링크를 엣지라 한다. degree(분지수) 어떤 노드의 이웃한 노드 갯수.어떤 그래프의 분지수는 그 그래프의 최대 분지수를 말한다. 인접하다는 의미는 두 노드가 링크로 서로 연결 되어있는 상태를 말한다. 경로는
8. 균형이진탐색트리
균형이진탐색트로(BST)?이진트리는 search, insert, delete 연산들이 O(h) 시간이 걸린다는 걸 기억하자. 즉 이 연산들을 효율적으로 하려면 트리의 높이를 최소화해야 한다.이진트리에서 빼곡히 노드를 채워넣어 높이를 최소로 하면 대략 log n 정도가 되는데,균형이진탐색트리는 노드를 최대한 채워넣어 높이를 log n이 되도록 유지하는 자료구
7. 힙
힙힙을 알기 위해서는 트리에 대한 기본적인 지식이 필요하다. 힙의 특성어떤 특정 값을 찾아내는 기능은 지원하지 않지만,값을 삽입하고, 최대값(최소값)을 찾거나 삭제하는데 큰 강점을 가진 자료구조.만약 최소값을 찾거나 삭제하고 싶으면 힙성질을 반대로 설정하면 된다. 간단한 용어 설명 트리 표현법 표현법 1:level 0 부터 해당 노드 자리에 노드가 있
6. 이진트리
이진트리? 자식노드가 최대 2개 뿐인 트리를 이진트리라 한다!! 1234567891011121314class Node: def __init__(self, key, parent=None, left=None, right=None): self.key = key self.parent = parent self.left =
5. 스택과큐
a. 스택 Stack차례대로 삽입하고 최근에 저장된 값을 삭제(FILO) push스택에 값 추가pop가장 나중에 push된 값을 스택에서 제거하고 반환top가장 나중에 push된 값을 제거하지 않고 반환__len__스택의 저장된 요소 갯수를 반환isEmpty스택에 요소가 존재하는지 참거짓 1234567891011121314151617181920212223
4. 해쉬테이블
a. 해시테이블해시 테이블은 일종의 정보를 저장하는 서랍장. a는 2층에 b는 3층에 c는 1층에 넣어두는 방식…b를 보고 싶으면 어떤 서랍에 넣었는지 알아내서, 3층 서랍에 있는 내용 중에 b와 일치하는 것을 찾는 것. 해시테이블은 삽입, 삭제, 검색 연산을 빨리 처리할 수 있다. 만약 순서대로 정보를 서랍장에 넣었을 경우, 어떤 정보를 찾으려 할 때 일
3. 양방향리스트
a. 왜 양방향 연결 리스트가 필요한가?한방향 연결 리스트는 다음 노드를 연결하는 링크만 존재, 이전 노드를 알려면 head부터 다시 탐색을 해야된다… 이런 불필요한 연산을 줄이고자 이전 노드를 연결하는 링크가 있는 양방향 연결 리스트를 구현하고자 한다. 양방향 연결 리스트의 주요 개념은 다음과 같다. 이전 노드로의 링크(prev)를 포함해 이전 노드로 이
2. 배열과리스트
a. 배열(array)데이터를 연속적인 메모리 공간에 저장 주소를 통해 매우 빠르게 접근 배열의 시작 주소, 저장된 값의 종류, 인덱스 세가지 정보로 원하는 값의 주소를 계산 가능. 읽기와 쓰기 연산에 O(1)시간이 걸림 고정된 길이를 가지며, 읽기와 쓰기만 지원하는 경우가 많다. b. 리스트 (파이썬)c의 배열에는 실제 데이터가 저장된 형식이지만, py
1. 연결리스트
a. 연결리스트 기본 개념연결리스트는 노드가 링크에 의해 기차처럼 연결된 순차 자료구조. 노드는 실제 값을 가지고 있는 data 정보와 인접 노드로 향하는 link 정보로 구성된 클래스로 구현한다. 다른 값에 접근하려면 링크에 따라 원하는 노드의 데이터에 접근한다. 다만, 배열처럼 index로 접근할 수 없다. 어떤 값을 찾으려면 처음부터 순차적으로 찾아야