1. 배열과 리스트
코딩테스트는 자료구조를 빼놓고는 논할 수 없다.
자료구조는 데이터를 효율적으로 저장,접근,수정하기 위한 그릇이자
코테에서 데이터를 다루기 위한 전략이다.
사용해야 하는 알고리즘에 따라 적절한 자료구조를 선정해서 사용하는 것이 매우 중요하다!
그 중에서도 우리는 먼저 기초 자료구조인 배열과 리스트를 살펴보자!
모두가 알겠지만 기본 자료구조인, 배열과 리스트는 비슷하지만 다르다.
배열(Array List)이란, 메모리의 연속된 공간에 값이 채워져 있는 형태의 자료구조이다.
배열의 값은 인덱스를 통해서 참조할 수 있고, 선언한 타입의 값만 저장가능하다.
배열의 특징은 간략히 정리하면 아래와 같다.
1. 인덱스를 사용하여 값에 바로 접근 가능
2. 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다(삭제하려면 해당 인덱스 주변에 있는 값을 이동시켜야 한다)
3. 배열의 크기는 선언할 때 정할 수 있고, 한 번 선언하면 크기를 늘리거나 줄일 수 없다.
4. 구조가 간단해서 코딩테스트에서 많이 사용한다.
리스트(Linked List)는, 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조이다.
(노드는 값과 포인터를 묶어서 부르는 단위)
리스트의 특징은 아래와 같다.
1. 인덱스가 없어서 값에 접근하려면 head 포인터부터 순서대로 접근해야 해서 접근하는 속도가 느리다
2. 포인터로 연결되어 있어서 데이터를 삽입하거나 삭제하는 연산 속도가 빠르다.
3. 선언할 때 크기를 별도로 지정하지 않아도 된다. 즉, 리스트의 크기는 정해져 있지 않아서 크기가 변하기 쉬운 데이터를 다룰 때, 편하다.
4. 포인터를 저장할 공간이 필요해서 배열보다 구조가 복잡하다.
그래서 배열과 리스트의 차이점은 아래와 같은 그림으로 쉽게 이해할 수 있지 않을까?
추가/삭제 - 배열은 느리지만, 리스트는 빠르다.
(왜? 배열은 값을 변경하기 위해 값들을 이동시켜야함 하지만, 리스트는 포인터로 연결되어 있어서 값을 바로 추가 삭제 가능)
인덱스 조회(접근) - 배열은 빠르지만, 리스트는 느리다.
(왜? 배열은 인덱스에 해당하는 값에 바로 접근 가능하지만, 리스트는 Head 포인터 부터 접근하기 때문에 속도가 느리다)
그런데..?
파이썬에서는 이 모든게 상관없다. 왜냐하면,
파이썬의 리스트는 리스트의 특징과 배열의 특징까지 모두 가지도록 구현되었다.
그래서 우리는 코테에서 이러한 파이썬의 자료구조를 사용해서 다른 언어 보다 조금 더 쉽게 문제에 접근할 수 있다.
2. 구간 합
구간 합은, 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다.
코테에서 사용하는 빈도가 높다
구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다.
합 배열은 아래와 같이 정의 한다.
S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i]
(A[0]부터 A[i]까지의 합, A: 리스트, S: 합 배열)
여기서 합 배열은 기존의 배열 데이터를 전처리한 배열이라고 생각하면 된다.
이렇게 합 배열을 구해두면, 일정 범위의 합을 구하는 시간이 기존보다 절약된다.
A[i] 부터 A[j]까지의 배열 합을 합 배열 없이 구하는 경우,
최악의 경우에는 i=0, j=N 이고, 시간복잡도는 O(N)이 된다.
하지만, 합 배열을 구해두면 바로 구간의 합을 구할 수 있으니, 시간복잡도는 O(1)이 된다.
합 배열은 아래와 같이 쉽게 구할 수 있다.
S[i] = S[i-1] + A[i]
이런 합 배열을 가지고, 구간 합도 쉽게 구할 수 있다.
S[j] - S[i-1] -> i ~ j 까지의 구간 합
이 처럼 합 배열과 구간 합 공식을 잘 사용한다면 코테에서 시간복잡도를 줄이는데 많은 도움이 될 것이다!
'알고리즘 > 개념' 카테고리의 다른 글
| 코딩 테스트를 준비하기 위한 기초 개념 (시간복잡도, 디버깅) - 디버깅 (0) | 2024.12.31 |
|---|---|
| 코딩 테스트를 준비하기 위한 기초 개념 (시간복잡도, 디버깅) - 시간복잡도 (0) | 2024.12.31 |