본문 바로가기

전체 글74

[쓰면서 익히는 알고리즘과 자료구조](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) 배열(Array) 1.3 두 수의 합 찾기 def two_sum_brute_force(nums: list[int], target: int) -> list[int]: for i in range(0, len(nums)): for j in range(i+1, len(nums)): if (nums[i] + nums[j]) is target: return [i, j] return [-1, -1] def two_sum_hash(nums: list[int], target: int) -> list[int]: hashtable_dict = {} for i in range(0, len(nums)): value = target - nums[i] if hashtable_dict.get(value) is not None: return sorte.. 2023. 2. 6.
[쓰면서 익히는 알고리즘과 자료구조](0) 왜 알고리즘을 배워야 할까? 왜 알고리즘을 배워야 할까? 알고리즘 문제 해결 경험을 통해 실제 개발에서 어떤 문제를 해결하는데 도움이 된다. 노트 레이아웃을 이용한 알고리즘 문제 풀이 접근 방법 문제 분석과 함께 어떤 알고리즘과 자료구조가 적절한지 파악한다. 문제로 부터 요구사항과 제한사항을 수집한다 어떤 식으로 접근할지 다양한 아이디어를 제시한다. 코딩을 통합개발 환경 도움 없이 화이트 보드나 종이에 연습한다 시간/공간 복잡도를 고려한다. 어떤 테스트 케이스를 통과하는지에 대해서 고려한다. Constraints (범위, 제한사항) 문자열, 배열 그리고 숫자 배열을 얼마나 많은 요쇼들을 가질 수 있는가? 문자열의 경우 길이가 얼마나 길어질 수 있는가? 숫자의 경우 최댓값과 최솟값은 얼마인가? 어떤 요소들이 있는가? 숫자의 경우 정수.. 2023. 1. 25.
[헤드퍼스트 디자인패턴](3) 데코레이터 패턴(Dacorator Pattern) 상속맨 디자인에 눈을 뜨다 상속 남용 → 실행 중에 클래스를 꾸미는 방법을 배웁니다. 데코레이터 패턴을 배우면 기존 클래스 코드를 바꾸지 않고도 객체에 새로운 임무를 추가할 수 있습니다. 스타버즈라는 빠르게 성장한 커피 업체가 있습니다. 처음에는 Beverage 라는 추상 클래스를 만들고 모든 음료를 이 클래스의 서브 클래스로 구현하였습니다. 하지만 음료와 옵션의 종류가 늘자 DarkRoastWithWhip, DecafWithSteamedMilk 같은 수많은 클래스가 폭발적으로 생겨났습니다. 이 스타버즈는 어떠한 디자인 원칙을 어기지 않은걸까요? (힌트 2가지) (정답 확실 X) 애플리케이션에서 달라지는 부분을 찾아내고 달라지지 않는 부분과 분리한다. 구현보다는 인터페이스에 맞춰서 프로그래밍한다. 상속보.. 2023. 1. 25.

티스토리툴바