알고리즘7 [쓰면서 익히는 알고리즘과 자료구조](8) 정렬(Sort) 8.1 거품 정렬(Bubble Sort) 거품 정렬은 정렬 중에서 가장 직관적인 정렬 방식이다. def bubble_sort(arr): n = len(arr) for i in range(n): done_sort = True for j in range(n - i - 1): if arr[j] > arr[j + i]: arr[j], arr[j +1] = arr[j + 1], arr[j] done_sort = False if done_sort: break return arr 8.2 삽입 정렬(Insertion Sort) def insertion_sort(arr): n = len(arr) for i in range(1, n): key_item = arr[i] j = i - 1 while j >= 0 and arr.. 2023. 2. 13. [쓰면서 익히는 알고리즘과 자료구조](7) 동적 프로그래밍(Dynamic Programming) 동적 프로그래밍은 어디서 유래되었을까? 동적(Dynamic)이란 말은 수학자인 리처드 벨만이 알고리즘의 시가변적(time_varing)이며 다단계적인 특성을 나타내기 위해서 채택한 용어라고 한다. 동적프로그래밍 알고리즘을 적용한다는 것은 하나의 문제를 작은 단위로 쪼개어 해결하고 결과를 수집 및 병합하여 최정 결론을 만들어내는 일련의 과정을 말한다. 여기서 중요한 포인트가 하나 더 있는데 동적 프로그래밍은 쪼개어진 문제를 해결해가는 과정에서 연산의 결과값을 저장하고 그 이후엔 중복된 연산의 저장된 값을 꺼내어 쓸 수 있다는 것이다. 동적 프로그래밍으로 해결하는 문제는 모든 경우의 수를 파악하여 진행하면(brute-forece) 지수승의 시간 복잡도를 가지는 경우가 많다. 피보나치수열도메모이제이션을 사용하.. 2023. 2. 13. [쓰면서 익히는 알고리즘과 자료구조](6) 트리(Tree) 트리(Tree)는 계층적 데이터를 저장하고 활용하기 위한 자료구조다. 6.2 이진 트리(Binary Tree) 다양한 목적과 목표의 트리 구성이 있는데, 이 책에서는 이진 트리 관련 문제를 주로 다루겠다. 기본적으로 이진 트리는 자식 노드가 최대 2개인 트리 구성을 말한다. 이진 트리의 종류로는 다음과 같은 세가지가 있다. 정 이진 트리(full binary tree) 모든 노드가 자식 노드를 2개 가지고 있다 완전 이진 트리(complete binary tree) 마지막 레벨을 제외한 모든 레벨에 노드가 차있다. 균형 이진 트리(balanced binary tree) 루트 노드 기준으로 왼쪽 하위 트리와 오른쪽 하위 트리의 깊이 차가 1을 넘지 않는 트리를 말한다. 6.2.1 이진 트리 표현 이진 트리.. 2023. 2. 11. [쓰면서 익히는 알고리즘과 자료구조](5) 큐(Queue) FIFO(First In First Out) 구조다. 5.1.1 큐의 기본 연산들 큐도 스택과 비슷하게 데이터를 넣고(Enqueue) 꺼내는 (Dequeue) 연산이 기본이다. Enqueue : 큐에 새로운 아이템 추가, 시간 복잡도는 O(1) Dequeue: 가장 먼저 들어갔던 아이템을 큐에서 꺼낸다. 시간 복잡도는 O(1) Front: 큐의 처음 데이터를 확인한다. Roar: 큐의 마지막 데이터를 확인한다. 5.1.2 Python 에서 Queue 사용하기 리스트 사용, append()와 pop()을 사용하면 큐 자료구조 표현 가능 리스트는 내부적으로 배열을 사용하기 떄문에 pop(0)을 통해 맨 앞 아이템을 계속 꺼내 배열을 정리하는 작업은 큐 자료구조로 이용가능하다 속도 면에서 효율적이지 못한 부분.. 2023. 2. 11. [쓰면서 익히는 알고리즘과 자료구조](4) 스택(Stack)과 재귀(Recursion) 💡 FILO - First In Last Out 재귀 알고리즘은 정상적인 수행 및 완료되기 위해 아래 3가지 조건을 만족해야 한다. 베이스(base) 케이스가 반드시 정의돼야 한다. 베이스 케이스는 재귀 호출을 마무리할 수 있는 조건이다. 앞서 살펴본 예제의 베이스 케이스는 nums 배열 요소 개수가 1인 경우로, 재귀 호출을 안 하고 마무리한다. 지속적으로 재귀 인자가 변경돼야 하고 변경되는 인자는 베이스 케이스로 수렴해야 한다. 예제를 보면 다음 재귀 호출에 전달되는 인자는 맨 앞 요소가 빠진 상태로 전달되고 이를 통해 배열의 요소 개수가 베이스 케이스로 다가가는 모양새가 된다. 재귀 알고리즘은 자기 자신을 호출하는 과정이 필요하다. 재귀함수와 레지스터 EBP (Extened Base Pointer:.. 2023. 2. 10. [쓰면서 익히는 알고리즘과 자료구조](3) 연결 리스트(Linked List) 많이 등장하는 자료구조 단점 특정 위치의 데이터를 찾기 위해서는 처음부터 순회해야 한다. 주소값도 저장해야 되서 추가 메모리 공간이 필요하다 연속적인 메모리 공간으로 관리되지 않아서 CPU 캐시 입장에서 비용이 더 든다 class Node(object): def __init__(self): self.data: object = None self.next: Node = None 3.4 연결 리스트 뒤집기 class Node(object): def __init__(self): self.data: object = None self.next: Node = None def reverse_list(head: Node) -> Node: prev = None curr = head while curr is not None.. 2023. 2. 8. [쓰면서 익히는 알고리즘과 자료구조](2) 문자열(String) 파이썬에서 문자열은 처음 생성된 이후 변경 불가능한 불변(immutable) 객체이다. string + string = 새로운 string 객체 2.3 회문(Palindrome) 확인 문자열 알고리즘 문제 중 빈번하게 등장하는 회문에 관한 간단한 문제를 풀어보자. 문자열이 회문인지 아닌지 확인하자, 알파벳과 숫자로 이루어져있으며, 알파벳은 대/소문자를 구분하지 않는다. def is_palindrome(s: str) -> bool: i = 0 j = len(s) - 1 s = s.lower() while i < j: while i < j: if s[i].isalnum(): break i += 1 while i < j: if s[j].isalnum(): break j -= 1 if s[i] != s[j]: .. 2023. 2. 7. 이전 1 다음
