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

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


최근 장고를 활용하면서 재밌는 아이디어 없을까 하다가..

졸업과 취업을 앞두고 있는 제가 생각나면서

학교 졸업 가능 여부를 일일이 확인하던 모습이 보였습니다.


이에 따라서 교내 행정정보시스템에서 성적표를 .xls파일로 다운 받고, 단순히 그 파일과 영어성적 입력으로 졸업가능 여부를 확인해주는 사이트를 개발하였습니다.


먼저 사이트 주소는 아래와 같습니다.


www.uos-info.com


해당 사이트는 django(2.0 version)를 이용하여 개발되었습니다.


aws ec2와, 도메인 설정을 위해 aws route53을 이용하였습니다.



일단은 제가 속해있는 전자전기컴퓨터공학부에 한해서 서비스가 제공되고 있지만

혹여나 다른 과나 학부에 의한 요청도 들어오면 추가해보도록 하겠습니다.


학교에서 필요로하는 졸업요건은 쉽게 확인이 가능하지만, 각 학과나 학부별로 다른 졸업요건을 제가 일일이 확인할 수가 없어서 서비스에 대한 필요를 말씀해주시는 학과 및 학부에 대해 서비스를 추가할 예정입니다.


해당 서비스에서는 단순하게 여러개의 rule-based를 기반으로 졸업 여부를 확인해줍니다.

시립대 전자전기컴퓨터학부의 경우에는 특정 세부 분야로 지정된 교양을 듣거나, 전공과목을 들어야 하는 조건이 있는데 이에 대해서는 서울시립대학교에서 open API로 제공하는 서비스로 요청을 보내서, 성적표에 있는 수업의 세부분야를 확인하거나 몇학년 몇학기 수업인지 확인하여 졸업요건에 해당하는지를 체크하는 식으로 구성되어 있습니다.


해당 사이트에 대해 추가적인 문의사항이나 건의사항이 있으신 분들은 언제든지 자유롭게 댓글 및 이메일을 통해서 연락주시면 감사하겠습니다.


블로그 이미지

Tigercow.Door

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