자료구조 기초와 Big-O

목록 보기

18/19

자료구조 기초와 Big-O 표기법 정리

개요

자료구조는 데이터를 효율적으로 저장하고 관리하기 위한 방법입니다. 이 글에서는 실무에서 자주 사용하는 주요 자료구조(Array, LinkedList, Stack, Queue, Tree, Graph, HashMap)의 특징과 시간 복잡도를 Java 예제와 함께 설명합니다. 또한 알고리즘 성능을 평가하는 Big-O 표기법의 개념과 실무 적용 방법을 다룹니다.

자료구조 기초
- Array (배열)
- LinkedList (연결 리스트)
- Stack (스택)
- Queue (큐)
- Tree (트리)
- Graph (그래프)
- HashMap (해시맵)
- 자료구조 시간 복잡도 비교표
Big-O 표기법
- Big-O란?
- 주요 Big-O 복잡도
- Big-O 판단 방법
- 실무에서 Big-O 고려가 필요한 상황
FAQ
정리

자료구조 기초

Array (배열)

개념

배열은 인덱스 기반으로 데이터를 관리하는 자료구조입니다. 메모리 상에서 연속적으로 할당되며, 각 요소는 0부터 시작하는 인덱스로 접근할 수 있습니다.

핵심 특징

배열의 주요 특징은 다음과 같습니다. 인덱스 기반 접근으로 특정 위치의 데이터를 즉시 조회할 수 있으며, 연속된 메모리 공간에 데이터가 붙어서 저장됩니다. Java 기본 배열은 생성 시 고정 크기를 가지며, 인덱스를 알면 O(1) 접근 시간으로 즉시 접근할 수 있습니다.

시간 복잡도

배열의 연산별 시간 복잡도는 접근 O(1), 탐색 O(n), 삽입 O(n)(중간 위치) 또는 O(1)(맨 끝, 크기 여유가 있을 때), 삭제 O(n)입니다.

사용 시기

배열은 데이터 크기가 고정되어 있을 때, 특정 위치(인덱스)의 데이터를 자주 조회할 때, 메모리 효율이 중요할 때, 순차적으로 모든 데이터를 순회할 때 적합합니다.

실전 예시: 게임 순위표

public class RankingSystem {
    private int[] rankings;
    
    public RankingSystem(int size) {
        this.rankings = new int[size];
    }
    
    public int getScore(int rank) {
        return rankings[rank - 1];
    }
    
    public void updateScore(int rank, int score) {
        rankings[rank - 1] = score;
    }
    
    public void printRankings() {
        for (int i = 0; i < rankings.length; i++) {
            System.out.println((i + 1) + "등: " + rankings[i] + "점");
        }
    }
}

특정 등수의 점수 조회와 등수 업데이트는 O(1), 전체 순위표 출력은 O(n) 시간이 소요됩니다.

LinkedList (연결 리스트)

개념

연결 리스트는 각 노드가 데이터와 다음 노드의 참조(포인터)로 구성된 자료구조입니다. 메모리 상에서 흩어져 있지만 참조로 연결되어 있습니다.

핵심 특징

연결 리스트는 노드 구조로 각 노드가 데이터와 다음 노드 참조를 가집니다. 비연속적 메모리에 데이터가 흩어져 있어도 되며, 동적 크기로 필요에 따라 노드를 추가하거나 삭제할 수 있습니다. 중간 삽입/삭제가 유리하여 포인터만 조정하면 O(1) 시간에 작업할 수 있습니다(위치를 알고 있을 때).

노드 구조

class Node {
    int data;
    Node next;
    
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

시간 복잡도

연결 리스트의 연산별 시간 복잡도는 접근 O(n)(처음부터 순회해야 함), 탐색 O(n), 삽입 O(1)(위치를 알고 있을 때), 삭제 O(1)(위치를 알고 있을 때)입니다.

사용 시기

연결 리스트는 중간 삽입/삭제가 빈번할 때, 크기가 동적으로 변할 때, 순차적 접근만 필요할 때(인덱스 접근 불필요), 앞/뒤 탐색이 필요할 때(이중 연결 리스트) 적합합니다.

실전 예시: 브라우저 히스토리

public class BrowserHistory {
    class Page {
        String url;
        Page prev;
        Page next;
        
        Page(String url) {
            this.url = url;
        }
    }
    
    private Page current;
    
    public void visit(String url) {
        Page newPage = new Page(url);
        
        if (current != null) {
            newPage.prev = current;
            current.next = newPage;
        }
        
        current = newPage;
    }
    
    public String goBack() {
        if (current != null && current.prev != null) {
            current = current.prev;
            return current.url;
        }
        return null;
    }
    
    public String goForward() {
        if (current != null && current.next != null) {
            current = current.next;
            return current.url;
        }
        return null;
    }
}

새 페이지 방문, 뒤로가기, 앞으로가기 모두 O(1) 시간에 처리됩니다.

Stack (스택)

개념

스택은 LIFO(Last In First Out) 구조로, 가장 나중에 들어간 데이터가 가장 먼저 나옵니다. 한쪽 끝에서만 삽입과 삭제가 일어납니다.

핵심 특징

스택은 LIFO 구조로 마지막에 넣은 것이 먼저 나옵니다. 한쪽 끝만 사용하여 top에서만 push/pop이 발생하며, 주요 메서드로 push(삽입), pop(삭제 및 반환), peek(조회만)를 제공합니다.

시간 복잡도

스택의 연산별 시간 복잡도는 삽입(push) O(1), 삭제(pop) O(1), 조회(peek) O(1), 탐색 O(n)입니다.

사용 시기

스택은 함수 호출 스택(Call Stack), 브라우저 뒤로가기, 실행 취소(Undo) 기능, 괄호 검증, DFS(깊이 우선 탐색)에 사용됩니다.

실전 예시: 실행 취소(Undo) 기능

public class TextEditor {
    private Stack<String> history;
    private Stack<String> redoStack;
    private String currentText;
    
    public TextEditor() {
        this.history = new Stack<>();
        this.redoStack = new Stack<>();
        this.currentText = "";
    }
    
    public void type(String text) {
        history.push(currentText);
        currentText += text;
        redoStack.clear();
    }
    
    public void undo() {
        if (!history.isEmpty()) {
            redoStack.push(currentText);
            currentText = history.pop();
        }
    }
    
    public void redo() {
        if (!redoStack.isEmpty()) {
            history.push(currentText);
            currentText = redoStack.pop();
        }
    }
    
    public String getCurrentText() {
        return currentText;
    }
}

텍스트 입력, Ctrl+Z(실행 취소), Ctrl+Y(다시 실행) 모두 O(1) 시간에 처리됩니다.

Queue (큐)

개념

큐는 FIFO(First In First Out) 구조로, 먼저 들어간 데이터가 먼저 나옵니다. 한쪽 끝에서 삽입하고 반대쪽 끝에서 삭제합니다.

핵심 특징

큐는 FIFO 구조로 먼저 넣은 것이 먼저 나옵니다. 양쪽 끝을 사용하여 rear에서 삽입하고 front에서 삭제하며, 주요 메서드로 offer/add(삽입), poll/remove(삭제 및 반환), peek(조회만)를 제공합니다.

시간 복잡도

큐의 연산별 시간 복잡도는 삽입(offer) O(1), 삭제(poll) O(1), 조회(peek) O(1), 탐색 O(n)입니다.

사용 시기

큐는 프린터 대기열, 작업 스케줄링, BFS(너비 우선 탐색), 이벤트 처리에 사용됩니다.

실전 예시: 게임 매칭 대기열

public class GameMatchmaking {
    class Player {
        String name;
        int rating;
        
        Player(String name, int rating) {
            this.name = name;
            this.rating = rating;
        }
    }
    
    private Queue<Player> waitingQueue;
    
    public GameMatchmaking() {
        this.waitingQueue = new LinkedList<>();
    }
    
    public void joinQueue(Player player) {
        waitingQueue.offer(player);
        System.out.println(player.name + " 대기 중... 앞에 " + 
                          (waitingQueue.size() - 1) + "명");
    }
    
    public void startMatch() {
        if (waitingQueue.size() >= 2) {
            Player p1 = waitingQueue.poll();
            Player p2 = waitingQueue.poll();
            
            System.out.println("매칭 완료: " + p1.name + " vs " + p2.name);
        } else {
            System.out.println("대기 인원 부족");
        }
    }
    
    public int getQueueSize() {
        return waitingQueue.size();
    }
}

대기열 추가, 게임 시작(2명씩 매칭), 대기 인원 확인 모두 O(1) 시간에 처리됩니다.

Tree (트리)

개념

트리는 계층적 구조를 가진 자료구조로, 루트 노드에서 시작해 부모-자식 관계로 연결됩니다. 순환(cycle)이 없는 것이 특징입니다.

핵심 특징

트리는 루트 노드 1개를 최상위에 가지며, 부모-자식 관계로 각 노드가 0개 이상의 자식을 가집니다. 순환이 없어 한 노드에서 출발해 다시 돌아올 수 없으며, 리프 노드는 자식이 없는 노드입니다.

Binary Tree (이진 트리)

이진 트리는 각 노드가 최대 2개의 자식만 가지는 트리입니다.

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int value) {
        this.value = value;
    }
}

시간 복잡도 (균형 이진 탐색 트리 기준)

균형 이진 탐색 트리의 연산별 시간 복잡도는 탐색 O(log n), 삽입 O(log n), 삭제 O(log n)입니다.

사용 시기

트리는 파일 시스템, DOM 구조, 데이터베이스 인덱스(B-Tree), 의사결정 트리, 계층적 데이터 표현에 사용됩니다.

실전 예시: 파일 시스템

public class FileSystem {
    class FileNode {
        String name;
        boolean isDirectory;
        List<FileNode> children;
        
        FileNode(String name, boolean isDirectory) {
            this.name = name;
            this.isDirectory = isDirectory;
            this.children = new ArrayList<>();
        }
        
        void addChild(FileNode child) {
            children.add(child);
        }
    }
    
    private FileNode root;
    
    public FileSystem() {
        root = new FileNode("/", true);
    }
    
    public void printFileTree(FileNode node, String indent) {
        String icon = node.isDirectory ? "[DIR] " : "[FILE] ";
        System.out.println(indent + icon + node.name);
        
        for (FileNode child : node.children) {
            printFileTree(child, indent + "  ");
        }
    }
    
    public void createSampleTree() {
        FileNode docs = new FileNode("Documents", true);
        FileNode downloads = new FileNode("Downloads", true);
        
        docs.addChild(new FileNode("report.txt", false));
        docs.addChild(new FileNode("image.png", false));
        
        root.addChild(docs);
        root.addChild(downloads);
    }
}

전체 파일 출력은 DFS 방식으로 O(n) 시간이 소요됩니다.

Graph (그래프)

개념

그래프는 노드(정점)와 간선(Edge)으로 구성된 자료구조입니다. Tree와 달리 순환 구조를 가질 수 있으며, 모든 노드가 대등한 관계입니다.

핵심 특징

그래프는 순환이 가능하여 한 노드에서 출발해 다시 돌아올 수 있습니다. 루트가 없어 모든 노드가 대등하며, 방향성에 따라 방향 그래프와 무방향 그래프로 나뉩니다. 가중치를 간선에 부여하여 비용이나 거리 값을 표현할 수 있습니다.

표현 방법

인접 리스트(Adjacency List) 방식으로 그래프를 표현할 수 있습니다.

Map<Integer, List<Integer>> graph = new HashMap<>();
graph.put(1, Arrays.asList(2, 3));
graph.put(2, Arrays.asList(1, 4));
graph.put(3, Arrays.asList(1, 4, 5));

Tree vs Graph

특징	Tree	Graph
순환	불가능	가능
루트	있음	없음 (또는 여러 개)
간선 수	n-1개	제한 없음
관계	계층적	네트워크형

사용 시기

그래프는 소셜 네트워크(친구 관계), 지도 길찾기, 네트워크 라우팅, 추천 시스템에 사용됩니다.

실전 예시: 소셜 네트워크

public class SocialNetwork {
    private Map<String, List<String>> friendGraph;
    
    public SocialNetwork() {
        this.friendGraph = new HashMap<>();
    }
    
    public void addFriend(String user1, String user2) {
        friendGraph.computeIfAbsent(user1, k -> new ArrayList<>()).add(user2);
        friendGraph.computeIfAbsent(user2, k -> new ArrayList<>()).add(user1);
    }
    
    public List<String> getFriends(String user) {
        return friendGraph.getOrDefault(user, new ArrayList<>());
    }
    
    public boolean areFriends(String user1, String user2) {
        return friendGraph.getOrDefault(user1, new ArrayList<>()).contains(user2);
    }
    
    public List<String> findMutualFriends(String user1, String user2) {
        List<String> friends1 = getFriends(user1);
        List<String> friends2 = getFriends(user2);
        
        List<String> mutual = new ArrayList<>();
        for (String friend : friends1) {
            if (friends2.contains(friend)) {
                mutual.add(friend);
            }
        }
        return mutual;
    }
}

친구 추가는 O(1), 친구 목록 조회는 O(1), 친구 여부 확인은 O(k)(k는 친구 수), 공통 친구 찾기는 O(k1 * k2) 시간이 소요됩니다.

HashMap (해시맵)

개념

해시맵은 Key-Value 쌍으로 데이터를 저장하는 자료구조입니다. 해시 함수를 사용해 Key를 해시값으로 변환하여 저장 위치를 결정합니다.

핵심 특징

해시맵은 O(1) 접근으로 평균적으로 상수 시간에 데이터를 조회, 삽입, 삭제할 수 있습니다. 순서가 없어 데이터가 삽입 순서를 보장하지 않으며(LinkedHashMap 제외), 중복 Key를 허용하지 않습니다(같은 Key로 삽입하면 덮어쓰기). 해시 충돌이 발생할 수 있지만 체이닝이나 개방 주소법으로 해결합니다.

시간 복잡도

해시맵의 연산별 시간 복잡도는 평균적으로 조회 O(1), 삽입 O(1), 삭제 O(1)이며, 최악의 경우 O(n)입니다(해시 충돌이 심할 때).

사용 시기

해시맵은 빠른 검색이 필요할 때, 중복 체크가 필요할 때, Key-Value 관계를 표현할 때, 캐싱이 필요할 때 사용됩니다.

실전 예시: 학생 자리 배치

public class ClassroomSeating {
    class Student {
        String id;
        String name;
        
        Student(String id, String name) {
            this.id = id;
            this.name = name;
        }
    }
    
    class Seat {
        int number;
        String studentId;
        
        Seat(int number, String studentId) {
            this.number = number;
            this.studentId = studentId;
        }
    }
    
    public void demonstrateHashMapEfficiency() {
        List<Seat> seats = new ArrayList<>();
        List<Student> students = new ArrayList<>();
        
        for (int i = 1; i <= 100; i++) {
            seats.add(new Seat(i, "S" + i));
        }
        
        for (int i = 1; i <= 30; i++) {
            students.add(new Student("S" + i, "학생" + i));
        }
        
        Map<String, Seat> seatMap = new HashMap<>();
        for (Seat seat : seats) {
            seatMap.put(seat.studentId, seat);
        }
        
        for (Student student : students) {
            Seat seat = seatMap.get(student.id);
            if (seat != null) {
                System.out.println(student.name + "는 " + seat.number + "에 앉음");
            }
        }
    }
}

HashMap을 사용하면 학생 ID로 자리를 찾을 때 O(1) 시간이 소요되어 총 130번의 연산(100번 삽입 + 30번 조회)으로 완료됩니다. 반복문으로 찾으면 O(n*m)으로 최대 3,000번의 연산이 필요합니다.

자료구조 시간 복잡도 비교표

자료구조	접근	탐색	삽입	삭제	특징
Array	O(1)	O(n)	O(n)	O(n)	인덱스 기반, 연속 메모리
LinkedList	O(n)	O(n)	O(1)📍	O(1)📍	포인터 연결, 비연속 메모리
Stack	O(n)	O(n)	O(1)	O(1)	LIFO, 한쪽 끝만 사용
Queue	O(n)	O(n)	O(1)	O(1)	FIFO, 양쪽 끝 사용
Binary Tree	O(log n)⚖️	O(log n)⚖️	O(log n)⚖️	O(log n)⚖️	계층 구조, 순환 없음
HashMap	O(1)✅	O(1)✅	O(1)✅	O(1)✅	Key-Value, 순서 없음

📍 위치를 알고 있을 때
⚖️ 균형 이진 탐색 트리 기준
✅ 평균적인 경우

Big-O 표기법

Big-O란?

Big-O는 알고리즘의 성능(효율성)을 나타내는 수학적 표기법입니다.

시간 복잡도는 코드가 얼마나 빠른지를 나타내고, 공간 복잡도는 코드가 메모리를 얼마나 사용하는지를 나타냅니다.

왜 필요한가?

같은 기능을 하는 코드라도 성능이 다를 수 있습니다. Big-O 표기법을 사용하면 알고리즘의 효율성을 객관적으로 비교할 수 있습니다.

주요 Big-O 복잡도

O(1) - Constant Time (상수 시간)

O(1)은 데이터 크기와 상관없이 항상 같은 시간이 걸립니다.

int[] arr = new int[1000000];
int value = arr[500000];

Map<String, Integer> map = new HashMap<>();
int score = map.get("김철수");

배열에서 인덱스로 접근하거나 HashMap에서 조회할 때 O(1) 시간이 소요됩니다.

실생활 비유로는 책의 정확한 페이지 번호를 알고 바로 펼치는 것과 같습니다.

시간
 │
 │ ──────────────  O(1)
 │
 └──────────────> 데이터 크기

O(log n) - Logarithmic Time (로그 시간)

O(log n)은 데이터가 2배 늘어나도 1번만 더 실행됩니다.

int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

이진 탐색은 정렬된 배열에서 O(log n) 시간에 값을 찾습니다.

데이터별 실행 횟수는 10개일 때 약 4번, 100개일 때 약 7번, 1,000개일 때 약 10번, 1,000,000개일 때 약 20번입니다.

실생활 비유로는 사전에서 단어를 찾을 때 중간을 펴고 앞/뒤를 판단하는 것과 같습니다.

O(n) - Linear Time (선형 시간)

O(n)은 데이터 크기에 비례해서 시간이 늘어납니다.

void printAll(int[] arr) {
    for (int num : arr) {
        System.out.println(num);
    }
}

배열의 모든 요소를 출력할 때 O(n) 시간이 소요됩니다.

데이터별 실행 횟수는 10개일 때 10번, 100개일 때 100번, 1,000개일 때 1,000번입니다.

실생활 비유로는 사전에서 처음부터 끝까지 한 페이지씩 넘기며 단어를 찾는 것과 같습니다.

O(n log n) - Linearithmic Time

O(n log n)은 효율적인 정렬 알고리즘의 시간 복잡도입니다.

Arrays.sort(arr);

병합 정렬과 퀵 정렬은 O(n log n) 시간이 소요됩니다.

실생활 비유로는 카드를 효율적으로 정렬하는 것과 같습니다.

O(n²) - Quadratic Time (제곱 시간)

O(n²)은 데이터 크기의 제곱에 비례해서 시간이 늘어납니다.

void findDuplicates(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] == arr[j]) {
                System.out.println("중복: " + arr[i]);
            }
        }
    }
}

중복을 찾기 위한 이중 반복문은 O(n²) 시간이 소요됩니다.

데이터별 실행 횟수는 10개일 때 100번, 100개일 때 10,000번, 1,000개일 때 1,000,000번입니다.

실생활 비유로는 반 학생들이 서로 악수하는 것과 같습니다.

성능 순서 (빠른 순)

O(1) > O(log n) > O(n) > O(n log n) > O(n²) > O(2ⁿ) > O(n!)
빠름 ←──────────────────────────────────────────→ 느림

Big-O 비교 그래프

시간
 │                              
 │                            ╱ O(n²)
 │                        ╱╱╱
 │                    ╱╱╱
 │                ╱╱╱       ╱ O(n)
 │            ╱╱╱       ╱╱╱
 │        ╱╱╱       ╱╱╱
 │    ╱╱╱       ╱╱╱
 │╱╱╱───────╱╱╱────────────── O(log n)
 │──────────────────────────── O(1)
 └──────────────────────────> 데이터 크기

Big-O 판단 방법

1. 반복문 하나 → O(n)

for (int i = 0; i < n; i++) {
    // ...
}

2. 중첩 반복문 → O(n²)

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // ...
    }
}

3. 절반씩 줄이기 → O(log n)

while (n > 1) {
    n = n / 2;
}

4. 직접 접근 → O(1)

arr[index] = value;
map.get(key);

실무에서 Big-O 고려가 필요한 상황

1. API 응답 시간

문제는 사용자가 늘어날수록 API가 느려지는 것이고, 해결은 O(n²)를 O(n) 또는 O(1)로 최적화하는 것입니다.

2. 페이지네이션

문제는 전체 데이터를 메모리에 로드하면 OutOfMemoryError가 발생하는 것이고, 해결은 DB에서 필요한 부분만 조회하는 것입니다.

3. 검색 기능

문제는 선형 검색이 데이터가 많으면 느린 것이고, 해결은 DB 인덱스 또는 검색 엔진을 활용하는 것입니다.

4. 중복 체크

문제는 이중 반복문이 O(n²)인 것이고, 해결은 HashSet/HashMap을 사용하여 O(n)으로 개선하는 것입니다.

5. 배치 작업

문제는 N+1 쿼리 문제로 시간 초과가 발생하는 것이고, 해결은 벌크 연산으로 쿼리 횟수를 줄이는 것입니다.

최적화가 필요한 신호

최적화가 필요한 경우는 API 응답이 3초 이상 걸리거나, 데이터베이스 쿼리가 100번 이상 실행되거나, OutOfMemoryError가 발생하거나, 배치 작업이 예상보다 10배 이상 오래 걸리거나, 사용자가 느리다고 불평할 때입니다.

FAQ

Array와 ArrayList의 차이는 무엇인가요?

Array(배열)는 크기가 고정되어 있고, 기본 타입(int, char 등)을 저장할 수 있으며, int[] arr = new int[10]; 형태로 선언합니다.

ArrayList는 크기를 동적으로 변경할 수 있고, 객체만 저장할 수 있어 Wrapper 클래스를 사용하며, ArrayList<Integer> list = new ArrayList<>(); 형태로 선언합니다.

내부적으로 ArrayList는 Array를 사용하며, 크기가 부족하면 더 큰 배열을 만들어 복사합니다.

LinkedList는 언제 사용해야 하나요?

LinkedList는 중간 삽입/삭제가 빈번할 때, 앞/뒤에서 추가/삭제가 많을 때(Deque로 사용), 순차적 접근만 필요할 때 사용합니다.

ArrayList는 인덱스로 직접 접근이 많을 때, 맨 뒤에 추가만 하는 경우, 메모리 효율이 중요할 때 사용합니다.

실무에서는 대부분 ArrayList를 사용합니다. LinkedList가 필요한 경우는 드뭅니다.

Stack과 Queue는 어떤 클래스를 사용하나요?

Stack은 다음과 같이 선언합니다.
Stack<Integer> stack = new Stack<>();
Queue는 다음과 같이 선언합니다.
Queue<Integer> queue = new LinkedList<>();
Deque<Integer> deque = new ArrayDeque<>();
실무에서는 Stack 클래스보다 Deque 인터페이스의 ArrayDeque 구현체를 사용하는 것이 권장됩니다.

HashMap과 HashSet의 차이는 무엇인가요?

HashMap은 Key-Value 쌍을 저장하며, map.put(key, value);로 삽입하고 map.get(key);로 조회합니다.

HashSet은 Value만 저장하며(내부적으로 HashMap 사용), set.add(value);로 삽입하고 set.contains(value);로 존재 여부를 확인합니다.

둘 다 O(1) 시간 복잡도를 가지며, 중복을 허용하지 않습니다.

Tree에서 순환이 없다는 것은 정확히 무슨 의미인가요?

순환(Cycle)은 한 노드에서 출발해서 다시 그 노드로 돌아올 수 있는 경로를 의미합니다.

Tree에서는 A → B → D로 갔다가 D → A로 돌아올 수 없습니다.
    A
   / \
  B   C
 /
D
Graph(순환 가능)에서는 A → B → D → C → A로 다시 A로 돌아올 수 있습니다.
A ←→ B
↕    ↕
C ←→ D
Tree는 계층적 구조이기 때문에 부모 → 자식 방향으로만 이동하며, 역방향이나 순환 경로가 없습니다.

O(1)인데 왜 실제로는 느릴 수 있나요?

Big-O는 데이터 크기가 충분히 클 때의 추세를 나타냅니다. 작은 데이터에서는 결과가 다를 수 있습니다.

예를 들어 HashMap 조회는 O(1)이지만 해시 충돌이 많으면 O(n)에 가까워지고, Array 직접 접근은 O(1)이지만 캐시 미스가 있으면 느릴 수 있습니다.

실무 팁은 Big-O가 가이드라인일 뿐이므로, 실제 성능은 프로파일링으로 측정해야 한다는 것입니다.

O(log n)은 왜 빠른가요?

절반씩 줄어들기 때문입니다.

1,000,000개 데이터에서 O(n)은 1,000,000번, O(log n)은 약 20번만 실행됩니다.

2를 몇 번 곱해야 1,000,000이 되는지 계산하면 약 20번입니다.
2^20 = 1,048,576 ≈ 1,000,000

실무에서 자료구조를 직접 구현하나요?

대부분 Java 기본 라이브러리를 사용합니다. ArrayList, LinkedList, HashMap, HashSet, Stack, Queue(LinkedList), TreeMap, TreeSet 등을 활용합니다.

직접 구현하는 경우는 특수한 요구사항이 있을 때, 성능 최적화가 필요할 때, 면접 문제를 풀 때입니다.

중요한 것은 각 자료구조의 특징과 시간 복잡도를 이해하고 적재적소에 사용하는 것입니다.

정리

자료구조 선택 가이드

상황	추천 자료구조	이유
인덱스로 빠른 접근	Array, ArrayList	O(1) 접근
중간 삽입/삭제 빈번	LinkedList	O(1) 삽입/삭제
마지막에 넣은 것 먼저 꺼내기	Stack	LIFO
먼저 넣은 것 먼저 꺼내기	Queue	FIFO
계층 구조 표현	Tree	부모-자식 관계
네트워크 관계 표현	Graph	노드 간 자유로운 연결
빠른 검색/중복 제거	HashMap, HashSet	O(1) 접근

Big-O 체크리스트

코드 작성 시

코드를 작성할 때 이중 반복문이 있으면 O(n²), 절반씩 줄이면 O(log n), 한 번만 순회하면 O(n), 직접 접근하면 O(1)입니다.

최적화 시

최적화를 고려할 때 HashMap/HashSet으로 개선 가능한지, 정렬 후 이진 탐색이 가능한지, 불필요한 반복문을 제거할 수 있는지, DB 쿼리를 줄일 수 있는지 확인합니다.

허정석

이전 포스트

CPU 스케줄링과 Linux 프로세스·포트

다음 포스트

자료구조 기초와 Big-O

TIL

자료구조 기초와 Big-O 표기법 정리

개요

목차

자료구조 기초

Array (배열)

개념

핵심 특징

시간 복잡도

사용 시기

실전 예시: 게임 순위표

LinkedList (연결 리스트)

개념

핵심 특징

노드 구조

시간 복잡도

사용 시기

실전 예시: 브라우저 히스토리

Stack (스택)

개념

핵심 특징

시간 복잡도

사용 시기

실전 예시: 실행 취소(Undo) 기능

Queue (큐)

개념

핵심 특징

시간 복잡도

사용 시기

실전 예시: 게임 매칭 대기열

Tree (트리)

개념

핵심 특징

Binary Tree (이진 트리)

시간 복잡도 (균형 이진 탐색 트리 기준)

사용 시기

실전 예시: 파일 시스템

Graph (그래프)

개념

핵심 특징

표현 방법

Tree vs Graph

사용 시기

실전 예시: 소셜 네트워크

HashMap (해시맵)

개념

핵심 특징

시간 복잡도

사용 시기

실전 예시: 학생 자리 배치

자료구조 시간 복잡도 비교표

Big-O 표기법

Big-O란?

왜 필요한가?

주요 Big-O 복잡도

O(1) - Constant Time (상수 시간)

O(log n) - Logarithmic Time (로그 시간)

O(n) - Linear Time (선형 시간)

O(n log n) - Linearithmic Time

O(n²) - Quadratic Time (제곱 시간)

성능 순서 (빠른 순)

Big-O 비교 그래프

Big-O 판단 방법

1. 반복문 하나 → O(n)

2. 중첩 반복문 → O(n²)

3. 절반씩 줄이기 → O(log n)

4. 직접 접근 → O(1)

실무에서 Big-O 고려가 필요한 상황

1. API 응답 시간

2. 페이지네이션

3. 검색 기능

4. 중복 체크

5. 배치 작업

최적화가 필요한 신호

FAQ

Array와 ArrayList의 차이는 무엇인가요?

LinkedList는 언제 사용해야 하나요?

Stack과 Queue는 어떤 클래스를 사용하나요?

HashMap과 HashSet의 차이는 무엇인가요?