Category Archives: 알고리즘

Codility – OddOccurrencesInArray 문제 풀이 (난이도 : 하)

Posted on by

Codility – OddOccurrencesInArray 문제 풀이 (난이도 : 하)

// you can also use imports, for example:
// import java.util.*;
import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        HashMap<Integer, Boolean> pairedMap = new HashMap();

        for(int i = 0 ; i < A.length ; i++){
            int occurredNumber = A[i];
            Boolean paired = pairedMap.get(occurredNumber);
            if(paired == null || paired == true){
                pairedMap.put(occurredNumber, false);
            }
            else{
                pairedMap.put(occurredNumber, true);
            }
        }

        Iterator iterator = pairedMap.keySet().iterator();
        int minValue = Integer.MAX_VALUE;
        while(iterator.hasNext()){
            int key = iterator.next();
            Boolean paired = pairedMap.get(key);
            if(paired == false){
                minValue = Math.min(minValue, key);
            }
        }

        return minValue;
    }
}

Codility – BinaryGap 문제 풀이 (난이도 : 하)

Posted on by

Codility – BinaryGap 문제 풀이 (난이도 : 하)

사이트에서 문제 복제 및 배포(publish)는 허가하지 않는다니 그냥 풀이만……

class Solution {
    
    public int solution(int N) {
        int mode = 0;
        
        //remove 0 gaps without 1
        do{
            mode = N%2;
            N = N/2;
        }while(mode == 0);
        
        //count 0 gaps and get max 0 gap count
        int maxGapCount = 0;
        int gapCount = 0;
        while(N != 0){
            mode = N%2;
            N = N/2;
            if(mode == 1){
                maxGapCount = Math.max(maxGapCount,gapCount);
                gapCount = 0;
            }
            else{
                gapCount++;
            }
        }
        
        return maxGapCount;
    }
}

하노이 탑 문제 정리

Posted on by

읽고있는 파이썬 책에 하노이 탑이 예제로 나왔다. 이거 학생때 배웠던거지! 하며 가벼운 마음으로 보는데 순간 하나도 이해가 되지 않았다. 어떻게 풀었는지도 기억이 나질 않는다. 심지어 소스를 보았는데도 이해가 가지 않는다. 뭐지! 하는 위기감에 정리해 본 하노이 탑 문제.

하노이 탑 ( 출처 : 위키백과 )

  1. 설명
    하노이의 탑(Tower of Hanoi)은 퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다.게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다.

    1. 한 번에 하나의 원판만 옮길 수 있다.
    2. 큰 원판이 작은 원판 위에 있어서는 안 된다.

    하노이의 탑 문제는 재귀 호출을 이용하여 풀 수 있는 가장 유명한 예제 중의 하나이다. 그렇기 때문에 프로그래밍 수업에서 알고리즘 예제로 많이 사용한다. 일반적으로 원판이 n개 일 때, 2n-1번의 이동으로 원판을 모두 옮길 수 있다. 메르센 수라고 부른다).참고로 64개의 원판을 옮기는 데 약 18446744073709551615번을 움직여야 하고, 한번 옮길 때 시간을 1초로 가정했을 때 64개의 원판을 옮기는 데 5849억 4241만 7355년 걸린다.

  2. 참고 그림
    300px-Tower_of_HanoiTower_of_Hanoi_4

문제의 분해

  1. 원판이 한개일경우 풀이
    1번 기둥의 1번 원반을 3번 기둥에 옮긴다.
    끝
  2. 원판이 두개인 경우 풀이
    1번 기둥의 1번 원반을 2번 기둥에 옮긴다.
    1번 기동의 2번 원반을 3번 기둥에 옮긴다.
    2번 기둥의 1번 원반을 3번 기둥에 옮긴다.
    끝
  3. 원판이 세개인 경우 풀이
    1 번 기둥의 1 번 원반을 3 번 기둥에 옮긴다.
    1 번 기둥의 2 번 원반을 2 번 기둥에 옮긴다.
    3 번 기둥의 1 번 원반을 2 번 기둥에 옮긴다.
    1 번 기둥의 3 번 원반을 3 번 기둥에 옮긴다.
    2 번 기둥의 1 번 원반을 1 번 기둥에 옮긴다.
    2 번 기둥의 2 번 원반을 3 번 기둥에 옮긴다.
    1 번 기둥의 1 번 원반을 3 번 기둥에 옮긴다.
    끝
  4. 원판이 n개인 경우 풀이
    1번 기둥에서 n-1번 까지의 원판을 2번(여분의 기둥)으로 옮긴다.
    1번 기둥에서 n번 원판을 3번으로 옮긴다.
    2번 기둥의 n-1번 까지의 원판을 3번으로 옮긴다.
    끝

1~4의 과정을 보면 하노이 탑 문제는

hanoi(n) = 2hanoi(n-1) + move(n)

로 정의 될 수 있다. 좀더 상세히 정리를 하면

hanoi(n, startPeg, endPeg) = hanoi(n-1, startPeg, extraPeg) + move(n) + hanoi(n-1, extraPeg, endPeg)

가 된다.

문제 풀이

  1. 리컬시브 구조를 이용한 풀이 
    def hanoiRecursive(ndisks, startPeg=1, endPeg=3):
    global phase
    if ndisks:
        extraPeg = 6 - endPeg - startPeg
        hanoiRecursive(ndisks-1, startPeg, extraPeg)
        print(startPeg, "번 기둥의", ndisks, "번 원반을", endPeg, "번 기둥에 옮깁니다.")
        hanoiRecursive(ndisks-1, extraPeg , endPeg)
  2. Stack을 이용한 풀이 
    def hanoiStack(ndisks, startPeg=1, endPeg=3):
    stack = []
    stack.append((ndisks, startPeg, endPeg, False))
    while len(stack) > 0:
        disks, start, end, move = stack.pop()
        extraPeg = 6 - end - start
        if move:
            print(start, "번 기둥의", disks, "번 원반을", end, "번 기둥에 옮긴다.")
        elif disks > 0:
            stack.append((disks - 1, extraPeg, end, False))
            stack.append((disks, start, end, True))
            stack.append((disks - 1, start, extraPeg, False))

 

2. 유전자 알고리즘

Posted on by
Reply

집단지성 프로그래밍 이란 책을 보며 알게된 알고리즘이다. 그냥 여기저기 이야기만 들었지 실질적으로 정체를 파악하고 구현을 해보게 된건 이번이 처음이다.

유전자 알고리즘에 대한 자세한 설명은 엔하위키-유전자 알고리즘(http://ko.wikipedia.org/wiki/%EC%9C%A0%EC%A0%84_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)에 아주 자세히 잘 나와있다.

그냥 내식대로 간단히 정리하자면 무수히 많은 경우의 수 중 일부의 경우들을 샘플링하여 1세대 데이터군을 만들고 이 데이터들중 최적을 선택하여 교배하고 돌연변이 발생 시켜 더 나은 다음 세대군을 만드는 과정을 여러번 반복하여 최적의 결과를 찾아가는 알고리즘이다. (나 왜이리 글을 못쓰지?)

알고리즘 순서를 대충 요약하면 다음과 같다.

  1. 무수히 많은 경우의 수 중 일부의 경우를 랜덤하게 샘플링하여 하나의 데이터 세트를 구성한다. 이런 한 세트를 세대라고 부른다. 최초 샘플링에 의해서 만들어진 세대를 1세대 라고 한다.
  2. 한 세대가 구성이 되었으면 이중 최적에 가까운 일정 수를 선택한다. 이 선택된 데이터들을 엘리트라고 한다. 엘리트 선택 비율은 딱히 정해져있진 않은거 같다. 난 10% 정도를 엘리트로 선택하기로 했다.
  3. 선택된 엘리트들을 교배(교차)시키거나 돌연변이를 일으켜 이전 세대와 동일한 구성원 수를 갖는 다음 세대를 구성한다.
  4. 새로운 세대로 2~3과정을 여러번 반복한다.
  5. 더 이상 좋은 결과가 나오지 않거나 일정 횟수 이상 반복한 결과를 취한다.

연습삼아 만들어 본 것은 난수로 이루어진 정수들로 부터 0에 근접한 수를 만들어 내는 프로그램이다. 프로그램 돌아가는 과정은 다음과 같다.

  1. 랜덤함수를 이용하여 일정수 이상의 난수를 생성하여 1세대를 구성한다.
  2. 구성된 세대를 오름차순으로 정렬한다. 정렬할때는 절대값을 사용하여 음수도 0보다 큰 수로 정렬되게 한다.
  3. 정렬된 수중에서 0에 가까운 10%의 수를 선택한다.
  4. 버려진 90%의 구성원을 대치할 새로운 구성원을 만든다. 일정한 확률을 정하여 구성원 수가 모두 찰때까지 교차(교배) 혹은 돌연변이를 일으킨다.
    1. 교차(교배) : 선택된 가장 작은 10%수중 랜덤으로 두개를 선택하여 교배(교차)시킨다. 첫번째 수의 앞 16bit, 두번째 수의 뒤 16bit를 취한 값을 합하여 새로운 수를 만든다.
    2. 돌연변이 : 선택된 가장 작은 10% 수중 랜덤을 하나를 선택해서 돌연변이를 일으킨다. 랜덤하게 몇개의 비트를 선택하여 inverse 시킨다.
  5. 2~4를 계속 반복한다.
  6. 최종 결과를 확인한다.

실험 결과는 아래 처럼 나왔다.

  1. 실험 1
    1. 조건 : 세대구성수 100, 세대교체 횟수 100, 엘리트 비율 10%, 돌연변이 발생 확률 10%, 총 시도 횟수 5회
    2. 결과 : -1, 43, 10, 515, -2
  2. 실험 2
    1. 조건 : 세대구성수 1000, 세대교체 횟수 10, 엘리트 비율 10%, 돌연변이 발생 확률 10%, 총 시도 횟수 5회
    2. 결과 : 344, -81, -3588, -1045, 109
  3. 실험 3
    1. 조건 : 세대구성수 10, 세대교체 횟수 1000, 엘리트 비율 10%, 돌연변이 발생 확률 10%, 총 시도 횟수 5회
    2. 결과 : 2, 16, 16, -1, 0
  4. 실험 4
    1. 조건 : 세대구성수 1000, 세대교체 횟수 1000, 엘리트 비율 10%, 돌연변이 발생 확률 10%, 총 시도 횟수 5회
    2. 결과 : 1, 1, 1, 0, 1
  5. 실험 5
    1. 조건 : 세대구성수 10000, 세대교체 횟수 100, 엘리트 비율 10%, 돌연변이 발생 확률 10%, 총 시대 횟수 5회
    2. 결과 : -1, -1, -1, 0, 1
  6. 실험 6
    1. 조건 : 세대구성수 100, 세대교체 횟수 10000, 엘리트 비율 10%, 돌연변이 발생 확률 10%, 총 시대 횟수 5회
    2. 결과 : 1, 0, 1, -1, -1

 

예전에 페북에 끄적거렸던과 달리 실험2와 실험3을 비교해 보면 세대수가 많아도 세대 교체횟수가 적절하지 않으면 그 반대의 경우보다 결과가 좋지 않게 나오는거 같다. 오히려 적은 구성수도 돌연변이가 적절히 발생하면서 세대교체가 많이 이루어지면 자연히 좋은 결과를 내는것 같다. 그리고 실험 4~6을 보면 전체 경우수의 일정 비율 이상을 샘플링 한다면 구성원수와 교체횟수를 극단적으로 치우치게 하지만 않는다면 다 좋은 결과를 도출해 내는것 같다.

실험1 기준으로 32bit 정수 표현의 모든 경우의 수를 비교하는것( O(2^32) )로 반드시 0을 찾을 수 있다.)에 대비하여 100개의 원소를 100번 정렬하는 것( O(100*log(100) * 100) )으로 거의 근사치(2~16)를 구한것을 보면 완벽한 최적값을 요구하는 조건이 아니라면 상당히 유용한 알고리즘인것 같다.

특이한 점은 1과 같이 어느정도 최적치에 근접한 이후부터는 변화가 거의 없다. 아마 세대의 모든 엘리트들의 값이 1로 통일된 상태에서는 교배도 더이상 의미가 없고 돌연변이만을 통해서 0에 도달해야하는데 돌연변이 같은 우연발생으로 최적에 도달하려는 시도는 논리적으로 성공을 보장할 수는 없는 부분이니 운에 맡기는 방법밖에 없기 때문에 그런 것이 아닐까 한다.

결과적으로 유전자 알고리즘은 경우의 수를 모두 따지기 어려운 매우 큰 집단에 대해서 일정 수준의 최적치를 얻기에는 좋은 방법인것 같다. 다만, 완벽한 최적값을 기대한다면 실망할 여지가 크다.

아래는 토비 세가란의 집단지성프로그래밍 책을 참고하여 만든 코드다. net.abh0518.genetic 패키지가 유전자 알고리즘 구현 부분이다.
https://github.com/abh0518/ProgrammingCollectiveIntelligence

1. 분할정복(divide and conquer) 알고리즘

Posted on by
Reply

요즘 알고리즘 공부하면서 느끼는 가장 어려운점은 해결해야할 문제에 적용할 알고리즘을 선택하는 과정이다. 사실 적용할 알고리즘을 찾았어도 해당문제에 맞게 변형하여 적용하는것이 진짜 어려운데 난 머리가 나빠서 그런지 먼저 적용할 알고리즘을 선택하는 과정에서도 골치를 섞는다. 그래서 나름 요령을 정리해보기로 했다.

사실 ‘알고리즘 문제 해결 전략’ 책을 보면 다양한 알고리즘들의 원리와 적용 대상이 상세히 나오긴 하는데 매번 수페이지나 되는 내용들을 들춰보기도 힘들고 해서 나름 한두줄 정도로 정리한 요약 판을 만들어 보면 어떨까 하는 생각이 들었다.

뭐 얼마나 쓸모있을지는 알 수 없지만, 안하는것보다 나을거 같으니 일단 분할정복부터 시작해본다.

분할정복(divide and conquer)

개요

문제의 범위를 더 작은 단위로 쪼개어 해결한 뒤 각각의 중간 결과를 합하여 최종 결과를 도출하는 문제풀이 기법이다. 대표적인 사례는 머지소트와 퀵소트이다. 문제를 해결하는 함수 f(n)를

 { f(1) = c , f(n) = C + 2f(n/2) }

의 형태로 변형할 수 있을 때 적용할 수 있다. 그냥 말로는 쉬운데 실제로 적용 포인트를 찾는게 생각보다 어렵다.

설명

보통 O(n2)의 시간이 걸리는 계산(함수)를 O(nLog(n))시간대로 최적화 할때 분할정복을 사용할 수 있다. O(n2)의 시간이 걸리는 함수의 계산 과정을 다음을 만족하는 계산과정으로 변형하면 분할정복이 가능하다.(사실은 가능할거 같다 -.-; 그냥 깔짝깔작 공부하나 얻은 요령이다보니 수학적 근거는 없다.)

  1. 함수내에 중간 결과를 처리하는 과정(A라 하자)가 있다.
  2. A가 한번 수행되면 현재의 데이터는 두개로 나뉘어지고 각각 나누어진 데이터들은 상호 완전히 독립되어(배타적이라고 해야하나?) 다시 A에 적용된다.

분할정복의 대표적인 예인 퀵소트를 살펴보면 pivot 값을 기준으로 정렬할 데이터를 나누는 과정 A가 있고 이 A가 수행될 때마다 데이터는 pivot을 기준으로 자연스럽게 좌,우로 나뉘어져 2를 만족한다. 다음 계산에서 pivot을 기준으로 좌우로 나뉜 데이터는 각각 독립적으로 다시 A가 적용되며 정렬이 반복된다. 이런 방식으로 A과정이 N번 반복될때마다 2n개의 정렬된 원소들을 얻으며 최종적으로 O(nLog(n))의 시간을 얻을 수 있다.

셀렉트 소트와 비교를 하며 생각해 보면 이해가 쉽다.

셀렉트 소트

  1. 전체배열을 한번 비교하여 가장 작은 원소를 찾는 select 과정을 A라고 하면 n번째 수행에서 (배열크기-n)의 시간을 소요하여 결과적으로 O(n) 시간 소요한다.
  2. A가 n번 반복될때마다 1개의 정렬된 원소를 얻으므로 이것을 n-1번 반복하여 정렬된 결과를 얻는다. 최종 결과로 O(n2)시간을 소요한다.

퀵소트

  1. pivot기준으로 원소를 좌우로 나누는 계산을 A라고 하면 A는 n번째 반복마다 n개로 쪼개진 영역별로 수행 되어 평균 (배열크가-전체pivot갯수) 시간 소요한다. 결과적으로 O(n) 시간을 소요한다.
  2. A가 n번 반복될때마다 데이터가 2n개의 구역으로 나뉘며 다음계산에서 나뉘어진 구역마다 A를 수행하여 2n개의 정렬된 원소(pivot)를 얻는다. 총 수행 시간은 2n을 역산한 log(n)으로 최종 결과로 O(nLog(n))의 시간을 소요한다.

맺음

개인적인 생각으로 분할정복으로 문제를 풀때 가장 중요한건 A를 잘 만드는것 같다. 사실 A가 제대로 만들어지면 2는 자연스레 해결된다. 반면 2의 데이터를 나누는 기준을 아무리 잘 잡아도 A가 똥망이면 O(n2)이 되는 처참한 결과를 얻을 수도 있다.

한번은 문제 풀면서 정말 생각없이 A를 만들었더니 대충 O(n3)의 결과가 나왔었다. 털썩….