close
프로필 배경
프로필 로고

Jwhy's Blogitory

Book Study/[CS] 누구나 자료구조와 알고리즘 · 2025. 7. 20. fullscreen 넓게보기

[Chapter1] - 자료 구조가 중요한 까닭

코드 품질과 효율성

프로그래밍을 처음 배울 땐 "돌아가기만 하면 성공"이었다면, 시간이 흐르면서 코드의 품질, 특히 효율성이 핵심이 된다.

예시: 2부터 100까지의 짝수 출력

var i = 0
while (i++ <= 100) {
    if (i % 2 == 0) println(i)
}
var i = 2
while (i <= 100) {
    println(i)
    i += 2
}

→ 같은 기능이지만 연산 횟수가 다르다. 성능 향상을 위해선 불필요한 연산을 줄이는 것이 핵심이다.

자료구조

자료구조(Data Structure)란, 데이터를 조직하고 저장하는 방식을 의미하며, 코드 성능에 직접적인 영향을 준다. 속도 비교 시, 실행 시간보단 연산 단계 수 기준이 더 명확한데 이를, 시간 복잡도(Big-O)로 표현한다.

코틀린의 배열 종류

코틀린에서 기본 타입의 배열을 생성하는 방법은 2가지가 존재한다.

val a = IntArray(3) { it + 1 }  // [1,2,3]
val b = arrayOf(1,2,3)          // Array<Int>

배열은 런타임 시점에 크기가 고정된 상태로 Heap 영역에 동적으로 할당된다. 크기는 변하지 않으며, GC의 대상이 된다.

영역 설명
Code 컴파일된 실행 코드
Static 전역/정적 변수
Stack 지역 변수, 함수 호출 정보
Heap 동적 할당 메모리

동적으로 할당된 메모리는 GC에 의해서 나중에 메모리가 수거된다.

IntArray

IntArray는 프리미티브 타입(int[]) 형태로 저장된다. 때문에, 메모리에는 int 값 그대로 저장이 된다.

Heap
 ┌────┬────┬────┐
 │ 1  │ 2  │ 3  │ ← 연속된 int 값 저장 (primitive)
 └────┴────┴────┘

Array

Array의 경우 제네릭 타입을 사용하기 때문에, 다양한 객체 타입을 넣을 수 있으며, Int라는 클래스의 객체 주소 값을 저장하게 된다.

Heap
 ┌────────┬────────┬────────┐
 │ ref1   │ ref2   │ ref3   │ ← 참조값 (각 Integer 객체의 주소)
 └────────┴────────┴────────┘
    ↓        ↓        ↓
  Integer  Integer  Integer
   (1)       (2)       (3)

Int 타입 자체는 프리미티브 타입이지만, Array<T>를 사용할 경우, 박싱, 언박싱이 일어나게 된다.

val a = Array<Int>(3) { it }

실제 JVM 바이트코드에서는 다음과 같이 변환된다.

Integer[] a = new Integer[3];
for (int i = 0; i < 3; i++) {
    a[i] = Integer.valueOf(i);
}

성능 측면에서는 IntArray 사용이 유리하다.

배열 연산

읽기 / O(1)

int형(4바이트) 배열의 첫 번째 요소 arr[0]가 메모리 주소 0x1000에 저장되어 있다면, arr[1]은 0x1004, arr[2]는 0x1008와 같이 각 요소가 4바이트 간격으로 연속 저장하고, 시작 메모리 주소를 기억해 두기 때문에, 임의의 인덱스에 직접 접근이 가능하다.

검색 / O(N)

기본적인 검색 로직은 다음과 같다.

fun linearSearch(arr: IntArray, target: Int): Int? {
    for (i in arr.indices) {
        if (arr[i] == target) return i
    }
    return null
}

즉, 처음부터 끝까지 탐색을 하는 것은 최대 연산이 N번 이루어질 수 있으므로, O(N)의 시간 복잡도를 가지게 된다. 실제로 kotlin에서는 배열의 값을 찾을 때, find 함수를 호출하면, 내부적으로 firstOrNull을 호출하게 된다.

삽입 / O(N)

배열 중간의 삽입할 경우, 배열에 가장 끝 부분에 새로운 칸을 할당한 뒤, 삽입할 부분의 뒷 데이터를 한 칸씩 뒤로 밀어낸 후, 빈 자리에 새 값을 넣게 된다. 때문에 최대 N번의 연산이 이뤄진다.

삭제 / O(N)

배열 중간의 데이터를 삭제할 경우, 삭제된 공간으로 뒷 데이터를 한 칸씩 당겨야하기 때문에 최대 N번의 연산이 이뤄진다.

연습 문제

문제 1, 2번

원소 100개를 포함하는 배열과 집합이 있을 때, 연산에 걸리는 단계 수 계산

연산 항목 배열 단계 수 배열 기반 집합 단계 수
읽기 1번 1번
검색 (없는 값) 100번 100번
맨 앞에 삽입 101번 201번
맨 뒤에 삽입 1번 101번
맨 앞에서 삭제 100번 100번
맨 뒤에서 삭제 1번 1번

문제 3번

일반적으로 배열에서 검색 연산은 첫 인스턴스를 찾지만, 모든 인스턴스를 찾고 싶다면 총 몇 단계가 걸릴까?

정답 : N번

티스토리툴바