전체 글 썸네일형 리스트형 [자료구조] Binary Search Tree 이진탐색트리 Binary Search Tree 이진탐색트리 트리 구조 자체적으로는 트리 노드를 하나하나씩 방문하여 탐색해야 하기 때문에 시간 복잡도 측면에서 큰 이점이 없음. -> 더 빠른 탐색을 위해서 Binary Search와 마찬가지로 O(log₂n)의 시간 복잡도를 가지도록 고안됨 (데이터의 특성에 제약을 줌) 이진탐색트리의 특성 - 노드의 왼쪽 서브 트리에는 루트 노드보다 작은 값이 들어있다. - 노드의 오른쪽 서브 트리에는 루트 노드보다 큰 값이 들어있다. - 서브 트리 또한 이진 탐색 트리 구조이다. - 중복된 값은 일체 없다. - 루트 노드인 5를 기준으로 왼쪽 서브 트리에는 5보다 작은 수로 구성 되어있고 오른쪽 서브 트리에는 5보다 큰 수로 구성됨 - 하위의 서브 트리에서도 각 루트 노드를 기준으로.. 더보기 [자료구조] Tree 트리 그래프 vs 트리? 구분 그래프(Graph) 트리(Tree) 정의 객체 혹은 노드(Node)와 그것을 연결하는 간선(Edge)으로 모인 구조 그래프의 한 종류이고 방향성이 없으며 순환하지 않음 방향성 무방향 혹은 유방향으로 가능 무방향 그래프 순환성 순환 가능 자기 자신을 연결하는 간선(Self-Loop) 가능 순환(Cyclic), 비순환(Acyclic) 모두 가능 순환 불가능 자기 자신 연결 간선(Self-Loop) 불가능 비순환 그래프(Acyclic Graph) 루트 루트의 개념이 있거나 없을 수 있음 하나의 루트 노드 존재 모델 네트워크 모델 계층 모델 순회 넓이 우선 탐색(BFS) 깊이 우선 탐색(DFS) 전위(Pre) / 중위(In) / 후위(Post) 순회 방식 간선수 그래프에 따라 다르며 없.. 더보기 [자료구조] Deque 덱 Deque 덱 : "Double-ended Queue"를 줄여서 표현한 것으로 앞, 뒤로 모두 넣고 뺄 수 있는 자료구조. stack과 queue를 합친 자료구조로 이해됨. - 머리, 꼬리 양쪽 노드에서 추가와 삭제가 이뤄진다는 점에서 양방향 연결 리스트를 기반으로 덱을 구현하는 경우가 많음. - python에서 덱의 연산은 collections 모듈에서 제공하는 deque 클래스로 구현 가능 ▷ append(): 오른쪽에서 데이터를 삽입 ▷ appendleft(): 왼쪽에서 데이터를 삽입 ▷ pop(): 오른쪽에서 데이터 삭제 ▷ popleft(): 왼쪽에서 데이터 삭제 -출처 https://blog.naver.com/isaac7263/221507063144 더보기 [자료구조] Graph 그래프 Graph 그래프 -정점(vertex/node)들과 정점을 연결하는 간선(edge/arcs)로 이루어진 자료 구조 -G=(V,E) === 그래프=(정점의 집합, 간선의 집합) 그래프의 종류 -무방향 그래프 -방향 그래프 -가중치 그래프 -완전 그래프 그래프 구현 방법 -인접 행렬 두 정점을 연결하는 간선을 조회할 때 시간복잡도: O(1) 한 정점의 차수를 구할 때 시간복잡도: O(n) 모든 간선의 수를 알아낼 때 시간복잡도: O(n²) 단점: 간선의 수와 관계없이 항상 n² 크기의 2차원 배열을 사용해야 하므로 메모리가 낭비됨. -인접 리스트 두 정점을 연결하는 간선을 조회하거나 정점의 차수를 알기 위해서는 정점의 인접 리스트를 탐색해야 하므로 정점의 차수만큼의 시간이 필요: O(degree(v)) ※d.. 더보기 [알고리즘] Sequential Search 순차탐색, Binary Search 이진탐색 Sequential Search 순차탐색 -데이터 탐색 시 말 그대로 처음부터 순차적으로 탐색하는 방식. -데이터가 무작위로 나열되어 있는 리스트에서 사용함. -시간복잡도 O(N) Binary Search 이진탐색 -배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있음. -배열을 반으로 쪼개가면서 찾으려는 데이터와 중간점의 데이터를 비교해서 원하는 데이터를 찾음. -시간복잡도 O(logN) https://velog.io/@changhee09/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%83%89-%EC%88%9C%EC%B0%A8-%ED%83%90%EC%83%89-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89 [알고리즘] 탐색 - 순차 탐.. 더보기 [자료구조] Queue 큐 Queue 큐 -선입선출 (FIFO - First In First Out) 구조. -배열을 사용하거나 연결리스트를 사용할 수 있음. -선형큐에서는 배열의 뒷쪽은 계속해서 채워지고 배열의 앞은 계속 원소가 빠져서 결론적으로 배열이 계속해서 뒤로 밀려나게 됨. 따라서 큐의 인덱스가 가장 끝에 도달하게 되면 배열이 비어있음에도 큐에 원소를 삽입할 수 없게 됨. 이를 보완하기 위해 원형큐 사용. 원형큐 -나머지 연산을 이용해 큐의 인덱스가 끝에 도달하면 다시 처음으로 돌아가도록 짬. https://velog.io/@mcc919/Data-Structure-%EC%9B%90%ED%98%95-%ED%81%90Circular-Queue-%EC%95%8C%EC%95%84%EB%B3%B4%EA%B8%B0 [Data Str.. 더보기 [자료구조] Stack 스택 Stack 스택 -후입선출 (LIFO - Last In First Out) -top에 데이터를 추가하거나 삭제하는 연산은 항상 상수 시간에 가능. -스택과 재귀 알고리즘 https://bentist.tistory.com/57 재귀(Recursion)와 스택(stack)영역 다른 알고리즘과는 다르게 제목에 재귀와 함께 스택 영역을 적어놓은 이유가 있다. 재귀 함수를 호출하는 것과 메모리 스택 영역의 연관성은 마지막 부분에 정리하겠다. 1.1 재귀(Recursion) * 위키 bentist.tistory.com - 스택 잘 정리된 글 https://yoongrammer.tistory.com/45 [자료구조] 스택 (Stack) 목차 [자료구조] 스택 (Stack) 스택은 한쪽 끝에서만 자료를 넣거나 뺄 수 .. 더보기 [자료구조] Array 배열, Linked list 연결리스트 - 배열 잘 정리된 글 https://yoongrammer.tistory.com/43 [자료구조] 배열 (Array) 목차 [자료구조] 배열 (Array) 배열은 연속된 메모리 공간에 순차적으로 저장된 데이터 모음입니다 대부분에 프로그램 언어에서 동일 타입의 데이터를 저장합니다. 예를 들어 배열이 "int"타입인 yoongrammer.tistory.com https://chunggaeguri.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EB%B0%B0%EC%97%B4Array%EC%9D%B4%EB%9E%80 [ 자료구조 ] 배열(Array)이란? 배열(Array)이란? 배열은 메모리 상에 데이터(원소)를 연속하게 배치한 자료구조 배열은 같은 타입의 .. 더보기 이전 1 2 3 4 5 6 다음 목록 더보기
