nathan_H

시작하기 알고리즘을 풀다보면 그래프 자료구조를 사용하는 경우가 많고, 그래프 자료구조를 사용하는 문제의 상당수는 DFS, BFS을 구현해 문제를 해결하는 경우가 많다. 그리고 문제의 난이도가 올라갈수록 단순한 DFS, BFS가 아닌 다양한 형태로 변형한 DFS, BFS을 요구한다. 그래서 DFS, BFS 개념과 몇가지 유형을 통해 한번 DFS, BFS을 뿌시고자 한다. Graph 자료형 그래프 자료형의 경우 선형 자료구조나 트리 자료구조로 표현하기 어려운 多:多의 관계 를 가지는 원소들을 표현하기 위한 자료구조로 객체의 정점과 객체를 연결하는 간선의 집합이다. 그래프 객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)의 집합 𝐺 = (𝑉,𝐸) − 𝑉는 그래프에 있는 정점들의 집합 − 𝐸..

큐는 스택 자료구조와 달리 FIFO (First-In First-Out)- 선입 선출 특징으로 넣을 때에는 한 쪽 끝에서 밀어 넣어야 한다. -> enqueue 연산 꺼낼 때에는 반대 쪽에서 뽑아 꺼내야하는 제약 -> dequeue 연산 즉 enqueue로 삽입된 원소가 가장 나중에 dequeue로 빠져나온다는 것이다. 추상적 자료구조 구현 method size() - 현재 큐에 들어 있는 데이터 원소의 수 O(1) isEmpty() - 현재 큐가 비어 있는지 판단 O(1) enqueue(x) - 데이터 원소 큐에 추가 O(1) dequeue - 큐에 맨 앞에 저장된 데이터 원소 제기 or 반환 O(n) peek() - 큐의 맨앞에 저장된 데이터 원소 반환(제거 x) O(1) dequeue 시간 복잡도 ..

Stack은 LIFO 규칙을 따르는 자료구조로 데이터를 삽입할 때는 마지막 위치에 들어오고 데이터를 삭제 & 반환할때도 마지막 위치부터 삭제 & 반환을 하는 알고리즘이다. 스택의 경우는 활용범위가 넓기 때문에 잘 알고 있다면 유용하게 사용 할 수 있다. 그리고 특히 알고리즘 문제나 기업 코딩 테스트에도 빈번하게 나오기 때문에 로직을 잘 이해하고 다양한 스택 관련 문제를 풀면 좋다. 코드구현 class ArrayStack: ''' By using python list make stack ''' def __intit__(self): self.data = [] def is_Empty(self): return True if not self.data else False def size(self): return l..

Double LinkedList reference 어서와! 자료구조와 알고리즘은 처음이지? | 프로그래머스 앞서 살펴본 단뱡향 연결리스트와 달리 이번에는 양방향 연결리스트로 링크가 한쪽방향이 아닌 양방형으로 연결된 Double LinkedList에 대해서 살펴볼려고 한다. 말 그대로, 양방향 연결 리스트에서는 노드들이 앞/뒤로 연결되어 있습니다. 즉, 인접한 두 개의 노드들은 앞의 노드로부터 뒤의 노드가 연결되어 있을뿐만 아니라, 뒤의 노드로부터 앞의 노드도 연결되어 있습니다. 한 노드의 입장에서 보자면, 자신보다 앞에 오는 노드를 연결하는 링크와 자신보다 뒤에 오는 노드를 연결하는 링크를 둘 다 가진다. 또한 양방향 연결리스트는 기존 단방향 연결리스트와 달리 HEAD, TAIL노드에 Dummy인 빈 노..

Linked List 연결리스트는 대표적은 추상적 자료구조의 한 예로 기존 리스트 자료구조와 달리 Node와 Link를 가진 자료구조이다. 위에 그림처럼 데이터를 담고 있는 Node 그리고 각 노드들은 연결하는 Link를 통해 이루어져 있다. 연결 리스트의 장단점 연결리스트의 경우 링크를 통해 각 데이터가 연결이 되어 있기 때문에 배열에 비해 추가 / 삭제가 용이한 점을 가지고 있다. 반면에 특정 데이터를 찾기 위한 순차 탐색에 있어 탐색 속도가 배열에 비해 느린 단점을 가지고 있다. 하지만 연결 리스트는 '동적 할당'을 기반으로 한 자료구조이기 때문에 크기를 미리 지정할 필요가 없다는 큰 장점을 가지고 있기 때문에 많이 사용되어 진다. 그래서 궁극적으로 내가 어떠한 목적을 가지고 코드를 구성하느냐에 따..