분류 전체보기

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..

1. Recursion 우리는 목표를 달성하기 위해 어떠한 메소드 안에서 또 다른 메소드를 호출할 수 있다는 사실을 알고 있습니다. 이와 유사하게 메소드는 자기 스스로 또한 호출할 수 있습니다. Recursion(재귀) 방식은 programming technique 중 하나로 어떤 메소드가 목적을 달성하기 위해서 본인 스스로를 호출할 수 있는 메소드를 말합니다. 두 가지 접근 to repetitive algorithms(반복 알고리즘) iteration(순회) loops(for, while, do-while) recursion(재귀) Function calls itself 즉, 함수가 자기 자신을 계속해서 반복하여 호출하는 방법 문제를 breaking down 하기에 적절한 방식 break down: 주..

1. Search Algorithms linear search(선형 탐색) 'The searching operation'은 정렬된 데이터로부터 주어진 item을 찾아내는 것입니다. 만약 발견한 item이 정렬된 리스트에서 가져올 수 있다면 그것이 위치한 index 위치를 반환하거나 발견하지 못했다는 사실(None)을 반환합니다. (발견하지 못한 것이 0이 아님에 주의! -> 0 또한 index이기 때문에) 리스트 안의 item을 search하는 가장 쉬운 방식은 linear search 방법이며, 이는 전체 리스트의 item을 하나씩(one-by-one) 찾는 방식입니다. 이 포스팅에서는 개념 이해를 돕기 위해서 리스트의 item's type을 integer 변수로 할 것인데요, 정수가 비교적 제일 이해..

1. Object(객체) 전반적인 의미, 보여지고 만질 수 있는 물질적인 것. 프로그래밍 관점, 메모리 상에 존재하는 함수와 변수의 조합 파이썬에서 모든 것은 object입니다. integers strings functions files etc. 2. 파이썬 정수(Integer)는 단순 정수보다 더 많은 것을 의미한다. 표준 파이썬의 구현은 C로 쓰여졌다. 이는 이것은 모든 파이썬 object가 단순히 교묘하게 위장된 C 구조체라는 것을 의미하며, 이 구조체는 그 가치뿐만 아니라 다른 정보도 포함합니다. 예를 들어, x = 10000과 같이 파이썬에서 정수를 정의할 때 x는 단순히 'raw' 정수가 아닙니다. 이것은 실제로 여러 값을 포함하는 복합적인 C 구조에 대한 포인터입니다. 3. Python va..

자료구조와 알고리즘 with 파이썬은 위와 같은 영어 교재를 기반으로 작성한 내용입니다. 자료구조와 알고리즘 카테고리에 python 문법이 있으셔서 놀랐겠지만 아무래도 파이썬으로 해당 부분을 진행해 나갈 것이기 때문에 기본적으로 알아야 하는 파이썬 문법들을 정리해 보았습니다. 만약 파이썬을 이미 잘 아시는 분이라면 해당 포스팅은 건너 뛰셔도 좋습니다! 1. Python Flow Control 프로그램은 통상적으로 순서에 따라 실행되지만 프로그램 실행의 흐름(flow)를 제어하기 위한 주된 두 가지 방식이 존재합니다. conditional statements(is, else,...) loops(for, while ...) 2. if - else statements if...else 와 elif statem..

이번 시간에는 백트래킹 알고리즘에 대해서 알아보도록 하겠습니다. 1. 백트래킹이란? 백트래킹(BackTracking)은 해를 찾는 도중 해가 아니라서 막히면, 뒤로 되돌아 가서 다시 해를 찾아 나가는 방법입니다. 또한 다음과 같이 풀어서 설명하기도 합니다. 재귀적으로 문제를 하나씩 풀어가다가 현재 재귀를 통해 확인 중인 노드가 제한 조건에 의해 위배 되고 있지는 않은지 판단하고(이 과정이 유망한지를 판단하는 과정), 그러한 경우에 해당 노드를 제외하고 돌아가서 다음 단계로 나아가는 방식이다. 여기서 중요한 점은 특정 노드는 제외하고 진행을 이어간다는 점입니다. 부르트 포스는 무작정 그냥 모든 방법에 대하여 가능한 해를 나열하는 것이라면 백트래킹은 모든 조합의 수를 살펴보되 단 조건이 만족할 때만 살펴보는..

이번 시간에는 분할 정복 알고리즘(Divide & Conquer Algorithm)에 대해서 알아보도록 할 것입니다. 1. 분할 정복 알고리즘이란? 분할 정복(Divide and Conquer)는 여러 알고리즘의 기본이 되는 핵심 해결 방법으로 다음과 같은 정의를 내리고 있습니다. 문제를 즉각 해결할 수 있을 때까지 재귀적 방식을 통해 두 개 이상의 하위 문제(Sub-problems)들로 나누고(Divide 과정), 문제를 해결한 다음(Conquer 과정) 그 결과를 바탕으로 다시 전체 문제로 돌아가 합치면서 해결해 나가는 과정. 말 그래도 분할했다가 정복하는 알고리즘 인 것입니다. 다음 그림이 그 예시를 보여줍니다. 사실 분할 정복 알고리즘은 굉장히 많이 쓰는 알고리즘으로 이 수업에서도 몇 번 다룬 적..

이번 시간에는 완전 탐색(브루트 포스)에 대해서 배워보도록 할 것입니다. 1. 완전 탐색 알고리즘이란? 한때 유명했던 초등 학교 수학 문제 풀이가 있습니다. 문제가 의도한 대로 푼 풀이는 아니지만 문제가 원하는 답을 얻기 위해서 접근한 과정은 꼭 틀리다 볼 수는 없습니다.(근데 답은 틀렸다. ) 이처럼 완전 탐색은 모든 경우의 수를 전부 다 체크해서 정답을 찾는 방법입니다. 즉, 다시 말해서 무식하게 모든 경우의 수를 하나하나 다 해보겠다는 방법인 것입니다. 이러한 방식이 굉장히 무식하다고 하여 "Brute Force" 라는 이름이 붙여졌고 모든 알고리즘 중에서 가장 단순하고 직관적인 방법이라고 할 수 있습니다. 예를 들어, 금고의 4자리 비밀번호를 풀려고 할 때, 이 알고리즘으로 푸는 방법은 0000부..