개발자의 기록장 블로그

문제의 크기가 너무나 커서 접근하기 어려울 때, 우리는 그 문제의 크기를 줄여나가면서 해결책을 찾아보기도 한다.예를들어 크기가 100인 문제가 있으면 이를 각각 50의 크기로 쪼개 부분문제를 만들어 이를 각각 해결하고,해결한 문제의 답을 합쳐서 100의 크기의 문제를 해결하는 식이다. 이 알고리즘은 총 3종류의 단계가 있다. DivideConquerCombineDivide 단계는 문제의 크기를 나누는 과정으로 문제의 크기를 계속 줄여준다는 점에서 recursive case로 표현된다Conquer 단계는 문제의 크기가 충분히 작아 답을 찾을 수 있는 단계라는 점에서 base case로 표현 가능하다.그런데... 이게 말처럼 쉽지는 않다.conquer를 하는 과정에서 문제 크기가 예상외로 충분히 작지 않아 ..

우리가 알고리즘 문제를 만났을 때, 가장 먼저 해보아야 할 방식이 Brute force 접근 방식이다.Brute = 무식한 , Force = 힘 으로, 무식하게 접근하는 알고리즘 문제 접근 방법이다. 해가 존재할 것이라 기대되는 영역의 처음부터 끝까지를 조사하는 방식으로, 알고리즘 설계 방식에서가장 기초적인 방식이라 할 수 있다.원하는 답을 설계시 영역을 잘 설정했다면 100% 얻어낼 수 있는 방식이지만 input이 매우 큰 경우에도 과연 그럴까? 이 알고리즘은 답을 찾을 확률이 상대적으로 높으나 반드시 찾을 수 있는 것은 아니다. input의 값이 매우 크거나 컴퓨터 성능이 좋지않다거나해서 모든 범위를 탐색하는 것이 유의미한 시간 범위를 넘어가는순간에 답을 찾는 것이 의미가 없어지는 상황이 발생할 수 ..

이진 탐색을 사용하기 위해선, 정렬된 리스트를 사용해야 한다고 했다. 그러면 그냥 sort 메소드나 sorted 함수를 사용하면 될탠데... 이런 기능이 어떻게 작동하는지 알아보자! 선택 정렬선택 정렬은 기준 값을 하나 선택해서 모든 다른 리스트의 값과 비교해가며 더 작은 값들을 찾아서 정렬해가는 알고리즘을 사용한다.-> 각 위치에 어떤 값이 들어갈지 찾는 것. def selectSort(list_): for i in range(len(list_)): minIndex = i for j in range(i+1,len(list_)): if list_[i] list_[j]: minIndex = j temp = list_..

우리가 늘상 사용하는 index(list, data)는 과연 어떤 원리로 동작하는 것일까?기본적으로 어떠한 리스트에서 데이터의 위치를 찾는 것을 목표로 동작해야한다. 즉, 데이터의 값이 어디있는지 찾고, 그 값의 인덱스를 리턴해주어야 한다. 우리는 보통 무언가를 찾을 때 처음부터 쭈욱~ 찾아보거나 어떤 기준을 잡고 살펴보기 시작한다.한 뭉텅이씩 눈에 들어오는 양만큼 그룹을 묶어서 찾는다거나, 절반을 먼저보고 나머지를 본다거나... 컴퓨터도 똑같이 리스트에서 데이터를 찾을 때, 처음부터 쭉 살펴보거나 어떠한 기준을 가지고 리스트를 살펴보기 시작한다. 가장 기본적인 탐색 방법으로 선형 탐색과 이진 탐색에 대해서 살펴보자. 선형 탐색선형 탐색은 말 그대로 리스트를 linear하게 살펴보면서 데이터의 위치를 찾..

일단 물은 0번과 -1번 인덱스에는 찰 수 없다. 양 옆에 막아줄 빌딩이 없기 때문! 해당 인덱스 양 옆에 자신보다 큰 건물이 있으면 물이 들어감자신의 왼쪽과 오른쪽 건물중에서 가장 큰 건물 중 제일 작은 건물의 높이가 물이 들어갈 수 있는 최대 높이임최대 높이에서 자신의 높이를 빼주면?! 그 인덱스에 들어가는 물의 양이 됨!  def trapping_rain(buildings): rain_container = [] for i in range(1,len(buildings)-1): max_left = max(buildings[:i]) max_right = max(buildings[i:]) upperbound = min(max_left, ..

튜플 두개를 넘기면 거리 계산을 해주는 함수를 distance로 정의해서 참조하자.일단 거리를 계산해서 최소거리를 구하는 것은 어렵지 않다.그런데 그 최소거리가 누구의 것인지 알려면, 반드시 key-value 쌍의 데이터 구조여야 한다.따라서 dict 구조를 사용했다. from math import sqrtdef distance(store1, store2): return sqrt((store1[0] - store2[0]) ** 2 + (store1[1] - store2[1]) ** 2)def closest_pair(coordinates): container = {} def find_value(x): return container[x] for i in range(len(c..

Brute Force 해결방식의 핵심은 가장 무식하게 하나하나씩 다 해보는 것이다.하나 하나씩 1:1 매칭을 해준다 -> 2중 for문 사용곱했을 때 최대가 되는 수부호가 다를 때와 같을 때 고려해야 하는 지 생각해 보았으나 최대값만 리턴하면 되므로 상관없음!def max_product(left_cards, right_cards): # 코드를 작성하세요. ans = [] for i in range(len(left_cards)): for j in range(len(right_cards)): ans.append(left_cards[i]*right_cards[j]) return max(ans)

하노이 탑 문제를 보고 간단한 것 같은데 간단하지 않았다... 그래서 일단 수열을 풀듯 4번까지는 직접 그려가면서 생각해 보았다. 원판의 개수가 1개일 때, 1번 기둥에서 3번 기둥으로 옮기면 끝원판의 개수가 2개일 때, 1번째 원판을 2번기둥으로 옮겨주고, 2번째 원판을 3번기둥으로 옮겨주고 1번째 원판을 3번째 기둥으로 옮겨준다.원판의 개수가 3개일 때, 1번째와 2번째 원판을 2번기둥으로 옮겨주고, 3번째 기둥을 3번기둥으로 옮겨주고, 1번째와 2번째 기둥을 3번째 기둥으로 옮겨준다원판의 개수가 4개일 때, 1,2, 그리고 3번째 원판을 2번 기둥으로 옮겨주고...위의 과정을 통해 생각해보니 공통적으로 나오는 움직임을 찾았다. 1번 기둥에서 2번 기둥으로 옮기기1번 기둥에서 3번 기둥으로 옮기기2번..