728x90

자료구조 7

[알고리즘] Algorithm with Math: 순열 / 조합

순열(Permutation) - 요소 n개 중에 m개를 선택하여 순서에 상관 있게 뽑는 경우의 수 - nPr = n! / (n-r)! 5장에서 3장을 선택하는 모든 순열의 수 = 5P3 = (5x4x3x2x1) / (2x1) = (5x4x3) = 60 - 요소를 뽑는 개수만큼 반복문 중첩 public static ArrayList permutation() { String[] cases = new String[]{"도", "개", "걸", "윷", "모"}; ArrayList result = new ArrayList(); for (int i = 0; i < cases.length; i++) { for (int j = 0; j < cases.length; j++) { for (int k = 0; k < ca..

[자료구조] Search Algorithm: 트리 순회, BFS / DFS

트리 순회(Tree Traversal) - 특정 목적을 위해 트리의 모든 노드를 한 번씩 방문 - 트리 순회는 항상 왼쪽에서 오른쪽으로 조회함 트리 순회 방법 - 전위 순회(preorder traverse) : 루트부터 순회를 시작해 왼쪽에서 오른쪽으로 이동해 노드 탐색 탐색 순서 : 0 → 1 → 3 → 7 → 4 → 8 → 2 → 5 → 9 → 6 - 중위 순회(inorder traverse) : 왼쪽에서 순회를 시작해 루트를 중간에 거쳐 오른쪽으로 이동해 노드 탐색 탐색 순서 : 7 → 3 → 1 → 8 → 4 → 0 → 9 → 5 → 2 → 6 - 후위 순회(postorder traverse) : 왼쪽에서 오른쪽으로 노드 탐색 후 루트를 가장 마지막에 순회 탐색 순서 : 7 → 3 → 8 → 4 ..

[자료구조] 이진 트리(Binary Tree)

이진 트리(Binary Tree) - 자식 노드가 최대 두 개인 노드들로 구성된 트리 이진 탐색 트리(Binary Search Tree) - 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가진 이진 트리 이진 트리의 종류 - 정 이진 트리(Full Binary Tree) : 각 노드가 0개 혹은 2개의 자식 노드를 가짐 - 완전 이진 트리(Complete Binary Tree) : 마지막 레벨을 제외한 모든 노드가 가득 차 있고, 마지막 레벨의 노드는 왼쪽만 채워져 있음 - 포화 이진 트리(Perfect Binary Tree) : 모든 레벨이 가득 채워져 있고, 모든 리프 노드의 레벨이 동일함 References - 이진 트리의 종류와 설명

[자료구조] 트리(Tree)

트리(Tree) - 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조 - 단방향 그래프의 한 구조로, 나무를 거꾸로 뒤집어 놓은 것처럼 하나의 뿌리로부터 가지가 사방으로 뻗은 형태를 가짐 - 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조 트리의 구조 - 루트(Root) : 트리 구조가 시작되는 꼭짓점 데이터 - 노드(Node) : 트리 구조에서 연결된 각각의 데이터로, 두 개의 노드가 상하 계층으로 연결되면 각각 부모 노드(Parent Node)와 자식 노드(Child Node)로 나뉘고, 자식이 없는 노드는 리프 노드(Leaf Node)라고 부름 - 서브 트리(Sub Tree) : 루트에서 뻗어나오는 큰 트리 내부에서 트리 구조를 갖춘 작은 트리 ..

[자료구조] 그래프(Graph)

그래프(Graph) - 여러 개의 점들이 서로 선으로 복잡하게 연결되어 있는 관계를 표현한 자료구조 - 하나의 점을 정점(vertex), 하나의 선을 간선(edge)라고 함 - 두 점끼리 직접적인 관계가 있는 경우 점 사이를 이어주는 간선이 존재하며, 두 정점은 인접하다고 표현함 - 간접적인 관계를 가진 두 점은 몇 개의 점과 선에 걸쳐서 이어짐 그래프의 표현 방식 - 인접 행렬 두 점간 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)로 표시한 2차원 배열 형태의 행렬로 표현 두 정점 사이에 관계가 있는지 확인하거나, 가장 빠른 경로를 찾고자 할 때 사용 - 인접 리스트 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현 인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 ..

728x90