25.11.18일자 - TIL

코딩 테스트 3-7
트리의 기본 개념과 구성 요소를 이해하는 시간.
트리 자료구조를 배열과 연결 리스트로 구현하는 방법을 학습.
트리의 순회 방식의 원리와 차이점을 파악.

전위, 중위, 후위 순회 방법이 있다.

선형과 달리 부모-자식 관계를 기반으로 한 계층 구조를 형성한다.

루트(root)노드에서 시작하여, 간선(vertex)을 통해 자식 노드로 이어지는 구조로 뿌리와 유사하다.

노드 - 트리를 구성하는 요소(값)
간선 - 노드와 노드를 잇는 선, 상대적으로 위에 있으면 부모 노드, 아래라면 자식 노드라고 한다.
레벨 - 루트 노드에서 특정 노드까지 거쳐가는 최소한의 간선 수(촌수)
리프 노드 - 자식 노드가 없는 노드를 칭하는 명칭
차수 - 특정 노드에서 아래로 향하는 간선의 개수(자식 노드 수)

배열로 구현하면 구현하는 건 쉽지만 비효율적이기 쉽다.

인접 리스트로 구현하기.

// 목적: 인접 리스트 방식으로 트리를 표현하고 출력하는 예제 (노드 추가 버전)
// 동작: 각 노드는 자식 노드를 리스트로 저장하며, 출력 시 부모 -> 자식 관계를 보여줌

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 9; // 노드 개수 (0부터 8까지 총 9개 노드)
    vector<vector<int>> tree(n);

    // 트리 간선 정보 추가 (0을 루트로 가정)
    tree[0].push_back(1);
    tree[0].push_back(2);
    tree[1].push_back(3);
    tree[1].push_back(4);
    tree[2].push_back(5);
    tree[2].push_back(6);
    tree[3].push_back(7);
    tree[4].push_back(8);

    // 트리 출력
    for (int i = 0; i < n; ++i) {
        cout << i << " -> ";
        for (int child : tree[i]) {
            cout << child << " ";
        }
        cout << endl;
    }

    return 0;
}

/*
출력결과
0 -> 1 2
1 -> 3 4
2 -> 5 6
3 -> 7
4 -> 8
5 ->
6 ->
7 ->
8 ->
*/

인접리스트로 구현하는 케이스가 나올 확률은 더 높으나 둘 다 나올 만 하다.

순회
트리에 존재하는 모든 노드를 빠짐없이 한 번씩 방문하는 과정
부모 노드를 먼저 방문하면 전위 순회, 중간에 방문하면 중위 순회, 마지막에 방문하면 후위 순회라 부른다.

전위 순회
부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드
왼쪽 자식을 타고 내려간 후 자식이 없을 때 돌아온 후 오른쪽 자식 노드를 가는 순서로 진행.
// 목적: 인접 리스트 방식으로 구성된 트리에서 전위 순회를 수행하는 예제
// 동작: 전위 순회 방식 (부모 → 왼쪽 자식 → 오른쪽 자식)으로 트리 노드를 출력

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> tree(100);

void preorder(int node) {
    cout << node << " ";             // 1. 부모 방문
    for (int child : tree[node]) {   // 2. 자식들 순서대로 순회
        preorder(child);
    }
}

int main() {
    int n = 7;
    tree[0] = {1, 2};  // 0 -> 1, 2
    tree[1] = {3, 4};  // 1 -> 3, 4
    tree[2] = {5, 6};  // 2 -> 5, 6

    preorder(0); // 루트부터 시작

    return 0;
}

/*
출력결과:
0 1 3 4 2 5 6
*/

전위 순회가 가장 깔끔하게 생각하기 쉽다.

중위 순회
왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드

배치 자체가 왼쪽은 하락 오른쪽은 상승일 때 오름차순으로 출력하기 위한 방법(정렬 상태로 출력을 원할 때)

순회 방법 자체는 전위와 유사하지만 출력을 하지 않고 왼쪽 자식 노드를 타고 내려가서 없을 때 까지 진행한 후 출력을 시작한다는 차이가 있다.


후위 순회
트리를 삭제하거나 트리 구조의 메모리를 해체할 때 쓰인다.
왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모 노드



이진 탐색 트리
이 노드의 기본 규칙
 현재 노드보다 값이 적으면 왼쪽으로 이동한다.
 현재 노드보다 값이 크거나 같으면 오른쪽으로 이동한다.

중위 탐색을 하면 정렬을 할 수 있다.

이진 탐색 트리의 효율
1 2 3 6 8 7 9 의 트리에서 5를 찾았을 때
 부모 노드인 3에서 큰 수 6으로 간 후 왼쪽 자식 노드가 없으므로 존재하지 않음으로 종결된다.

트리가 균형을 유지하고 있을 때 노드 N개의 탐색 시간 복잡도는 O(logN)이 된다.

레드. 블랙 트리 는 균형 잡힌 이진 트리라는 개념만 이해하면 좋다.

루트 1 왼쪽 노드 = A x 2 +1  오른쪽 노드 = A x 2 +2


#include <iostream>
#include <vector>
#include <string>

using namespace std;

// 전위순회
string preorder(const vector<int>& nodes, int idx) {
  if (idx < nodes.size()) {
    string ret = to_string(nodes[idx]) + " ";
    ret += preorder(nodes, idx * 2 + 1);
    ret += preorder(nodes, idx * 2 + 2);
    return ret;
  }

  return "";
}

// 중위순회
string inorder(const vector<int>& nodes, int idx) {
  if (idx < nodes.size()) {
    string ret = inorder(nodes, idx * 2 + 1);
    ret += to_string(nodes[idx]) + " ";
    ret += inorder(nodes, idx * 2 + 2);
    return ret;
  }

  return "";
}

// 후위순회
string postorder(const vector<int>& nodes, int idx) {
  if (idx < nodes.size()) {
    string ret = postorder(nodes, idx * 2 + 1);
    ret += postorder(nodes, idx * 2 + 2);
    ret += to_string(nodes[idx]) + " ";
    return ret;
  }

  return "";
}

vector<string> solution(const vector<int>& nodes) {
  vector<string> result;
  string pre = preorder(nodes, 0);
  string in = inorder(nodes, 0);
  string post = postorder(nodes, 0);

  // 마지막 공백을 제거한 결과를 result에 추가
  pre.pop_back();
  in.pop_back();
  post.pop_back();

  result.push_back(pre);
  result.push_back(in);
  result.push_back(post);

  return result;
}

// 아래 코드는 테스트 코드 입니다.
#include <iterator>
#include <iostream>
void print(vector<string> vec)
{
    copy(vec.begin(), vec.end(), std::ostream_iterator<string>(cout, "\n"));
    cout << endl;
}

int main()
{
    print(solution({1, 2, 3, 4, 5, 6, 7}));
    /**
     출력값
     1 2 4 5 3 6 7
     4 2 5 1 6 3 7
     4 5 2 6 7 3 1
    **/

    return 0;
}


대진표와 관련된 문제

(x + 1)/2 = 부모 노드의 번호(정수로 치환했을 시)



다단계 칫솔 판매

트리로 보이더라도 트리 외에 더 효율적인 풀이 법이 있을 수 있다.

Unordered_map  key - value
이것을 사용해도 계층 구조를 구현할 수 있다.



==========================================================
캠프 튜터님의 C 언어 기초 세션
C++이 아니라 그보다 근본인 C언어에 대한 해설

냉부를 보며 요리에 흥미를 가지고 어느 정도 하게 되신 이야기.
기반에 대해 공부해야 이에 파생된 여러가지를 수행할 수 있으니 이를 잘 가져가면 좋다.
컴퓨터는 사실 바보다.
지시한 것만 한다.
절대 추측하지 않는다.
틀림없이 빠르게 반복한다.

단순 반복을 자동화 할 수 있는 능력이다.


#include <stdio.h>

int main() {
     printf(:Hello world!:);
     return 0;
}

#include - :도구 가져오기 - C++에서도 똑같이 쓰이는 언어
printf  - (글자 출력)
stdio.h   std/i(입력)/o(출력)/h


번역가(프로그래머)가 알아보기 위해 표시하는 것(?)
 -main()
 프로그램의 시작점
괄호는 항상 쌍으로 존재해야 한다.

{} - 영역을 표시해주는 괄호
return 0; - 프로그램을 무사히 종료하면 0을 보내라 ->없어도 괜찮지만 과거부터 관습적으로 써주던 마무리 내용.

; (세미콜론) - 문장의 마침표

'" 구분을 잘해야 하겠다.
문제가 있을 때 {}내에 문제가 있음으로 표시해준다.

띄어쓰기에 대한 이야기
 정리를 해두기 위해서 하는것

번역기를 -컴파일러- 라고 부른다.
중국어 주문 이야기

[c 코드] -> [컴파일러] -> [기계어(2진법 수)] -> [실행]

에러가 왜 발생할까?

문법 에러
세미콜론 누락
변수 이름 오타
라이브러리 포함 안 함 (stdio.h)
등

main.cpp:3:2: error: main cannot be declared as global variable
 int main(1); {
 ^
main.cpp:3:15: error: expected unqualified-id
 int main(1); {
              ^
2 errors generated.

틀린 것을 구글링 하면 해설을 볼 수 있다.(AI설명 등과 함께)

변수  <-> 상수

사과 세 개를 사서 총 가격을 계산하는 상황
사과 한 개 가격을 본다.
몇 개 살지 정한다.
계산해서 총 가격을 구한다.
그 값을 기억하고 있다가
계산대에서 직원에게 알려준다.

중간 정보를 어딘가에 기억하고 있어야 한다!
 사과 가격/ 개수 / 계산한 금액

필요 정보를 저장할 공간을 확보하고
값을 넣은 뒤
필요할 때 꺼내 쓰고
중간 계산(연산/변환)한 후
다시 저장해서
결과를 보여준다.

여기서 저장해 둘 곳이 변수다.

변수 선언 : 상자를 만든다.

자료형 변수이름;

int -정수
float - 실수
char - 문자 (하나의)

변수를 RAM(메모리)에 저장함

int age = 20;
a=b  b를 a에 대입하겠다.

변수의 이름은 숫자로 할 수 없다.
공백은 변수에 포함할 수 없다.  (_ 사용하는 이유.)
언더스코어를 제외한 특수문자는 사용할 수 없다.

printf("%d"),  printf("%f"),  printf("%c")  정수/실수/문자 출력

\n  줄바꿈

#include <stdio.h>

int main() {
    int age = 25;
    float height = 175.5;
    char grade = 'B';

    printf("age: %d\n", age);
    printf("height: %.1f\n", height);
    printf("grade: %c\n", grade);

    return 0;
}

형식 지정자와 변수 값의 쌍이 같으면 문제가 없다.
위 문구에서 
printf("age: %d 

scanf

#include <stdio.h>

int main() {
    int age;
    float height;
    char grade;

    printf("age : \n");
    scanf("%d", &age);

    printf("height: \n");
    scanf("%f", &height);

    printf("grade (A/B/C): \n");
    scanf("%c", &grade);

    printf("\nResult\n");
    printf("age: %d\n", age);
    printf("height: %.1f\n", height);
    printf("grade: %c\n", grade);

    return 0;
}

값을 하나 씩 적어줘야 정상 출력이 된다.
age
28(입력)
height
178.1(입력)
grade (A/B/C)
A (입력)
->

Result
age: 28
height: 178.9
grade: A


===========================================================
언리얼 실습 1-10

이중 1-10만 포함 나머지 내용은 11장의 실습내용

+            -             X              /
Add, Subtract, Multiply, Divide

XOR - 두 참 거짓이 서로 다를 때 참


============================
언리얼 실습 1-11

11장 여분 내용과 숙제 4-1의 내용
30발일 때 재장전(R 키 입력 시) FUll! 출력
0발일 때 사격(마우스 우클릭 시) No_Bullet 출력