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

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

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

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

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

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