ao

1. DFS DFS(Depth-first Search)을 직역하면 깊이 우선 탐색이라는 뜻으로, 연결된 노드를 따라 방문을 한 뒤에 더 이상 연결된 노드가 없을 때 이전 노드로 돌아가서, 이전 노드에 연결된 노드를 따라 탐색하는 법입니다. 위의 사진에서 1번 노드부터 탐색을 한다고 해보겠습니다. 오름차순으로 방문한다는 가정하에 1 -> 2 -> 6 순으로 진행됩니다. 6과 연결된 노드가 없기 때문에 다시 2번 노드로 돌아가 8번 노드를 방문하게 됩니다. 8번 노드와 인접한 노드는 모두 방문을 끝냈기 때문에 최상위 노드(1번)으로 돌아가 3번 노드부터 시작하여 마찬가지로 오름차순으로 진행하여 3번 노드부터 이어진 노드를 방문합니다. 위의 과정을 거치고나면 1 -> 2 -> 6 -> 8 -> 3 -> 5->..

해시맵은 Map 인터페이스에 속해있는 Collection으로, 데이터들을 Key와 Value로 구성된 entry 객체를 저장하는 자료구조입니다. 여기서 key는 고유한 속성이지만, Value는 고유한 속성이 아니기 때문에 Value는 중복이 될 수 있습니다. Hash는 특정 키에 대한 값을 빠르게 찾아올 수 있는 장점이 있습니다. key-value가 1:1로 매칭되기 때문에 삽입, 삭제, 검색 과정에서 O(1)의 시간복잡도를 가집니다. 1. Hashmap 선언 import java.util.HashMap; public class Test { public static void main(String[] args) { HashMap hm = new HashMap(); // 타입 설정x Object 입력 Has..

1. Deque Deque는 Double-ended Queue 입니다. 이는 양 끝에 삽입/삭제를 지원한다는 것입니다. 양 끝에 삽입/삭제 시 O(1)의 시간복잡도를 만족하게 됩니다. 내부적으로는 double-linked list로 구현되어 있습니다. append() : deque의 right end에 요소 추가 appendleft() : deque의 lef end에 요소 추가 pop() : deque의 right end의 요소 삭제 popleft() : deque의 left end의 요소 삭제 2. List Deque와는 다르게 python의 List는 fixed size memory blocks(array)로 구현되어 있습니다. 이름은 List여서 링크드 리스트처럼 보이지만 고정된 사이즈의 메모리를 ..

트리는 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조입니다. 트리는 계층적 관계(Hierarchical Relationship)을 표현하는 자료구조입니다. 이 트리라는는 자료구조는 표현에 집중합니다. 자료에서 무엇인가를 저장하고 꺼내야 한다는 사고에서 벗어나 트리라는 자료구조를 바라보는 것이 좋습니다. 1. 트리를 구성하고 있는 구성요소들(용어) Node (노드) : 트리를 구성하고 있는 각각의 요소 Edge (간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선 Root Node (루트 노드) : 트리 구조에서 최상위에 있는 노드 Terminal Node ( = leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드 Internal Node (내부노드, 비단말 노드..

1. Stack Stack은 선형 자료구조의 일종으로 자료를 쌓아 올리는 형태의 자료구조입니다. Data를 맨 아래부터 쌓기 때문에 가장 먼저 넣은 원소가 늦게 나오고, 나중에 들어간 원소가 가장 먼저 나옵니다. (후입선출 : LIFO=Last In FIrst Out) 자료의 삽입 삭제는 한 곳(Top)에서만 이뤄집니다. 만약 스택이 비어있을 때 자료를 꺼내려고 시도를 하면 Stack Underflow가 발생하고, 반대로 스택이 꽉 차있을 자료를 넣으려고 하면 Stack Overflow가 발생합니다.. 이 Stack은 재귀적인 알고리즘, 후위 표기법 계산, 역순 문자열 만들기에 쓰이며, 웹 브라우저의 뒤로가기, 문서작업에서 Ctrl+z(가장 나중에 수정한 내역을 되돌림)에 쓰입니다. 2. Queue Qu..

https://refreshment-wg.tistory.com/58 Array & Linked list 자료구조의 종류 중 하나인 Array와 Linked list의 차이를 알아보겠습니다. 1. Array 먼저 Array는 논리적 저장 순서와 물리적 저장 순서가 일치합니다. 즉, index로 해당 element에 접근할 수 있다는 것입니 refreshment-wg.tistory.com Linked list와 array의 차이에 대해 적으면서 시간복잡도라는 개념이 나와 정리해보았습니다... 먼저 알고리즘에서 로직을 코드로 구현할 때 시간복잡도를 고려한다는 것은 '입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마나 걸리는가' 입니다. 즉. 시간복잡도는 문제를 해결하는데 걸리는 시간과 입..

자료구조의 종류 중 하나인 Array와 Linked list의 차이를 알아보겠습니다. 1. Array 먼저 Array는 논리적 저장 순서와 물리적 저장 순서가 일치합니다. 즉, index로 해당 element에 접근할 수 있다는 것입니다. 그렇기 때문에 찾고자 하는 원소의 index값을 알고 있다면 Big-O(1)에 해당 원소로 접근할 수 있습니다. (random access가 가능하다는 장점) But, 삭제 혹은 삽입 과정에서는 해당 원소에 접근해 작업을 완료한 뒤(O(1)), 또 한가지의 작업을 추가적으로 해줘야 하기 때문에, 시간이 더 걸립니다. 만약 배열의 원소 중 어느 원소를 삭제했다고 했을때, 배열의 연속적 특징이 깨져 빈 공간이 생기게 됩니다. 따라서 삭제한 원소보다 큰 indedx를 갖는 ..

1. 자료구조 자료구조는 데이터를 원하는 규칙 혹은 목적에 맞게 저장하기 위한 구조입니다. 자료구조의 종류는 선형구조, 비선형구조, 파일구조(순차, 색인, 직접 파일), 단순구조(정수, 실수, 문자열)가 있습니다. 1) 선형 구조 List, Stack, Queue는 데이터를 선의 형태로 나열하는 선형(Linear)입니다. 2) 비선형 구조 Tree, Graph는 데이터를 나란히 저장하지 않는 비선형 구조입니다. 이 자료구조는 알고리즘과 밀접한 관계를 갖습니다. 알고리즘은 자료구조에 쌓인 데이터를 활용해 어떤 문제를 해결하기위한 동작들의 모임으로, 자료구조가 결정되어야 효율적인 알고리즘을 결정할 수 있습니다. 즉, 알고리즘은 자료 구조에 의존적으로 자료구조에 따라 알고리즘이 달라집니다. [자료구조] 자료구..