[KB IT's Your Life 7기] 12주차 후기 - 코딩테스트 준비

[KB IT's Your Life 7기] 12주차 후기 - 코딩테스트 준비

안녕하세요! KB IT's Your Life 7기 기자단입니다 😊

벌써 12주차가 됐네요! 시간이 정말 빠르게 지나가는 것 같아요.

 

이번 주는 본격적인 알고리즘 준비 에 들어갔어요.

재귀, 그리디, 완전 탐색 개념을 배우고, 지난 시간에 배웠던 DFS까지 활용해서 문제도 직접 풀어봤답니다!

오늘 포스팅에서 차근차근 정리해볼게요

---

1. 재귀 (Recursion)

재귀란 함수가 자기 자신을 다시 호출하는 것 이에요.

처음 들으면 좀 신기하게 느껴지죠? 함수가 자기 자신을 부른다고?!

재귀를 사용하면 복잡한 문제를 작은 단위로 쪼개서 해결할 수 있어요.

대표적인 예시로 팩토리얼 계산이 있어요.

int factorial(int n) {
    if (n == 1) return 1;       // 기저 조건 (Base Case)
    return n * factorial(n - 1); // 재귀 호출
}

여기서 핵심 포인트가 하나 있어요!

재귀 함수를 만들 때는 반드시 기저 조건(Base Case) 을 설정해야 해요.

기저 조건이 없으면 함수가 무한히 자기 자신을 호출하다가 스택 오버플로우가 발생하거든요

재귀 호출이 일어날 때마다 문제의 크기가 점점 작아지고, 기저 조건에 도달하면 호출이 멈추면서 결과가 쌓여서 올라오는 구조예요!

---

---

2. 그리디 (Greedy)

그리디는 매 순간 가장 좋아 보이는 선택을 하는 알고리즘 이에요.

이름 그대로 탐욕적으로, 지금 당장 눈앞에 있는 최선의 선택을 계속해서 쌓아가는 방식이죠!

대표적인 예시로 거스름돈 문제가 있어요.

1260원을 거슬러줘야 할 때, 500원 → 100원 → 50원 → 10원 순서로 큰 단위부터 최대한 많이 사용하는 거예요.

int change = 1260;
int coins[] = {500, 100, 50, 10};
int count = 0;

for (int i = 0; i < 4; i++) {
    count += change / coins[i];
    change %= coins[i];
}

cout << count << endl; // 6

그런데 그리디가 항상 정답을 보장하진 않아요!

그리디 알고리즘이 통하려면 탐욕적 선택이 최적해를 보장하는 문제 여야 해요.

문제를 보고 "매 순간의 최선이 전체의 최선이 될 수 있는가?" 를 먼저 판단하는 게 중요해요.

---

---

3. 완전 탐색 (Brute Force)

완전 탐색은 말 그대로 가능한 모든 경우의 수를 다 탐색해서 답을 찾는 방법 이에요.

무식해 보이지만, 사실 가장 확실한 방법이기도 해요

완전 탐색의 대표적인 방식으로는 이런 것들이 있어요.

 

반복문(Loop) → 단순히 모든 경우를 반복문으로 순회하는 방법
재귀(Recursion) → 모든 경우를 재귀적으로 탐색하는 방법
BFS / DFS → 그래프나 트리 구조에서 모든 노드를 탐색하는 방법
순열 / 조합 → 모든 순열이나 조합을 생성해서 탐색하는 방법

 

완전 탐색은 시간 복잡도가 높아질 수 있기 때문에, 입력 크기가 작을 때 유효해요.

문제를 보고 "입력 범위가 작다!" 싶으면 완전 탐색을 먼저 떠올려보는 게 좋아요!

---

---

4. 잠깐! 지난 시간 복습 - BFS와 DFS

지난 시간에 BFS(너비 우선 탐색) 와 DFS(깊이 우선 탐색) 를 공부했는데요!

주로 BFS 위주로 다뤘었죠.

 

오늘은 재귀까지 배웠으니 DFS를 제대로 활용해볼 차례예요!

간단하게 두 개를 비교하고 넘어갈게요.

BFS DFS

탐색 방식	가까운 노드부터 탐색	깊이 우선으로 탐색
자료구조	큐(Queue)	스택(Stack) 또는 재귀
최단 경로	✅ 유리	❌ 불리
메모리	상대적으로 많이 사용	상대적으로 적게 사용
적합한 문제	최단 경로, 레벨 탐색	경우의 수, 백트래킹

DFS는 재귀와 찰떡궁합이에요!

깊이 들어가면서 모든 경우를 탐색하고, 막히면 되돌아오는 백트래킹 방식으로 활용할 수 있거든요.

그럼 바로 실전 문제로 가볼게요! 🔥

---

---

5. 예시 문제 풀어보기 - 프로그래머스 : 양과 늑대 🐑🐺

오늘 배운 재귀 + DFS를 활용해서 풀 수 있는 문제를 가져왔어요!

바로 프로그래머스의 "양과 늑대" 문제예요.

📋 문제 설명

이진 트리 구조의 노드들이 주어지고, 각 노드에는 양(0) 또는 늑대(1)가 있어요.

루트 노드(0번)부터 시작해서 트리를 탐색하는데, 방문한 노드의 양과 늑대 수를 누적해요.

단, 늑대 수 ≥ 양 수 가 되는 순간 양이 모두 잡아먹혀서 탐색이 불가능해져요.

이 조건을 지키면서 탐색할 때, 최대로 모을 수 있는 양의 수 를 구하는 문제예요!

💡 풀이 핵심 아이디어

핵심은 이거예요.

특정 노드를 방문하면, 그 노드의 자식 노드들이 새롭게 방문 가능한 후보 로 추가돼요.

그리고 후보 중 어떤 노드를 다음에 방문할지는 자유롭게 선택할 수 있어요.

즉, 현재 방문 가능한 후보 노드 목록을 들고 다니면서 DFS로 모든 경우를 탐색하면 돼요!

🖊️ C++ 풀이 코드

#include <bits/stdc++.h>
using namespace std;

int answer = 0;
vector<int> graph[18];

void dfs(int node, vector<int> next, int sheep, int wolf, int* info) {
    // 현재 노드가 양인지 늑대인지 확인
    if (info[node] == 0) sheep++;
    else wolf++;

    // 늑대 수가 양 수 이상이면 탐색 중단
    if (wolf >= sheep) return;

    // 최댓값 갱신
    answer = max(answer, sheep);

    // 현재 노드의 자식들을 후보에 추가
    vector<int> nextNodes = next;
    for (int child : graph[node]) {
        nextNodes.push_back(child);
    }

    // 현재 노드는 후보에서 제거 후 나머지 후보 탐색
    nextNodes.erase(find(nextNodes.begin(), nextNodes.end(), node));

    // 후보 노드들 중 하나씩 선택해서 DFS
    for (int next_node : nextNodes) {
        dfs(next_node, nextNodes, sheep, wolf, info);
    }
}

int solution(vector<int> info, vector<vector<int>> edges) {
    // 트리 구성
    for (auto& edge : edges) {
        graph[edge[0]].push_back(edge[1]);
    }

    // 루트(0번)에서 시작, 초기 후보는 {0}
    dfs(0, {0}, 0, 0, info.data());

    return answer;
}

📝 코드 흐름 정리

Step 1. 트리를 인접 리스트로 구성해요.

Step 2. 루트 노드(0번)부터 DFS를 시작해요. 초기 후보 목록은 {0} 이에요.

Step 3. 현재 노드 방문 시 양/늑대 수를 업데이트하고, 늑대 ≥ 양이면 즉시 리턴해요.

Step 4. 현재 노드의 자식들을 후보 목록에 추가하고, 현재 노드는 후보에서 제거해요.

Step 5. 남은 후보 노드들을 하나씩 선택해서 재귀적으로 탐색해요.

Step 6. 탐색하면서 양의 수 최댓값을 계속 갱신해요.

---

---

6. 이번 주 느낀 점 ✍️

이번 주는 정말 알고리즘의 핵심들을 한꺼번에 배운 느낌이에요.

재귀는 처음엔 머릿속에서 계속 호출이 쌓이는 게 잘 안 그려져서 어려웠는데, 직접 코드를 짜보면서 점점 감이 잡히더라고요!

그리디는 "이게 진짜 최선인가?" 를 항상 의심하면서 접근해야 한다는 게 포인트인 것 같아요.

완전 탐색은 확실한 만큼 시간 복잡도를 항상 염두에 두는 습관이 중요하다는 걸 느꼈어요.

그리고 오늘 풀어본 양과 늑대 문제는 DFS + 백트래킹의 묘미를 제대로 느낄 수 있는 문제였어요!

후보 노드를 들고 다니면서 탐색하는 아이디어가 처음엔 낯설었지만, 이해하고 나니까 정말 깔끔한 풀이라는 생각이 들었답니다 😄

앞으로도 꾸준히 알고리즘 문제를 풀면서 실력을 키워나가야겠어요!

다음 포스팅에서도 유익한 내용으로 돌아올게요 🙌

---

 

---