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

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

이번 포스팅에서는 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_ 가장 긴 팰린드롬 길이 구하기  (0) 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_ 가장 긴 팰린드롬 길이 구하기  (0) 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_ 가장 긴 팰린드롬 길이 구하기  (0) 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

안녕하세요.

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



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