Pure’s Dev Blog
AboutBlog

자료구조

시간 복잡도

시간복잡도란 입력크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간이다.
실행시간은 프로그램이 돌아가는 컴퓨터의 사양과 현 상태에 따라 달라지기 때문에 정확히는 시간보다는 주요로직이 얼마나 반복되는가를 판단하는 지표라고 생각해야 한다.
이를 표기하는 단위로 빅-오 표기법 을 보통 사용한다.

빅 오 표기법 (Big - O notation)

예를 들어 10n^2 + n 의 시간복잡도를 가지는 로직이 있다고 하자.
이 때 가장 큰 증가속도를 가지는 항만을 가지고 시간복잡도를 표기하는 것이 빅오 표기법이다.
notion image
위 차트를 보면 n! > 2^n > n^2 > nlogn > n > logn > 1 의 순서로 복잡도가 낮아진다.
알고리즘 문제를 풀 때도 보면 왠만하면 nlogn을 넘기지 않아야 시간초과가 나지 않는다.
 
딴 건 다 잘 이해가 되는데 logN의 복잡도는 쉽게 이해가 되지 않았다.
로그는 지수 함수의 역함수이고 어떤 수를 나타내기 위해 고정된 밑을 몇 번 곱해야 하는지를 나타낸다.
위의 등식을 보면 32라는 수는 밑인 2를 총 5번 곱해야 된다는 것을 나타내고 있다.
#include<bits/stdc++.h>
using namespace std; 
int N;
void solve(int N){
	int a = 0, i = N; 
	while (i > 0) {
		a += i;
		i /= 2; 
	}
  cout << a << '\n';
}
int main(){ 
	cin >> N;
	solve(N);
	return 0; 
}
위와 같은 로직이 있다. N을 2로 계속 나누다 보면 i = 0 이되면서 while을 탈출하게 된다.
예를 들어 N = 10 이라면 10 → 5 → 2 → 1 → 0 까지 가고 반복이 종료된다.
이 말은 N을 2로 몇 번 나누어야 1이 되는지와 같다. ==
따라서 O()이 되는 것이다.
 

시간복잡도를 왜 체크할까?

기존 코드의 시간복잡도를 계산해서 더 낮은 복잡도로 개선한다면 성능적으로 향상되었다고 말할 수 있다.
따라서 시간복잡도는 비효율 → 효율로 나아가기 위한 지표라고 볼 수 있다.
 

공간복잡도

공간복잡도는 로직이 실행되는데 필요한 메모리 공간의 양이다.
이는 PS 하는 데에는 굳이 신경쓰지 않아도 되는 개념이다.
대신 문제에 주어진 변수들의 최대범위와 문제의 메모리 제한 최대값을 보고 적당히 생각하면 된다.
N으로 배열을 만든다고 했을 때 보통 1000만까지는 된다고 생각해도 문제가 없다.
 

JAVA의 대표적인 자료구조

강의는 C++ 기준이지만 나는 JAVA 충이기 때문에 JAVA 위주로 정리해야 겠다.
notion image

List

  1. ArrayList
    1. 가장 많이 쓰임. 중간 인덱스의 요소를 삭제하면 그 뒤 인덱스 요소들이 한 칸씩 앞으로 당겨진다.
    2. 비유하자면 한 곳에 책을 쌓아둔 형태이다.
  1. Vector
    1. ArrayList와 똑같이 작동하지만 멀티쓰레드를 통해 동시에 호출하는 것이 불가능하다. (Thread-safe)
  1. LinkedList
    1. 앞 뒤의 요소들을 실제로 연결해서 저장한다. 줄줄이 소세지 같은 형태이다.
 

Set

  1. HashSet
    1. 객체들을 순서없이 저장하고 hashcode를 통한 중복을 방지한다.
  1. TreeSet
    1. Comparator 인터페이스를 이용해 삽입되는 값이 비교되면서 정렬된 자리로 들어가게 된다.
  1. SortedSet
    1. 구현체는 없고 저렬된 set을 조작하기 위한 메서드들이 담겨 있다
    2. headSet(): 가장 작은 값부터 인자로 넘긴 값 직전까지의 요소들을 Set으로 리턴한다. [min, n)
    3. tailSet(): 가장 큰 값부터 인자로 넘긴 값까지 포함해서 요소들을 Set으로 리턴한다. [n, max]
    4. subSet(): 인자로 넘긴 A, B 사이의 인자들을 Set으로 리턴한다. [A, B) 형태로 리턴된다.
 

Stack, Queue, Deque

Stack은 후입선출(LIFO), 큐는 선입선출(FIFO)의 방식으로 동작하는 자료구조들이다.
자바에는 Deque가 있어서 Deque의 메서드로 Stack, Queue를 만들 수 있다.
Deque는 앞뒤가 다 뚫린 통이라고 생각하면 된다. LIFO 방식으로 넣고 꺼내면 스택이 되고 FIFO로 넣고 꺼내면 큐가 된다.
 

Map

  1. HashMap
    1. Key, Value 형태로 데이터를 저장한다.
  1. HashTable
    1. 해시 함수를 통해 해시값을 생성하고 해시값과 Key를 매핑해서 해시 값을 주소 값으로 쓰는 구조이다.
Copyright 2025 Pure