매일코딩

[배열을 이용한 이진 트리의 표현] 이진트리의 가장 큰 특징은 자식 노드를 2개씩 가진다는 것이다. 이러면 노드 번호를 붙여서 부모, 자식 노드에 접근하기가 굉장히 편리해진다. 트리의 번호는 상->하, 왼->오의 순으로 번호가 붙는다. 루트노드를 1로 시작할 때 왼쪽 노드는 2, 오른쪽 노드는 3 이렇게 번호가 붙는다. 그렇담 이진트리의 규칙을 적용해 부모노드를 i, 왼쪽 자식 노드를 2*i, 오른쪽 자식 노드를 2*i+1라는 규칙성을 적용할 수 있다. 노드 번호가 i인 노드의 부모 노드 : i/2 노드 번호가 i인 노드의 왼쪽 자식 노드 : 2*i 노드 번호가 i인 노드의 오른쪽 자식 노드 : 2*i+1 위의 트리를 배열로 표현하면 저렇게 될 것이다. 그렇다면 높이가 h일 때 배열의 크기는 어떻게 설정..

트리 비선형 구조 (원소들 간에 1:n 관계를 가지는 것) 선형구조는 원소들 간에 1:1의 관계를 가지는 것임. 대표적으로 linkedList, arrayList가 있음 원소들 간에 계층관계를 가짐 상위원소에서 하위 원소로 내려가면서 확장되는 트리 모양의 구조 [트리의 용어] 노드: 트리의 원소 트리의 원소: A,B,C,D,E,F,G,H,I,J,K,L 간선: 노드를 연결하는 선으로 부모 노드와 자식 노드를 연결 루트 노드: 트리의 시작 노드 루트노드: A 형제노드: 같은 부모노드를 가진 노드들 형제 노드: B,C,D 조상노드: 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들 J의 조상 노드들: F,B,A 서브트리: 부모노드와 연결된 간선을 끊었을 때 생성되는 트리 A의 서브 트리: B트리, C..

[그래프와 트리의 차이] 그래프 트리 정의 노드(node)와 그 노드를 연결하는 간선(edge)를 하나로 모아놓은 자료 구조 그래프의 한 종류 DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류 방향성 방향 그래프(Diredctd) 무방향 그래프(Undirected) 모두 존재 방향 그래프(Directed Graph) 사이클 사이클(Cycle) 가능 자체 간선(self-loop)도 가능 순환 그래프(Cyclic), 비순환 그래프(Acyclic) 모두 존재 사이클(Cycle) 불가능 자체 간선(Self-loop) 불가능, 비순환 그래프(Acyclic Graph) 루트 노드 루트 노드 개념이 없음 한 개의 루트 노드만이 존재, 모든 자식 노드는 한 개의 부모 노드만을 ..

그래프를 탐색하는 방법에는 DFS, BFS 알고리즘이 있다. 이번엔 BFS에 대해 정리해 보겠다. 2. BFS BFS는 현재 노드에서 이동 가능한 다음 레벨의 노드를 모두 확인한 후, 다음 레벨의 노드들을 모두 큐(Queue)에 담는다 이후 큐에 담긴 노드 위치들을 하나씩 꺼내며 다음 방문할 노드들을 탐색한다. . DFS가 갈 수 있는데 까지 깊게 갔다면, BFS는 일단 주변에 연결된 노드들을 먼저 방문하여 넓게 탐색하는 알고리즘이다. 필요한 것 큐: 방문 차례의 기록을 목적으로 함 배열: 방문 정보의 기록을 목적으로 함 DFS와 달리 BFS는 재귀적으로 동작하지 않는다. BFS를 구현할 때, 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다. 그렇지 않으면 무한루프에 빠질 수 있다. BFS는 방문한 ..

[그래프의 탐색] 그래프의 모든 정점을 한번씩 탐색하기 위해 BFS, DFS 알고리즘이 개발되었다. 깊이 우선 탐색 Depth First Search : DFS 넓이 우선 탐색 Breadth First Search: BFS 1. DFS 한 정점에서 갈 수 있는데까지 완벽하게 탐색하는 방법이다. 한 정점에서 이동 가능한 다음 정점으로 이동하고, 다시 다음 정점에서 연결된 노드를 탐색하는 알고리즘이다. 더이상 갈 수 없으면 뒤로 돌아올 수 있도록 현재 위치를 스택(Stack)에 저장해야 한다. 필요한 것 스택: 현재 어떤 정점에서 탐색하는지 추적 배열: 정점의 방문 여부를 체크 DFS는 Stack을 사용하여 구현하는 방법과 재귀 호출로 구현하는 방법이 있다. DFS를 구현할 때, 어떤 노드를 방문했었는지 여..

1. 그래프 개념 [그래프 용어 정리] 목적: 출발지, 목적지를 정하고 그에 맞는 최적의 경로를 구하기 ex) 지도, 지하철 노선도 최단 경로, 전기 회로의 소자들, 도로(교차점과 일방 통행길) 그래프: 노드와 간선으로 이루어진 자료 구조.(1, 2, 3) 노드 (Node, Vertex) 간선 (Edge): 정점간의 관계를 나타낸다. G = (V, E)로 나타낸다. 경로 (Path): 시작점에서 도착점으로 가는 간선의 연속된 것 (2 -> 3 -> 1) 사이클: 정점 A에서 다시 A로 돌아오는 경우 ( A -> B -> D)단순 경로와 단순 사이클 경로/ 사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로/ 사이클 DAG (Diredcted Acyclic Graph) 사이클이 없는 그래프. 트리(Tr..