CS 지식/자료구조와 알고리즘(Python)

1. Shortest Path Algorithms (최단거리 알고리즘) 1-1. Single-Source Shortest Paths 최단 거리 문제에서, 우리는 weight(가중치)가 부여된 방향 그래프(directed graph) G = (V, E)가 주어집니다. (앞으로 나오는 G=(V, E) 에서 대문자 V와 대문자 E는 각각 노드(vertex)와 간선(edge)의 집합을 의미합니다.) 가중치 함수(weight function)는 아래 식과 같습니다. 위 식의 의미는 edge를 real-valued weights(실수 가중치)에 매핑하겠다는 의미입니다.즉, 각 edge마다 주어지는 path에 대한 값이 존재한다는 것인데요. 특정 path의 weight를 의미하는 w(p) (p = 인 곳에서)는 해당..

1. Greedy Algorithms 다양한 최적화 문제들 중에서 최선의 선택을 결정하기 위한 방법으로 다이나믹 프로그래밍(동적계획법)을 사용하는 것은 다소 지나친 행동일 수 있습니다. 그렇기 때문에 더 단순하고 효율적인 알고리즘을 택해야 하는데, 그러한 관점에서 그리디 알고리즘(Greedy Algorithm)은 항상 그 순간에 최선으로 보이는 선택을 하는 알고리즘으로, 이는 내가 한 선택이 globally optimal solution(결과적으로 최선의 선택)을 이끌기 희망하는 locally optimal choice(당장의 최선의 선택)을 만들어 내는 알고리즘입니다. 그리디 알고리즘에 대해 요약을 한 내용은 다음과 같습니다. 현재 상황에서 가장 좋아보이는 선택을 한다. local optimum(극댓값..

자료구조와 알고리즘(with Python) 카테고리에서는 해당 알고리즘 및 자료구조로 코딩 문제를 잘 풀기 위해 파이썬 언어로 중요한 점들을 위주로 기술한 글입니다. 만약 DP에 대한 더 심화적이고 구체적인(이론) 내용을 보고 싶으신 분들은 아래 링크를 참고해주세요. [CS 지식/자료구조와 알고리즘(Java)] - [Algorithm] Dynamic Programming(다이나믹 프로그래밍) 알고리즘 [Algorithm] Dynamic Programming(다이나믹 프로그래밍) 알고리즘 이번 시간에는 다이나믹 프로그래밍(동적 계획법 ,DP)에 대해서 배워 보도록 하겠습니다. 1. 다이나믹 프로그래밍이란? Dynamic Programming 줄여서 DP(또는 동적 계획법)는 특정 범위까지의 값을 구하 cd..

10. Heaps heap을 이용하여 sorting을 하는 것을 heap sort라고 합니다. heap이 주로 사용되는 곳은 priority queue(우선순위 큐)입니다. Complete binary tree (완전 이진 트리) 완전 이진 트리는 그 높이에 대한 노드 수가 최대인 트리를 말합니다. 즉, 모든 레벨에서 노드들로 꽉 채워져 있는 것을 말합니다. 즉, 첫 번째 그림(height = 0) 에서 height 0에 대해 node를 maximum으로 채우는 경우는 오직 1개가 들어가는 구조입니다. 이진 트리(Binary tree)는 거의 완전합니다. 다음 두 조건만 만족한다면. 마지막 레벨을 제외하고 모든 노드가 채워진 트리 구조입니다. 노드는 왼쪽에서 오른쪽으로 채워져야 합니다. Propertie..

1. Dictionary and Copy in Python 그래프는 자료구조의 꽃이라 불릴 정도로 굉장히 중요하고 그 만큼 어려우며 대부분의 코딩테스트의 문제 중에서 킬러 문제를 담당하는 문제입니다. 그렇기 때문에 이를 제대로 이해해 보기 위해 파이썬의 개념을 먼저 익혀보도록 하겠습니다. 만약 파이썬 개념에 대해서 잘 아시는 분이시라면 중반부로 넘어가셔도 좋습니다! Python Dictionary (파이썬 딕셔너리) 우리가 많이 쓰는 리스트 자료구조에는 순서가 존재했습니다.(ordered) 하지만 딕셔너리는 순서가 없는 item의 모음으로 각 item이 key/value 쌍을 갖습니다. (즉, 순서가 없다! - unordered) Dictionary is mutable(변경 가능) and iterable..

Trees(트리 자료구조) 1. Terminology (용어) tree 자료구조: 저장할 data를 노드에 저장하면서 노드들이 트리형태로 나열된 형태. root node:위 그림에서 44번 노드 parent node(ancestor;조상) / children node(desendant;후손) 25번 노드의 ancestor -> 20, 39, 44 번 노드 오른쪽 점선 네모 박스는 67의 desendant node들이지만 왼쪽 박스는 67의 desendant node가 아니다. 2. Binary trees (이진 트리) Binary tree는 모든 노드가 두 자식을 최대로 갖는 구조입니다.(자식 노드가 최대 2개) binary tree에서 노드들 배치는 왼쪽 서브 트리와 오른쪽 서브 트리의 형태로 조직화되..

1. Stack ADT(스택) 1-1. Stacks(스택) stack은 부엌에서 접시를 쌓는 것과 유사한 방식으로 data를 저장하는 자료구조입니다. 우리는 스택의 제일 윗 부분(top)에 접시를 둘 수 있고, 접시가 필요할 때 이 스택의 제일 윗 부분(top)으로부터 가져올 수 있습니다. 즉, 스택에 추가되는 마지막 접시는 그 스택으로부터 제일 먼저 집어 들어지는 것입니다. 이와 유사하게 stack 자료구조는 우리로 하여금 하나의 말단(end)으로부터 data를 읽고 저장할 수 있게끔 해주고 마지막에 추가되는 element가 첫 번째로 집어집니다. 따라서, stack은 last in, first out(즉, LIFO) 구조라고 합니다. 1-2. Basic operations(기본 연산) stack구조에..

Abstract Data Types(ADT) 1) Encapsulation (캡슐화) 2) Inheritance (상속) 3) Polymorphism (다형성) Encapsulation 멤버 함수의 구현과 object의 data에 대한 구현이 class를 사용하는 programmer들에게 알려지지 않도록 혹은 적어도 무관하게끔 class 정의하는 것은 여러 용어를 통해 알려져 있습니다. 사용되는 용어 중에 가장 흔한 것은 information hiding, data abstraction, and encapsulation이고 이것들 모두는 어떠한 class의 구현 시 세부사항이 그 class를 사용하는 programmer로부터 숨겨져 있다는 것을 의미합니다. 이러한 원칙은 OOP(Ojbect Oriente..

1. Linked List ADTs Linked List를 ADT(Abstract Data Types)로 만들어 볼 것입니다. 참고로 파이썬의 리스트라고 하는 자료구조는 링크드리스트입니다! 그래서 생각해 보시면 다른 언어와 달리 파이썬에서 리스트(다른 언어의 배열)를 선언할 때는 그 크기를 지정하지 않고도 원소를 삽입하는 것을 아실 수 있습니다. 그래서 다른 언어의 배열에서 특정 인덱스에 접근하는 것은 random access이기 때문에 시간 복잡도가 O(1)이지만 파이썬에서는 노드를 타고 쭉 가기 때문에 O(N)의 시간복잡도를 갖습니다. 그렇다면 이제 링크드리스트에 대해서 알아볼까요? 2. Singly linked lists (단일 연결 리스트) 중요한 컨셉 head node: 리스트에서 가장 앞에 있..

1. Sorting (정렬) 이란? Sorting Algorithms의 종류 Bubble sort (버블 정렬) Insertion sort (삽입 정렬) Quick sort (퀵 정렬) Merge sort (병합 정렬) Topological sort (위상 정렬) Sorting이란 크기 순으로 오름차순 정렬된 리스트로 모든 아이템을 배치하는 것을 말합니다. 위 (a) 리스트에는 숫자가 212인 item이 여러개가 있기 때문에 숫자를 key값으로 sorting하게 되면 그들 간의 순서를 정하기가 모호합니다. 이 경우에, 같은 숫자의 key에 대한 item들이 정렬되지 않은 리스트에서 정렬되어있던 순서가 sorted data에 반영되어 정렬되면 Stable sort(안정 정렬)라 하고, 그렇지 않으면 Uns..