전공 테트리스/자료구조 썸네일형 리스트형 [자료구조] 10. 그래프, BFS, DFS, 위상 정렬 1. 그래프 - 그래프란?- 그래프 관련 용어- 방향그래프- 무방향 그래프- 그래프의 구현 (인접행렬/ 인접 리스트 ) - 방향그래프 (Directed Graph)두 정점을 잇는 간선에 방향이 있는 그래프 - 무방향 그래프 (Undirected Graph)두 정점을 잇는 간선에 방향이 없는 그래프 - 그래프의 구현 (인접행렬; Adjacency Matrix)원소 = 1 : 0 ? 이어져있다 : 이어지지 않았다. 원소가 1이면 두 정점은 이어져있다.원소가 0이면 두 정점은 이어지지 않았다. # 무방향 그래프대각선을 기준으로 대칭을 이룸따라서... 간선 수 x 2 = 1의 개수 # 방향 그래프대칭을 이루지 않기 때문에(방향이 있으니... 당연히 대칭이 아님)간선 수 = 1의 개수 # 무방향 그래.. 더보기 [자료구조] 9. B-트리, 해쉬 테이블 1. B-트리 - B-트리란?- 원소삽입 - B-트리란?다음을 모두 만족하면 m차 B-트리a. 모든 리프노드의 깊이가 동일b. 노드 당 자식 수는 [m/2] ~ m개 (leaf 노드 제외) // [m/2] : 올림함수c. 자식 노드의 수는 데이터 수보다 +1 (leaf노드 제외) // 즉, m차 B-트리에서 노드 내 데이터 최대 수는 m-1개d. 단일 노드 내에서 데이터는 정렬됨e. 트리 관점에서도 데이터는 정렬됨 - 원소 삽입 데이터 수 제한을 넘어서지 않는 경우에서 삽입⁘ 탐색과 유사한 방법으로 새 데이터를 삽입할 적절한 리프 노드 선정⁘ 해당 리프 노드에 데이터가 추가될 여유가 있으면 그대로 삽입 데이터 수 제한을 초과하는 경우에서 삽입⁘ 리프 노드에 데이터 삽입될 여유가 없으면.. 더보기 [자료구조] 8. 이진탐색트리, AVL트리, 레드-블랙트리 1. 이진 탐색 트리 (Binary Search Tree) - 탐색트리란?- 이진탐색이란?- 이진탐색트리란?- 이진탐색트리 연산 (삽입, 삭제) - 탐색트리란탐색을 위한 트리 기반의 자료구조 * 트리 :연결그래프이자 Cycle을 가지지 않는 그래프* 연결그래프 : 모든 두 정점 사이에 경로가 존재하는 그래프* 순환 : 시작 정점과 종료 정점이 동일한 Path(같은 정점 및 간선이 중복되지 않은 walk) - 이진탐색이란정렬된 배열의 경우, 반을 쪼개서 탐색 - 이진탐색트리 (BST)아래 두 조건을 만족하는 이진트리a. 임의의 노드 좌측 서브트리에는 자신보다 작은 값만이 존재b. 임의의 노드 우측 서브트리에는 자신보다 큰 값만이 존재(오른쪽 서브트리 노드의 키값 Q. 이진탐색트리와 힙의 차이점 두.. 더보기 [자료구조] 7. 이진트리 구현, 데이터 순회 완전 이진트리 → 왼쪽부터 꽉꽉 차있기 때문에 “인덱스”를 통한 동적 할당이 가능함… (힙.. )‘경사 이진트리 → 중간중간에 듬성듬성 빈 칸이 많이 생겨서 인덱스를 통한 동적 할당으로의 구현이 어려움→ 그럼 이진 트리 구현 어떻게 하느냐? “양방향 linked list”를 통한 구현class node: def __init__(self, data, prev, next): self.data = data self.prev = prev self.next = next def insert(value, position): new_node = node(value, position, position.next) new_node.prev.next = new_node new_node.next.prev = new.. 더보기 [자료구조] 6. 트리, 힙, 우선순위 큐 선형 자료구조 → linked list(단방향, 양방향), 스택, 큐모든 상황을 표현해 낼 수 없다는 단점비선형 자료구조 → 그래프, 트리[선형]이란 데이터 요소들이 순차적으로 나열되어있는 구조[비선형]이란 상하관계, 계층적 구조[보행]특정 정점에서 다른 정점으로 갈 때 거치는 정점과 간선의 나열[닫힌 보행] - 시작 정점과 종료 정점이 동일한 보행[열린 보행] - 시작 정점과 종료 정점이 다른 보행[경로] - 같은 정점 및 간선이 중복되지 않은 보행[사이클] - 시작 정점과 종료 정점이 동일한 경로닫힌 보행과 경로의 조건 모두 만족 [연결 그래프] - 모든 두 정점 사이에 경로가 존재하는 그래프[그래프] - 정점과 간선으로 이루어짐 (연결되어 있는 대상 간의 관계를 표현하는 자료구조)[트리] - 연결그.. 더보기 [자료구조] 5. Circle queue (원형 큐) 큐덱 큐(queue) 선입선출의 자료구조.. FIFO… First In First Out즉 대기열임 .. 기다리는 순서대로 나가니까..front.. 전단 ~~~~~ rear… 후단삭제하는 곳 들어오는 곳큐의 연산 5가지enqueue(e) : e를 후단에 삽입dequeue() : 전단에서 데이터 삭제isEmpty() : Empty면 True, 아니면 False 반환isFull() : Full이면 True, 아니면 False 반환peek() : 큐의 맨 앞 요소를 삭제하지 않고 !! 반환 동적배열을 이용함.. 단방향 linked 리스트→ del queue[0] 하면 전방에 있는 원소 삭제.. 스택은 top 원소 삭제→ peek… queue[0] 하면 전방의 원소 반환…class queue단점원소를 삭제할 .. 더보기 [자료구조] 4. 원형 linked 리스트, Stack 원형 linked 리스트스택 자료구조의 이해와 응용 원형 linked 리스트기존 linked 리스트의 한계 → 데이터 삭제의 경우, prev를 알아야 했음원형 linked 리스트는 첫 노드~ 마지막 노드를 연결한 자료구조장점** 마지막 노드를 참조하는 Last가 단방향 linked 리스트의 head 역할을 함→ 마지막 노드와 첫 노드를 O(1) 시간에 접근 가능하다는 장점→ 리스트가 Empty가 아니라면, 어떤 노드도 None을 갖지 않아 프로그램에서 None 조건 검사 안 해도 됨단점반대 방향으로 노드를 방문하기 쉽지 않음양방향 원형 linked 리스트양방향 linked 리스트에서 첫 노드와 마지막 노드를 이어 만든 자료구조시간 복잡도 (단방향, 양방향, 원형 linked 리스트)삭입 및 삭제O(1)탐.. 더보기 [자료구조] 3. 시간복잡도 & 연결형 자료구조 1. 알고리즘의 성능 분석 알고리즘의 성능 분석실행시간 측정법알고리즘의 실제 실행 시간 측정하는 것알고리즘을 실제로 구현해야한다동일한 HW/ SW 환경 사용해야 한다알고리즘 복잡도 분석법직접 구현 x, 수행 시간 분석알고리즘이 수행하는 연산의 횟수를 측정하여 비교연산의 횟수 = 입력 크기 n의 함수시간 복잡도 분석 : 수행 시간 분석공간 복잡도 분석 : 필요한 메모리 공간 분석주어진 문제를 해결하기 위한 대부분의 알고리즘이 비슷한 크기의 메모리 공간을 사용 실행시간 측정실제 측정한 시간의 한계프로그래머의 숙련도구현에 사용된 언어의 종류알고리즘을 실행한 컴퓨터의 성능에 따라 수행 시간이 달라질 수 있다.복잡도 분석구현하지 않고 알고리즘의 효율성 평가알고리즘의 연산 횟수를 대략적으로 계산복잡도 함수 T(n).. 더보기 이전 1 2 다음
