2021080

알고리즘 문제를 풀때 어떤 자료구조를 사용해야하는가?

 

python

snake = []

snake.append((1,3))

snake.append((1,2))

snake.append((1,1))

(1,3) (1,2) (1,1) => (1,4) (1,3) (1,2)

 

1. 단일 객체에 대한 표현 - Point

: 간단하기 때문에 굳이 자료구조를 사용하지 않음.

 

2. 단일 객체에 대한 표현 - Array

 

1. 탐색 : O(N)

2. 삽입 : O(N) but 맨 뒤 삽입은 O(1)

3. 삭제 : O(N) but 맨 뒤 삭제는 O(1)

4. 값 조회 : O(1)

- 머리 추가 : O(N)

- 뱀 옮기기 : O(N)

 

3. 단일 객체에 대한 표현 - LinkedList

참고로 파이썬에선 링크드리스트가 없어 deque로 대체, CPP는 리스트 사용

1. 탐색 : O(N)

2. 삽입 : O(N) but 삽입될게 정해지면 O(1)

3. 삭제 : O(N) but 무엇이 삭제될지 안다면 O(1)

4. 값 조회 : O(1)

- 머리 추가 : O(1)

- 뱀 옮기기 : O(N)

 

4. 단일 객체에 대한 표현 - Doubly Linked List(Deque)

1. 탐색 : O(N)

2. 삽입 : O(N) but 맨뒤, 맨앞 O(1)

3. 삭제 : O(N) but 맨뒤, 맨앞 O(1)

4. 값 조회 : O(N), 첫번째는 O(1)

- 머리 추가 : O(1)

- 뱀 옮기기 : O(1)

 

5. Stack

1. 맨 위 원소 조회: O(1)

2. 맨 위 원소 삽입: O(1)

3. 맨 위 원소 삭제: O(1)

=> 앞에 추가는 불가능하다.

 

파이썬 queue 대신 deque를 쓰는 이유

: 코딩테스트를 할때는 queue의 여러 기능들이 시간초과를 일으킬 수 있기 때문

 

6. Queue

1. 맨앞, 맨뒤 원소 조회 : O(1)

2. 맨 뒤 원소 삽입 : O(1)

3. 맨 앞 원소 삭제 : O(1)

 

 

<겹치는지 여부 확인>

1. 직접 순회

시간 복잡도 : (N^2)

Points 외 추가적인 공간복잡도 : O(1)

 

2. Checked 배열

시간 복잡도 : O(N)

Points 외 추가적인 공간복잡도 : O(R^2) (단, R는 checked 배열의 크기)

 

1차원 리스트를 추가해서 시간복잡도를 줄이고 싶어 하지만 최악의 경우엔 결국 시간복잡도는 O(N), 공간복잡도는 O(R^2)가 된다. 그래서 결국 2차원 리스트를 이용하는 것과 1차원리스트에서 겹치는 부분을 체크하는 것이 동일하다.

 

3. Hash Set

시간 복잡도 : O(N)

Points 외 추가적인 공간복잡도 : O(N)

시간 복잡도와 공간 복잡도가 가장 적지만 구현이 어렵다.

 

<여러 객체를 이동>

<다중 객체에 대한 표현>

1. 1차원 배열

2. 2차원 배열