20250204 - Graph 학습하기!

명절 이후 개인적인 일로 조금 바빠지다 보니 약간 집중을 못하고 있습니다.

다시 힘내보겠습니다.

다들 새해 복 많이 받으세요!

코딩테스트

[level 1] 바탕화면 정리 - 161990

https://school.programmers.co.kr/learn/courses/30/lessons/161990

[level 1] 바탕화면 정리 - 161990 풀이코드

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

int lux = 0, luy = 0, rdx = 0, rdy = 0;
vector<int> solution(vector<string> wallpaper) {
    vector<int> answer;
    lux = wallpaper.size();
    luy = wallpaper[0].length();
    for (int i = 0; i < wallpaper.size(); i++) 
    {
        for (int j = 0; j < wallpaper[i].length(); j++) 
        {
            if (wallpaper[i][j] == '#') 
            {
                if (lux > i) lux = i;
                if (luy > j) luy = j;
                if (rdx < i + 1) rdx = i + 1;
                if (rdy < j + 1) rdy = j + 1;
            }
        }
    }
    answer.push_back(lux);
    answer.push_back(luy);
    answer.push_back(rdx);
    answer.push_back(rdy);
    return answer;
}

g++ -std=c++14 -Wall a.cpp -o test.out 실행 버그

MacOS 소프트웨어 업데이트를 진행하면서 약간 문제가 생긴 것 같다.

간단하게 해결 CommandLineTools를 제거 후 다시 설치(업데이트 보다 안전하고 빠르게 해결되는 것 같다.)

$ sudo rm -rf /Library/Developer/CommandLineTools
$ sudo xcode-select --install`

그래프 이론

그래프(Graph) → 정점과 간선들의 집합

정점(Vertex, Node)

• 그래프에서 데이터를 저장하는 기본 단위(사람, 위치 등)
• 보통 V또는 N으로 표현
• 정점들 사이를 간선으로 연결

간선(Edge)

• 정점과 정점을 연결하는 선
• 보통 E 또는 M으로 표현
• 방향이 있는 간선(유방향 그래프, 단방향 간선), 방향이 없는 간선(무방향 그래프, 양방향 간선)

InDegree & OutDegree

• A에서 B로 향하는 간선이 6개, B에서 A로 향하는 간선은 7개
  • A의 OutDegree(나가는 간선) → 6
  • A의 InDegree(들어오는 간선) → 7

가중치

• 정점과 정점사이에 드는 비용
• A에서 B까지 이동하는데 3칸이 든다면 → 해당 가중치는 3

트리

• 자식노드와 부모노드로 이루어진 계층적인 구조
• 무방향 그래프(양방향)
• 사이클이 없다(무한 루프 X)
• 간선(Edge)의 수 = 정점(Vectex, Node)의 수 - 1 → E = V - 1
• 모든 노드와 노드의 관계는 유일하다.
• 루트노드
  • 최상단에 위치한 부모 노드
• 리프노드
  • 각 가지에 맨 끝에 있는 노드, 자식 노드가 없는 노드
• 내부 노드
  • 루트노드와 리프노드 사이에 있는 노드
• 깊이
  • 루트 노드에서 특정 노드까지 최단거리로 갔을 때의 거리
• 높이
  • 루트 노드에서 리프 노드까지의 가장 긴 거리
• 서브트리
  • 트리 안에서 있는 작은 트리
• 숲(forest)
  • 트리의 집합

이진트리

• 자식노드의 수가 2 이하 인 트리
• 정이진 트리 (Full Binary Tree)
  • 자식 노드가 0 또는 2개인 이진 트리
• 완전 이진 트리 (Complete Binary Tree)
  • 왼쪽에서부터 채워져 있는 이진 트리
  • 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있고 마지막 레벨은 왼쪽부터 채워져 있다.
• 변질 이진 트리 (Degenerate Binary Tree)
  • 리프노드를 제외한 나머지 노드가 자식 노드가 하나밖에 없는 트리
• 포와 이진 트리 (Perfect Bianry Tree)
  • 모든 노드가 꽉 차 있는 이진 트리
• 균형 이진 트리 (Balanced Binary Tree)
  • 모든 노드에서 봤을 때 왼쪽 하위 트리와 오른쪽 하위 트리의 높이 차가 1 이하여야 한다.