2024-12-05.md

🗓️ 2024-12-05

🐌 스크럼

• 학습 목표 1. DFS
• 학습 목표 2. BFS
• 학습 목표 3. C++ Vector

💡 새로 배운 내용

1. DFS (Depth First Search) 깊이 우선 탐색

다음 브랜치로 넘어가기 전에 지금 위치한 branch를 완벽하게 탐색하고 넘어가는 방법

• 재귀나 스택으로 구현
• 노드 방문시 방문 여부를 반드시 검사해야 함 (무한 루프 방지)
• 현재 보고 있는 브랜치에 해답이 있다면 빠르게 발견할 수 있지만, 그게 아니라면 오히려 시간이 너무 많이 들 수 있음

for (int i = 0; i < graph[x].size(); i++) // 인접한 노드 사이즈만큼 탐색
{
	int y = graph[x][i]; // 현재 브랜치의 노드
	if (!visited[y]) // 방문하지 않았으면 즉 visited가 False일 때 not을 해주면 True가 되므로 아래 dfs 실행
        dfs(y); // 인접 노드 값으로 재귀적으로 또 방문
}

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

현재 노드를 방문하고 인접한 모든 노드를 탐색하는 방법

• 큐를 이용하여 구현
• 더이상 방문하지 않은 노드가 없을 때까지 BFS 적용
• 특정 조건의 최단 경로 알고리즘을 계산할 때 사용

void bfs(int start) {
    queue<int> q;
    q.push(start); // 첫 노드를 queue에 삽입
    visited[start] = true; // 첫 노드를 방문 처리

    // 큐가 빌 때까지 반복
    while (!q.empty()) {
        // 큐에서 하나의 원소를 뽑아 출력
        int x = q.front();
        q.pop();
        cout << x << ' ';
        // 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for (int i = 0; i < graph[x].size(); i++) {
            int y = graph[x][i];
            if (!visited[y]) {
                q.push(y);
                visited[y] = true;
            }
        }
    }
}

2. C++ Vector

크기가 동적으로 변하는 배열

• 크기 조정 가능
  • push_back(): 값 추가
  • pop_back(): 마지막 값 제거
• 배열처럼 인덱스로 접근 가능
• 자동 메모리 관리

vector<int> vector;

2차원 vector

2차원 배열처럼 쓰는 벡터
각 행이 또 다른 벡터로 되어있음

vector<vector<int>> grid(3, vector<int>(4, 0))

/*
0 0 0 0
0 0 0 0
0 0 0 0
*/

vector<pair<int, int>>

pair란, 두 값을 하나로 묶는 구조체
여러 개의 (x, y) 좌표를 저장할 때 유용

vector<pair<int, int>> points;

points.push_back(1,2);
points.push_back(3,4);

for (auto point: points){
    cout << point.first << "," << point.second << endl;
}

/*
(1,2)
(3,4)
*/

👏🏻 오늘의 회고

• C++은 알고리즘 문제 풀기에 편한 구조체나 함수들이 너무 많은 거 같다. C로 할 땐 머리 굴려가면서 직접 하나하나 짰어야 하는데 미리 만들어져 있는 걸 응용하니 더 편한 거 같다. 근데 너무 어렵다. C++도 잘 모르겠는데 알고리즘 문제까지 풀려하니 더 어려운 거 같다! 이번 기회로 새로운 언어도 익히고 알고리즘 실력도 키워봐야겠다. 😇

🔗 참고 자료 및 링크

• DFS, BFS 레퍼런스
• C++ pair