시간복잡도

빅오 표기법 Big-O notation 으로 나타낸다. 계수, 상수는 계산 X

1억당 1초로 계산

---

자료구조

배열

메모리 상에 원소를 연속하게 배치한 자료구조

배열의 특징

1. O(1)에 i 번쨰 원소를 조회 및 변경 가능
2. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 있음
3. 중간에 새로운 값을 삽입 삭제 하는데에 O(N)이 소요 (선형만큼의 시간 복잡도)
   ⇒ 삽입, 삭제하려면 배열 사용하면 안된다.

딕셔너리(맵)

Key-Valeu 구조로 데이터를 저장하는 자료구조,
특정 Key 로 데이터를 O(1)에 삽입, 삭제, 조회할 수 있는 자료구조

딕셔너리 문제

스택

FILO, 나중에 넣은 값을 가장 먼저 꺼내는 자료구조

스택의 특징

1. 스택의 가장 마지막 데이터를 확인하는데 O(1)
2. 스택의 가장 마지막 데이터를 삭제하는데 O(1)

스택 문제

def solution(arr):
    answer = []
    # [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    # print('Hello Python')
    s = []
    s.append(arr[0])
    for i in range(1, len(arr)):
        if arr[i] in s and arr[i-1] is arr[i]:
            continue
        s.append(arr[i])
    
    answer =s
    return answer

def solution(arr):
    answer = []
    # [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    # print('Hello Python')

	for a in arr:
        if len(answer) != 0 and answer[-1] == a:
            continue
        else:
            answer.append(a)
    
    return answer

• O(N)
• python 에서 top() 은 stack[-1] 하면 된다.

큐

FIFO, 먼저 넣은 값을 가장 먼저 꺼내는 자료구조

큐의 특징

1. 큐의 가장 마지막에 데이터를 삽입하는데 O(1)
2. 큐의 가장 첫번째 데이터를 삭제하는데 O(1)

힙 (바이너리 이진트리)

먼저 작은(큰) 값을 가장 먼저 꺼내는 자료구조, 최대 최소값을 찾을 때 좋은 자료구조

힙의 특징

1. 힙의 가장 작은(큰) 데이터를 확인하는데 O(logN)
2. 힙의 가장 작은(큰) 데이터가 아니면 확인 불가능

힙 문제

---

정렬

정렬 알고리즘 기준

• 퀵 소트
• 머지 소트
• 병합 소트
• 버블 소트

가장 효율적인 정렬 알고리즘은 O(NlogN) 이 소요된다.

정렬문제, 슬라이싱 사용하기

정렬문제, 문자열 내 마음대로 정렬하기

def solution(strings, n):
    answer = []
    for s in strings:
        tmp = (s[n], s)
        answer.append(tmp)
    answer = sorted(answer, key = lambda x: (x[0], x[1]))
    ans = []
    for a in answer:
        ans.append(a[1])
    return ans

기능 개발