개발/자료구조

[자료구조] 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)

1. 너비 우선 탐색(Breadth-first-Search)[BFS] 너비우선 탐색은 트리를 가로질러서 순회한다. 예시) 루트 -> 루트의 자식들 -> 루트의 자식들의 자식들 아래로 내려가기전에 같은 레벨에 있는 모든 노드들을 거쳐가는것이고 큐를 이용한다. 2. 깊이 우선 탐색(Depth-first-Search)[DFS] 형제 노드로 넘어가기전에 수직으로 트리의 끝까지 내려간다. (1) 전위 탐색 : 왼쪽을 모두 순회한 다음 오른쪽 순회 (2) 후위 탐색 : 루트가 가장 마지막에 순회한다 -> 거꾸로 순회한다. (3) 중위 탐색 : 먼저 왼쪽 전체를 순회하고 노드를 방문하고 그다음 오른쪽 순회 3. 너비우선과 깊이우선 사용 시간 복잡도는 둘다 같지만 트리에 따라 공간복잡도가 다르다. 완전히 펼쳐져서 넓게..

[자료구조] 이진트리

1. 트리 연결리스트는 선형으로 한가지를 선택한다. 반면에 트리는 비선형으로 여러가지 선택을 할수 있다. 트리는 무조건 자식 노드만 가리켜야 하고 부모나 형제를 가리킬수 없다는 규칙이 있다. 2. 이진트리 트리중 이진 트리는 부모가 가질수 있는 최대 자식노드는 2개이다. 따라서 노드는 2개 이하의 자식노드를 가질 수 있다. 또한 이진트리는 자기보다 작은수는 왼쪽, 큰수는 오른쪽에 배치한다는 특징을 가지고 있다. 3. 트리 용어 root : 꼭대기 노드 child : 자식 노드 parent : 부모 노드 siblings : 부모가 같은 자식들 leaf : 자식이 없는 노드 edge : 노드에서 다른 노드로 향하는 화살표 4. 이진트리 클래스 (1) 클래스 및 노드 class Node { constructo..

[자료구조] 스택-큐

1. 스택과 큐 스택 : 후입선출 - 나중에 들어온것이 먼저 나간다. 큐 : 선입선출 - 먼저 들어온것이 먼저 나간다. 배열을 이용하여 구현한다면 스택은 배열의 기본 메소드 push와 pop을 이용하면 시간 복잡도 O(1)로 처리할 수 있지만 큐는 push, shift 또는 unshift, pop 을 이용하기 때문에 시간복잡도 O(n)이다. 자료구조를 직접 만들어 사용한다면 큐의 시간복잡도를 O(1)로 낮출수 있다. 2. 스택 (1) 클래스 및 노드 class Node { constructor(val) { this.val = val; this.next = null; } } class Stack { constructor() { this.first = null; this.last = null; this.si..

[자료구조] 양방향 연결리스트

1. 양방향 연결리스트 [자료구조] 단방향 연결리스트 1. 자료구조 자료구조는 스택, 큐, 이진트리, 이진힙, 해시테이블 등 다양한 자료의 구조를 말한다. 자료구조가 많은 이유는 데이터에 따라 특정한 자료구조가 효율적이기 때문이다. 따라서 일부 diary-blockchain.tistory.com 단방향 연결리스트의 노드들에 next 뿐만 아니라 앞의 노드도 표시해주는 prev도 포함한다. 양방향이기 때문에 더 많은 메모리가 사용된다. 하지만 그만큼 제거, 삽입 할때 이전과 다음 노드를 알고 있으니 단방향 연결리스트보다 빠르게 처리 할 수 있다. 2. 양방향 연결리스트 클래스 (1) 클래스 및 노드 class Node { constructor(val) { this.val = val; this.next = ..

[자료구조] 단방향 연결리스트

1. 자료구조 자료구조는 스택, 큐, 이진트리, 이진힙, 해시테이블 등 다양한 자료의 구조를 말한다. 자료구조가 많은 이유는 데이터에 따라 특정한 자료구조가 효율적이기 때문이다. 따라서 일부 자료구조는 매우 특화되어있는 반면 배열 객체와 같이 자주 사용되고 있는 일부 자료구조들은 매우 일반적이다. 2. 연결리스트 연결리스트란 데이터 요소들을 가리키는 인덱스 없이 그냥 다수의 데이터 요소들로 구성된다. 마치 객체들이 연속으로 연결되어 있는 기차와 같다고 보면 된다. 여기서 각각의 요소들을 노드라고 부른다. 따라서 연결리스트들은 다수의 노드들로 구성되고 각각의 노드는 문자열 혹은 숫자와 같은 하나의 데이터 요소들을 저장한다. 각 노드들은 다음 노드를 가리키는 정보 역시 저장하고 있어야 하며 다음 노드가 없을..