ITeus

이번 포스팅은 알고리즘을 설계하는 방법 중 분할정복 방법에 대한 포스팅입니다. 분할정복이란 글자 그 자체로 이해하면 편합니다. 1. 분할 : Data를 분할한다. 2. 정복 : 분할된 Data에 알고리즘을 적용한다. 3. 결합 : 정복단계의 알고리즘 결과를 취합한다. 위 3단계를 거쳐서 알고리즘이 수행되는 단계를 거치는 알고리즘 설계기법입니다. (단, 3단계 결합이 빠지는 경우도 분할정복 방법론으로 봅니다) 분할정복을 사용하는 알고리즘으로는 이진탐색, 퀵정렬, 합병정렬등을 예로 들 수 있습니다 이진 탐색을 예로 볼까요? 위 이진탐색의 내용을 다시 보겠습니다. 정복에서 알고리즘이 종료되지 않는다면 분할 단계에서 받은 부분배열에서 또다시 부분배열을 나누게 됩니다. 원하는 수준으로 작은 Data가 나오기 전까..

이번 포스팅은 가장 기초적이면서 원시적인 알고리즘 설계 방법론입니다. 이름하야 Brutal 방법론. 한국어로는 대충 단순방법론 이라고 할수있겠네요 ^_^;; 가장 쉬운 설게방법 이면서, 일반적으로 최고의 비효율을 보여줍니다. 탐색 알고리즘을 예로 들어보겠습니다. def find_value(list, value): for i in list: if i == value: return Ture find_value([9,4,8,7,5,3,1,2,1,64,9,7,6,2,6,3,4,8,99],99) 위 같은경우 Element가 n개 있을 경우 n개의 모든 원소에 대해서 처음부터 순차적으로 찾는 값과 동일한지 여부를 확인하는 알고리즘 입니다. 동일한 비교문을 n개의 Element에 적용하기 때문에 시간복잡도로 보면 O..

알고리즘의 경우 알고리즘에 들어가는 데이터의 수와 알고리즘의 구성 또는 해당 알고리즘을 실행하는 컴퓨터에 따라서 알고리즘 수행시간이 유동적으로 나타납니다. 이때, 동일한 동직을 수행하는 알고리즘 끼리 성능을 어떻게 비교할까요? 이번 포스팅은 알고리즘의 점근성능에 대한 내용입니다. 1. 점근성능 알고리즘의 점근 성능이란, 실제 수행시간은 아니지만 해당 알고리즘의 성능을 대변하는 수치를 의미합니다. 알고리즘의 점근성능을 이야기할 때 몇가지를 가정합니다. 1. 일반 사칙연산이나 비교문은 동일한 시간이 소요된다.(Data와 상관없이 상수시간이 소요된다) 2. 알고리즘의 수행시간은 최고차항의 영향이 지배적이다. 아래 예시 알고리즘을 살펴보겠습니다. #숫자를 입력받아, nxnxn 행렬을 만드는 알고리즘 입니다. d..

이번 포스팅은 Hash를 이용한 빠른 탐색 문제에대한 포스팅 입니다. programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 해당 문제를 살펴보면, 다수가 참가한 경기에서 한명만이 낙오가 발생하였고 해당 낙오자가 누구인지 찾는 문제입니다. 간단히 생각하면, 참가자를 Sorting하고, 완료자를 Soring해서 index순으로 비교하면 답은 찾을 수 있습니다. 하지만, 두개의 List를 Sorting하고 inde..

C언어를 해보신분이라면 아시겠지만 C언어에선 함수의 매개변수를 수정해도, 해당 매개변수의 변화가 Global 변수에 영향을 주지 않습니다. #include void f(int a, int b){ a = a + b; } int main() { int v1 = 9; int v2 = 1; f(v1, v2); printf("%d",v1); return 0; } ==> 9 위 예시를보면, v1이 a로 입력, a에 1을 더해서 a가 10으로 출력된것 같지만 그렇지 않죠. 그렇기 때문에 C언어같은 경우 Pointer라는 개념을 통해서 매개변수 자체를 바뀌게할 수 있는 방법이 있습니다. 하지만 Python을 봅시다. Python은 Pointer가 없습니다. 그러면 Python은 매개변수를 어떤방식으로 전달할까요? 아래..

이번 포스팅은 Event Listener의 정체입니다. 많은분들이 코딩을 배우면서, 반응형 System(Web, Application...)을 배우면서 Event Listener에 대해서 배우게 됩니다. Event Listener는 Event(사용자의 Click or 키보드 입력 등.... Not normal한 상태)가 발생할 경우 해당 행동을 인지하고, 사용자에게 결과를 반환해 줍니다. 설명을 잘 살펴보면 1. 사용자의 특정 입력을 받는다. 2. 해당 입력이 무엇인지 판단한다. 3. 입력에 따라 정해진 결과를 반환한다. 함수의 구조와 매우 유사한 것을 알 수 있습니다. 그렇다면, 함수를 이용해서 아래와같은 Event Listener를 만들 수 있을 것입니다. def listener_left(): whi..