자료구조 - 트리, 그래프, 이진트리

1️⃣ 굿모닝 세션

---

코플릿에서 어떤값이 입력으로 들어오는지 모릅니다. 실제로 코딩 테스트를 보면 입력값을 숨겨놓은 경우가 많다.

엣지 케이스를 쉽게 알 수 없도록? 이게 목적인가? 

 

길찾기 문제, 내비게이션 문제 => Graph로 해결(수학에서 나오는 그래프랑은 다르다)

결국 DFS/BFS를 학습하기 위해서이다.

 

 

2️⃣ 데일리 코딩

---

공백이 들어간 문자열을 입력받아 문자열을 구성하는 각 단어의 첫 글자로 이루어진 문자열을 리턴한다.

입력값 : String str

출력값 : String 

 

• 빈 문자열
  • isEmpty() 메서드 사용
  • 문자열이 비어있거나 Null인 경우가 있다. str==null 연산자==로 널값 확인 가능. (true/false). 
  • isEmpty()의 단점은 " " 공백으로 채워진 문자열은 값이 있다고 판단한다는 것이다.(false)  ""일 경우 true
  • 자바 11에서 추가된 isBlank() 메서드를 통해서  빈 문자열이거나, 공백만 갖는 문자열(" ")이면 true, 아니면 false를 반환함으로써 더욱 편리해졌다. 하지만 나는 자바 8을 사용하고 있기 때문에 isEmpty()를 사용.

// 빈 문자열인 경우 문자열 그대로 리턴
if(str.isEmpty()) return str;

        System.out.println("Hello".isEmpty()); //false
        System.out.println(" Hello".isEmpty()); //false
        System.out.println("".isEmpty()); //true
        System.out.println(" ".isEmpty()); //false, isBlank()메서드라면 true

• null VS 공백 VS 빈 값
  • null이란 값이 없는 상태를 말하고 "null"이라는 키워드를 가지고 있습니다.
  • 어떠한 값으로도 초기화 되지 않고 컴파일러가 인지하여 힙 메모리상에 어떠한 데이터도 만들지 않습니다.
  • null은 참조형 변수에만 할당 될 수 있습니다. 
  • 참조형 변수(reference variable)는 기본형 변수 8가지를 제외한 나머지로 값이 저장된 메모리의 주소를 담고 있는 변수를 말합니다. 기본형 변수는 변수값 그 자체를 담고 있습니다.

Java 에서는 문자열에 저장된 값이

 

1. null 일 때 : 메모리상에 데이터를 만들지 않는다. 

2. 길이가 0인 경우 : String 형으로 빈 값을 메모리에 할당한다.

3. 공백이 포함된 경우 

 

를 모두 다르게 취급하고 있습니다.

 

• 문자열이름.split( ) 메서드
  • 자바에서 문자열을 배열로 분리하기 위해 가장 많이 사용하는 방법으로 string.split()을 쓴다.
  • str.split(" ") ⬅ 인자로 구분자 혹은 정규식을 넣어준다. (공백을 구분자로 문자열 배열을 만들어!)

public class Main {
    public static void main(String[] args) {
        String str="Hello i am sksdud nice to meet you";
        String[] strNew=str.split(" ");
        System.out.println(Arrays.toString(strNew));
    }
}
// 출력 
// [Hello, i, am, sksdud, nice, to, meet, you]

• Arrays.toString()
  • 자바에서 배열 내용 그 자체를 출력하고자 할 때
  • strNew.toString()을 사용하면 배열 내용이 아니라 배열의 주소값이 출력된다.
  • Arrays.toString(strNew)를 사용한다. 
• 문자열 결합
  • 두 문자열을 합칠 때도 덧셈(+)을 사용한다. 
  • 문자열 + anyType ➡ 문자열 + 문자열 ➡ 문자열
  • 피연산자가 모두 숫자일 때는 두 수를 더하지만, 어느 한쪽이라도 String이면 다른 한 쪽도 String으로 만든 다음 두 String을 반환한다. 
• charAt() 메서드
  • String 타입으로 저장된 문자열 중에서 한 글자만 선택해서 char타입으로 변환해준다.
  • 문자열이름.charAt(문자열 번호);
• 결과 출력하기
  • 결과값을 담을 빈 문자열을 하나 만든다.
  • 배열 수만큼 반복문을 돌면서 각 요소의 첫번째 알파벳을 추출한 후 더한다. (문자열 결합)
  • 더한 결과를 리턴한다. 

String strReturn="";
for(int i=0;i<strNew.length;i++){
	strReturn+=strNew[i].charAt(0);
}
return strReturn;

 

 

3️⃣ 연습문제

---

 

수도코드를 습과화하랍신다.

아 나 왜이렇게 못하지 짜증난다 ㅏ 

주석을 쓰던가 종이에 펜으로 쓰던가 아무렇게나 하려무나

 

 

length

size();

 

length는 메서드로 구현된 것이 아니다. 

메소드 실행문( )

 

 

5번 프린터

List

ArrayList 

차이 

 

다르게 쓰이는 이유

어떤 상황에서 쓰이는지

 

 

 

 

4️⃣ 학습 컨텐츠

---

Tree

그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 트리구조라고 부른다. 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조이다. 

비선형 구조. 무방향 연결 계층적 자료구조. 

• 루트(root)라는 하나의 꼭짓점 데이터를 시작으로 여러개의 데이터를 간선(edge)으로 연결합니다. 
  • 각 데이터를 노드라고 한다.
  • 두개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가진다.
  • 부모노드(Parent Node), 자식노드(Child Node)
  • 자식이 없는 노드는 리프노드(Leaf Node)
  • 용어정리 : 노드, 간선, 루트, 부모노드, 자식노드, 형제노드, 리프노드
• 자료구조 Tree는 깊이, 높이, 레벨을 측정할 수 있다.
  • 깊이 (Depth)
  • 루트로부터 하위 계층의 특정 노드까지의 깊이를 표현한다. 배열의 인덱스 처럼 0, 1, 2...
  • 레벨(Level)
  • 같은 깊이를 가지고 있는 노드를 묶어서 레벨(Level)로 표현한다. 같은 레벨에 나란히 있는 노드를 형제노드(Sibling Node)라고 한다. Level 1, Level 2, Level 3...
  • 높이(Height)
  • 리프노드를 기준으로 루트까지의 높이를 표현한다. 리프노드를 0으로 둔다. 리프노드의 부모 높이는 1. 
• 서브트리
  • root에서 뻗어 나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리를 서브 트리라고 부른다. 

파일 시스템이 대표적인 트리구조이다.

---

Binary Search Tree

트리구조는 편리한 구조를 전시하는 것 외에 효율적인 탐색을 위해 사용한다. 이진트리, 이진탐색 트리

• 이진트리
  • 자식 노드가 최대 두개인 노드들로 구성된 트리.
  • 왼쪽 자식 노드, 오른쪽 자식 노드
  • 정 이진 트리, 완전 이진 트리, 포화 이진 트리
• 이진 탐색 트리
  • 모든 왼쪽 자식의 값이 루트나 부모보다는 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가진다. 

이진 트리 종류	영문명	설명
정 이진 트리	Full binary tree	각 노드가 0개 혹은 2개의 자식 노드를 갖는다.
포화 이진 트리	Perfect binary tree	정 이진트리이면서 완전 이진 트리인 경우이다. 모든 리프 노드레벨이 동일하고 모든 레벨이 가득 채워져있다.
완전 이진 트리	Complete biary tree	마지막 레벨을 제외한 모든 노드가 가득 차 있어야한다. 마지막 레벨의 노드는 차지 않아도 되지만 왼쪽은 채워져야한다.

트리 순회

특정 목적을 위해 트리의 모든 노드를 한번씩 방문하는 것을 트리 순회라고 한다. 트리는 계층적 구조라는 특징을 가지기 때문에 모든 노드를 순회하는 방법엔 크게 세가지가 있다.

• 전위 순회(preorder) 
• 중위 순회(inorder)
• 후위 순회(postorder)

중위와 후위 순회의 시작은 맨 아래에서부터

 

---

그래프

그래프는 여러개의 점들이 서로 복잡하게 얽혀있는 관계를 표현한 자료구조이다. 수학에서 쓰이는 그래프와 달리 컴퓨터 공학에서의 그래프는 거미줄처럼 여러개의 점과 선으로 이어져있는 복잡한 네트워크망과 같은 모습을 가진다. 

직접적인 관계. 간접적인 관계. 하나의 점을 정점(Vertex), 하나의 선은 간선(Edge)

 

그래프의 표현방식

인접행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 2차원 행렬입니다.

인접 리스트는 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현합니다.  

 

그래프의 용어들

사이클(Cycle)

한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현한다. 

자기루프(Self loop)

정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기루프를 가졌다고 표현한다. 다른 정점을 거치지 않는것이 특징.

 

 

BFS / DFS - 그래프 탐색의 대표적인 방법

그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적.

• Breathed - First Search
  • 가까운 정점부터 탐색한다.
  • 너비 우선 탐색
• Depth - First Search
  • 하나의 경로를 끝까지 탐색한 후, 원하는 도착지가 아니라면 다음 경로로 넘어가서 탐색
  • 깊이 우선 탐색
  • BFS보다 시간은 오래 걸릴지라도 모든 노드를 완전히 탐색할 수 있다. 

 

 

 

✅ 느낀 점

---

1. 아 해결하기 어렵다
2. 구글링
3. 해당 문제를 해결하기 위한 메서드들이 이미 나와있음

구글링을 잘하는 것도 능력이요. 해당 메서드들을 이미 만들어놓은 선배님들께도 감사를 표한다. 지금은 메서드들을 찾아서 하는데 코딩 테스트에서는 구글링을 하지 못하니 중요한 메서드들은 외워서 정리해야겠다. 사실 메서드가 아니라 코딩을 짜는 논리력이 더 부족한거같긴 하지만 머리에 들은 게 있어야 논리력도 나오지... 메서드들을 공부하면서 자바 기초를 다지는 느낌이라서 나쁘지 않은거같다. 

 

💙 Weak Point 

조건문 분기 잘하는 법 

코드의 흐름 파악하기 

논리력

💚 마음가짐 

어떻게 그런 생각을 했지? X

수학문제 풀듯이 코딩을 하자 - 체득

---

나의 부족함을 인정하고
발전할 수 있다는 믿음을 가지고 노력한다.
누구나 처음은 있다는 것을 기억할 것