[KB IT's your life 7기] 코딩테스트 특강 시작! 자료구조·알고리즘·시간복잡도·그래프까지

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

드디어 코딩테스트 특강이 시작됐어요!!

끝까지 재미있게 읽어주세요! 🚀

---

📌 자료구조가 뭔데?

수업 시작하자마자 자료구조가 무엇인지부터 들어갔어요.

자료구조는 데이터를 저장하고 관리하는 방식이에요.
영어로 Data Structure. 이렇게 말하면 뭔가 대단해 보이는데 사실 우리가 이미 쓰고 있는 거예요.

예를 들어 학생 이름을 저장한다고 해볼게요.

String student1 = "김민수";
String student2 = "이서연";
String student3 = "박지훈";

이것도 자료구조예요. 변수에 하나씩 담은 거죠.
근데 이러면 "전체 학생 이름 출력해줘" 할 때 일일이 다 써야 되잖아요.

String[] students = {"김민수", "이서연", "박지훈"};
for (String s : students) {
    System.out.println(s);
}

배열로 바꾸면 반복문 하나로 끝나요.
똑같은 데이터인데 어떻게 저장하느냐에 따라 문제 해결 방법이 달라지는 거예요.
이게 자료구조의 핵심이었어요.

강사님이 HashMap 예시도 보여주셨는데 이름으로 바로 점수를 꺼낼 수 있는 거 보고 아 이래서 자료구조를 많이 알아야 하는 거구나싶었습니다.

---

알고리즘 = 문제 해결 방법

자료구조 다음은 알고리즘이에요.

알고리즘이라고 하면 뭔가 수학 공식 같고 어려워 보이는데
강사님 설명 들으니까 의외로 단순했어요.

공 5개를 오름차순 정렬하라는 문제가 있으면
가장 작은 숫자를 찾아서 맨 앞에 놓고, 남은 공들에서 또 가장 작은 걸 찾아서 놓는
이 과정 자체가 알고리즘이래요.

그래서 알고리즘 공부할 때 정답이 하나 있을 것 같다는 생각을 내려놓아야 한다더라고요!
오히려 다양한 방법을 열어두고 그중에 효율적인 걸 고르는 게 중요하다는 말이 인상 깊었어요.

---

시간 복잡도

1일차에서 가장 집중해서 들었던 파트가 시간 복잡도예요.

시간 복잡도가 뭐냐면 내가 짠 코드가 실행되는 데 얼마나 걸리느냐를 수치화한 거예요.

코드를 실행하면 CPU가 한 줄 한 줄 처리하잖아요.
반복문이 있으면 그 안의 코드가 여러 번 실행되니까 시간이 늘어나요.
입력값 n이 커지면 커질수록 시간이 얼마나 늘어나느냐를 함수로 나타낸 게 시간 복잡도인 거예요.

근데 매번 5N² + 3N + 30 이런 식으로 정확하게 쓰기 귀찮잖아요.
그래서 가장 큰 항만 딱 떼서 대략적으로 표현하는 게 빅오 표기법(Big-O Notation)이에요.

• 5N² + 3N + 30 → O(N²)
• 10M + 5 → O(M)
• 상수만 있으면 → O(1)

이렇게 대강 표현하자! 가 핵심이었어요.

강사님이 퀴즈를 6개나 내셨는데, 처음에는 쉽게 시작했어요.

배열을 한 번 순회하는 코드 → O(M)
이중 반복문(for 안에 for) → O(N²)

어려웠던 문제도 있었어요
반복문이 두 개 있는데, j의 초기화가 for문 바깥에 있는 코드였거든요.
다들 반복문 두 개니까 N제곱이지!라 생각 했는데

정답은 O(N)이었어요.

왜냐면 j가 바깥에서 딱 한 번 초기화되고 나면, while문이 전체적으로 N번만 실행되고 끝나거든요.
이후에 i가 아무리 올라가도 j는 이미 N이 돼버려서 while문 안으로 못 들어가요.

이 문제를 통해서 강사님이 하고 싶었던 말은 이거였어요:

"반복문 몇 개니까 시간 복잡도가 어떻다" 이렇게 기계적으로 외우면 안 돼요.
실제 코드가 어떻게 동작하는지를 이해해야 시간 복잡도를 계산할 수 있습니다.

O(N log N)도 나왔어요

오후에는 j *= 2로 올라가는 반복문이 나왔는데, 이게 바로 로그예요.

2를 몇 번 곱해야 N이 되느냐 = log N번.
N이 128이면 7번, 1024면 10번… 아무리 N이 커져도 log N은 천천히 올라가요.

바깥에 N번 반복하는 for문이 있고, 안에 log N번 도는 while문이 있으면 → O(N log N)

근데 여기서도 j 초기화 위치에 따라 O(N log N)이 될 수도 있고 O(N)이 될 수도 있다는 함정이 있었어요.
아까 그 패턴이랑 똑같은 거예요. j가 바깥에서 초기화되면 while문이 전체에서 딱 log N번만 돌고 끝나니까요.

---

시간 복잡도를 실전에서 어떻게 쓸까?

여기서부터 진짜 꿀팁이 나왔어요.

코딩테스트 문제를 보면 제약 조건에 N의 범위가 적혀 있거든요.
예를 들어 "N ≤ 10⁵" 이렇게요.

이때 내가 생각한 풀이가 O(N²)이면?
→ (10⁵)² = 10¹⁰ → 10⁸(약 1초) 기준을 훨씬 넘김 → 시간 초과!

그래서 O(N log N)이나 O(N)으로 풀 방법을 찾아야 하는 거예요.

강사님 말씀이 10⁵가 보이면 출제자가 힌트를 주는 거다. N제곱으로 풀지 말라는 뜻이래요.

---

완전 탐색 — 코딩테스트의 기본 중의 기본

시간 복잡도 끝나고 바로 완전 탐색(Brute Force) 설명이 나왔어요.

완전 탐색은 "가능한 모든 경우의 수를 다 해보는 것"이에요.
컴퓨터의 강점이 뭐예요? 우리보다 처리 속도가 몇천만 배 빠르다는 거잖아요.
그러니까 그냥 다 시켜보는 거예요.

예를 들어 배열에서 타겟값 5를 찾으라고 하면,
앞에서부터 하나씩 비교하면 되죠. 이게 완전 탐색이에요.

"두 수의 합이 14가 되는 인덱스 쌍을 찾아라" 같은 문제도,
이중 반복문으로 모든 조합을 다 해보면 풀려요. O(N²)이지만 풀리긴 풀리는 거죠.

강사님이 강조하신 건, 앞으로 배울 DFS, BFS, 해시테이블 같은 것들도 결국 완전 탐색을 좀 더 효율적으로 하는 방법이라는 거예요.
기본이 완전 탐색이고, 거기서 시간 초과 나면 더 효율적인 알고리즘을 찾는 흐름인 거죠.

---

그래프, BFS, DFS

2일차는 본격적으로 그래프에 들어갔어요.
이날부터 머리가 진짜 바빠졌습니다…

그래프 표현 방법

그래프를 코드로 어떻게 표현하냐가 첫 번째 관문이었어요.

간선 리스트: 문제에서 보통 이 형태로 주어져요. [[0,1], [0,2], [3,1]] 이런 식으로 "누가 누구랑 연결됐다"만 쭉 나열한 거예요.

인접 리스트: 우리가 실제로 코드에서 쓸 형태예요. 각 노드별로 "나랑 연결된 노드가 누구누구다"를 리스트로 정리한 거예요.

문제에서는 간선 리스트로 주지만, 우리는 인접 리스트로 변환해서 써야 해요.
이 변환 코드가 거의 모든 그래프 문제에서 템플릿처럼 쓰인다고 하셨어요.

// 간선 리스트 → 인접 리스트 변환 (양방향)
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
    graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
    graph.get(edge[0]).add(edge[1]);
    graph.get(edge[1]).add(edge[0]); // 양방향이면 이것도 추가
}

이거 강사님이 한 20~30번 구현해봐서 그냥 술술 나와야 한다고 하셨어요.
진짜 템플릿 수준으로 외워야 하는 코드래요...

BFS — 가까운 데부터 방문하기

BFS(Breadth-First Search)는 너비 우선 탐색이에요.
시작 노드에서 가까운 노드부터 차례대로 방문하는 방식이에요.

핵심 자료구조는 큐(Queue)예요. First In, First Out.
먼저 예약한 노드를 먼저 방문하니까, 자연스럽게 가까운 데부터 방문이 되는 거예요.

동작 과정을 정리하면:

1. 시작 노드를 큐에 넣고 방문 표시
2. 큐에서 하나 꺼내서 방문
3. 연결된 노드 중 방문 안 한 것들을 큐에 넣고 방문 표시
4. 큐가 빌 때까지 2~3 반복

Queue<Integer> queue = new ArrayDeque<>();
boolean[] visited = new boolean[n];

queue.offer(start);
visited[start] = true;

while (!queue.isEmpty()) {
    int current = queue.poll();
    for (int next : graph.get(current)) {
        if (!visited[next]) {
            queue.offer(next);
            visited[next] = true;
        }
    }
}

강사님이 이 코드를 한 줄 한 줄 실행해주시면서 "예약하고 → 방문하고 → 예약하고 → 방문하고" 이 흐름을 반복해서 보여주셨는데, 이거 보니까 진짜 이해가 됐어요.

BFS의 꿀기능: 시작 노드에서 각 노드까지의 최단 거리를 구할 수 있어요!
큐에 노드 번호만 넣는 게 아니라 거리 정보까지 같이 넣으면 되거든요.

DFS

DFS(Depth-First Search)는 깊이 우선 탐색이에요.
하나의 경로를 선택하면 끝까지 파고든 후, 막히면 되돌아와서 다른 경로를 탐색하는 방식이에요.

BFS는 큐를 쓴다면, DFS는 재귀함수(또는 스택)를 써요.
왜냐면 깊이 들어갔다가 되돌아올 때, "내가 마지막으로 어디서 왔더라?"를 알아야 하거든요.
Last In, First Out — 스택의 특성이 딱 맞는 거예요.

재귀로 구현하면 코드가 진짜 짧아요:

void dfs(int current, List<List<Integer>> graph, boolean[] visited) {
    visited[current] = true;  // 방문 먼저!
    for (int next : graph.get(current)) {
        if (!visited[next]) {
            dfs(next, graph, visited);  // 재귀 호출
        }
    }
}

BFS랑 비교하면 구조 차이가 확 보이죠?
BFS는 "예약 → 방문 → 예약 → 방문"이고,
DFS는 "방문 → 다음 노드 DFS 호출 → 또 방문 → 또 호출"이에요.

강사님이 DFS 동작 과정을 하나하나 추적해주셨는데,
재귀 호출이 쌓였다가 하나씩 빠져나오는 과정이 처음엔 정신없었어요.
근데 "dfs(1) 했더니 알아서 막 방문하고 다 끝나고 돌아왔네. 오케이, 그럼 dfs(3) 해야지" 이런 식으로 이해하니까 좀 감이 잡혔어요.

재귀가 처음이신 분들은 지금 당장 이해 안 되는 게 정상이래요.ㅜㅜㅜ

---

아직 6일이나 남았는데 벌써 이 정도면
다음 수업이 기대되면서도 살짝 무섭습니다 😂

다음 포스트에서 또 만나요!