TigerCow.Door

안녕하세요. 문범우입니다.

지난 포스팅에서 시간복잡도, 공간복잡도 등에 대해서 알아보며 Big-O 표기법에 대해서 살펴보았습니다.

이번에는 실제로 특정 코드나 알고리즘을 대상으로 그 시간복잡도를 분석해보는 실습을 진행해보도록 하겠습니다.


아래에서 다루게 될 예제들은 ''코딩인터뷰 완전 분석"(게일라크만맥도웰 지음, 이창현 옮김)_인사이트출판 서적에서 일부 참고 및 발췌하였습니다.



 > N에 대한 정확한 사용


우리는 이전 포스팅에서도 그러했듯이 Big-O 표기법으로 나타낼때에 흔히 O(N), O(log N) 과 같이 나타냅니다. 그런데 이때 N에 대해 정확하게 이해하지 못하였다면 추후 잘못된 분석을 할 수 있습니다.

아래와 같은 상황을 생각해보겠습니다.


여러개의 문자열로 구성된 배열이 있습니다. 

이때 각각의 문자열에 대해 먼저 정렬을 하고 이후 전체 문자열을 사전순으로 다시 정렬하는 알고리즘이 있습니다.

이러한 알고리즘의 수행시간은 어떻게 될까요?


간단히 생각해보면, 각 문자열을 정렬하는데 O(N*logN)의 시간이 소요되므로 모든 문자열에 대해서는 O(N*N*logN)이 소요될 것입니다. 그리고 전체 문자열들에 대해 사전순으로 정렬해야 하므로 O(N*logN) 이 추가됩니다.

즉, 해당 알고리즘의 수행시간은 O(N*N*logN + N*logN) = O(N*N*logN) 이라고 생각할 수 있습니다.


하지만 이는 완벽하게 틀린 분석입니다.

어디서 부터 잘못됐는지 아시겠나요?

바로 N에 대한 정확하지 않은 사용입니다.

위의 분석에서는 문자열의 길이와 문자열의 개수 모두 N으로 중복해서 사용하였습니다. 이는 아예 다른 시간복잡도를 가져오게 되는 큰 실수입니다.


제대로된 분석을 위해서는 다음과 같이 변수를 정의하고 진행합니다.


- 가장 길이가 긴 문자열의 길이를 s라고 하자.

- 배열의 길이를 a라고 하자.


이렇게 된다면, 각 문자열을 정렬하는데 O(s * log s) 가 소요되며 모든 문자열에 대해서 생각해 보면, O(a * s * log s) 가 소요됩니다.

그리고 문자열 비교시, 두개를 서로 비교할 때 O(s) 만큼 시간이 소요되고 이것을 총 O(a * log a) 번해야 하므로 O(a * s * log a) 만큼의 시간이 소요 됩니다.

따라서 전체 시간 복잡도는, O(a * s * (log a + log s)) 입니다.




> 재귀 호출 패턴 분석


아래는 균형 이진 탐색 트리에서 모든 노드의 값을 더하는 간단한 코드입니다. 수행시간을 한번 분석해보죠.


1
2
3
4
5
6
int sum(Node node){
    if(node == null){
        return 0;
    }
    return sum(node.left) + node.value + sum(node.right);
}
cs



1. 재귀호출 패턴분석


위의 코드가 단지 이진 트리라는 이유로, 또는 재귀호출이라는 이유로 시간복잡도에 로그가 들어간다고 생각하면 안됩니다. 

실제로 재귀 함수에 분기가 여러개 존재한다면 수행 시간은 일반적으로 O(분기^깊이)가 됩니다. 즉, 두 개의 분기만 존재하는 재귀함수라면 일반적으로 O(2^깊이)의 시간복잡도를 가지게 됩니다.


그렇다면 깊이는 어떻게 될까요? 위의 코드에서 나온 트리는 균형 이진 탐색 트리입니다. 즉, 총 N개의 노드가 있다면 깊이는 대략적으로 log N 의 값을 가지게 됩니다.

그럼 수식에 따라 시간복잡도는 O(2^(log_2 N))이 되는 것을 알 수 있습니다.

하지만 조금 더 살펴보도록 합시다.

결과에 나온 log_2 N 는 과연 무엇을 의미할까요?

2^(log_2 N) = P 라고 생각해본다면, 양변에 로그를 취해

log_2 2^(log_2 N) = log_2 P 가 됩니다. 그러면 로그의 특징에 따라서,

log_2 N * log_2 2 = log_2 P

log_2 N = log_2 P

N = P

가 됩니다.

따라서 총 시간복잡도는 O(N) 이 됩니다.



2. 코드가 무엇을 의미하는가


위에서는 재귀 호출 패턴 분석을 통해 시간복잡도를 분석해보았습니다.

하지만 조금 더 직관적인 방법으로는, 코드가 무엇을 하는지를 살펴보면 알 수 있습니다.

위의 코드는 트리의 각 노드를 한 번씩 방문한 뒤 각 노드에서 상수 시간에 해당하는 일을 하게 됩니다. 즉, 수행시간은 노드의 개수와 선형관계에 있음을 알 수 있고, 이에 따라 N개의 노드가 있을때 알고리즘의 시간복잡도는 O(N)임을 알 수 있습니다.




> 순열(permutation)의 개수를 구하는 코드


아래의 코드는 입력된 문자열로 나타낼 수 있는 순열의 개수를 구하는 코드입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
void permutation(String str){
    permutation(str, "")
}
 
void permutation(String str, String prefix){
    if(str.length() == 0){
        System.out.println(prefix);
    }else {
        for(int i=0; i<str.length(); i++){
            String rem = str.substring(0,i) + str.substring(i+1);
            permutation(rem, prefix + str.charAt(i));
        }
    }
}
cs


코드를 보면 꽤 까다로울 수 있습니다.

이에 대한 시간복잡도 분석을 먼저 스스로 해보시고 보시는 것도 추천드립니다 :)


먼저 위의 코드를 분석하기 위해 permutation 함수가 얼마나 호출되는지, 각 호출마다 걸리는 시간이 얼마나 걸리는지를 나누어 생각하면 쉽게 분석할 수 있습니다.


1. 순열이 완성되는 시점에서의 permutation 함수 호출

순열이 완성되는 시점에서는 코드의 7번째 라인이 실행되는 것인데, 이 또한 permutation 함수가 호출되었기 때문에 입니다. 따라서 특정 문자열에 대한 순열의 개수만큼, permutation 함수가 호출될 것이며 이 값은 n! 입니다.


2. 순열 생성이 완성되기 전에 permutation 함수 호출

동시에 9~12번째 코드라인이 얼마나 호출되어 반복되는지를 살펴보아야 합니다.

트리구조로 생각한다면 1번에서 알아본 n! 는 결국 리프노드의 개수입니다.

그리고 루트에서 리프노드까지의 거리는 n일 것이며, 이를 통해 트리의 총 노드는 절대로 n*n! 을 넘지 못합니다.


3. 한 번의 permutation 호출에서의 소요 시간

한번의 호출이 있었을 때 연산 시간이 얼마나 걸리는지를 파악합니다.

7번째 줄에서는 문자열 전체를 출력하기 때문에 O(N) 시간이 걸리며, 10번째 줄에서 시행되는 substring 함수 또한 O(N) 시간이 걸리게 됩니다.

( 단순 함수 호출이기에 O(1)로 생각하실 수 있으나 java 업데이트 후 해당 함수가 O(N)의 소요시간을 갖게 되었습니다. )


이렇게 1,2,3으로 나누어 분석한 결과 permutation 함수의 총 시간 복잡도는 O(N * N * N!) 임을 알 수 있습니다.




> 피보나치 수 1


아래의 코드는 N번째 피보나치 수(Fibonacci number)를 구하는 코드입니다.


1
2
3
4
5
int fib(int n){
    if (n <= 0return 0;
    else if (n == 1return 1;
    return fib(n-1+ fib(n-2);
}
cs


이는 위에서 우리가 알아보았던 재귀 호출 패턴 분석을 이용하면 O(2^N) 의 시간복잡도를 가지게 됩니다.


하지만 이를 좀 더 세밀하게 분석해보면 약 O(1.6^N)의 시간복잡도가 나오게 됩니다. 구체적으로 다루지는 않겠지만, 우리가 재귀 호출에 대해서 트리구조로 그려볼 때, 호출 스택의 밑바닥에서 가끔식 한번의 호출만 필요한 경우 등이 그 이유일 것입니다.




> 피보나치 수 2


이번에도 위와 같은 동작을 하는, 피보나치 수와 관련된 코드이지만 이번에는 이전에 계산된 결과 값을 정수 배열에 저장하고 이를 이용하는 방식의 알고리즘 입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
void allFib(int n){
    int[] memo = new int[n+1];
    for (int i=0; i<n; i++){
        System.out.println(i+": "+fib(i,memo));
    }
}
 
int fib(int n, int[] memo){
    if (n <= 0return 0;
    else if (n == 1return 1;
    else if (memo[n] > 0return memo[n];
    memo[n] = fib(n-1, memo) + fib(n-2, memo);
    return memo[n];
}
cs


위의 코드에 대해 임의의 n 값으로 실제 호출 스택을 그려본다면 fib(i)를 호출할 때마다 fib(n-1)과 fib(n-2)의 계산이 이미 끝나 있고 이를 단순히 배열에서 가져오는 연산을 진행하는 것을 알 수 있습니다.

즉, 이러한 과정은 상수시간 안에 동작하고 상수 시간의 동작을 총 N번 반복하기 때문에 해당 알고리즘의 시간복잡도는 O(N)을 가지게 됩니다.


이러한 방법은 메모이제이션(Memoization) 이라고 불리는 방법으로써, 지수 시간이 걸리는 재귀 알고리즘을 최적화할 때 쓰는 흔한 방법 중 하나 입니다.

비슷한 방법 중 하나로는 동적계획법(Dynamic Programming) 이 있습니다.


물론 메모이제이션과 동적계획법이 아예 같은 개념인 것도 아니고, 아예 다른 개념인 것도 아닙니다.

필요하다면 추후 다루게 되겠지만 간단하게 살펴보면, 메모이제이션은 결과를 구하고 이를 할용하면서 문제를 해결하는 것이고, 동적계획법은 큰 문제에 대해 작은 부분으로 나누어 작은 것부터 해결해 나가는 것 입니다.



이렇게 지난 포스팅에서 알아본 시간복잡도에 대한 개념에 이어 여러가지 예제들을 함께 살펴보았습니다.

해당 예제들을 통해 실수 할 수 있는 부분들을 캐치하여 추후 자신이 분석하고자 하는 알고리즘에 대해 보다 정확한 분석이 이루어 져야 합니다.

블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc

안녕하세요. 문범우입니다.

최근 Java로 알고리즘 스터디를 시작하게 되었습니다.

단순히 문제풀이 보다는 이론적인 내용들을 살펴보며 관련된 문제를 푸는 방식으로, 기초부터 다시 살펴보려합니다.

이번에는 직접적인 알고리즘 내용에 앞서, 알고리즘 분석 즉 시간복잡도와 공간복잡도에 대해 이야기를 먼저 진행해보겠습니다.



> 왜 알아야 하는가?


Big-O 표기법은 알고리즘의 효율성을 나타내는 지표 혹은 언어이다.

이를 통해 자신이 작성한 알고리즘이 이전보다 빨라졌는지 느려졌는지 판단하는데 도움이 될 것이다.

물론 이 외에 다른 개발자들과 특정 알고리즘에 대해 이야기하거나 효율성 판단등에 의해서 Big-O 표기법을 통해 보다 원활하게 의사소통을 진행할 수 있다.


실제로 Big-O 표기법 이외에 다른 표기법도 있으나 이에 대해서는 혼동을 피하기 위해 제일 마지막에서 언급하겠다.


또한 Big-O 표기법에 대해 이해하는 방식이 조금씩 상이할 수 있지만 그 정의를 정확하게 이해한다면 문제되지 않을 것이다.



> Big-O 표기법의 정의


Big-O 표기법은 사전적으로, 시간(또는 공간)의 상한을 이야기한다.

즉, 시간복잡도와 공간복잡도의 상한에 대해서 이야기하는 것이다.

(주로 시간복잡도를 다루게 될 것이므로 시간을 대표로 설명하겠다.)


정의대로 이야기한다면 시간복잡도에 대해서 이야기할 어떤 것의 최악의 경우(가장 느렸을 경우)에 대한 시간을 이야기 하는 것이다.

즉, 평균적으로 10시간이 걸리는 업무가 있지만 특정 상황에 따라 20시간이 걸린다고 생각해보자. 이때 그 업무에 대한 시간의 상한은 20시간이다. 아무리 오래 걸려도 20시간이면 되기때문이다.

이때 이야기 하는 '아무리 오래 걸려도' 라는 키워드가 결국 Big-O이다.


그럼 이러한 의문이 들 수 있다.


"그럼 그 업무는 아무리 오래 걸려도 100시간 안에 할 수 있으니, 시간의 상한이 100시간이라고 해도 맞는건가요?"


그렇다. 정의에 따라서는 전혀 틀린말이 아니고 수학적으로도 옳은 표기이다.

하지만, 대체로는 그렇게 이야기하지 않는다.


Big-O가 대략적으로 어떤걸 의미하고자 하는지 이해가 갔다면 조금 더 수식적으로 살펴보자.


이를 위해서 위에서 언급한 예시를 조금 더 구체화 해보자.

특정 업무에 대해서 처리할 문서가 n개라고 가정하자.


이때 만약 A라는 사람은 정직하게 일해서 문서당 소요시간이 1시간이다.

근데 B라는 사람은 아직 경력이 부족해서 문서당 소요시간이 2시간이다.

슬프게도 C라는 사람은 호기심이 많아 문서개수에 대해 제곱시간이 소요된다.

놀랍게도 D라는 사람은 자동화 툴을 만들어 놓아서 문서개수에 상관없이 10시간이 소요된다.


이러한 사람들에 대해 각각 Big-O로 소요시간을 나타내보자.


A는 O(N)이다.

문서 1개당 소요시간이 1시간이므로 문서가 늘어나면 소요시간도 선형적으로 늘어난다.


B는 O(2N)이다.

A와 비슷하게 선형적으로 늘어나지만 그 값이 2배일 뿐이다.


C는 O(N^2)이다.

A와 B에 비해 호기심이 많은 C는 문서당 제곱시간이 소요된다고 하였기에 위와 같이 표기된다.


D는 O(10)이다.

자동화 툴을 만들어 놓은 D는 문서 개수와 상관없이 무조건 10시간이 소요된다.


Big-O표기는 위와 같이 표기하는 것이다.

하지만 아직 한가지가 남았다. Big-O 에서는 작은 것들은 신경쓰지 않는다.


정말 간단하게 이야기한다면 Big-O 표기법은, 제일 영향력있는 놈만 신경쓰겠다는 이야기다.

실제로 알고리즘에 큰 영향을 주는 것만 고려하겠다는 이야기인 것이다.


이것은 특정 수식에서 최고차항을 제외한 나머지를 무시한다는 의미이기도 하며, 최고차항에 대한 상수배 또한 무시하겠다는 것이다.


최고차항에 대한 상수배를 무시하겠다는 것은

즉, Big-O 정의에 따르면, O(N)과 O(2N)은 모두 동일하게 O(N)으로 표기된다.

그렇다면, O(10)은 어떻게 표기될까?

상수 시간이므로 O(1) 로 표기된다.


그리고 최고차항을 제외한 나머지를 무시하겠다는 것은,

O(N^2 + 10N + 3) 으로 표시된 값이 있을때 이를 O(N^2)과 같이 표기하겠다는 것이다.



위와 같이 알아본 Big-O 표기법은 초기에 언급한 것과 같이 단순히 시간복잡도를 분석하는데만 사용되지 않는다. 시간 또는 공간 모두 분석하는데 사용되며 공간에 대해 분석하는 것을 공간복잡도라고 이야기한다.


공간복잡도에 대해서 추가적인 설명을 하자면 다음과 같다.


> 공간복잡도

재귀 호출에서 사용하는 스택 공간 또한 공간 복잡도 계산에 포함된다.

하지만 함수를 단지 n번 호출했다고 해서 무조건 O(n) 공간을 사용하는 것은 아니다.



Big-O 표기법에서 주로 사용되는 표현들에 대한 대소비교를 해본다면 다음과 같다.(시간복잡도, 공간복잡도 순서)


O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)


그럼 마지막으로, 처음에 이야기했던 Big-O 이외의 표기법들에 대해 간단히 알아보자.


+ Big-Omega

빅 오메가라고 부르는 표기법은 시간에 대한 등가 또는 하한의 개념을 나타낸다.

즉 모든 process는 Ω(1)로 표기할 수 있다. 결국 오메가로 표기되는 알고리즘은 Ω 수행시간보다 빠를 수 없다.


+ Big theta

빅 세타라고 부르는 표기법은 Big-O와 Big-Omega 모두를 이야기한다.

즉, 특정 알고리즘의 시간복잡도가 O(N) 이면서 Ω(N) 이라면 이는 θ(N)이라고 표기할 수 있다.




이렇게 Big-O에 대한 개념적인 내용을 정리해보았습니다.

추후 필요하다고 생각되면 특정 코드나 내용들에 대해 시간복잡도와 공간복잡도를 계산해보는 내용에 대해서도 정리해보겠습니다.



블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc

안녕하세요. 문범우입니다.

이번에 소개해드릴 알고리즘 문제는, 2017년 카카오톡 블라인드테스트 1차 코딩시험에서 나왔던 문제중 난이도가 제일 낮다는 소개된 '비밀지도' 문제입니다.


해당 문제는 프로그래머스를 통해, 아래 주소에서 만나보실 수 있습니다.

https://programmers.co.kr/learn/courses/30/lessons/17681?language=python3


난이도가 가장 낮다고 소개된 만큼, 문제자체도 간단하고 풀이도 어렵지 않습니다.

따라서 해당 문제는 추가적인 설명대신 코드만 첨부해드리도록 하겠습니다.

추가적으로 궁금한 사항이 있으시면 언제든지 댓글 및 카카오톡이나 이메일을 통해서 연락주시면 바로 답변드리도록 하겠습니다.


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
26
27
28
29
30
def solution(n, arr1, arr2):
    answer = []
    decode_arr1 = []
    decode_arr2 = []
    tmp_str = ''
    tmp_answer = ''
    for i in arr1:
        tmp_str = str(bin(i))[2:]
        while(len(tmp_str) < n):
            tmp_str = '0'+tmp_str
        tmp_str = tmp_str.replace('0',' ')
        tmp_str = tmp_str.replace('1','#')
        decode_arr1.append(tmp_str)
    for i in arr2:
        tmp_str = str(bin(i))[2:]
        while(len(tmp_str) < n):
            tmp_str = '0'+tmp_str
        tmp_str = tmp_str.replace('0',' ')
        tmp_str = tmp_str.replace('1','#')
        decode_arr2.append(tmp_str)
    
    for i in range(n):
        for j in range(n):
            if (decode_arr1[i][j] == '#'or (decode_arr2[i][j] == '#'):
                tmp_answer += '#'
            else:
                tmp_answer += ' '
        answer.append(tmp_answer)
        tmp_answer = ''
    return answer
cs


블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc

안녕하세요. 문범우입니다.

요새 많은 기업들이 공채시즌이 다가와서 그런지, 평소보다 알고리즘 문제풀이에 대한 학원이나 온라인강의에 대한 광고가 많아진 것 같네요.


요새보면 대부분의 기업에서 SW인원들은 다른 시험보다 코딩테스트를 중요시하고 있고 많은 사람들이 제일 까다로워 하는 부분인 것 같습니다.


요새 개인적으로 공부하는 기계학습이나, 리액트네이티브때문에 블로그활동을 자주못하고 있는데, 오랜만에 프로그래머스에 들어갔다가 2017년 카카오톡 블라인드테스트 1차 코딩문제를 공개해두었길래 이번주에 하나씩 풀어보려합니다.


처음에는 쉬운문제부터 풀어보려했는데.. 나중에 확인해보니 이번에 소개해드릴 '추석트래픽' 문제가 가장 어려웠다고 하네요.


프로그래머스에서 제공하는 작년 카카오톡 코딩테스트 문제는 아래에서 만나보실수 있으며,

https://programmers.co.kr/learn/challenges


이에 대한 전체적인 해설은 아래에서 만나보실수 있습니다.

http://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/



오늘 소개해드릴 '추석트래픽' 문제의 정답률이 약18%라고 하지만, 개인적인 생각으로는 2017 카카오톡 블라인드테스트 1차 코딩테스트에서 총 5시간이 주어졌기때문에 어려웠다기보단 시간이 부족했다는 이야기가 많았을 듯 합니다.


문제에 대한 전체적인 안내나, 난이도정도등에 대해서는 위에 소개해드린 해설에서 확인해보시길 바랍니다.



1. 추석 트래픽


추석 트래픽 문제에 대한 설명은 따로 진행하지 않겠습니다.

제가 말로 주구장창 설명하는 것보다 직접 문제와 예제를 보시는게 이해가 빠를 것 같아서요 :'(


특별히, 예제3번에서 하나의 그림을 보여주고 있습니다.

x축을 시간으로 두고 각각의 트래픽을 bar형태로 표시해두었죠.

그리고 1초라는 시간범위(구간)를 정해서, 가장 많은 트래픽이 포함되는 구간에서의 트래픽 개수를 찾아내고 있습니다.


해당 그림을 보면서 어디서 많이 낯익다 싶었습니다.

바로, An activity-selection problem 문제입니다.

작년 알고리즘수업을 들으면서 봤던 문제인데, 잘 모르시는 분들은 한번 쯤 찾아보셔도 좋을 듯 합니다.


먼저 저는 입력되는 lines 를 하나씩 가져와서 datetime 객체로 바꾸고 이를 end_datetime으로 두었으며 lines에서 주는 실행시간을 가져와서 실행시간의 초단위 값 processing_s 와, 실행시간의 micro second단위 값 processing_ms 를 만들었습니다.

그리고 이 세개의 값를 이용해서, 트래픽의 시작시간을 구해 datetime객체로 하여 start_datetime으로 두었습니다.


이들을 이용해 같은 트래픽끼리 하나의 리스트로 묶어서, start_end_datetime 리스트에 저장하였고, 추후 answer를 탐색하기 위해 sorted_time 리스트를 만들어 start_datetime과 end_datetime의 모든 요소를 같이 저장하였습니다.

그리고 모든 lines에 대한 처리가 끝나면 sorted_time 리스트는 sort함수를 통해 오름차순으로 정렬합니다.


즉, 예제 1번과 같이 입력이 다음과 같다면,

입력: [
2016-09-15 01:00:04.001 2.0s,
2016-09-15 01:00:07.000 2s
]


start_end_datetime = [[ '2016-09-15 01:00:02.002000', '2016-09-15 01:00:04.001000' ], [ '2016-09-15 01:00:05.001', '2016-09-15 01:00:07.000']]


sorted_time = [ '2016-09-15 01:00:02.002000', '2016-09-15 01:00:04.001000', '2016-09-15 01:00:05.001', '2016-09-15 01:00:07.000']


과 같이 만들어지게 됩니다.


이제 문제에서 원하는 답을 찾을 차례입니다.

여기서 저도 한번 헤매고, 1000 micro second마다 탐색하는 방법으로 시도해봤더니 역시나 시간초과에 걸렸었습니다....


하지만 조금 더 생각해보면, 구하고자 하는 초당 최대 처리량이 변하는 순간은 단지 어떤 트래픽의 시작 또는 종료 시점뿐 입니다.

즉, 위에서 만들어두었던 sorted_time 리스트에 있는 시간에서만 초당 최대 처리량의 변화가 발생합니다.

따라서 우리는 sorted_time 리스트를 범위로 for문을 돌리면 되고, sorted_time 리스트에서 꺼낸 하나의 요소를 compare_time으로 두었고, 여기에 1초를 더한 시간을 compare_time_one으로 두었습니다.

그리고 start_end_datetime에서 하나씩 꺼내어 compare_time과 compare_time_one이라는 범위에 해당 트래픽이 속하여있는지를 탐색하고 각각의 탐색에 따른 최대값을 찾아 정답으로 반환하면 됩니다.


설명이 잘 된지는 모르겠으나, 실제로 코드를 보시면서 이해해보시면 잘 이해할 수 있을 것이라고 생각됩니다.


전체적인 python 코드는 다음과 같습니다.


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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import datetime
 
def solution(lines):
    start_end_time = []
    sorted_time = []
    tmp_answer = 0
    answer = tmp_answer
    for line in lines:
        split_line = line.split()
        split_day = split_line[0].split('-')
        split_time = split_line[1].split(':')
        split_s = split_time[2].split('.')
 
        Y = int(split_day[0]); M = int(split_day[1]); D = int(split_day[2])
        h = int(split_time[0]); m = int(split_time[1])
        s = int(split_s[0]); ms = int(split_s[1])*1000
        
        end_datetime = datetime.datetime(Y,M,D,h,m,s,ms)
        
        split_processing = split_line[2][:-1].split('.')
        processing_s = int(split_processing[0])
        if len(split_processing) == 1:
            start_datetime = end_datetime - datetime.timedelta(seconds=processing_s)
        else:
            processing_ms = int(split_processing[1]) * 1000
            start_datetime = end_datetime - datetime.timedelta(seconds=processing_s) - datetime.timedelta(microseconds=processing_ms)
        start_datetime = start_datetime + datetime.timedelta(microseconds=1000)
        start_end_time.append([start_datetime,end_datetime])
        sorted_time.append(start_datetime)
        sorted_time.append(end_datetime)
    sorted_time.sort()
    
    for compare_time in sorted_time:
        compare_time_one = compare_time + datetime.timedelta(seconds=1)
        if compare_time >= start_end_time[-1][1]:
            break;
        for each in start_end_time:
            if (compare_time <= each[0])and(each[0< compare_time_one):
                tmp_answer += 1
            elif (compare_time <= each[1])and(each[1< compare_time_one):
                tmp_answer += 1
            elif (each[0<= compare_time)and(compare_time_one <= each[1]):
                tmp_answer += 1
        if answer < tmp_answer:
            answer = tmp_answer
        tmp_answer = 0
    if answer == 0:
        answer += 1
    return answer
cs


만약 코드에 대해 궁금한 사항이나, 보다 효율적인 방법에 대해서 말씀해주실 점이 있다면 언제든지 댓글 또는 카카오톡, 이메일을 이용해서 말씀해주세요 :)

블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc

안녕하세요 .문범우입니다.

이번 포스팅에서는 hackerrank의 The Grid Search 문제를 풀어보았습니다.

난이도는 Medium, rate는 약 75%입니다.

문제 개념이나 이해자체는 크게 어렵지 않다고 생각되나 몇가지 고려할 부분들이 존재합니다.


제가 중요시 생각한 점은,

먼저 탐색하고자 하는 P배열에 대해 그 첫번째 행이 G배열에서 존재할때만 실질적인 탐색문을 반복하는 것과

그 첫번째 행이 G배열의 특정행에서 반복하여 존재할 수 있기 때문에 인덱스를 고려해가며 탐색하는 것 입니다.


보다 자세한 설명은 코드에 주석으로 달아 놓았습니다.

궁금하시거나 코드를 보다 효율적으로 개선할 방법에 대해서는 댓글 및 카카오톡, 이메일을 통해 말씀해주시면 감사하겠습니다 :)


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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
 
public class Solution {
 
    // Complete the gridSearch function below.
    static String gridSearch(String[] G, String[] P) {
        // G를 입력배열, P를 목표배열이라 하겠음
        int G_width = G[0].length(); // 입력배열의 가로길이 -> 목표배열 한줄씩 탐색시 사용됨. 
        int G_height = G.length// 입력배열의 세로길이 -> 목표배열 탐색 중에 입력배열의 높이를 넘어가면 NO를 반환
        int P_width = P[0].length(); // 목표배열의 가로길이
        int P_height = P.length// 목표배열의 세로길이 -> 목표배열 탐색 중에 목표배열의 높이를 넘어가면 YES를 반환
        int start_num = -1
        // 탐색중인 목표배열의 1 행이 13일떄, 입력배열에 01300130 과 같이 중복되서 나타날 수 있음
        // 이때 입력배열의 한줄에 대해 각각 검사하기 위해 사용하기도 하며
        // 목표배열의 1행이 위와 같이 13이고, 2행이 27일때, 입력배열이 다음과 같을 수 있음
        // 01300130
        // 99992799
        // 이러한 경우를 위해 각 입력배열의 각줄에 목표배열의 행이 포함되는지 여부뿐아니라,
        // 그 시작 인덱스가 일치하는지 알아야 하기 때문에 이때 start_num이 사용됨
        int count_from = -1;
        int count = 0;
        // count_from과 count변수는 입력배열의 탐색하고자 하는 목표배열의 행에 대해
        // 입력배열의 한 행에 몇개나 같은 문자열이 포함되어있는지를 저장함.
        // 즉, 위와 같이 01300130 같은 경우 count가 2가 되어서
        // 각각에 대해서 탐색을 진행해야 하기 때문에 탐색문을 2번 실행하게함
        for(int j=0;j<G_height;j++){ // 입력배열의 한 행씩 탐색을 진행함
            if(G[j].contains(P[0])){ // 어찌되었는 목표배열의 첫번째 행이 입력배열에 존재할때 탐색을 시작해야함
                count = 0
                start_num = -1;
                // count와 start_num 초기화, count_from은 아래 while문을 통해서 자동적으로 초기화가 됨
                while((count_from = G[j].indexOf(P[0], count_from + 1))>=0){
                    // G[j]에 P[0]가 어느 인덱스에서 시작되는지 확인, 이때 그 뒤에 count_from+1 인자를 줌으로써
                    // G[j]의 count_from+1 인덱스 이후로 부터 확인을 하는 것,
                    // 존재한다면 양수값을 주기때문에 count 값을 하나 증가,
                    // 존재하지 않는다면 -1을 반환하므로 count_from이 초기화 되는 기능이 됨
                    count++;
                }
                // 실질적인 탐색문 시작
                for(int i=0;i<count;i++){
                    start_num = G[j].indexOf(P[0], start_num+1); // G[j]에서 P[0]가 포함된 인덱스를 구함
                    for(int k=0;k<P_height;k++){ // 이제 모든 목표배열행에 대해 탐색할 것
                        if((G[j+k].contains(P[k]))&(start_num == G[j+k].indexOf(P[k],start_num))){
                            // 목표배열의 다음행이 입력배열의 다음행에 포함되어있는지 확인하면서
                            // 그 시작위치가 동일한지 확인 -> else: 즉, 그게 아니면 목표배열의 첫행에 대해 재탐색
                            if(k+1 == P_height){
                                // k가 증가하다가 목표배열의 높이를 넘어가면 모든 목표배열에 대해 탐색이 된 것이므로
                                // YES를 반환
                                return "YES";
                            }else if(j+k+1 == G_height){
                                // k가 증가하다가 목표배열의 높이를 넘어가기 전에 입력배열의 높이를 넘어가면
                                // 입력배열에 목표배열이 완전하게 존재하지 않는 것이기 때문에 NO를 반환
                                return "NO";
                            }
                        }else{
                            break;
                        }
                    }
                }
            }
        } // 해당 for문이 끝난 것은 입력배열에 목표배열이 포함되어 있지 않다는 뜻이기에 NO를 반환함
        return "NO";
    }
 
    private static final Scanner scanner = new Scanner(System.in);
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
 
        int t = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
 
        for (int tItr = 0; tItr < t; tItr++) {
            String[] RC = scanner.nextLine().split(" ");
 
            int R = Integer.parseInt(RC[0]);
 
            int C = Integer.parseInt(RC[1]);
 
            String[] G = new String[R];
 
            for (int i = 0; i < R; i++) {
                String GItem = scanner.nextLine();
                G[i] = GItem;
            }
 
            String[] rc = scanner.nextLine().split(" ");
 
            int r = Integer.parseInt(rc[0]);
 
            int c = Integer.parseInt(rc[1]);
 
            String[] P = new String[r];
 
            for (int i = 0; i < r; i++) {
                String PItem = scanner.nextLine();
                P[i] = PItem;
            }
 
            String result = gridSearch(G, P);
 
            bufferedWriter.write(result);
            bufferedWriter.newLine();
        }
 
        bufferedWriter.close();
 
        scanner.close();
    }
}
 
cs


'Algorithm > Java 풀이' 카테고리의 다른 글

JAVA #3_ The Grid Search  (0) 2018.08.08
JAVA #2_ Lily's Homework  (0) 2018.08.05
Java #1_ 가장 긴 팰린드롬 길이 구하기  (1) 2018.07.12
블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc

안녕하세요. 문범우입니다.

이번에는 Hackerrank의 문제를 풀어보았습니다.

문제 이름은 Lily's Homework이며 Medium 난이도에 속해있습니다.

생각외로 rate가 47% 정도로 좀 낮은편 입니다.

해당 문제는 아래 주소에서 풀어보실 수 있습니다.


https://www.hackerrank.com/challenges/lilys-homework/problem


코드에 주석을 통해 설명을 덧붙여 놓았기 때문에 추가적인 설명은 생략하겠습니다.

해당 코드는 아래 github 주소에서도 확인할 수 있습니다.


https://github.com/doorBW/algorithm_practice


보다 궁금한 점이 있으신 분들은 댓글 및 이메일, 카카오톡을 통해 연락주시면 바로 답변드리도록 하겠습니다 :)


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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
 
public class Solution {
    static int lilysHomework(int[] arr) {
        // arr을 오름차순 또는 내림차순의 형태로 만들어야 한다.
        // 그때가 문제에서 말한 cost가 가장 적은 경우기 때문에,
        // 이때 문제는, arr을 오름차순으로 만드는데 필요한 swap횟수와
        // arr을 내림차순으로 만드는데 필요한 swap횟수가 다르다.
        // 따라서 오름차순 및 내림차순 두 방법 모두 시행하고 그 중 작은 값을 반환한다.
 
        int answer_asc = 0;
        int answer_desc = 0;
        int idx,temp;
        int arr_length = arr.length;
        // 기존 arr은 오름차순에서 사용될 것
        // 내림차순에서 사용될 arr_desc을 만들고 기존 arr을 복사해서 넣는다.
        int[] arr_desc = new int[arr_length];
        System.arraycopy( arr, 0, arr_desc, 0, arr_length );
 
        // 오름차순으로 정렬된 sorted_arr
        int[] sorted_arr = new int[arr_length];
        System.arraycopy( arr, 0, sorted_arr, 0, arr_length );
        Arrays.sort(sorted_arr);
        
        // 내림차순으로 정렬된 reversed_arr
        int[] reversed_arr = new int[arr_length];
        for(int i=0;i<arr_length;i++){
            reversed_arr[i] = -1 * arr[i];
        }
        Arrays.sort(reversed_arr);
        for(int i = 0; i < arr_length; i++){
            reversed_arr[i] *= -1;
        }
        
        // 오름차순을 위한 hash map
        HashMap<Integer, Integer> idxMap_asc = new HashMap();
        for(int i=0;i<arr_length;i++){
            idxMap_asc.put(arr[i],i);
        }
 
        // 내림차순을 위한 hash map
        HashMap<Integer, Integer> idxMap_desc = new HashMap();
        for(int i=0;i<arr_length;i++){
            idxMap_desc.put(arr_desc[i],i);
        }
        
        // 오름차순을 통한 cost 계산
        for(int i=0;i<arr_length;i++){
            if(sorted_arr[i] != arr[i]){
                idx = idxMap_asc.get(sorted_arr[i]);
                idxMap_asc.put(arr[i],idx);
                temp = arr[i];
                arr[i] = sorted_arr[i];
                arr[idx] = temp;
                answer_asc++;
            }
        }
 
        // 내림차순을 통한 cost 계산
        for(int i=0;i<arr_length;i++){
            if(reversed_arr[i] != arr_desc[i]){
                idx = idxMap_desc.get(reversed_arr[i]);
                idxMap_desc.put(arr_desc[i],idx);
                temp = arr_desc[i];
                arr_desc[i] = reversed_arr[i];
                arr_desc[idx] = temp;
                answer_desc++;
            }
        }
        
        // 더 작은값을 반환한다.
        return answer_asc > answer_desc ? answer_desc : answer_asc;
    }
 
    private static final Scanner scanner = new Scanner(System.in);
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
 
        int n = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
 
        int[] arr = new int[n];
 
        String[] arrItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
 
        for (int i = 0; i < n; i++) {
            int arrItem = Integer.parseInt(arrItems[i]);
            arr[i] = arrItem;
        }
 
        int result = lilysHomework(arr);
 
        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();
 
        bufferedWriter.close();
 
        scanner.close();
    }
}
 
cs


'Algorithm > Java 풀이' 카테고리의 다른 글

JAVA #3_ The Grid Search  (0) 2018.08.08
JAVA #2_ Lily's Homework  (0) 2018.08.05
Java #1_ 가장 긴 팰린드롬 길이 구하기  (1) 2018.07.12
블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc

안녕하세요. 문범우입니다.

오랜만에 파이썬으로 풀이한 재밌는 알고리즘 문제를 가져왔습니다.

알고리즘 문제는 프로그래머스의 알고리즘 연습에 나온 야근 지수 문제이며 해당 문제는 아래 주소에서 풀어볼 수 있습니다.

문제에 대한 설명도 해당 주소에 나와있기에 문제에 대한 설명은 생략하겠습니다.

https://programmers.co.kr/learn/courses/30/lessons/12927


사실 예전에 매우 간단히 풀이한 문제인데

다시 확인해보니 문제 개편이 되면서..

테스트 케이스가 매우 까다롭게 변했더라구요.

그래도 정확도 통과는 비교적 무난했지만, 효율성 테스트에서 계속 막혀 씨름을 하다가 마침내 풀게되었습니다.

코드와 함께 간단한 해설을 첨부합니다.

추가적으로 궁금하신점이 있으신분들은 이메일이나 카카오톡으로 언제든지 문의해주세요 :)


1. 정확도 통과, 효율성 실패


먼저 정확도는 통과했지만 효율성에서 실패한 처음 코드입니다.


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
26
27
28
29
def solution(n, works):
    result = 0 # 결과를 담을 변수
    sumOfWorks = 0 # 모든 일의 합을 담을 변수
    for i in works: # 모든 일의 합을 구한다.
        sumOfWorks+=
    # 남은 일보다 n이 클때는 0을 반환
    if(n >= sumOfWorks): return 0
 
    # n이 0이될때 까지 반복
    while(n!=0):
        works[works.index(max(works))]-=1 # works에서 가장큰 값을 하나 줄이면서
        n-=1 # n의 값을 하나 줄인다.
        if(min(works) == max(works)): break
        # 만약 works에서 가장큰 값과 가장 작은 값이 같아지면 반복문을 나간다.
 
    # n이 0까지 줄어들어든 것이 아니라면
    if not n==0:
        # 이때는, works에서 가장큰값과 가장 작은 값이 같은 상황
        # 즉, works의 모든 값이 동일한 상황이다.
        # 따라서, n의 크기만큼의 요소를 -1씩해서 각각을 제곱하여 결과에 더하고
        # 나머지는 -1을 하지 않고 제곱해서 결과에 더한다.
        return n*((min(works)-1)**2+ (len(works)-n)*((min(works))**2)
    # n이 0까지 줄어든 것이라면 남은 works의 모든 값을 제곱해서 더한다.
    else:
        for i in works:
            result += i**2
 
    # 야근 지수를 최소화 하였을 때의 야근 지수는 몇일까요?
    return result
cs


코드에 대한 상세한 내용은 주석으로 설명하였습니다.

전체적인 알고리즘을 말씀드리면,

단순히 works 리스트에서 가장 큰 값을 찾아 이를 하나씩 줄이는 방법입니다.

추가로, 처음에 모든 남은 일의 합이 n 보다 작으면 0을 반환하게 하는 특수조건이 있습니다.

또한, works 리스트에서 값을 하나씩 줄이다가 최소값과 최대값이 동일한 시점, 즉 works 리스트의 모든 요소가 같아지는 시점도 따로 빼내어서 바로 계산하게끔 처리하였습니다.


위와 같은 풀이는 제목과 같이 정확도 테스트 케이스는 모두 통과하였으나 효율성 테스트 케이스에서 통과하지 못했습니다.

이에 따라 조금 다른 방식으로 생각해서 풀어보았습니다.



2. 정확도 통과, 효율성 통과


먼저 두번째로 풀이하여 정확도와 효율성 모두 통과한 코드는 다음과 같습니다.


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 solution(n, works):
    result=0 # 결과를 담을 변수
    works.append(0# 최소값을 위해 works에 0추가
    works.sort() # works를 오름차순으로 정렬
    for i in range(1,len(works)): 
        # works에 대해 맨뒤에서 부터 확인할 것임
        # 인덱싱하기 편하게 하도록 i는 1부터 시작
        tmp = works[-i] - works[-(i+1)] # works에서 첫번째로 큰 숫자와 두번째로 큰 숫자의 차이 구함
        if tmp*< n: # 해당 차이 x 몇번째인지가 n보다 작으면
            n -= tmp*# 그만큼 n을 빼주고
            for j in range(1,i+1):
                works[-j] -= tmp # 첫번째로 큰 숫자를 두번째로 큰숫자와 같게 만든다.
        else# 해당 차이 x 몇번째인지가 n보다 작은게 아니라면
            q = n//# n에 대해서 몇번째인지로 나눈다. 이때 몫은 q, 나머지는 n
            n = n%i
            for j in range(1,i+1):
                works[-j] -= q # 제일 뒤의 숫자부터, i번째까지 몫만큼 빼준다.
            for j in range(1,n+1):
                works[-j] -= 1 # 나머지 처리
            break # 끝
    for i in works:
        result += i**2
 
    # 야근 지수를 최소화 하였을 때의 야근 지수는 몇일까요?
    return result
cs


해당 코드또한 주석으로 설명을 달아놓았지만, 적절한 예시가 없으면 바로 이해하기 힘들수 있기에 하나의 예시를 통해 어떤식으로 알고리즘이 result를 찾아내는지 확인해보도록 하겠습니다.


먼저 입력으로 n = 100, works = [10,9000,9997,9998,9999,10000] 이 들어온다고 가정합니다.

works가 위와 같이 정렬된 상태가 아니어도 4번째줄 코드에서 오름차순으로 정렬합니다.

5번째줄의 for문부터 확인해보도록 하겠습니다.

먼저 첫번째 for문은 i가 1부터 (works의 길이)-1 이므로, 해당 예시에서는 1부터 5까지 반복됩니다.

다음 줄을 보시면 아시겠지만 works의 뒤의 요소부터 인덱싱을 할때 -i 라고 명시하기때문에 i값이 1부터 시작되도록 하였습니다.

(works[-1]은 works의 가장 뒤에 있는 요소를 인덱싱합니다.)

따라서 첫번째 반복에서 tmp = 1 이 됩니다.

그리고 9번째줄 if문을 확인하면 tmp = 1 * i = 1 => 1이 되기 때문에 n보다 작아서 10~12번째줄을 수행하게 됩니다.

10번째줄에 의해서 n이 1000에서 999로 줄어들게 되고, works는 다음과 같이 변화합니다.

works = [10,9000,9997,9998,9999,9999]

즉, 뒤에서 첫번째 요소를 두번째 요소와 같게 만듭니다.


그리고 i가 하나 증가하고 첫번째 for문의 두번째 반복이 진행됩니다.

같은 방법에 의해서, n은 999에서 997로 줄어들게 되고, works는 다음과 같이 변화합니다.

works = [10,9000,9997,9998,9998,9998]

첫번째 반복에서는 n이 1만큼 감소했지만 두번째 반복에서는 i가 2이기 때문에 n이 2만큼 감소합니다. 즉, 뒤에서 첫번째, 두번째 요소를 세번째요소와 같게 만드는 것입니다.


세번째 반복에서도 동일하여, n은 994가 되고, works은 다음과 같이 됩니다.

works = [10,9000,9997,9997,9997,9997]


이제 네번째 반복입니다.

이때 tmp = 9997 - 9000 = 997 이 됩니다.

현재 i = 4이기 때문에 9번째 줄의 코드에서, tmp*i = 3988 로써 현재 n = 994 보다 크게 되므로 10~12번째줄을 수행하지 않고 13번째, else문이 실행됩니다.

그리고 14번째 줄에 의해 q = 994//4 = 248이 되고, n = 994%4 = 2 가 됩니다.

그리고 16~17번째 줄에 의해서 현재 9997의 값을 갖고있는 요소들이 q = 248 만큼 감소합니다. 즉, works가 다음과 같이 변화합니다.

works = [10,9000,9749,9749,9749,9749]


총 줄어든 값은 248 * 4 = 992 인데, 위에서 나머지 계산을 통해 n = 2가 되었습니다. 두 값을 더해서 생각해보면 이전의 n 값인 994와 같음을 알 수 있습니다.

그리고 나머지 2를 처리하기 위해 n이 0이 될때까지 works의 가장 뒤의 요소부터 1씩 감소시킵니다.


n은 i로 나눈 나머지이기 때문에 절대로 (해당 예시에서는)9749의 값을 갖는 요소를 벗어날 수 없습니다.

따라서 works는 다음과 같이 변화합니다.

works = [10,9000,9749,9749,9748,9748]


그리고 break문을 만나 반복문을 벗어나 결과를 출력하게 됩니다.



해당 알고리즘을 어떻게 간단하게 설명해야 할지 몰라서 까다로웠던 예시를 하나 들어서 설명드렸습니다.

조금이나마 간단하게 설명해본다면 처음 입력받는 works에 대해 가장 큰 값들부터 고려하여, 그 다음 큰 값과 같게하면서 줄여나가는 방법입니다. 이는 단순히 1씩 감소시키는 것이 아니라, 큰 값들의 차이만큼 감소 시키며 그 전의 큰 값들도 같이 감소시키게 됩니다. 그리고 감소시킬 값과 n을 비교해가면서 감소시킬 값이 n보다 크면 안되므로 이럴때는 n값을 지금까지 줄여나간 요소의 개수 만큼으로 나누어 그 몫을 줄여나간 요소들에 대해 동등하게 감소시키고, 나머지는 그 요소들에 대해 1씩 줄이는 방법입니다.



블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc

안녕하세요. 문범우입니다.

이번 포스팅에서는 Java 언어를 통해서 '가장 긴 팰린드롬' 이라는 알고리즘 풀이를 풀어보도록 하겠습니다.

해당 문제는 아래 프로그래머스 사이트에서 풀어보실 수 있습니다.


https://programmers.co.kr/learn/courses/30/lessons/12904?language=java



1. 문제 접근


팰린드롬이란, 문자열을 거꾸로 뒤집었을때도 모양이 같은 것들을 말합니다.

예를 들어, 'aba', 'aaddaa' 등도 팰린드롬이며 'asddfd' 라는 문자열에서는 'dfd'가 팰린드롬 문자열입니다.


해당 문제는 입력으로 주어지는 문자열에서 길이가 가장 긴 팰린드롬을 찾아서 그 길이를 반환하는 문제입니다.


팰린드롬에 대한 자세한 설명은 문제 또는 구글링을 통해 확인하실 수 있습니다.


먼저, 팰린드롬 문자열은 그것이 홀수 길이 이거나 짝수 길이 일때로 나누어서 생각해볼 수 있습니다.

팰린드롬 문자열이 홀수 길이 일때에는, 하나의 문자열을 기준으로 잡아서 그 왼쪽과 오른쪽 문자열을 서로 비교해가며 구하면됩니다.

팰린드롬 문자열이 짝수 길이 일때에는, 연속으로 동일한 문자열 2개를 기준으로 잡아서 그 왼쪽과 오른쪽 문자열을 서로 비교해가며 구하면됩니다.


하지만 중요한건, 우리는 입력되는 문자열에 대해서 계산될 팰린드롬 문자열의 길이가 홀수인지 짝수인지 미리 알 수 없습니다.

따라서, 입력되는 문자열에 대해 홀수 길이에 대한 알고리즘과, 짝수 길이에 대한 알고리즘을 모두 통과시키도록 하고 여기서 더 큰 값을 반환하도록 해야 합니다.



2. Java 코드


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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution
{
    public int solution(String s)
    {
        int max_len = 1;
        int temp_len = 1;
        int len = s.length();
        // 팰린드롬 길이가 짝수일 경우
        for(int i=0; i<len-1; i++){
            if(s.charAt(i) == s.charAt(i+1)){ // 짝수 문자열에서 팰린드롬 기준점 선출
                temp_len = 0;
                for(int j=i+1; j<len; j++){
                    try{
                        char left = s.charAt(i+1-j+i); // left 위치선정
                        // left 위치 선정은 약간 까다로울 수 있음.
                        // 직접 연습장에 예시를 하나 두고 i와 j값을 변화시키며 확인해보는 것이 좋음
                        char right = s.charAt(j);
                        if(left == right){
                            temp_len += 2;
                        }else{
                            break;
                        }
                    }catch(Exception e){
                        break;
                    }
                }
            }
            if(max_len < temp_len){
                max_len = temp_len;
            }
        }
        // 팰린드롬 길이가 홀수일경우
        for(int i=0; i<len-1; i++){
            temp_len = 1;
            for(int j=i-1; j>=0; j--){
                try{
                    char left = s.charAt(j);
                    char right = s.charAt(i+i-j); // right 위치선정
                    // 이 또한 직접 예시를 하나 두고 i와 j값을 변화시키며 확인해보는 것이 좋음
                    if(left == right){
                        temp_len += 2;
                    }else{
                        break;
                    }
                }catch(Exception e){
                    break;
                }
            }
            if(max_len < temp_len){
                max_len = temp_len;
            }
        }
        return max_len;
    }
}
cs


해당 코드는 아래 github 주소에서도 만나보실 수 있습니다.

https://github.com/doorBW/algorithm_practice

'Algorithm > Java 풀이' 카테고리의 다른 글

JAVA #3_ The Grid Search  (0) 2018.08.08
JAVA #2_ Lily's Homework  (0) 2018.08.05
Java #1_ 가장 긴 팰린드롬 길이 구하기  (1) 2018.07.12
블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc

안녕하세요. 문범우입니다.

이번 포스팅에서는 분류나 회귀에서 사용되는 KNN(K - Nearest Neighbors) 알고리즘에 대해서 알아보도록 하겠습니다.



1. KNN(K - Nearest Neighbors)


KNN, K-최근접 이웃 알고리즘은 특정공간내에서 입력과 제일 근접한 k개의 요소를 찾아, 더 많이 일치하는 것으로 분류하는 알고리즘입니다.


말로 이해하는 것보다 아래 그림을 통해 이해하는 것이 훨씬 쉬울 것 입니다.


위의 그림과 같은 좌표공간을 예시로 확인해보겠습니다.

위에서 파란색 점으로 되어 있는 그룹을 A그룹이라고 생각하고, 주황색 점으로 되어 있는 그룹을 B라고 하겠습니다.

이때 우리는 별 모양으로 표시된 입력값이 A그룹에 속하는지, B그룹에 속하는지를 알고 싶습니다.


그리고 이럴때 사용되는 KNN 알고리즘은 다음과 같이 적용됩니다.

우선 k값을 정의해줘야 합니다. 해당 k값에 대한 설명은 조금 밑에서 드리도록 하고, 우선 k를 3이라는 값으로 정했다고 생각해보겠습니다.


그럼 우리는 입력값과 가장 근접한 k개의 요소를 찾습니다. k = 3이므로 3개의 요수를 찾아보면 다음 그림과 같습니다.


별 모양의 점을 기준으로 원을 그려서 확인함으로써, 위의 빨간색 원과 같이 파란색 점 하나와 주황색 점 두개가 선택됨을 알 수 있습니다.

그리고 이를 통해 입력값은 주황색 점의 그룹, 즉 B의 그룹과 더 일치하다는 판단을 내릴 수 있습니다.


추가적으로 생각해보면, KNN 알고리즘은 정의한 k 값에 따라서 입력값의 분류 결과가 달라질 수 있습니다.


만약 우리가 k를 3으로 두지 않고 1로 두었다면, 아래 그림과 같은 원이 그려짐으로써 입력값은 A그룹으로 분류될 수 있습니다.



 KNN 알고리즘을 사용할 때는 적절한 k값을 찾아 설정해주는 것이 중요합니다.


또한, 위와 같이 2개의 그룹에 대해 분류를 할때 만약 k값을 짝수로 한다면 어떻게 될까요?

만약 k = 4 라고 설정했다면 다음과 같은 결과가 나옵니다.


그림에서 확인할 수 있듯이, 파란색 점 2개, 주황색 점 2개가 됨으로써 입력 값이 어떠한 그룹이라는 결론을 내릴 수 없게 됩니다.


그렇다고 무조건 k를 홀수 값으로 설정해야 하는 것은 아닙니다.

위와 같이 2개의 그룹에 대한 분류를 할때는 무조건 홀수 값을 주어야 겠지만, 만약 입력값을 3개의 그룹에 대해 분류를 할때 k = 3으로 둔다면 각각의 그룹의 요소가 하나씩 포함되어 위와 같이 어떠한 그룹이라는 결론을 내지 못하는 상황이 올 수 있습니다.


즉, KNN알고리즘을 사용할때는 분류될 그룹의 종류등을 고려하여 적절한 k값을 설정해주는 것이 중요합니다.



2. 파이썬으로 구현하기


위에서 알아본 KNN 알고리즘을 파이썬으로 구현해 보았습니다.

* 코드는 jupyter notebook에서 실행하였습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
%matplotlib nbagg
 
A_x_list = [0,2,4,1,1,4]
A_y_list = [4,1,5,5,2,6]
A_x = np.array(A_x_list)
A_y = np.array(A_y_list)
 
B_x_list = [7,7,5,7,10,9]
B_y_list = [4,0,2,2,3,3]
B_x = np.array(B_x_list)
B_y = np.array(B_y_list)
 
finding_point = [5,4]
 
plt.figure()
plt.scatter(A_x,A_y)
plt.scatter(B_x,B_y)
plt.scatter(finding_point[0],finding_point[1], marker='*')
 
plt.show()
cs


먼저 입력값과 기존에 존재하는 A그룹, B그룹을 좌표상으로 나타내보았습니다.

위의 코드를 통해 나오는 그래프는 아래와 같이, 우리가 위에서 살펴봤던 예제 그림과 같습니다.



그리고 실제로 입력값을 KNN 알고리즘에 적용시켜 분류하는 코드는 다음과 같습니다.


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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
# L리스트에서 c번째 작은 값 찾는 함수
def count_min_value(L,c):
    temp = L.copy()
    temp.sort()
    item = temp[c-1]
    return L.index(item),item
 
# 입력값이 A그룹인지 B그룹인지 찾는 함수::KNN Algorithm 적용
def finding_AorB(k,x,y):
    numA = 0
    numB = 0
    A_xy = []
    B_xy = []
    # x,y 좌표가 따로 있는 것을 하나의 리스트로 통합
    for i in range(len(A_x_list)):
        A_xy.append([A_x_list[i],A_y_list[i]])
    for i in range(len(B_x_list)):
        B_xy.append([B_x_list[i],B_y_list[i]])
 
    A_distance = []
    B_distance = []
    # x,y 좌표에 대해 입력값과의 거리 산출
    for each in A_xy:
        dis = ((each[0- x)**2 + (each[1- y)**2)**(1/2)
        A_distance.append(dis)
    for each in B_xy:
        dis = ((each[0- x)**2 + (each[1- y)**2)**(1/2)
        B_distance.append(dis)
    A_result = []
    B_result = []
    
    A_min_count = 1
    B_min_count = 1
    while(numA + numB < k):
        min_A = 99999
        min_B = 99999
 
        _, min_A = count_min_value(A_distance,A_min_count)
        _, min_B = count_min_value(B_distance,B_min_count)
 
        if min_A < min_B:
            numA += 1
            A_min_count += 1
            A_result.append(A_xy[A_distance.index(min_A)])
            A_distance[A_distance.index(min_A)] = -1
        elif min_A > min_B:
            numB += 1
            B_min_count += 1
            B_result.append(B_xy[B_distance.index(min_B)])
            B_distance[B_distance.index(min_B)] = -1
        elif min_A == min_B:
            numA += 1
            numB += 1
            A_min_count += 1
            B_min_count += 1
            A_result.append(A_xy[A_distance.index(min_A)])
            A_distance[A_distance.index(min_A)] = -1
            B_result.append(B_xy[B_distance.index(min_B)])
            B_distance[B_distance.index(min_B)] = -1
    if numA > numB:
        print("RESULT: The point is A")
    elif numA < numB:
        print("RESULT, The point is B")
    elif numA == numB:
        print("I DON'T KNOW")
    print("A point is",A_result,"\nB point is",B_result,"\n")
            
cs


위의 코드를 통해 k = 1, 2, 3, 4 로 실행 시켜보면 아래와 같은 결과가 나옵니다.




이렇게 하여 KNN 최근접 이웃 알고리즘에 대해서 알아보았습니다.

위에서 구현된 파이썬 코드는 아래 github주소에 있습니다 :)


https://github.com/doorBW/KNN-Algorithm-by-python


오류가 발생하거나 잘못된 점이 있다면 언제든지 피드백 해주시길 바랍니다.

블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc

안녕하세요. 문범우입니다.

오랜만에 재미난 알고리즘 문제를 풀게되어 포스팅하게 되었습니다.

문제의 출처는 HackerRank 이며 아래의 주소입니다.


https://www.hackerrank.com/challenges/magic-square-forming/problem


문제설명에 대한 전문은 위의 링크에서 확인하실 수 있으며, 제 github에서도 확인하실 수 있습니다.

https://github.com/doorBW/hacker_rank_algorithm_practice


문제에 대해서 간단히 설명드리면 아래와 같습니다.


- Forming a Magic Square


먼저, Magic Square는 마방진이라고 이야기하겠고, 마방진에 대한 규칙은 다음과 같습니다.

3*3 형태를 가지는 마방진 행렬에서는 1부터 9까지 9개의 숫자를 이용하며, 모든 열과 행, 대각선의 합이 같아야합니다.


그럼 문제에 대해서 알아봅니다. 문제에서 input 값으로 3*3 행렬이 들어옵니다.

근데 이때 들어오는 행렬은 마방진의 규칙을 만족할 수도 만족하지 않을 수도 있습니다. 이러한 행렬을 마방진의 규칙에 만족시키기 위해서는 특정 숫자의 값을 바꿔야 하겠죠? 

즉, 아래와 같은 행렬이 input으로 들어온다고 생각해봅시다.


4 9 2

3 5 7

8 1 5


위의 행렬은 5가 두번쓰였을 뿐아니라, 세번째 열, 세번째 행, 왼쪽위에서 시작하는 대각선의 합이 14입니다.

이때 오른쪽 아래의 숫자 5를 6으로 바꿔주면 마방진의 규칙을 만족하게 됩니다.

이렇게 우리가 한 행동은 5 -> 6 으로 바꿔주는 것인데, 이때 1만큼의 변경을 cost 1로 계산합니다.

예를 들어 우리가 마방진을 만들기 위해 특정 위치에 있는 숫자들에 대하여 다음과 같은 변화를 주었다면,


2 -> 3, 7 -> 4


이때는 cost가 총 4가 되는 것입니다.

하지만 마방진은 단 하나만 존재하는 것이 아닐 것입니다.

이렇게 입력으로 주어진 행렬을 마방진으로 만들때 발생하는 최소 cost를 구하는 것이 문제입니다.



- Solving


먼저 전체적인 코드는 하단에 작성해두었습니다.

코드에서 주석을 통해 간단하게 나마 설명을 써두었지만, 조금 더 자세히 이야기해보려고 합니다.


처음 문제를 접근했을때, 문제를 어떻게 해결할 것인가 생각해보았습니다.

주어진 행렬에 대해서 특정 위치의 값을 변화시키며 그 행렬이 마방진의 규칙을 만족하게끔 하는 방법이 떠올랐으나, 이는 경우의 수가 너무 많았습니다.

그리고 어떤 위치의 숫자를 변화시켜야 할지 기준을 잡는 것도 너무 어렵다고 느껴졌습니다.


그리고 생각했던 방법은, 마방진 규칙을 만족하는 모든 행렬을 찾아내고, 입력받은 행렬과 하나씩 비교해가며 그 중 최소의 cost를 찾아내는 방법이었습니다.

물론 이 방법에서는 과연 마방진 규칙을 만족하는 모든 행렬이 몇개나 될까가 미지수였지만 그래도 처음에 생각했던 방법보다는 경우의 수가 훨씬 적을 것 같아서 해당 방법으로 풀이를 시작했습니다.


그리고 문제에서 주어진 것보다 더 많은 내용을 참고하기 위해 magic square, 마방진이라는 개념에 대해서 찾아보았습니다. 자세히 검색해본 것은 아니지만 대체로 마방진을 만드는 몇가지 원리에 대해서 이야기를 많이 하고 계셨습니다.

하지만 우리에게 실질적으로 필요했던건, 마방진의 원리 그 자체를 알아서 3*3에서 존재할 수 있는 모든 마방진이 필요했습니다.


따라서 직접 그 원리를 얕게나마 확인해보는 과정이 필요했습니다.


기본적으로 3*3 마방진에서 하나의 행 또는 열 또는 대각선의 합은 무조건 15입니다.(이를 증명하는 것은 쉬우니 스스로 해보시길 바랍니다.)

따라서 저는 먼저 1~9까지의 숫자들중 중복이 없는 3개의 숫자의 합이 15를 이루는 그룹을 만들었습니다. 예를 들면 3,5,7 과 같은 그룹입니다.

각 숫자의 순서와 상관없이 만들어 보았을때 이러한 그룹은 총 8개가 만들어졌습니다.


그리고 아래와 같은 형태의 행렬을 생각해보았습니다.


a  b  c

d  e  f

g  h  i


위의 행렬을 통해 8개의 식을 세울 수 있습니다.


a + b + c = 15

d + e + f = 15

g + h + i = 15

a + d + g = 15

b + e + h = 15

c + f + i = 15

a + e + i = 15

c + e + g = 15


그런데 이렇게 식을 세워보니 새로운 사실을 알 수 있었습니다.

위의 식에서 각 알파벳이 사용되는 횟수가 달랐습니다.

예를 들어 한가운데 존재하는 e 같은 경우 혼자서만 4번 사용되었고, 4개의 알파벳은 3번, 4개의 알파벳은 2번 사용되었습니다.

그리고 위의 식들은 숫자 위치만 적절히 조정하면 우리가 위에서 만든, 합이 15인 8개의 그룹입니다.


이러한 사실들을 통해 저는 위에서 만들었던 8개의 그룹을 바탕으로 각 숫자가 몇번 사용되었는지 카운팅 해본결과, 4번 사용되는 것은 숫자 5, 3번 사용되는 것은 2,4,6,8 이고 2번 사용되는 것은 1,3,7,9 이었습니다.

즉, 위에서 만든 알파벳 행렬이 마방진 규칙을 만족한다고 가정한다면 사실상 알파벳 e는 무조건 5의 값을 가질 것이며, 3번 사용되는 a,c,g,i는 2,4,6,8과 대응되고 나머지 알파벳은 1,3,7,9와 대응될 것입니다.


그렇다면, 우리가 만든 8개의 그룹을 한번 더 나누어 볼 수 있습니다.

숫자 5가 포함된 것은 무조건 2행에서만 사용될 수 있기 때문입니다.

따라서 저는 첫번째 행과 세번째 행에 사용될 수 있는 그룹과, 두번째 행에 사용될 수 있는 그룹을 만들었습니다.

추후 실제로 이 그룹들을 바탕으로 마방진 규칙을 만족하는 행렬을 만들 것이기에 이번에는 숫자들의 순서(위치)등을 고려하여 모든 경우의 수를 다루었습니다.

그리고 아래의 추가적인 조건을 활용하였습니다.


- 숫자 5가 포함된 그룹에서 나머지 두 숫자는 모두 1,3,7,9 중의 숫자이다.(2번 사용되는 숫자들)


이를 통해 second_lines 와 other_lines 라는 두개의 그룹을 만들었으며, 이제 이러한 두 그룹을 이용해서 행렬을 만들었습니다.

그리고 행렬을 만들면서 마방진의 규칙을 추가하여 최종적으로 마방진 규칙을 만족하는 행렬은 magic_square 이라는 리스트에 추가하였습니다.


이러한 과정을 통해 마방진 규칙을 만족하는 모든 행렬은 총 8개가 되었습니다.

걱정했던 것과는 달리 적은 개수이기에 최종적으로 cost를 구하기 위한 과정을 가졌습니다.

입력받은 행렬을 8개의 행렬에 대해 각 위치별 숫자의 차이값을 구해서 최소의 cost를 구하여 반환하였습니다.


위의 과정을 통해 작성한 코드는 HackerRank에서 100% 통과를 받았습니다.


전체 코드는 아래와 같습니다.


Forming a Magic Square Code(Click)


코드가 완성도 있거나, 완벽하다고는 생각하지 않습니다.

코드에 대한 피드백은 언제든지 환영이며, 추가적으로 궁금하신 점은 댓글이나 이메일을 이용해주시면 감사하겠습니다.

블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc