Adore__
[Do it!_Data Structure] 본문
Source : inflearn 'Do it! 알고리즘 코딩테스트 with python'
Array & List
배열
메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조
- 장점)
- 값을 index를 통해 직접 접근이 가능하다
- 단점)
- 새로운 값의 삽입 혹은 특정 index의 값을 삭제하기 어려움.
- 메모리가 연속적으로 붙어있다 보니, 삽입 삭제를 하려면 근처 값을 이동시키는 것이 필요
- 배열의 크기를 한번 선언하면, 이후에 수정할 수 없다. (크기를 늘리거나 줄일 수 없다.)
리스트
노드 (값-pointer) 단위로 연결된 자료구조이다. 다음 노드는 pointer가 가리킨다.
- 단점) index가 없으므로 head부터 순서대로 접근해야 한다. 따라서 속도가 매우 느리다.
- 장점) pointer로 연결되어 있어서 삽입 삭제가 빠르다. 크기가 가변적이다 (정해져 있지 않음).
🔻 python에서는 배열과 list를 구분하지 않는다
구간합
▪️백준 문제 11660번
원소 하나하나 더하는 것보다, 합배열의 차로 구하는 것이 시간복잡도를 줄이는 방법이다.
이 문제의 핵심은
- 입력된 N 크기만큼 미리 숫자 배열과 구간합 배열 만들기
- 숫자들이 한줄씩 들어오면, for문으로 받아서 미리 만들어 놓은 배열에 append하기
- 구간합 계산 방법으로 구간합 배열 업데이트 하기
- 구간합의 차로 특정 구간의 원소 합 구하기
🔻입력된 숫자들을 받을 때, input().split()보다 input = stdin.readline 으로 함수를 재정의 하는 것이 시간복잡도를 줄이는 방법이다.
✔︎ 문제 풀고 github에 올림
▪️백준 Sliding window 문제 11003번 (난이도 상)
이 문제는 단순히 입력과 출력의 관계만 놓고 보면 단순한 문제이다.
크기가 L인 창을 보폭 1씩 오른쪽으로 슬라이딩 하면서 최솟값을 sorting해주면 된다.
하지만 이 문제가 어려워지는 이유는 바로 L과 N의 최대값 (500만) 때문이다.
최악의 상황 Big O로 시간복잡도를 따지면, 500만개의 숫자를 모두 sorting해야하기때문에 무조건 시간초과 문제가 생긴다.
그러면 하나씩 sorting하지 않고 어떻게 최솟값을 구할까? 이 아이디어를 내는 것이 이 문제의 핵심이다.
여기서 우리는 deque 자료구조가 필요하며 아이디어는 크게 두 단계로 나뉠 수 있다.
1) 최소값 가능성이 없는 데이터를 삭제한다
만약 5 뒤에 2가 들어올 때 크기비교를 하면 5가 더 크다. 5는 최소값이 될 가능성이 없으므로 5는 날려준다.
즉, 새로 들어오는 원소와 그 앞에 있는 원소의 크기를 비교할 때, 앞의 원소 >= 새로운 원소 이면 먼저 들어갔던 원소를 삭제한다.
2) window 크기 밖으로 넘어간 데이터 삭제
1 5 2에서 우리는 5를 제거하고 1 2가 남은 상태이다.
그럼 계속해서 들어오는 3을 비교한다. 2는 3보다 작으므로 최소값이 될 가능성이 있으니 살려둔다.
그러면 이때 1 2 3 이 되어버리는데, 사실 이는 1 (5) 2 3 이었다. window 크기는 3이므로, (5) 2 3 을 벗어난 맨 앞의 1을 제거해주어야 한다.
즉, (들어오는 index i) - (window 크기) >= 가장 앞 원소의 index j 인 경우, 맨 앞에 있는 원소를 제거한다.
✔︎ 문제 풀고 github에 올림
Stack & Queue
- 스택
- 후입 선출 구조
- push -> append / pop / top -> arr[-1]
- 큐
- 선입 선출 구조
- deque을 사용해야 삽입 삭제 시간복잡도가 적음
- push -> append / pop / popleft
▪️백준 17298번 (골드)
