TigerCow.Door

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

이번에 소개해드릴 알고리즘 문제는, 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

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

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

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

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

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

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

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

문제의 출처는 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

안녕하세요.

이번 포스팅에서는 파이썬을 이용하여 링크드 리스트를 구현해보도록 하겠습니다.



1. 링크드 리스트(Linked list)란?


먼저 링크드 리스트가 무엇인지 간단히 살펴보도록 하겠습니다.



링크드 리스트는 위와 같이 세개의 형태를 가지고 있습니다.

그림에서 두번째, 양방향 연결 리스트는 *Prev 가 자신보다 앞의 요소를 가르키는 것입니다.

단순히 단방향 연결리스트를 구현하면 어떤 요소의 앞의 요소를 탐색하기 위해서 결국 다시 처음부터 검색을 진행해야 하는 일이 발생할 수 있기 때문에 수행능력이 보다 안좋을 수 있습니다.

이러한 것을 보완하기 위해 양방향 연결 리스트 및 환형 연결 리스트라는 개념이 있는데, 이들은 단방향 연결 리스트보다 구현하기는 상대적으로 어려울 수 있지만 앞에서 말씀 드린 상황과 같을 때 보다 효율적으로 수행될 수 있습니다.



2. 단방향 연결 리스트 구현하기


이번 포스팅에서는 단방향 연결 리스트만 구현해보도록 하겠습니다.

기본적으로 Node 클래스와 LinkedList 클래스를 구현하였습니다. Node 클래스는 단순히 새로운 노드를 만들어 리스트에 삽입할때 사용됩니다.

LinkedList는 insert, delete, search, print, listNum 의 함수를 가집니다.

insert는 사용자가 지정한 값을 리스트의 맨 뒤에 삽입시키며 delete는 첫 번째 요소를 출력하며 이를 삭제합니다. search는 사용자가 지정한 값이 리스트의 몇번째에 있는지 탐색합니다. print는 현재 리스트를 출력해주고 listNum은 리스트의 요소가 몇개인지 출력합니다.


이를 구현한 전체 파이썬 코드는 아래와 같습니다.

LinkedList 자료구조 코드 보기


추가적으로 궁금한 사항이나 잘못된 점이 있으면 댓글을 남겨주세요 :)

블로그 이미지

Tigercow.Door

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

안녕하세요.

이번 포스팅에서는 파이썬으로 큐 자료구조 구현에 대한 내용을 소개해드리도록 하겠습니다.


1. 큐(Queue)란?


먼저 큐 자료구조에 대해서 간단하게나마 알아보도록 하겠습니다.



큐 자료구조는 위의 그림과 같이 요소(item)을 삽입하는 Enqueue 기능과 요소를 빼내는 Dequeue 기능이 있습니다.

그리고 처음에 삽입한 요소가 먼저 빠지게 되는 First In First Out(FIFO) 특징을 가지고 있습니다.



2. 큐(Queue) 구현하기


제가 파이썬 코드로 구현한 큐 자료구조는 위에서 말씀드린 Dequeue 기능과 Dequeue 기능을 포함한, 큐가 비어있는지 확인하는 isEmpty 기능을 구현하였으며 추가로 큐가 비어있을때 Dequeue를 수행하면 에러메세지와 함께 False 값을 리턴하게 하였습니다.


완성된 코드는 아래와 같습니다.


Queue 자료구조 코드 확인하기



추가적으로 궁금한 사항은 댓글을 이용해주세요.

블로그 이미지

Tigercow.Door

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

안녕하세요.

최근 파이썬을 공부하면서 기본적인 자료구조 알고리즘을 구현해보고자 생각이 들어서 포스팅을 하게 되었습니다.

제 노트북이 고장나서 노트북은 센터에 고이고이 잠들어있기 때문에.. 구름IDE로 코딩을 진행하였습니다.

나름 괜찮다고 생각이 드네요.


그럼 파이썬으로 구현한 스택 자료구조 소개해드리도록 하겠습니다.


1. 스택이란?


먼저 스택 자료구조를 구현하기 전에 간단하게나마 해당 자료구조에 대해 알아보도록 하겠습니다. 



위의 그림과 같이 스택은 push와 pop이라는 기능을 가지고 있습니다.

스택 자료구조는 말 그대로, 쌓아 올리는 것과 같은 자료구조입니다.

즉, push은 item을 쌓아올리는 기능이고, pop은 쌓여져 있는 item에서 제일 위의 것을 꺼내는 작업입니다.

따라서 스택 자료구조는 Last In First Out(LIFO) 와 같은 특성을 가지고 있습니다.



2. 스택 구현하기


제가 파이썬 코드로써 구현해볼 것은 클래스로 스택개체를 만들고, push와 pop기능을 구현하고 해당 스택이 비어있는지 확인하는 isEmpty기능까지 구현합니다.

또한 스택이 비어있을때 pop기능을 시도하면 에러메세지를 출력하며 False 값을 리턴하게 하겠습니다.


완성된 코드를 보면 아래와 같습니다.

Stack 자료구조 코드 확인하기


일부로 파이썬에서 기본적으로 제공하는 pop() 기능을 이용하지 않고 Stack 자료구조의 pop기능을 구현하였습니다.


추가적으로 궁금한 사항은 댓글에 남겨주세요 :)

블로그 이미지

Tigercow.Door

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

문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그래 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.


입력

첫째 줄에 N이 주어진다. (3<=N<=5000)


출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.


예제입력: 18

예제출력: 4


먼저 정답으로 인정된 코드는 아래와 같습니다.


정답 코드


문제를 정리해보면, N = a*5 + b*3 이 되도록 하는 (a+b)의 최소값을 구하라는 것입니다.

어찌되었든, N이라는 숫자가 위의 식과 같이 분해되게 하는 a,b를 찾는게 우선이라고 생각됩니다.

그 다음으로, a,b 합의 최소값을 찾는 순서가 되겠죠?


먼저, a,b 합의 최솟값을 갖는 경우는 어떠한 경우일까요?

입력으로 받은 숫자 N을 두개의 식으로 풀어낼 때, 5와 곱셈이 되는 숫자가 크게, 즉 숫자 a가 크게하는 것이 좋을 것입니다.

간단한 예를 들어서, 15라는 숫자가 있을 때, a를 크게하면 a=3, b=0 이 되어 a+b = 3이 될 것이고, b를 크게하면 a=0, b=5가 되어 a+b = 5가 될 것이기 때문입니다.


그럼 이제 풀이 알고리즘을 생각해보겠습니다.

일단, 숫자 N이 주어졌을 때, 이를 n으로 받겠습니다. 그리고, n을 먼저 5로 나누어 봅니다.

n = a*5 + k

나머지 k가 발생하겠죠?

만약 나머지 k가 0이라면 바로 끝내면 되겠지만 아닌 경우가 있을 것입니다.

그렇다면 나머지 k를 3으로 나누어 봅니다.

k = b*3 + i

이와 같이 여기서도 나머지 i가 발생합니다. 역시나, 나머지 i가 0이라면 이제 끝내면 됩니다.

그런데 i도 0이 아니라면 어떻게 할까요? 어쩔 수 없이, a를 하나 줄여 k를 5만큼 증가시켜야 합니다.

조금더 자세히 살펴볼게요.

i가 가질 수 있는 값은 0,1,2 총 3가지 입니다. 3으로 나눈 나머지이기 때문이죠.

만약 i가 0일땐, 그대로 출력을 하면 됩니다.

i가 1일땐, k값에 5를 추가하면 되겠죠?

k = b*3 + 1 이므로,

k+5 = b*3 +1 +5 = (b+2)*3 + 0 이기 때문입니다.

마찬가지로, i가 2일때는 k 값에 10을 추가하면 될 것입니다.

근데 k값에 5나 10을 추가하는 방법은 무엇이 있을까요?

네, 앞에서 계산한 a를 하나 또는 둘을 줄이면 됩니다.


이러한 알고리즘을 코드로써 구현하면 아래와 같이 구현됩니다.


1
2
3
4
5
6
7
8
9
10
11
12
= int(input())
= n//5
n%=5
= 0
while F>=0:
    if n%3 == 0:
        T = n//3
        n = n%3
        break
    F-=1
    n+=5
print((n==0and (F+T) or -1)
cs


먼저 1번라인에서 입력값을 받습니다.

그리고 먼저 F에 입력값을 5로 나눈 몫을 저장하고, n을 그 나머지로 바꿔줍니다.

그리고 F가 0보다 클동안 반복문을 실행하는데, F가 음수가 되버리면 말이 안되기 때문에 반복문을 종료하는 것입니다.

그리고 반복문 내에서는, 위에서 얻은 나머지 n을 3으로 나눴을 때 0이 될 때 T에 그 몫을 저장하고 반복문을 끝냅니다.

n을 3으로 나눴을 때 나머지가 0이 아니라면, F를 하나 줄이고 n에 5를 더하게 되죠.

이렇게 해서 맨 마지막 12번 라인에서 최종 나머지 n이 0일 때는 F+T를 출력하고, n=0이 아닐때는 5와 3을 통해 입력값을 만들 수 없는 것이므로 -1을 출력합니다.

블로그 이미지

Tigercow.Door

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

문제

다음 소스는 N번째 피보나치 함수를 구하는 함수이다.


1
2
3
4
5
6
7
8
9
10
11
int fibonacci(int n) {
    if (n==0) {
        printf("0");
        return 0;
    } else if (n==1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}
cs


fibonacci(3) 을 호출하면 다음과 같은 일이 일어난다.

fibonacci(3) 은 fibonacci(2) 와 fibonacci(1) (첫 번째 호출)을 호출한다.

fibonacci(2) 는 fibonacci(1) (두 번째 호출)과 fibonacci(0) 을 호출한다.

두 번째 호출한 fibonacci(1) 은 1을 출력하고 1을 리턴한다.

fibonacci(0) 은 0을 출력하고, 0을 리턴한다.

fibonacci(2) 는 fibonacci(1) 과 fibonacci(0) 의 결과를 얻고, 1을 리턴한다.

첫 번째 호출한 fibonacci(1) 은 1을 출력하고, 1을 리턴한다.

fibonacci(3) 은 fibonacci(2) 와 fibonacci(1) 의 결과를 얻고, 2를 리턴한다.

이 때, 1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N) 을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.


입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어 있다.

첫째 줄에 N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.


출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.



예제 입력 :

3

0

1

3


예제 출력 :

1 0

0 1

1 2



쉽게 말해서, 피보나치 수열 함수 중 fibonacci(1)과 fibonacci(0) 이 몇 번 호출되는지 구하는 문제입니다.

먼저 최종 정답코드는 아래와 같습니다.

최종 정답 코드

fibonacci(N)을 호출했을 때 fibonacci(1)과 fibonacci(0)이 몇번 호출되었는지 알기 위해 아래와 같은 표를 작성해 보았습니다.


 N 값

 0

 1

 2

 3

 4

 5

 6

 7

 8

 0 호출회수

 1

 0

 1

 1

 2

 3

 5

 8

 13

 1 호출회수

 0

 1

 1

 2

 3

 5

 8

 13

 21


위의 표를 보고 규칙성을 찾으셨나요?

아직 애매하다면 조금 더 자세히 살펴볼게요.

fibonacci(2) = fibonacci(1) + fibonacci(0) 입니다.

그리고, fibonacci(3) = fibonacci(2) + fibonacci(1) 입니다.

그럼, fibonacci(3) 에서 0과 1의 호출 회수는, fibonacci(2)와 fibonacci(1)의 0과 1의 호출 회수를 각각 더하면 되겠죠?

이를 식으로 써본다면,

입력 값 3에 대한 0 호출회수 = (입력 값 2에 대한 0 호출회수) + (입력 값 1에 대한 0 호출회수)

입력 값 3에 대한 1 호출회수 = (입력 값 2에 대한 1 호출회수) + (입력 값 1에 대한 1 호출회수)


그럼 입력 값 4일때는 어떨까요?

fibonacci(4) = fibonacci(3) + fibonacci(2) 이므로,

입력 값 4에 대한 0 호출회수 = (입력 값 3에 대한 0 호출회수) + (입력 값 2에 대한 0 호출회수)

입력 값 4에 대한 1 호출회수 = (입력 값 3에 대한 1 호출회수) + (입력 값 2에 대한 1 호출회수)

입니다.


이제 뭔가 보이지 않나요?

호출회수 또한 피보나치 수열을 따르고 있습니다.

이러한 개념을 바탕으로 코드를 구현하면 아래와 같습니다.


먼저 최종 정답으로 통과한 코드는 아래와 같습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
= int(input())
 
zero = [1,0,1]
one = [0,1,1]
 
def cal(num):
    length = len(zero)
    if length <= num:
        for i in range(length,num+1):
            zero.append(zero[i-1]+zero[i-2])
            one.append(one[i-1]+one[i-2])
    print("%d %d"%(zero[num],one[num]))
 
for i in range(a):
    k = int(input())
    cal(k)
cs


먼저 처음에 몇번 계산을 할 것인지, 테스트 케이스의 개수를 a로 받습니다.

그리고 6번 라인부터 12번 라인까지가 각 숫자에 대한 0과 1의 호출 횟수를 출력하는 함수입니다.

위에서 알아본 바와 같이 피보나치 수열식으로 호출 횟수를 구하여 출력하였습니다.

이를 위한 초기값은 3번라인과 4번라인에 있습니다.


궁금하신 점이나 오류가 나는 점은 언제든 댓글을 달아주세요 :)

블로그 이미지

Tigercow.Door

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

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.

2. X가 2로 나누어 떨어지면, 2로 나눈다.

3. 1을 뺀다.


정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최소값을 출력하시오.



입력

첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 자연수 N이 주어진다.


출력

첫째 줄에 연산을 하는 횟수의 최소값을 출력한다.



예제 입력 : 2

예제 출력 : 1


예제 입력2 : 10

예제 출력2 : 3



처음에는 알고리즘을 단순하게 생각했다가 바로 틀려버린 문제입니다.

먼저 최종 정답으로 통과한 코드는 아래와 같습니다.


정답 코드



처음에는 단순히 반복문과 조건문을 이용해서 문제를 풀었습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
= int(input())
count = 0
 
while True:
    if a==1:
        print(count)
        break
    
    if a%3 == 0:
        a = a/3
    elif a%2 == 0:
        a = a/2
    else:
        a = a-1
    count = count + 1
cs


이렇게 해서 풀었더니 가차 없이 틀리더군요..

뭐가 틀렸을까 고민해보다가 예제입력2로 주어진 10이라는 숫자가 보였습니다.

처음에 작성한 코드에 10을 입력하면 count는 4로 출력됩니다.

하지만 문제에서 최소한의 연산을 이용하라고 했음에 유의해야합니다.

위의 코드대로라면 10 -> 5 -> 4 -> 2 -> 2 순서로 연산이 되어 연산 회수는 총 4번입니다.

하지만, 10에서 2로 나누지 않고 1을 빼는 연산을 우선으로 한다면?

10 -> 9 -> 3 -> 1 순서로 연산이 진행되어 연산 회수는 총 3번입니다.


이러한 결과를 도출하기 위해 고민했습니다.

연산에 우선순위를 두는 것은 소용이 없습니다.

10이라는 입력에 대해 올바른 출력을 위해 1을 빼는 것을 우선 순위로 처리한다면?

6이라는 숫자를 입력했을때, 6 -> 3 -> 1 의 순서가 아닌, 6 -> 5 -> 4 -> 2 -> 1 의 순서로 연산이 될 것 입니다.

그렇다면, 입력한 숫자로 세가지 연산을 모두 수행하여(1,2번 연산은 가능할 때만) 그 결과 값을 리스트로 저장하고, 그 리스트안에 있는 각각의 숫자들을 다시 세가지 연산 모두를 수행하도록 하고, 각 루프 한번당 count를 1씩 증가시키면 어떨까요?


정리해본다면, 세가지 연산을 모두 처리하는 함수 cal()을 만들어서 cal()함수를 재귀적으로 호출하는 방법입니다.


그래서 처음에 언급한 코드를 구현하게 되었습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
= int(input())
count = 0
minimum=[a]
def cal(a):
    list = []
    for i in a:
        list.append(i-1)
        if i%3 == 0:
            list.append(i/3)
        if i%2 == 0:
            list.append(i/2)
    return list
 
while True:
    if a == 1:
        print(count)
        break
    temp = minimum[:]
    minimum = []
    minimum = cal(temp)
    count +=1
    if min(minimum) == 1:
        print(count)
        break
cs


위의 코드를 보시면, 처음에 minimum이라는 리스트를 선언하고 초기값으로 입력값을 넣습니다.

그리고 4번 라인부터 12번 라인까지는 3가지 연산을 수행하고 그 결과값을 배열로써 반환하는 함수입니다.

15번에서 입력값이 1일때를 처리하고, 이후 minimum배열을 복사해서 temp 배열을 구성하고, minimum 배열은 다시 비우도록 합니다. 단순히 하나의 배열에 계속 넣게되면 메모리 초과가 될까봐 이런식으로 구현하였습니다.

그리고 temp를 cal()함수의 인자로 넣어 연산을 수행하고, 그 결과값 배열을 minimum으로 받습니다.

그리고 연산 count를 1 증가시키고, minimum에 있는 값중 최소값이 1일때 count값을 출력하며 반복문을 마무리하도록 합니다.


블로그 이미지

Tigercow.Door

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