목차

---

1. Graph
2. Tree
3. BsT
4. String method

배운 내용

---

**Tree**

• 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태
• 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조
• 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조
• 아래로만 뻗어나가기 때문에 사이클이 없다.

트리구조

• 루트(Root)라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결
• 노드(Node) : 트리 구조를 이루는 모든 개별 데이터
• 부모 노드(Parent Node)
• 자식 노드(Child Node)
• 형제 노드(Sibling Node)
• 리프 노드(Leaf Node) -자식이 없는 노드

트리구조의 레벨과 서브트리

**깊이 (depth)**

• 루트로부터 하위 계층의 특정 노드까지의 깊이(depth)
• 루트 노드 - 0 밑으로 하나씩 증가

**레벨(Level)**

• 같은 깊이를 가지고 있는 노드를 묶어서 레벨(level)로 표현
• 같은 레벨에 나란히 있는 노드를 형제 노드(Sibling Node)라고한다.

**높이(Height)**

• 리프 노드를 기준으로 루트까지의 높이(height)를 표현
• 각 리프 노드의 높이를 0으로 설정
• 부모 노드는 자식 노드의 가장 높은 height 값에 +1한 값을 높이로 가진다.

**서브 트리(Sub tree)**

• 트리 구조의 root에서 뻗어 나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리

실사용 예제

• 컴퓨터의 디렉토리 구조
• 월드컵 토너먼트 대진표 , 가계도, 조직도

**Graph**

• 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조
• 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다.
• 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어진다.
• 정점(vertex) - 하나의 점(노드라고도 한다)
• 간선(edge) - 하나의 선(정점 간의 관계를 나타냄)
• 인접 (adjacency) : 두 정점 간에 간선이 직접 이어져있다면 인접하다고 표현한다.
• 인접 정점 (adjacent vertex) : 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점
• 가중치 그래프 (weighted Graph): 연결의 강도(추가적인 정보, 위의 예시에서는 서울-부산으로 가는 거리 등)가 얼마나 되는지 적혀져 있는 그래프
• 비가중치 그래프 (unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프
• 무(방)향 그래프, 단방향 그래프
• 진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냄
• 자기 루프 (self loop) : 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 → 다른 정점을 거치지 않는다.
• 사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다
  고 표현

표현 방식

인접행렬

• 두 정점을 바로 이어주는 간선이 있다면 이 두 정점은 인접하다고 표현
• 인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬(2차원배열)
  • 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한 일종의 표
• 가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용

인접 리스트

• 각 정점이 어떤 정점과 인접하는지를 나타낸 리스트
• 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고있다.
• 메모리를 효율적으로 사용하고 싶을 때 주로사용
  • 인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지

실사용 예제

• 포털 사이트의 검색 엔진
• SNS에서 사람들과의 관계
• 내비게이션 (길 찾기)
  • 간선은 내비게이션에서 이동할 수 있음을 나타냄
  • 서로 이어져 있다는 사실만 알려줄뿐 거리가 얼마나 되는지는 알려주지 않는다.
• 추가적인 정보를 파악할수없는 그래프, 가중치(연결의 강도가 얼마나되는지) 적혀 있지 않은 그래프를 비가중치 그래프라고 한다.
• 선에 연결 정도(거리 등)를 표현한 그래프를 가중치 그래프라고 한다.

**Binary Search Tree**

• 효율적인 탐색을 위해 사용(계층적 구조)
• 자식 노드가 최대 두 개인 노드들로 구성된 트리
• 두 개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 구분
• 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을가진다.

**Tree traversal(****트리 순회)**

• 트리 구조에서 노드를 순차적으로 조회할 때의 순서는 항상 왼쪽부터 오른쪽
• **전위 순회 (preorder traverse)**
• **중위 순회 (inorder traverse)**
• **후위 순회 (postorder traverse)**

**BFS / DFS**

• 그래프의 데이터는 배열처럼 정렬이 되어 있지 않다. 그래서 원하는 자료를 찾으려면, 하나씩 모두 방문하여 찾아야 한다.
• 그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적

BFS(Breadth-First Search) - 너비 우선 탐색

• 가까운 정점부터 탐색 → 더는 탐색할 정점이 없을 때, 그다음 떨어져 있는 정점을 순서대로 방문
• 주로 두 정점 사이의 최단 경로를 찾을 때 사용

**DFS(Depth-First Search) - 깊이 우선 탐색**

• 하나의 경로를 끝까지 탐색한 후, 미국 도착이 아니라면 다음 경로로 넘어가 탐색
• 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용

어려운 내용(에러)

---

문제

입력받은 문자열을 공백을 기준으로 나누어 단어의 첫글자를 이어붙인 문자열 리턴

해결

1. 나의 풀이

StringTokenizer st = new StringTokenizer(str);
StringBuilder stb = new StringBuilder();
while(st.hasMoreTokens()){
   stb = stb.append(st.nextToken().substring(0,1));

}

return stb.toString();

1. 레퍼런스 코드

String[] words = str.split(" ");
    String result = "";

    for (int i = 0; i < words.length; i++) {
      result = result + words[i].charAt(0);
    }

String[] split(String str)

• split 함수는 입력받은 정규표현식 or 특정문자를 기준으로 문자열을 나누어 배열에 저장
• String[] words = str.split(" "); : 공백기준으로 문자열 나눔

String.substring()

• 변수이름.substring(begin) :인덱스가 begin인 문자부터 맨끝까지의 문자열
• 변수이름.substring(begin,end) : 인덱스가 begin인 문자부터 end까지의 문자열

String.join()

• String[] 배열의 요소들사이에 매개변수로 전해주는 문자를 추가하여 하나의 문자열로 만든다.
• join(”추가할 문자”, “대상 list”)

String[] foods = new String[] { "햄버거", "치킨", "피자", "파스타" };
String.join("+ ", foods)
//햄버거+ 치킨+ 피자+ 파스타