25.11.19일자 - TIL

코딩 테스트 3-8

그래프의 구성 요소, 구현 방식을 알 수 있는 시간
깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)의 기본 동작 원리와 구현 방법을 학습한다.

그래프의 개념 구성 요소, 표현 방법(인접 행렬과 리스트)
장단점과 성능을 비교

그래프란?
유한한 수의 정점과 이들을 연결하는 간선들의 집합으로 구성된 비선형 자료구조. <-> 트리 계층적 자료 구조

노드
동그라미로 표현한 부분
간선
노드와 노드를 연결한 것(주로 선으로 표현)
가중치
간선 위에 숫자로 표현한 수치

그래프의 특징
흐름을 표현하는 방향성
간선의 방향 유무에 따라 방향 그래프, 무방향 그래프로 나뉜다.

흐름의 정도를 표현하는 가중치
간선에 가중치가 있는 그래프를 가중치 그래프라고 한다.

시작과 끝의 연결  여부를 보는 순환
시작 노드에서 다시 시작 노드로 돌아오는 그래프를 순환 그래프라고 한다.
그렇지 않으면 비순환 그래프라고 한다.

그래프의 구현
인접 행렬과 인접 리스트가 있다.

==========
// 목적: 인접 행렬을 사용해 가중치가 있는 방향 그래프를 구현
// 동작: 서울(0)에서 부산(1)로 가는 간선이 있으며, 가중치는 400

#include <iostream>
using namespace std;

int main() {
    const int N = 2; // 노드 수 (서울, 부산)
    int graph[N][N] = {0}; // 초기화된 인접 행렬

    graph[0][1] = 400; // 서울(0) -> 부산(1)

    cout << "서울 → 부산 가중치: " << graph[0][1] << endl;

    return 0;
}

/*
출력결과
서울 → 부산 가중치: 400
*/
==========

인접 리스트

노드 개수만큼 배열을 준비한다.
이 배열의 인덱스는 시작 노드가 된다.
간선은 시작 노드에서 끝 노드까지 이어지는 선인데 각각 시작 노드에서 연결된 노드 들을 표시할 것이다.

각 배열에 해당 노드를 시작 노드로 하는 끝 노드 들을 추가한다.

인접 행렬과 인접 리스트 비교

인접 행렬의 장단점
단점
노드 수에 비해 간선 수가 적은 그래프 생성 시 메모리 낭비가 심하다.
인접 행렬의 경우 노드 수가 V라면 V x V 크기의 인접 행렬이 필요하기 때문.

장점
특정 간선이 있는지 확인하는 연산이 O(1)이므로 매우 빠르다.
임의 접근을 통해 바로 확인할 수 있기 때문
구현 난이도가 낮다!

노드 수가 1000개 미만일 때 사용하면 좋다.


리스트가 굳이 따지자면 좀 더 자주 사용되긴 한다.

인접 리스트의 장단점
단점
최악의 경우 간선의 개수가 E라고 하면, 특정 간선의 존재를 확인하는데 O(E)가 필요하다
물론 이런 케이스는 드물다

간선을 Edge라 칭하므로 E를 사용.

장점
실제 연결된 노드들에 대해서 만 연결하면 되므로 메모리 낭비가 없다.

주로 간선의 개수가 많으면 행렬 적으면 리스트를 활용하면 되고 판단이 어렵다면 리스트를 사용하는 것이 무난하다.


**둘은 잘 나온다
깊이 우선 탐색 (DFS)
더 이상 방문할 노드가 없으면, 가장 최근에 방문했던 노드로 간다.(백트래킹)
해당 노드와 연결된 노드 중 방문하지 않은 노드가 있는지 확인 후 1을 반복
위 과정을 모든 노드를 방문할 때까지 수행

스택과 재귀 함수를 이용해 이를 구현할 수 있다.
코딩 테스트에서는 재귀로 구현할 확률이 99%다.

===
// 목적: DFS는 한 방향으로 가능한 깊이까지 먼저 탐색하는 방식임을 설명
// 동작: 0 → 1 → 3 → 4 → 2

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

const int N = 5;
vector<int> graph[N];
bool visited[N];

void DFS(int v) {
    visited[v] = true;
    cout << v << " ";

    for (int u : graph[v]) {
        if (!visited[u]) {
            DFS(u);
        }
    }
}

int main() {
    graph[0] = {1, 2};
    graph[1] = {3};
    graph[3] = {4};

    DFS(0);
    return 0;
}

/*
출력결과
0 1 3 4 2
*/
===



너비 우선 탐색 (BFS)

시작 지점에서 방문 가능한 모든 인접 노드를 찾아 큐(Queue)에 넣는다.
큐에서 노드를 하나씩 꺼내며, 꺼낸 노드와 인접한 노드 중 아직 방문하지 않은 노드를 큐에 차례대로 추가한다.
큐가 빌 때까지 1. 2.를 반복하며, 모든 노드를 탐색한다.

===
// 목적: BFS는 가까운 노드부터 방문하므로 계층적 탐색이 가능함
// 동작: 0 → 1 → 2 → 3 → 4 순서로 방문됨

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

const int N = 5;
vector<int> graph[N];
bool visited[N];

void BFS(int v) {
    queue<int> Q;
    visited[v] = true;
    Q.push(v);

    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        cout << u << " ";
        for (int w : graph[u]) {
            if (!visited[w]) {
                visited[w] = true;
                Q.push(w);
            }
        }
    }
}

int main() {
    graph[0] = {1, 2};
    graph[1] = {3};
    graph[2] = {4};

    BFS(0);
    return 0;
}

/*
출력결과
0 1 2 3 4
*/
===

너비 우선 탐색은 공간 복잡도가 높다.   (큐에 쌓이는 내용물이 길게 늘어질 수 있다.)

너비 우선 탐색은 최단 경로임이 보장된다.


깊이 우선 탐색은 다시 돌아온다.

백터(vector)의 pair 타입

게임 맵의 최단거리

네트워크 개수 확인 문제.

===================================================================
코딩 테스트 3-9

백트래킹
백트래킹 알고리즘의 구조와 효율성 메커니즘을 이해하는 시간
다양한 제약 충족 문제에 백트래킹을 효과적으로 적용.

완전 탐색의 한계를 극복하는 기법인 백트래킹 알고리즘의 작동 원리를 학습한다.

상태 공간 트리와 유망 함수를 활용하여 불필요한 탐색을 가지치기(pruning)하는 과정을 익힌다.
N-Queen, 부분 집합 합 문제 등을 통해 활용 방법을 실습한다.

제약 만족 문제(Constraint Satisfaction Problem, CSP)는 주어진 제약 조건을 모두 만족하는 해답을 찾는 문제다.

스도쿠 - 아는거

지도 색칠 문제
인접한 영역이 서로 다른 색으로 칠해지도록 색칠하는 문제

N-Queen 문제
N개의 퀸이 서로 공격할 수 없도록 체스판에 배치하는 문제


외출을 했는데 집안에 물건을 두고 온 경우
 아파트의 모든 방을 확인하는 방법 - 이상한 사람행
 다른 집은 탐색하지 않고 내 집 안에서만 탐색 - 이것이 백트래킹

유망 함수란?
백트래킹의 핵심은 답이 될 가능성이 있는지 판단하는 것.
제약 조건 검사기 역할을 하며  현재까지의 부분 해답이 문제의 제약 조건을 만족할 가능성이 있는 지를 검사.
해답에 도달할 수 없다고 판단하면, false를 반환하고 이 경로는 탐색을 중단한다.

두 수의 합
1, 2, 3, 4 네 원소 중 두 개를 합쳐 6을 초과하는 수를 만드는 방법
처음 1과 2를 가지고는 달성할 수 없으므로 백트래킹한다.

부분 집합 합
완전 탐색  O(2^N)

N-퀸 문제
NxN체스판에 체스의 퀸을 N개 배치했을 때 서로를 공격할 수 없는 위치에 놓을 수 있는 방법이 있는지 찾는 문제


던파 문제

문제를 풀이할 때 그림을 미리 그려 구도를 이해하는 순서를 가지는 것이 풀이에 도움이 된다.
문제를 보고 그래프를 그릴 수 있어야 추리할 수 있게된다.

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

using namespace std;

int maxDepth = 0;
bool visited[8] = {false, };

// 최대방문 던전수를 갱신하면서 깊이우선탐색으로 던전을 탐험
void exploreDungeon(int depth, int power, vector<vector<int>>& dungeons) {
  if(maxDepth < depth)
    maxDepth = depth;

  for(int i = 0; i < dungeons.size(); i++) {
    // 이미 방문한 던전이거나,  최소 필요 피로도가 현재 남은 피로도 보다 많은 경우
    if(visited[i] || dungeons[i][0] > power)
      continue;

    // 방문이 가능한 가능한 모든 경우를 확인
    visited[i] = true;
    exploreDungeon(depth + 1, power - dungeons[i][1], dungeons);
    visited[i] = false;
  }
}

int solution(int initialPower,vector<vector<int>> dungeons) {
  // 던전탐색 시작
  exploreDungeon(0, initialPower, dungeons);

  return maxDepth;
}




// 아래 코드는 테스트 코드 입니다.
#include <iostream>

using namespace std;

int main()
{
  cout << solution(80, {{80, 20}, {50, 40}, {30, 10}}) << endl; // 출력값 : 3
  return 0;
}
===

N- 퀸 문제
==============
#include <vector>
#include <algorithm>

using namespace std;

// 현재 행에 이미 다른 퀸이 있는지 확인하는 함수
bool isSameRow(int placedRow, int currentRow) {
  return placedRow == currentRow;
}

// 대각선에 다른 퀸이 있는지 확인하는 함수
bool isDiagonalAttack(int placedCol, int placedRow, int currentCol, int currentRow) {
  return abs(placedCol - currentCol) == abs(placedRow - currentRow);
}

// 퀸을 안전하게 배치할 수 있는지 확인하는 함수
bool isSafePosition(const vector<int> &queen, int col, int row) {
  for (int i = 0; i < col; ++i) {
    if (isSameRow(queen[i], row) || isDiagonalAttack(i, queen[i], col, row)) {
      return false;
    }
  }
  return true;
}

// 퀸을 배치하는 함수
long long placeQueens(vector<int> &queen, int col) {
  int n = queen.size();
  if (col == n) {
    return 1;
  }

  long long count = 0;
  for (int row = 0; row < n; ++row) {
    // 퀸을 놓을수 있는 위치인 경우 퀸을 놓음
    if (isSafePosition(queen, col, row)) {
      queen[col] = row;
      count += placeQueens(queen, col + 1);
      queen[col] = -1;
    }
  }
  return count;
}

long long solution(int n) {
  vector<int> queen(n, -1);

  // 퀸을 놓을수 있는 경우의 수를 반환
  return placeQueens(queen, 0);
}





// 아래 코드는 테스트 코드 입니다.
#include <iostream>

using namespace std;

int main()
{
  cout << solution(4) << endl; // 출력값 : 2
  return 0;
}


=================================================================
코딩 테스트 4-1
최단 경로 알고리즘 중
다익스트라 알고리즘과 별만 포드 알고리즘에 대해 알아보는 시간.

단일 쌍 최단 경로 문제
 특정 두 노드간의 최단 경로를 찾는 문제.

*단일 출발점 최단 경로 문제
 한 시작점에서 다른 모든 노드까지의 최단 경로를 구하는 문제

모든 쌍 최단 경로 문제
플로이드 워셜, 존슨 알고리즘이 있다.


다익스트라 알고리즘의 개념
총 최단 경로와 부분의 최단 경로는 모두 최적의 경로임을 만족해야 성립한다.

그리디 속성
매번 순간의 최선을 선택한다. - 그것이 최종적인 최선이 아닐지라도.

모든 가중치가 양수여야만 한다.

네비게이션
네트워크에서 데이터 패킷이 목적지까지 최적의 경로를 따라 전송되도록 라우팅하는데 사용

다익스트라 알고리즘
직전 노드 배열 - 최소 비용 배열

인접 행렬은 보통 시험에 나오진 않지만 그걸 구현하지 못하면 좀 더 공부해야 한다.


시작 노드를 설정하고, 각 노드까지 최소 비용을 저장할 배열과, 경로 추적을 위한 직전 노드를 저장할 배열을 초기화합니다.
최소 비용 배열은 모든 값을 무한대로 초기화합니다. - 무한이 아니어도 되나 이렇게 하는 게 좋다.
직전 노드 배열은 모든 값을 -1로 초기화합니다.
시작 노드의 최소 비용은 0으로, 직전 노드는 자기 자신으로 합니다.

====
Dijkstra(G, s):    // G는 그래프, s는 시작 정점
 dist[] ← 모든 정점에 대해 무한대(∞)로 초기화
 dist[s] ← 0
 Q ← 새로운 우선순위 큐(최소 힙) 생성
 Q에 (dist[s], s)를 삽입    // (거리, 정점) 형태로 저장

 while Q가 비어 있지 않다면:
     (currentDist, u) ← Q에서 최소 거리 원소 추출    // extract-min
     if currentDist > dist[u] then
         continue    // 이미 더 짧은 경로가 dist[u]에 반영되었으므로 무시
     // u와 인접한 각 정점 v에 대해 거리 갱신 시도
    for (v, w) in G[u]:    // (인접 정점 v, 간선 가중치 w)
        if dist[u] + w < dist[v]:
            dist[v] ← dist[u] + w
            Q에 (dist[v], v)를 삽입    // 우선순위 큐에 갱신된 거리 삽입

 return dist
====

PQT 인접 리스트

성능
 인접 행렬을 활용하는 경우에는 O(V^2)
 인접 리스트를 활용하면 O(V+E)
 우선순위 큐(이진 합)를 활용할 경우 O(V+E)log V
 피보나치 합 을 활용할 경우 O(E+ VlogV) - 이긴 한데 알기만 하면 된다.(이것까지 활용을 요구하진 않음)

==========
function BellmanFord(Graph, start):

  // 1. 초기화
  for each node in Graph:
    distance[node] ← ∞
    previous[node] ← undefined

  distance[start] ← 0

  // 2. |V| - 1번 반복하며 모든 간선을 확인
  for i from 1 to (|V|-1):
    for each edge (u, v) in Graph:           // Graph는 (u, v, w) 형태로 유지된다고 가정
      cost ← distance[u] + edgeWeight(u, v)
      if cost < distance[v]:
        distance[v] ← cost
        previous[v] ← u

  // 3. 음수 사이클 확인(선택적)
  for each edge (u, v) in Graph:
    cost ← distance[u] + edgeWeight(u, v)
    if cost < distance[v]:
      // 음수 가중치 사이클 존재
      // 음수 사이클 처리 로직(필요 시 구현)
      // 예: 별도의 플래그로 사이클 발견 사실을 알린 뒤 종료 등
      break

  return distance, previous
==========
음의 순환은 N번 째 순환에 갱신이 존재한다면 있다는 것으로 분별을 할 수 있다.

47분부터 튜터님의 언어 완성 시범
#include<>를 사용하는 개념의 이해
뼈대를 우선적으로 만들어내는 과정
뼈대를 활용하기 위한 방법을 입력하는 과정
결과 값을 출력하기 위한 과정

52분30초까지(끝나지 않았음)

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

4-1 숙제 둘 다 깔끔하게 완료 18일자에 포함되어 있음.
4-2에서 해결하지 못한 내용

루프를 두 개 그리고 후행인 B를 초기화하는 과정이 있어야 했다.

 

 

반복하는 플렛폼과 한방향으로 움직이는 폰을 만드는 과정

위와 다르게 플렛폼과 차를 이동시키는 방법.

 

액터를 회전시키는 방법

위는 엑터를 기준으로 아래는 월드좌표를 기준으로 회전시킬 수 있다.

.