[정리] 알고리즘,자료구조 총 정리

01. 문제 풀이 단계

- 문제 이해, 조건씩 꼼꼼하게 체크 (반례 케이스 고려)

- 어떤 알고리즘, 자료구조를 사용해야 할지 체크

- 스스로 로직 먼저 만들어보기

- 작성한 로직 코드로 옮기기

- 시간 초과 발생시, 시간복잡도와 N의 범위 체크

 

[ 참고 ]

https://yeon-woo-kim.tistory.com/102?category=1170787 

시간 제한과 시간 복잡도

---

02. Array & Linked List

<1> 배열

- 탐색 : O(1)

- 삽입/삭제 : O(N)

---

<2> Linked List

- 탐색 : O(N)

- 삽입/삭제: O(N)

 

▶ python의 List는 내부적으로 동적 배열로 구현되어 있어서, 사실 문제 풀이시 List 사용함

---

03. 이진 탐색

* 정렬 되어 있을 때만 가능!

시간 복잡도 : O(logN) -> O(N)인 순차 탐색보단 효율적임

 

[ 참고 ]

https://yeon-woo-kim.tistory.com/55?category=1172294 

[Python] 이진탐색 binary search

▶ 문제풀이시 bisect 라이브러리 사용 

 

---

04. 정렬

<1> 버블 정렬

: 버블 정렬은 단순 교환 정렬이다. 시간 복잡도는 항상 O(N^2) 으로 그닥 효율적이진 않다.

일반 버블 정렬을 개선한 셰이커 정렬도 있는데, 그냥 개념정도만 숙지하고 있어도 충분한 듯하다.

 

[ 참고 ]

https://yeon-woo-kim.tistory.com/58?category=1172294 

[Python] 버블정렬 Bubble sort & 셰이커 정렬

▶ 문제풀이시 사용한 적 없음.

---

<2> 선택 정렬

: 제일 작은 애부터 선택해서 순서에 맞는 위치로 옮기며 정렬해 나간다.

이것도 항상 O(N^2)의 시간 복잡도를 가지며, 그닥 효율적이지 않다. 개념& 원리 정도만 숙지

---

<3> 삽입 정렬

: 정렬된 상태를 유지해가며 정렬하는 방법이다. 최악의 경우 시간복잡도는 O(N^2),

최선의 경우 시간 복잡도는 O(N)이다.

삽입 정렬을 개선한 이진 삽입 정렬이 존재하는데 이는 bisect 라이브러리를 사용하여 구현할 수 있다.

 

[ 참고 ]

https://yeon-woo-kim.tistory.com/59?category=1172294 

[Python] 단순 선택/삽입 정렬 & 이진 삽입 정렬

---

<4> 병합 정렬 (merge sort) ★

정렬에선 퀵정렬과 함께 가장 중요하다.

기술 면접에서도 단골 질문으로 나온다고 하니 정확하게 이해하는 것이 중요!

: 병합 정렬은 배열의 앞부분과 뒷부분의 두그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘이다.

여기서 그 유명한 분할 정복 개념이 사용된다.

보통 재귀로 구현하는데, merge 할 때 O(N) & merge_sort 할 때 O(log N)의 시간 복잡도를 가져서 결과적으로

항상 O(NlogN)의 시간 복잡도를 가진다

 

[ 구현 ]

array = [5, 3, 2, 1, 6, 8, 7, 4]


def merge_sort(array):
    if len(array) <= 1:
        return array
    mid = len(array) // 2
    left_array = merge_sort(array[:mid])
    right_array = merge_sort(array[mid:])

    return merge(left_array, right_array)


def merge(array1, array2):
    result = []
    array1_index = 0
    array2_index = 0
    while array1_index < len(array1) and array2_index < len(array2):
        if array1[array1_index] < array2[array2_index]:
            result.append(array1[array1_index])
            array1_index += 1
        else:
            result.append(array2[array2_index])
            array2_index += 1

    if array1_index == len(array1):
        while array2_index < len(array2):
            result.append(array2[array2_index])
            array2_index += 1

    if array2_index == len(array2):
        while array1_index < len(array1):
            result.append(array1[array1_index])
            array1_index += 1

    return result


print(merge_sort(array))  
# [1, 2, 3, 4, 5, 6, 7, 8] 

<6> 퀵 정렬 ★

 

 

 

 

[ 참고 ]

https://yeon-woo-kim.tistory.com/63?category=1172294 

[Python] 분할 정복 - 퀵 정렬(quick sort) & 합병 정렬(merge sort)

 

---

05. 해쉬

: 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수이다.

: 해쉬 table은 시간은 빠르지만 공간을 대신 많이 사용한다.

▶ python의 딕셔너리를 사용하여 구현한다 -> 경험상 꽤 유용하게 사용되는 편인 것 같다.

 

[ 참고 ]

https://yeon-woo-kim.tistory.com/118?category=1170787 

해시 문제 - dictionary 정리

 

※ 충돌시 해결방법으로 체이닝과 개방 주소법이 있는데 이는 예전에 정리해둔 자료를 참고하자

[참고]

https://yeon-woo-kim.tistory.com/56?category=1172294 

[Python] 해시법 hashing (1) - Chaining

https://yeon-woo-kim.tistory.com/57?category=1172294 

[Python] 해시법 hashing (2) - 오픈 주소법 open addressing

---

06. 트리

: 계층형 비선형 자료구조 -> 표현에 초첨

* 큐,스택이 자료를 저장하고 꺼내는데에 초점을 둔 선형구조 인 것과 달리 트리는 표현에 초점을 둔다.

 

트리는 편향이진트리, eval..?이었나 암튼 예전 수업 때 C언어로 별 신기한 트리들을 구현했었는데,,

이진트리, 완전 이진트리만 잘 알고 있어도 될 것 같다.

 

▶ 트리는 기술면접 단골 손님! 개념 원리 구현 빠삭하게 익히기

---

<1> 완전 이진트리

-> 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야한다!

: 완전 이진트리를 배열로 구현할 수 있는데, 0번 index는 none으로 채워두고 [None, 1,2,3,4,5..] 이런식으로 구현가능

당연한 이야기지만 왼쪽 자식= 부모*2 / 오른쪽 자식 = 부모*2 +1 / 부모 = 자식//2 이다.

 

※ 완전 이진 트리의 높이

- 높이가 h 일때 모든 노드가 꽉찬 완전 이진트리의 경우, 필요한 노드의 개수는 1+2^1+2^2+2^3... 이런식으로 2^(h+1)-1 만큼이 필요하다. 따라서 최대 높이는 O(log(N))이라고 할 수 있다. 이는 뒤의 힙의 시간 복잡도를 이해하는데 필요하다.

---

07. 힙

: 힙은 사실 최대,최소값 빠르게 찾기 위해 고안된 완전 이진 트리라서,, 트리 안에 있어야 하지만 중요하기 때문에 따로 정리를 해보겠다.

: data를 넣을 때마다 동적으로 최댓값을 반영하므로, 항상 최대/최소 값들이 필요한 경우에 유용하다

* 프로그래머스의 설탕배달? 문제가 이해하기 좋았는데 현재는 없어진듯하다.. 구글링해서 다시 풀어보기!! *

 

<1> Maxheap의 원소 추가

*python의 heapq에서는 Minheap만 제공하기 때문에, heappush 할 때 꼭 (-)를 붙여줘야한다. *

: 추가시에는 원소를 맨 마지막 노드에 넣고, 부모노드와 비교하며 자리 바꾸고..이걸 반복한다

-> 시간 복잡도 : O(log N) -> 트리의 최대 높이 만큼!

 

<2> Maxheap의 원소 제거

= root의 노드를 제거하는 것

: 제거시에는 루트 노드와 맨 끝 노드를 교체하고, 맨 끝 노드를 삭제하여 return해준다.

그리고 위에부터 차근차근 비교하며 재정렬 해준다.

-> 시간 복잡도 :O(log N)

 

[ 참고 ] 

https://yeon-woo-kim.tistory.com/119?category=1170787 

 

08. DP (다이나믹 프로그래밍)

- 진짜 애증증증의 DP이다..ㅎㅎ 이어서 계속..

* 이 부분은 재정리 예정 *

 

09. 그외에도, 최다 빈출로는 DFS,BFS,최단경로 알고리즘,백트랙킹 정도..