01강. 자료구조와 알고리즘의 역할: 왜 문제 해결 방식이 중요할까?

?1. 이번 강의에서 해결할 문제

게임 기록이 몇 개일 때는 모든 목록을 훑어도 충분하지만, 기록이 수십만 개로 늘면 같은 조회를 반복하는 비용이 커집니다. 코드를 먼저 쓰기보다 입력·출력·반복 작업을 보고 자료구조와 알고리즘을 선택해야 합니다.

✓2. 학습 목표

✓이 강의를 마치면

• 자료구조와 알고리즘의 역할을 구분합니다.
• 정확성·시간·메모리·구현 난이도를 선택 기준으로 사용합니다.
• 게임 기록 조회 문제에 List와 Map을 비교 적용합니다.

◇3. 핵심 개념

자료구조는 데이터를 저장하고 관계를 표현하는 방식이고, 알고리즘은 입력을 원하는 출력으로 바꾸는 유한한 절차입니다. 좋은 선택은 언제나 가장 복잡한 구조를 쓰는 것이 아니라 제약 조건 안에서 정확하고 충분히 빠르며 유지하기 쉬운 해법을 고르는 것입니다. 아래 예제는 순서가 필요한 원본은 List, 플레이어 ID로 반복 조회하는 색인은 Map에 둡니다. 표준 컬렉션의 API 계약과 현재 구현의 내부 구조는 같은 말이 아니므로 문서가 보장하는 동작을 기준으로 판단합니다.

먼저 알아야 할 용어

용어	뜻	게임 기록 예시
데이터	프로그램이 기억하고 처리할 값	플레이어 ID P1, 점수 1450
자료구조	여러 데이터를 어떤 모양과 규칙으로 보관할지 정한 것	입력 순서를 보존하는 List, 키로 찾는 Map
알고리즘	입력을 받아 원하는 결과를 만드는 단계의 모음	P1 기록을 훑어 최고 점수를 갱신하는 절차
연산	자료에 수행하는 한 가지 작업	추가, 조회, 변경, 삭제
색인	원본을 더 빨리 찾기 위해 별도로 만든 조회용 구조	플레이어 ID → 최고 점수

자료구조를 고를 때는 데이터의 모양보다 앞으로 자주 할 연산을 먼저 봅니다. 기록을 시간순으로 한 번 출력하려면 List 하나로 충분합니다. 반면 경기 결과가 들어올 때마다 특정 플레이어의 최고 점수를 수천 번 확인한다면, 원본 목록을 유지하면서 Map 색인을 함께 두는 편이 유리합니다. 다만 색인을 갱신하지 않으면 원본과 조회 결과가 달라질 수 있으므로 두 구조를 함께 쓸 때는 갱신 책임도 정해야 합니다.

✎4. 단계별 실습

1. 예제 파일 작성

실행 환경: 코드 편집기

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: 같은 이름의 파일이 있다면 덮어쓰기 전에 Git diff로 변경 범위를 확인합니다. 선택한 LTS JDK의 java -version과 javac -version이 모두 실행되어야 합니다.

대상 파일: src/AlgorithmChoice.java

src/AlgorithmChoice.java

import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class AlgorithmChoice {
    record GameRecord(String playerId, int score) {}

    static int bestByScan(List<GameRecord> records, String playerId) {
        int best = -1;
        for (GameRecord record : records) {
            if (record.playerId().equals(playerId)) best = Math.max(best, record.score());
        }
        return best;
    }

    public static void main(String[] args) {
        List<GameRecord> records = List.of(
                new GameRecord("P1", 1200), new GameRecord("P2", 900),
                new GameRecord("P1", 1450));
        Map<String, Integer> bestIndex = new HashMap<>();
        for (GameRecord record : records) {
            bestIndex.merge(record.playerId(), record.score(), Math::max);
        }
        System.out.println("선형 조회: " + bestByScan(records, "P1"));
        System.out.println("색인 조회: " + bestIndex.getOrDefault("P1", -1));
    }
}

코드 한 줄씩 이해하기

1. record GameRecord(String playerId, int score)는 한 경기 기록에 반드시 필요한 두 값을 한 묶음으로 만듭니다.
2. bestByScan은 best를 -1로 시작하고 목록을 앞에서부터 한 번 훑습니다. 같은 ID를 만날 때만 더 큰 점수로 바꿉니다.
3. List.of(...)는 입력 순서가 보존되는 원본 기록 세 개를 만듭니다.
4. new HashMap<>()은 플레이어 ID를 키로 사용하는 빈 색인을 만듭니다.
5. merge(key, value, Math::max)는 처음 본 ID면 점수를 넣고, 이미 있으면 기존 점수와 새 점수 중 큰 값을 남깁니다.
6. getOrDefault("P1", -1)은 P1이 없을 때 null 대신 약속한 값 -1을 반환합니다.

P1의 색인이 만들어지는 흐름은 다음과 같습니다.

읽은 기록	처리 전 P1 값	처리 후 P1 값	이유
P1, 1200	없음	1200	처음 본 키이므로 저장
P2, 900	1200	1200	다른 플레이어이므로 변화 없음
P1, 1450	1200	1450	두 값 중 큰 점수를 선택

2. PowerShell에서 컴파일·실행

실행 환경: Windows PowerShell

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: src/AlgorithmChoice.java가 저장되었고 out 폴더에는 삭제해도 되는 컴파일 결과만 있는지 확인합니다.

대상: src/AlgorithmChoice.java와 out 아래 생성되는 class 파일

Windows PowerShell

Set-Location C:\dev\game-ranking-algorithms
New-Item -ItemType Directory -Force .\out | Out-Null
javac -Xlint:all -d .\out .\src\AlgorithmChoice.java
java -cp .\out AlgorithmChoice

예상 결과: 두 방식은 저장 방식은 달라도 같은 질문에 답하므로 아래처럼 동일한 최고 점수를 출력해야 합니다.

선형 조회: 1450
색인 조회: 1450

실행 시간은 PC의 CPU·메모리, JDK 버전, JVM 워밍업, 백그라운드 작업과 입력 분포에 따라 달라질 수 있습니다. 측정값은 같은 조건에서 여러 번 비교하고 Big-O 분석과 함께 해석합니다.

→5. 코드와 알고리즘이 동작하는 이유

선형 조회는 기록을 한 번씩 확인하므로 조회 한 번에 O(n)입니다. 색인을 만드는 데 O(n) 시간과 O(p) 추가 공간이 들지만, 해시가 고르게 분산된 일반적인 상황에서 이후 플레이어 조회는 평균 O(1)입니다. 단 한 번 조회한다면 선형 탐색이 더 단순할 수 있고, 같은 키를 반복 조회한다면 색인이 유리합니다.

!6. 자주 하는 실수와 해결법

!자주 하는 실수

• 실수: 무조건 평균 O(1)인 Map이 빠르다고 결론 내리기 해결: 색인을 만드는 시간과 추가 메모리, 해시 충돌 가능성까지 포함해 비교합니다.
• 실수: 자료구조 이름부터 정하고 문제를 끼워 맞추기 해결: 입력 크기, 필요한 연산, 출력 순서를 먼저 적습니다.
• 실수: 성능만 보고 읽기 어려운 구조를 선택하기 해결: 제약을 만족하는 가장 단순한 해법을 우선합니다.

✎7. 직접 실습

실습 목표

같은 게임 기록을 List로 조회하고 Map으로 색인한 뒤, 질문의 종류에 따라 적합한 구조가 달라지는 이유를 설명합니다.

시작 전 상태

src/AlgorithmChoice.java가 위 코드와 같고 두 출력이 모두 1450인지 확인합니다. 실제 사용자 ID 대신 P1, P2 같은 가상 값을 사용합니다.

1단계: 가장 작은 변경 — 기록 한 개 추가

목록 끝에 new GameRecord("P1", 1300)을 추가하고 다시 실행합니다. 1300은 현재 최고 점수보다 작으므로 두 출력은 계속 1450이어야 합니다. 값이 바뀐다면 Math::max 대신 마지막 값을 무조건 저장하고 있지 않은지 확인합니다.

2단계: 값을 바꾸고 결과 비교

방금 추가한 점수를 1700으로 바꿉니다. 선형 조회와 색인 조회가 모두 1700으로 변해야 합니다. 이 단계는 자료구조가 달라도 같은 요구 사항에는 같은 결과를 내야 한다는 정확성 검증입니다.

3단계: 직접 적용 — 전투 횟수 색인

Map<String, Integer> battleCounts를 만들고 기록을 읽을 때마다 플레이어의 전투 횟수를 1 증가시키세요. Map.merge를 사용할 수 있지만 완성 코드를 먼저 복사하지 말고 다음 힌트만 이용합니다.

✎직접 실습

• 키는 record.playerId()입니다.
• 처음 본 플레이어의 기존 횟수는 0으로 생각합니다.
• 기대 결과는 P1=3, P2=1입니다(1단계에서 추가한 P1 기록을 유지한 경우).

4단계: 스스로 확인

• 원본 입력 순서를 출력하면 P1, P2, P1, P1 순서가 유지되나요?
• 최고 점수와 전투 횟수라는 서로 다른 질문에 각각 알맞은 색인이 있나요?
• 목록을 한 번 조회할 때와 같은 플레이어를 1만 번 조회할 때의 대략적인 연산 수를 비교했나요?

막혔을 때

증상	가능한 원인	확인과 해결
NullPointerException	없는 키의 값을 바로 더함	getOrDefault 또는 merge로 첫 값을 처리합니다.
P1 횟수가 항상 1	기존 값을 덮어씀	기존 횟수와 새 값 1을 더하는 병합 함수를 사용합니다.
선형 결과와 색인 결과가 다름	둘 중 하나만 새 기록으로 갱신	원본을 추가한 뒤 색인 생성 반복문도 모든 기록을 읽는지 확인합니다.

실습 기록에는 입력 크기, 예상 결과, 실제 결과, 시간·공간 복잡도와 사용한 JDK 버전을 함께 남깁니다.

?8. 이해 점검 질문 3개

?이해 점검

1. 자료구조와 알고리즘은 각각 무엇을 결정하나요?
2. 한 번만 조회하는 작은 목록에서 선형 탐색이 합리적일 수 있는 이유는 무엇인가요?
3. 평균 O(1) 조회를 위해 추가로 지불하는 비용은 무엇인가요?

■9. 핵심 요약

■핵심 요약

문제를 입력·출력·제약·반복 연산으로 나눈 뒤 자료구조와 알고리즘을 선택합니다. 빠른 구조가 항상 최선은 아니며 정확성, 메모리, 구현 복잡도까지 함께 판단합니다.

다음 강의 연결

다음 강의에서는 “빠르다”를 막연한 느낌이 아니라 입력 크기에 따른 증가율로 비교하기 위해 Big-O와 시간·공간 복잡도를 배웁니다.