손가락놀이터

문제 설명

길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다.
배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. (단, 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없습니다.)

예를 들어 A = [1, 4, 2] , B = [5, 4, 4] 라면

• A에서 첫번째 숫자인 1, B에서 두번째 숫자인 5를 뽑아 곱하여 더합니다. (누적된 값 : 0 + 5(1x5) = 5)
• A에서 두번째 숫자인 4, B에서 세번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 5 + 16(4x4) = 21)
• A에서 세번째 숫자인 2, B에서 첫번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 21 + 8(2x4) = 29)

즉, 이 경우가 최소가 되므로 29를 return 합니다.

배열 A, B가 주어질 때 최종적으로 누적된 최솟값을 return 하는 solution 함수를 완성해 주세요.

제한사항

• 배열 A, B의 크기 : 1,000 이하의 자연수
• 배열 A, B의 원소의 크기 : 1,000 이하의 자연수

입출력 예시

def solution(A,B):
    answer = 0
    
    A = sorted(A)   # 오름차순으로 정렬
    B = list(reversed(sorted(B)))   #  내림차순으로 정렬
    
    # index 별로 곱하여 더하기
    for idx in range(len(A)):
        answer += A[idx] * B[idx]

    return answer

문제 후기

처음에는 단순히 층에서 가장 높은 수, 그 중에서 위의 층과 다른 칸을 선택하려했습니다. 코드를 완성하고 확인해보니 실패가 나와 문제를 다시 읽고 DP라는 것을 깨달았습니다.

문제는 DP를 이용하는 것으로 같은 층의 값은 서로 영향을 미치지 않고 오직 위의 층 값에 영향을 받습니다. 따라서 층을 기준으로 DP를 작성했습니다.

문제 설명

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면,

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

제한사항

• 행의 개수 N : 100,000 이하의 자연수
• 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
• 점수 : 100 이하의 자연수

def solution(land):

    # 2번째 층부터 시작하므로 1로 시작
    idx = 1

    # DP 시작
    while idx < len(land):
        # 4개의 숫자 확인.
        for num in range(len(land[idx])):
            chk = []    # 임의의 배열.
            for d_num in range(len(land[idx-1])):
                if num != d_num:
                    # 위의 칸과 다를 때, 위의 층과의 합.
                    chk.append(land[idx][num]+land[idx-1][d_num])
            # 해당 칸에서 나올 수 있는 가장 높은 값.
            land[idx][num] = max(chk)
        # 층수 + 1
        idx += 1
    return max(land[len(land)-1])

머신러닝이란?

Machine Learning. 기계가 학습한다는 뜻입니다. 데이터가 주어졌을 때 기계가 데이터를 기반하여 학습하는 것으로 사람이 찾은 특징을 바탕으로 학습을 진행합니다. 따라서, 처리될 정보에 대해 더 많이 배울 수 있도록 많은 양의 데이터를 제공해야 합니다.

결국, 빅데이터를 통한 학습 방법으로 머신러닝을 이용할 수 있습니다. 머신러닝은 기본적으로 알고리즘을 이용해 데이터를 분석하고, 분석을 통해 학습하며, 학습한 내용을 기반으로 판단이나 예측을 합니다.

딥러닝이란?

완전한 머신 러닝을 실현하는 기술이라고 생각하면 됩니다. 머신러닝은 사람이 특징을 찾고 특징을 바탕으로 학습을 진행했다면 딥러닝은 스스로 데이터의 특징을 잡는 것입니다. 사람이 생각하지 못한 부분, 아니라고 생각했던 부분도 데이터의 특징이 될 수 있습니다.

의료에서 생각해보면 사람이 정해 놓지 않고 단순히 CT를 보고 특정 질병이 가지고 있는 특징을 확인하여 다음 Input 사진이 들어왔을 때 예측을 진행합니다.

딥러닝의 현재와 미래

현재 딥러닝은 엄청난 호황기를 맞이하고 있다고 생각합니다. 이전에 몇 차례 겨울을 지나면서 많이 힘들었지만 딥러닝의 시작인 제프리 힌튼과 여러 인공지능 분야의 대단하시고, 똑똑하면서 열정을 가지고 분들을 통해 발전이 이뤄지고 있습니다. 특히, 구글의 Tensorflow와 같은 딥러닝용 오픈소스를 통해서 우리와 같은 초심자들도 생각보다 쉽게(?) 접할 수 있게 됐다고 생각합니다.

여러 기업들이 단순히 정확성 n%를 위해서 천문학적인 돈을 투자 할만가, 아니면 투자를 한 기회비용만큼의 수익을 낼 수 있는가를 생각해보면 모르겠습니다...물론 저와 같은 이제 시작하는 사람들은 모르는 이야기죠....ㅠㅠ(잘못하면 AR, VR처럼 인기가 싹 사라질 수도)그래도 어디선가 지금도 개발하고 계신 분들 힘내주시고 오늘도 다짐하고 다시 공부 시작합니다 :)

문제 후기

해당 문제를 처음 접하고 문자를 list형태로 변환하여 해결하려 했습니다. 완성한 결과 배열이 계속해서 for문을 통해 탐색을 하여 시간초과가 나왔습니다. 이후 변환을 하지 않고 문자열상태에서 count와 +-를 활용하여 해결했습니다.

문자열로 나오는 경우 먼저 문자열로 해결할 수 있는지 확인하거나 시간을 확인한 이후 배열로 해결해야겠습니다.

문제 설명

0과 1로 이루어진 어떤 문자열 x에 대한 이진 변환을 다음과 같이 정의합니다.

1. x의 모든 0을 제거합니다.
2. x의 길이를 c라고 하면, x를 c를 2진법으로 표현한 문자열로 바꿉니다.

예를 들어, x = "0111010"이라면, x에 이진 변환을 가하면 x = "0111010" -> "1111" -> "100" 이 됩니다.

0과 1로 이루어진 문자열 s가 매개변수로 주어집니다. s가 1이 될 때까지 계속해서 s에 이진 변환을 가했을 때, 이진 변환의 횟수와 변환 과정에서 제거된 모든 0의 개수를 각각 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• s의 길이는 1 이상 150,000 이하입니다.
• s에는 '1'이 최소 하나 이상 포함되어 있습니다.

코드

def solution(s):

    change_transform = 0    # 변환 횟수
    remove_zero = 0         # 0 제거 횟수
    sentence = s            # input 값. 알고리즘 활용 문자

    # 2진수가 3자리 이상인 경우에 반복문 진행.
    while len(sentence) > 2:

        new_sentence = ""   # 변환한 문자
        chk_one = sentence.count("1")   # 1의 갯수, 다음 계산하는 이진수
        remove_zero += sentence.count("0")  # 제거한 0을 더해줌.
        len_next = chk_one  # 1의 갯수, 아래 while문에서 활용하는 변수

        # 1의 갯수를 다시 2진수로 변환. 
        while len_next > 1:

            new_sentence = str(len_next % 2) + new_sentence
            len_next = len_next // 2
        
        # 2진수가 3자리 이상인 경우 1을 추가.
        if chk_one != 2 and chk_one != 3:
            new_sentence = "1" + new_sentence
            change_transform += 1
        
        # 2진수가 "11" 인 경우 3번 변환과 0을 한번 제거
        elif chk_one == 3:
            change_transform += 3
            remove_zero += 1
            return [change_transform, remove_zero]
        
        # 2진수가 "10"인 경우 2번 변환과 0을 한번 제거
        else:
            change_transform += 2
            remove_zero += 1
            return [change_transform, remove_zero]

        sentence = new_sentence
    # 2진수가 "1"로 끝난 경우
    return [change_transform, remove_zero]

문제 후기

문제를 보고 가장 먼저 고민한 것은 15(1111)과 30(11110)과 같이 다음 오는 숫자가 자릿수가 증가하는 경우였습니다.

다른 것은 어떻게 하면 쉽게 숫자를 넘겨줄 수 있을까라는 생각을 했고 Queue와 배열을 고민하다 문제를 풀면서 queue의 의미가 없다고 생각하여 배열을 사용했습니다. 

해결 방식은 위에서부터 1인경우 pass하고 0이 나왔다면 0과 1의 자리를 바꾸고 뒤는 가장 작은 수를 배치하는 것입니다.

1001110 에서 1001110 -> 1010110로 바꾸고 뒤의 110은 가장 작은 수로 변경해야하므로 0의 갯수만큼 먼저 합치고, 그 이후 1을 합쳐서 1010011이 되는 방식입니다.

문제 설명

자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다.

• 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다.
• 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다.
• 조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다.

예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다.

자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.

Python 코드

def solution(n):
    arr = [] # n을 2진수로 변환
    res = [] # n 다음 숫자의 2진수

    # n 숫자를 2진수로 변환
    while n >= 2:
        if n % 2 == 0:
            arr.append(0)
        else:
            arr.append(1)
        n = n // 2
    arr.append(1)



    tmp = [] # 임의의 배열
    zero, one = 0,0 #
    val = 1 #
    result = 0 # 결과값.

    # n의 2진수로부터 시작
    for idx in range(len(arr)-1):
        k = arr[idx]

        # 만약 해당 값이 1이고 그 다음 값이 0인 경우 서로 변경.
        if k == 1 and arr[idx+1] == 0:
            # zero와 one을 이용하여 바꾼 부분 뒤를 가장 작은 수로 만듬.
            for i in range(one):
                res.append(1)
            for j in range(zero):
                res.append(0)

            res.append(arr[idx+1]) # 1과 0을 서로 변경.
            res.append(1)

            # 나머지 부분을 합침.
            res.extend(arr[idx+2:])

            # 2진수 -> 10진수
            for x in res:
                result += val * x
                val *= 2
            return result

        # 바꾸기 전의 1의 갯수
        elif k == 1:
            one += 1

        # 바꾸기 전의 0의 갯수
        elif k == 0:
           zero += 1

    # 만약 위에서 return이 안된 경우, 더이상 바꾸는 것으로 증가 안되는 경우
    for j in range(one):
        tmp.append(1)
    for i in range(zero):
        tmp.append(0)

    # 2번째에 0을 추가하여 1의 갯수도 같으면서 다음 큰 수
    tmp.append(0)
    tmp.append(1)

    for x in tmp:
        result += val * x
        val *= 2
    return result

문제 요약

해당 문제는 2019 카카오 겨울 인턴쉽 코딩테스트 문제입니다.

집합의 크기 순으로 튜플을 정리하는 문제입니다. 먼저 문자열을 분리하여 배열형태로 변형을 하고 각 집합의 크기를 활용하여 정렬하고 차례대로 뽑아냅니다.

문제 설명

셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, 다음과 같이 표현할 수 있습니다.

• (a1, a2, a3, ..., an)

튜플은 다음과 같은 성질을 가지고 있습니다.

1. 중복된 원소가 있을 수 있습니다. ex : (2, 3, 1, 2)
2. 원소에 정해진 순서가 있으며, 원소의 순서가 다르면 서로 다른 튜플입니다. ex : (1, 2, 3) ≠ (1, 3, 2)
3. 튜플의 원소 개수는 유한합니다.

원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음과 같이 집합 기호 '{', '}'를 이용해 표현할 수 있습니다.

• {{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}}

예를 들어 튜플이 (2, 1, 3, 4)인 경우 이는

• {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}

와 같이 표현할 수 있습니다. 이때, 집합은 원소의 순서가 바뀌어도 상관없으므로

• {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}
• {{2, 1, 3, 4}, {2}, {2, 1, 3}, {2, 1}}
• {{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}}

는 모두 같은 튜플 (2, 1, 3, 4)를 나타냅니다.

특정 튜플을 표현하는 집합이 담긴 문자열 s가 매개변수로 주어질 때, s가 표현하는 튜플을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• s의 길이는 5 이상 1,000,000 이하입니다.
• s는 숫자와 '{', '}', ',' 로만 이루어져 있습니다.
• 숫자가 0으로 시작하는 경우는 없습니다.
• s는 항상 중복되는 원소가 없는 튜플을 올바르게 표현하고 있습니다.
• s가 표현하는 튜플의 원소는 1 이상 100,000 이하인 자연수입니다.
• return 하는 배열의 길이가 1 이상 500 이하인 경우만 입력으로 주어집니다

from itertools import chain

def solution(s):
    answer = [] # 결과값
    arr = []    # 문자를 배열로 변환

    k = []      # 숫자를 임시로 저장
    tmp = ""    # 숫자값


    # 문자 입력값을 배열로 변환
    for i in s:

        if i.isnumeric():   # 값이 숫자인지 확인하여 숫자값 저장
            tmp += i
        elif i == "," and tmp != "":    # 숫자값 배열에 입력
            k.append(int(tmp))
            tmp = ""
        elif i == "}"and tmp != "":     # } 값을 기준으로 집합 분리
            k.append(int(tmp))
            arr.append([len(k),k])      # 집합의 크기와 집합 저장

            tmp = ""
            k = []


    for x in sorted(arr):       # 집합의 크기로 정렬
        answer.append(x[1])
    answer = list(chain(*answer))   # 1차원 배열로 변형

    res = []
    for x in answer:
        if x not in res:
            res.append(x)

    return res

a = "{{2},{2,1},{2,1,3},{2,1,3,4}}"
print(solution(a))

문제 설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

• ()() 또는 (())() 는 올바른 괄호입니다.
• )()( 또는 (()( 는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항

• 문자열 s의 길이 : 100,000 이하의 자연수
• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

def solution(s):
    answer = True
    arr = list(str(s))
    chk = 0
    for x in arr:
        if x == "(":
            chk += 1
        else:
            chk -= 1
        if chk < 0:
            return False
    if chk != 0:
        return False

    return True

문제 리뷰

처음 문제를 보고 단순히 완전탐색을 활용하여 풀려고 했으나 안된다는 것을 알고 방향을 바꿨습니다. DP를 이용하는 것이 가장 좋아보여서 적용 시켜서 풀었습니다.

문제 설명

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

예를 들어

가 있다면 가장 큰 정사각형은

가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

제한사항

• 표(board)는 2차원 배열로 주어집니다.
• 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
• 표(board)의 열(column)의 크기 : 1,000 이하의 자연수
• 표(board)의 값은 1또는 0으로만 이루어져 있습니다.

def solution(board):

    if len(board[0]) < 2:
        if [1] in board:
            return 1
        else:
            return 0
    for i in range(1, len(board)):
        for j in range(1, len(board[0])):
            if board[i][j] >= 1:                
                board[i][j] = min(board[i-1][j], board[i][j-1], board[i-1][j-1]) + 1

    return max([num for row in board for num in row]) ** 2