자료구조 알고리즘8

• 

  자료구조 알고리즘 DFS DFS 자료의 검색, 트리나 그래프를 탐색하는 방법. 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다. # 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다! graph = { 1: [2, 5, 9], 2: [1, 3], 3: [2, 4], 4: [3], 5: [1, 6, 8], 6: [5, 7], 7: [6], 8: [5], 9: [1, 10], 10: [9] } visited = [] # 1. 시작 노드(루트 노드)인 1부터 탐색합니다. # 2. 현재 방문한 노드를 visited에 추가합니다. # 3. 현재 방문한 노드와 인접한 노드 중에 방문하지 않은 노드에 방문합니다. # def dfs_recursion(adjace.. 자료구조 알고리즘 2022. 11. 29.

• 

  자료구조 알고리즘 그래프란?? 그래프란? 연결되어 있는 정점와 정점간의 관계를 표현할 수 있는 자료구조. 저번에 트리를 배우면서 배웠던 "비선형 구조" 에 대해 기억 나시나요? 비선형 구조는 표현에 초점이 맞춰져 있다고 말씀 드렸는데, 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있습니다. 이번 자료구조인 그래프는 바로 연결 관계에 초점이 맞춰져 있습니다. 페이스북을 예시로 들어볼게요! 제가 친구 "제니"를 알고 있고, "로제"와 친합니다. 그리고 "로제"는 트와이스 "사나"를 안다고 하면, 저는 "사나"와 2촌 관계라고 말할 수 있겠죠! 그래프에서 사용되는 용어들을 정리해드리면 다음과 같습니다! 노드(Node): 연결 관계를 가진 각 데이터를 의미합니다. 정점(Vertex)이라고도 .. 자료구조 알고리즘 2022. 11. 29.

• 

  자료구조 알고리즘 힙이란 무엇인가? 힙이란 무엇인가? 힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 항상 최대의 값들이 필요한 연산이 있다면? 바로 힙을 쓰면 되겠죠! 그러면 힙을 구현하려면 어떻게 해야할까요? 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조입니다. 다시 말하면 부모 노드의 값이 자식 노드의 값보다 항상 커야 합니다. 그러면 가장 큰 값은 모든 자식보다 커야 하기 때문에 가장 위로 가겠죠! 따라서 최대의 값들을 빠르게 구할 수 있게 되는 것입니다. 참고로, 힙은 다음과 같이 최대값을 맨 위로 올릴수도 있고, 최솟값을 맨 위로 올릴 수도 있습니다! 최댓값이 맨 위인 힙을 Max 힙, 최솟값이 맨 위인 힙을 Min 힙이라고 합.. 자료구조 알고리즘 2022. 11. 29.

• 

  자료구조 알고리즘 트리란 무엇인가? 트리란 무엇인가? 뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료 구조. 앞서 보인 큐(Queue), 스택(Stack) 은 자료구조에서 선형 구조라고 합니다. 선형 구조란 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태를 의미합니다. 이번에 배울 트리는 바로 비선형 구조입니다! 비선형 구조는 선형구조와는 다르게 데이터가 계층적 혹은 망으로 구성되어있습니다. 선형구조와 비선형구조의 차이점은 형태뿐만 아니라 용도에서도 차이점이 많습니다! 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있습니다. * 아래 폴더 구조가 대표적인 트리의 형태입니다! 트리는 이름에서부터 느껴지듯이 계층형 구조입니다! 위 아래가 구분되어 있습니다. 트.. 자료구조 알고리즘 2022. 11. 28.

• 

  자료구조 알고리즘 Queue 큐란 무엇인가? Queue 큐란 무엇인가? 한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형 구조.(선입선출/FIFO(First in First out)) 큐도 스택과 마찬가지로 일상생활에 접목해 보면 쉽게 이해할 수 있습니다. 일상생활 속 맛집을 갔을 때 온라인에서 티켓을 구매할 때 저희는 줄을 섭니다. 아래와 같이 먼저 온 사람이 먼저 대기열을 빠져나가게 됩니다 이과 같은 자료구조를 Queue라고 합니다 LinkedList 의 Queue class Node: def __init__(self, data): self.data = data self.next = None class Queue: def __init__(self): self.head = None self.tail = None def enqueue.. 자료구조 알고리즘 2022. 11. 26.

• 

  자료구조 알고리즘 Stack 스택이란? Stack 스택이란 무엇인가? 스택이란 한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조.(후입선출/LIFO(Last in First out)) 스택은 일상생활과 비교해 보면 너무나도 쉽게 이해가 가능합니다 프링글스를 먹으면 저희는 가장 위에 있는 감자칩부터 눈에 보이고 가장 위에부터 꺼내 먹을 수 있게 됩니다 다시 새로운 감자칩을 넣게 되더라도 아래부터가 아닌 위에서부터 쌓게 됩니다 이해가 힘들다면 그림을 보고 이해해 봅시다 LinkedList 의 Stack [4] -> [3] -> [2] -> [1] 새로운 Stack을 추가하면 [5] -> [4] -> [3] -> [2] -> [1] 마지막에 들어온 것이 self.head 가 됩니다 class Node: def __init__(self, data):.. 자료구조 알고리즘 2022. 11. 26.

• 자료구조 알고리즘 이진탐색 finding_target = 14 finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] def is_existing_target_number_binary(target, array): current_min = 0 current_max = len(array) - 1 current_guess = (current_min + current_max) // 2 while current_min 자료구조 알고리즘 2022. 11. 26.

• 자료구조 알고리즘 Array vs LinkedList LinkedList 사용법 자료구조 알고리즘 Array vs LinkedList 경우 Array LinkedList 특정 원소 조회 O(1) O(N) 중간에 삽입 삭제 O(N) O(1) 데이터 추가 데이터 추가 시 모든 공간이 다 차버렸다면 새로운 메모리 공간을 할당 받아야 한다 모든 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가하면 된다. 정리 데이터에 접근하는 경우가 빈번하다면 Array를 사용하자 삽입과 삭제가 빈번하다면 LinkedList 를 사용하는 것이 더 좋다 Li nkedList 1) LinkdList 는 self.head 에 시작하는 노드를 저장한다. 2) 다음 노드를 보기 위해서는 각 노드의 next 를 조회해서 찾아가야 한다 class Node: ## Node 를 만들어 줍니다 def __init__(self.. 자료구조 알고리즘 2022. 11. 23.