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

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

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

✓2. 학습 목표

✓이 강의를 마치면

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

◇3. 핵심 개념

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

✎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));
    }
}

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. 직접 실습

✎직접 실습

1. 플레이어별 전투 횟수 색인을 추가합니다.
2. 조회가 한 번일 때와 1만 번일 때 필요한 연산 횟수를 식으로 비교합니다.
3. 원본 순서가 필요한 이유와 Map만으로 충분하지 않은 이유를 설명합니다.

실습 기록에는 입력 크기, 예상 결과, 실제 결과, 시간·공간 복잡도와 사용한 JDK 버전을 함께 남깁니다. 실제 사용자 ID나 개인정보 대신 P1, P2 같은 가상 데이터를 사용합니다.

?8. 이해 점검 질문 3개

?이해 점검

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

■9. 핵심 요약

■핵심 요약

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