21-02-18 알고리즘 기초강의

in 알고리즘
  • 정렬되지 않은 리스트에서 주어진 키가 존재하는가? - 순차 탐색
  • 정렬된 리스트에서 주어진 키가 존재하는가? - 이분 검색
  • 이분검색의 알고리즘 설계방식: 분할정복(Divide-and-Conquer)
      :point_right: 정렬된 리스트 S에 어떤 키 x가 존재하는가?
  :point_right: 존재하면 S에서 x의 위치, 아니면 -1을 리턴

    S의 정가운데 원소와 x를 비교하여 같으면 해당 위치를 리턴 아니라면,
    Divide: 정 가운데 원소를 기준으로 S를 두개의 리스트로 분할
    Conquer: x가 정가운데 원소보다 크면 오른쪽, 작으면 왼쪽을 재귀 호출
    Obtain: 선택한 리스트에서 얻은 답을 리턴

파이썬으로 이분검색

1
2
3
4
5
6
7
8
9
10
11
def location (S, low, high):
    if (low > high):
        return 0
    else:
        mid = (low + high) // 2
        if (x == S[mid]):
            return mid
        elif (x < S[mid]):
            return location(S, low, mid -1)
        else:
            return location(S, mid+1, high)

자바스크립트로 이분검색

1
2
3
4
5
6
7
8
9
10
function location(arr, low = 0, high = arr.length) {     
    if(low > high) 
        return 0
    else {
        let mid = Math.floor((low + high) / 2);
        if(x === arr[mid]) return mid;
        else if (x < arr[mid]) return location(arr, low, mid-1);
        else return location(arr, mid+1, high);
    }
}

강의 내에서 x값은 전역변수를 사용하였음

합병정렬

  • 합병정렬의 알고리즘 설계방식: 분할정복(Divide-and-Conquer)

    Divide: 원소가 n개인 S를 n/2개의 원소를 가진 두 개의 리스트로 분할
    Conquer: 왼쪽의 리스트와 오른쪽의 리스트를 각각 재귀적으로 합병정렬
    Obtain: 각각 정렬된 두 개의 리스트를 정렬된 하나의 리스트로 합병하여 리턴


합병정렬 예시

파이썬으로 합병정렬

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def mergesort (S):
    n = len(S)
    if (n <= 1):
        return S
    else:
        mid = n // 2
        U = mergesort(S[0 : mid])
        V = mergesort(S[mid: n])
        return merge(U, V)

def merge(U, V):
    S = []
    i = j = 0
    while (i < len(U) and j < len(V)):
        if(U[i] < V[j]):
            S.append(U[i])
            i += 1
        else:
            S.append(V[j])
            j += 1
    if (i < len(U)):
        S += U[i : len(U)]
    else:
        S += V[j : len(V)]
    return S

자바스크립트로 합병정렬

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function mergesort (arr) {
    if(arr.length === 1) return arr;
    
    let mid = Math.floor(arr.length/2);
    let leftSide = arr.slice(0, mid)
    let rightSide = arr.slice(mid)
    
    return merge(mergesort(leftSide), mergesort(rightSide));
    
}

function merge(left, right) {
    let result = [];
    while (left.length !== 0 && right.length !== 0) {
		left[0] <= right[0] 
        ? result.push(left.shift()) 
        : result.push(right.shift());
	}

    return [...result, ...left, ...right];
}
  • 합병정렬의 문제점
    • 배열을 추가적으로 사용하게 됨 → 메모리 사용의 비효율성

합병정렬의 효율화

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def mergesort2 (S, low, high):
    if(low < high):
        mid = (low + high) // 2
        mergesort2(S, low, mid)
        mergesort2(S, mid + 1, high)
        merge2(S, low, mid, high)

def merge2(S, low, mid, high):
    U = []
    i = low
    j = mid +1
    while (i <= mid and j <= high):
        if (S[i] < S[j]):
            U.append(S[i])
            i += 1
        else:
            U.append(S[j])
            j += 1
    if (i <= mid):
        U += S[i : mid + 1]
    else:
        U += S[j : high + 1]
    for k in range(low, high +1):
        S[k] = U[k -low]

자바스크립트로 합병정렬 조금 더 생각해보기

1
2
3
4
5
6
7
8
9
10
11
12
// 파이썬처럼 배열을 덜 정의하면서 효율적으로 구현하는 법은 더 검색해볼 것
function mergesort (arr) {
    if(arr.length === 1) return arr;
    
    let mid = Math.floor(arr.length/2);
    let leftSide = arr.splice(0, mid)
    // splice함수를 사용하면 arr를 조작하므로 
    // arr에는 자동적으로 rightSide만 남게 됨

    return merge(mergesort(leftSide), mergesort(arr));    
}
// merge 함수는 상동하므로 생략

Comment and share

21-02-17 실패율 구하기

in 알고리즘

문제

실패율은 다음과 같이 정의한다.
스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수

전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.

통과한 코드 예시

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function solution(N, stages) {
    let answer = [];
    for(let i = 1; i <= N; i++) {
      let thisStageFailRate = stages.filter(s => s === i).length
      let otherUserFailRate = stages.filter(s => s >= i).length
      if (thisStageFailRate === 0) {
        answer.push({stage: i, failRate: 0});
      } else {
        answer.push({stage: i, failRate: thisStageFailRate/otherUserFailRate});
      }
    }

    return answer.sort((a,b) => (b.failRate === a.failRate) 
                       ? a.stage - b.stage : b.failRate - a.failRate)
                 .map(each => each.stage);
}

처음에 잘못 생각했던 것

  1. 실패율을 계산할 때 해당 스테이지를 클리어하지 못한 사용자 / 전체 사용자로 계산했던 것
    => 현재 스테이지를 클리어하지 못한 사용자 / 현 스테이지보다 높은 스테이지로 넘어간 사용자 수 로 계산해야 했음
  2. 실패율만 배열에 push 했던 것
    => 배열에 스테이지값과 실패율을 각각 갖는 객체를 push하여 객체 내 실패율로 sort한 후에 스테이지 값을 return할 수 있도록 map 함수를 사용해야 했음

Comment and share

Harry Kim

author.bio


author.job