ITeus

지난번 포스팅에서 이어집니다. teus-kiwiee.tistory.com/60?category=924328 매운음식 성애자(Way Cool) 프로그래머스의 힙의 첫번째 문제입니다. programmers.co.kr/learn/courses/30/lessons/42626?language=python3 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들.. teus-kiwiee.tistory.com 지난번, 단순 List를 사용해서, Scovile 지수가 원하는 값이 나올때까지 반복되는 매운음식 성애자 문제를 다뤘습니다. 하지만, 이때 List를 사용해서 효옹성 테스트를 지나가지를 못했습니다. 해당 문제에서는 Heap 구조를 사용해서 빠르게 Minimum 값을..

이번 포스팅은 동적계획법을 이용하는 정수 삼각형 문제입니다. programmers.co.kr/learn/courses/30/lessons/43105?language=python3 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 이번 문제는 이진트리와 유사해 보이는 피라미드 형식의 Data가 주어질때 오직 좌하 or 우하 로만 이동하여 모든값의 합이 최대가 되게하는 문제입니다. 아래 예시를 보시죠. 하지만 해당 문제는 이진트리도, 이진 탐색트리도 아니기 때문에 위에서부터 답을 찾아내려가면 애로사항이 발생합니다.(요 경우는 욕심쟁이 방법이라고 봐야겠죠?) 예를들어서, 7 -> 8 -> 1..

이번 포스팅은 욕심쟁이 방법론 입니다. 욕심쟁이 방법론은, 작은 문제에 대한 최선의 선택을 하는 알고리즘 방법론입니다. 무슨소리인지 감이 잘 안옵니다. 아래 예시를 보겠습니다. 1달러당 무게가 1이라고 가정해 봅시다. 이때 집게사장님은 욕심쟁이 이기 때문에, 무조건 큰 돈은 우선으로 줍습니다. 그러면 5달러를 모두 담고, 남은 공간에 3달라를 담는것이 주어진 상황에서 최선의 선택이겠죠? 하지만 이렇게 하면 최적의 이익을 얻을 수는 없습니다. 욕심쟁이 방법론은 동적 프로그래밍 방법론과 유사하게 작은 소문제에 대한 해를 찾아서, 전체 문제의 해를 찾는 알고리즘 계획 방법론입니다. 동적프로그래밍 방법론은 이전 단계의 최적해를 기억해서 전체 문제의 최적해를 찾는다면 욕심쟁이 방법론은 욕심을 부려서 모든 소문제의..

이번 포스팅은 동적 프로그래밍 방법론입니다. 방법론의 이름을 들으면 "??? 대체 무슨 방법론이야?" 라는 생각이 듭니다. 이름을 그대로 해석하면 이해를 할수가 없습니다. 동적 프로그래밍 방법론은 동적 계획법이라고 불리며 국소해를 저장하는 Table을 구축하고, 국소해를 저장/사용하는 알고리즘 방법론을 의미합니다. 아래 피보나치 수열을 구하는 방법을 보겠습니다. (너무 유명한 예제이지만, 이것만큼 숙련된 조교도 없습니다) #분할정복 방법을 사용한 피보나치수열을 구하는 함수 def fib_div(n): if n == 1: return 1 elif n == 0: return 0 result = fib_div(n-1) + fib_div(n-2) return result #동적 프로그래밍 방법을 사용한 피보나치..

이번 포스팅은 가장 기초적이면서 원시적인 알고리즘 설계 방법론입니다. 이름하야 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..