자료구조 (Data Structure)

배열과 리스트

배열

• 배열의 특징
  1. 인덱스를 사용하여 값에 바로 접근할 수 있다
  2. 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다
     • 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하다
  3. 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없다
  4. 구조가 간단하므로 코딩테스트에서 많이 사용한다

값에 바로 접근해야 하거나, 크기를 늘리거나 줄여야하는 상황이 있다면 배열을 사용하자

 

리스트

리스트는 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조이다 (JAVA는 ArrayList, LinkedList를 제공)

• 리스트의 특징
  1. 인덱스가 없으므로 값에 접근하려면 Head 포인터로부터 순서대로 접근해야 한다
     • 다시 말해 값에 접근하는 속도가 느리다
  2. 포인터로 연결되어 있으므로 데이터를 삽입하거나 삭제하는 연산 속도가 빠르다
  3. 선언할 때 크기를 별도로 지정하지 않아도 된다
     
     • 다시 말해 리스트의 크기는 정해져 있지 않으며, 크기가 변하기 쉬운 데이터를 다룰 때 적절하다
  4. 포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡하다

데이터를 삽입하거나 삭제해야 하는 경우, 크기가 변하기 쉬운 데이터를 다루는 경우에는 리스트를 사용하자

 

구간 합

합 배열을 이용하여 시간복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘

구간 합의 핵심 이론

합 배열 S 정의

배열 A가 있을 때 합 배열 S는 다음과 같이 정의한다

S[i] = A[0] + A[1] + … + A[i-1] + A[i] // A[0]부터 A[i]까지의 합

• 합 배열은 기존의 배열을 전처리한 배열이라고 생각하면 된다
  • 미리 합 배열을 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N) → O(1)로 감소\

• • A[i]부터 A[j]까지의 배열 합을 합 배열 없이 구하는 경우
    • 최악의 경우 ( i가 0이고 j가 N인 경우) ⇒ O(N)
    • 이를 O(1)로 감소시킬 수 있다

 

합 배열 S를 만드는 공식

S[i] = S[i-1] + A[i]

 

구간 합을 구하는 공식

S[j] - S[i-1] // i에서 j까지 구간 합

• 다음 그림은 배열 A의 A[2]부터 A[5]까지의 구간 합을 합 배열을 통해 구하는 과정을 보여준다
  • S[5] = A[0] + A[1] + A[2] + A[3] + A[4] + A[5]
  • S[1] = A[0] + A[1]
  • S[5] - S[1] = A[2] + A[3] + A[4] + A[5]

투 포인터

배열이나 리스트와 같은 선형 자료구조에서 두 개의 포인터를 사용하여 원하는 결과를 얻는 알고리즘 기법

투 포인터 이동 원칙

• sum > N : sum = sum - start_index; start_index++;
• sum < N : end_index++; sum = sum + end_index;
• sum == N : end_index++; sum = sum + end_index; count++;

 

슬라이딩 윈도우

• 2개의 포인터로 범위를 지정한 다음 범위(window)를 유지한 채로 이동(sliding)하며 문제를 해결하는 알고리즘
  
  • 이로 인해 중복 연산을 피하고, 새로운 구간에서 추가적인 계산을 최소화하여 연산량을 줄일 수 있다

 

스택과 큐

스택

스택은 삽입과 삭제 연산이 후입선출(LIFO; Last In First Out)로 이뤄지는 자료구조이다

• 후입선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있다

• 스택 용어
  
  • top : 삽입과 삭제가 일어나는 위치를 뜻한다
  • push : top 위치에 새로운 데이터를 삽입하는 연산이다
  • pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산이다
  • peek : top 위치에 현재 있는 데이터를 단순 확인하는 연산이다

스택은 깊이우선탐색(DFS), 백트래킹 종류의 코딩테스트에 효과적으로 사용된다

 

큐

큐는 삽입과 삭제 연산이 선입선출(FIFO; First In First Out)로 이뤄지는 자료구조이다

• 선입선출은 삽입과 삭제가 양쪽에서 일어나는 특징이 있다

• 큐 용어
  • rear : 큐에서 가장 끝 데이터를 가리키는 영역이다
  • front : 큐에서 가장 앞의 데이터를 가리키는 영역이다
  • add : rear 부분에 새로운 데이터를 삽입하는 연산이다
  • poll : front 부분에 있는 데이터를 삭제하고 확인하는 연산이다
  • peek : 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산이다

큐는 너비우선탐색(BFS) 종류의 코딩테스트에 효과적으로 사용된다