짹뚜 스튜디오

트리의 모든 노드들을 방문하는 트리 순회 알고리즘에는 3가지 방법이 있다. 전위 순회 (Preorder) 중위 순회 (Inorder) 후위 순회 (Postorder) 위 3가지 방법 모두 재귀로 구현할 수 있다. 전위 순회 (Preorder) 전위 순회는 주로 트리를 복사할 때 사용되는 방법이다. 하나의 노드를 방문했을 때 다음과 같은 순서로 진행된다. 루트 노드 방문 왼쪽 자식 노드 방문 오른쪽 자식 노드 방문 const tree=[[1,2],[3,4],[5,6],[.,.],[.,.],[.,.],[.,.]]; /* node 0 ~ 6을 포함한 트리를 2D 배열로 표현 각 노드별로 왼쪽 오른쪽 자식 노드를 배열로 표현 .은 자식 노드가 없음을 표현 0 / \ 1 2 / \ / \ 3 4 5 6 */ fu..

1. DFS Depth First Search(깊이 우선 탐색)은 한 정점(node)부터 시작해서 한 방향으로 탐색을 시작해서 더 이상 탐색할 것이 없을 때 이전 노드로 돌아와서 다음으로 연결된 노드를 확인하는 탐색 방법이다. DFS를 구현하는 방법에는 재귀와 스택을 이용한 방법이 있다. //visited[] = 해당 노드를 방문했는지 저장하는 배열 (모든 원소가 false로 초기화됨) //edges[][] = 각 노드별로 연결된 노드들을 저장한 배열 //스택을 이용한 DFS function dfs(index){ let stacks = []; stacks.push(index); visited[index] = true; while(stacks.length){ const next = stacks.pop();..

그래프는 정점 (node 또는 vertice)와 간선 (edge)로 이루어진 자료구조이다. 여기서 노드에는 데이터가 저장되고 엣지는 두 노드 사이의 관계를 나타낸다. 위 그래프에서 노드는 {1, 2, 3, 4, 5} 이고 엣지는 {12, 13, 23, 25, 34, 45}이다. 그래프의 종류에 대해서 알아보자. Directed Graph (방향 그래프): 두 노드를 연결하는 엣지의 방향이 존재하는 그래프. 왼쪽 그래프에서 엣지 1->2는 존재하지만 2->1 은 존재하지 않는다. edge(12) ≠ edge(21) Undirected Graph (무방향 그래프): 두 노드를 연결하는 엣지의 방향이 없이 양방향으로 연결되는 그래프. 오른쪽 그래프에서 엣지 1->2와 2->1이 같다. edge(12) = ed..

1. 순열 C++에서 다음 순열을 찾으려면 SLT 알고리즘에 있는 next_permutation 함수를 사용하면 된다. next_permutation의 시간 복잡도는 O(n)이다. 그러나 다른 언어에는 없기 때문에 직접 구현하면서 구조를 알아보려 한다. 다음과 같은 순서로 다음 순열을 찾게된다. a[i] a[i]를 만족하는 가장 큰 j를 찾는다. (j > i) a[i] 와 a[j]를 swap한다. a[i+1]부터 reverse 해준다. 이것을 Javascript로 구현하면 다음과 같다. // n = 배열의 length let index = -1; for(let i = n-2; i >=..