본문 바로가기

💾 Algorithm/- 자료구조 & 알고리즘16

[자료구조] 노드로 이루어진 트리 구현하기 (By Java) 오늘은 자료구조의 트리를 알고리즘 대회나 문제에서 풀기 쉽게 한 번에 구현하는 방법에 대해서 알아볼 것이다. 트리 자료구조 트리 자료구조는 지난 트리 자료 구조(1)-기본 트리 용어 및 개념 파트에서 설명했으므로 생략하고 바로 구현을 해보도록 하겠다. 트리 자료구조의 핵심 트리 자료구조에서의 핵심은 바로 노드이다. 여기서 노드란 트리 자료구조에 데이터를 저장하고 있는 하나 하나의 원소인 셈이다. 노드는 크게 Data Field와 Link Field로 나뉘어져 있다. 저기 위에서 보면 각각의 숫자에 해당하는 부분이 Data Field이며 연결되어 있는 간선은 Link Field이다. 그렇다면 위에서 말 했듯이 노드는 Data Field와 Link Field가 합쳐진 구조이므로 이를 그림으로 그린다면 아래와.. 2020. 9. 23.

[자료 구조] Java로 그래프 구현하기 :: 인접 리스트로 구현한 그래프 To Do 인접 리스트란? 가중치가 없는 그래프를 인접 리스트로 구현하기 가중치가 있는 그래프를 인접 리스트로 구현하기 지난 시간에 우리는 인접 행렬로 그래프를 그리는 시간을 가졌다. 오늘은 그래프를 그리는 또 다른 방법인 인접 리스트로 그래프를 그려보자. 인접 리스트 Adjancency List 인접 리스트는 한 노드에 연결 상태를 연결 리스트로 구현한 것을 의미한다. 우리가 아까 위에서 만들어 놨던 임의의 그래프를 토대로 연결 리스트로 만들어보자. 노드가 6개가 있으므로 1번 노드부터 관계를 찾아보자 1 -> 2 2 -> 1 - 3 - 4 3 -> 2 - 4 - 5 4 -> 3 - 5 - 6 5 -> 3 - 4 6 -> 4 관계를 찾았으니 이제 각 노드에 해당하는 연결 리스트를 만들어보자. 소스 코드.. 2020. 7. 21.

[자료 구조] Java로 그래프 구현하기 :: 인접 행렬로 구현한 그래프 우리는 지난 시간에 그래프에 대해서 학습하였다. 이번에는 이론적인 그래프를 직접 Java를 이용하여 코드로 옮겨 보는 학습을 해볼 예정이다. 이와 같은 노드를 갖고 있는 그래프가 있다고 생각해보자. 지난 번에도 말 했듯이 그래프를 구현하는 방법에는 두 가지가 있다. 인접 행렬 인접 리스트 오늘은 인접 행렬로 그래프를 구현해볼 것이다. 인접 행렬 인접 행렬(adjacency matrix)이란 은 그래프에서 어느 꼭짓점들이 변으로 연결되었는지 나타내는 정사각 행렬이다. 출처 : 위키 백과 위키 백과에서는 인접 행렬에 대한 예로 다음과 같은 그림을 보여준다. 이 그림을 분석해보자면 1번 노드부터 6번 노드까지 연결되어 있는 노드에 1을 넣는 것이다. 그럼 아까 그렸던 그래프를 한 번 인접 행렬로 옮겨 보자. .. 2020. 7. 21.

[자료 구조] 자바를 이용한 트리의 3가지 순회 방법 구현하기 :: Tree Traversal (InOrder, PostOrder, PreOrder) 트리 자료구조를 학습하는 가장 큰 이유는 지난 시간에서 설명했듯이 탐색을 효율적으로 하기 위함 이라고 했다. 이런 트리 탐색하는데에 조금 더 효율적이며 체계적인 방법이 있는데, 그 대표 주자 3가지를 이번 시간에는 알아보고 구현까지 마쳐보겠다. InOrder PreOrder PostOrder 레벨 순서 순회 (이번에는 다루지 않을 것이다) 순회 for(String name : names) { name.toString(); } 배열을 인덱스 0 부터 길이만큼 반복하는 것이 Iteration 이라고 불리는 순회를 하는 것이다. 순회라고 한다면 영어로는 Circulation. 바로 원소를 하나 하나 확인한다는 뜻이다. 우리는 사실 많은 부분에서 순회를 경험해 왔었다. 하지만 앞으로 우리가 배울 순회와 다른 점.. 2020. 7. 8.

이전 1 2 3 4 다음

티스토리툴바