kde's techblog kde's techblog

data struture & algorithm

• 분할정복법(divide and conquer)

  data struture & algorithm 2019. 6. 21. 23:38

  Introduction 분할정복법의 문제해결 과정 : 큰 문제를 같은 형태의 겹치지 않은 작은 문제들로 쪼갠다. 작은 문제들은 큰 문제의 형태와 다르지 않아야 하고 서로 겹치면 안된다. 작은 문제를 각각 해결한다. 작은 문제들을 해결한 결과를 합친다. 분할정복법의 예 1) : 이진탐색(binary search) 이진탐색을 하려면 숫자들은 오름차순으로 정렬되어 있어야 한다. 위와 같이 숫자들이 정렬된 배열이 있다고 하자. low는 배열의 첫번째 인덱스에 해당하는 0이고, high는 가장 마지막 인덱스에 해당하는 11이다. mid 는 low 와 high 를 더한 값을 반으로 나눈 결과를 반올림한 6이 된다. (반올림을 하던, 내림을 하던 상관없다. 어차피 mid를 기준으로 하는 상호배타적인 작은 문제로 분할..

• 탐욕법(greedy algorithms)

  data struture & algorithm 2019. 6. 15. 21:56

  1. Car Fueling 어떤 자동차가 A지점부터 B지점까지 이동해야한다고 가정하자. 자동차에는 연료가 만땅으로 채워져있고 연료가 만땅일 때 최대 400km 까지 달릴 수 있다. A지점과 B지점 사이의 거리는 950km이며 사이에 여러 개의 주유소가 있다. 운전자의 목표는 주유소를 경유하는 횟수를 최소한으로 하는 것이다. 여기서 운전자는 아래 세 가지 방법 중에 무엇을 택하면 되는가? 1. 자동차 위치 기준으로 제일 가까운 주유소에 들린다. 2. 자동차 위치 기준으로 남은 연료로 갈 수 있는 거리에 한해서 가장 멀리 있는 주유소에 들린다. 3. 연료가 다 떨어질 때까지 일단 달리고 본다. 당연히 2번일 것이다. 예를 들어, A지점에서 연료가 만땅인 상태로 출발했을 때 A지점 기준으로 각각 350km와 ..