사이트 바로가기 : 1977번 완전제곱수

문제

M과 N이 주어질 때 M이상 N이하의 자연수 중 완전제곱수인 것을 모두 골라 그 합을 구하고 그 중 최솟값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 완전제곱수는 64, 81, 100 이렇게 총 3개가 있으므로 그 합은 245가 되고 이 중 최솟값은 64가 된다.

첫째 줄에 M이, 둘째 줄에 N이 주어진다. M과 N은 10000이하의 자연수이며 M은 N보다 같거나 작다.

M이상 N이하의 자연수 중 완전제곱수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 완전제곱수가 없을 경우는 첫째 줄에 -1을 출력한다.

풀이

M = int(input())
N = int(input())

import math
min_num = math.ceil(M ** (1 / 2))
max_num = math.trunc(N ** (1 / 2))

answer = []
while True:
    if min_num > max_num:
        print(-1)
        break

    else:
        answer.append(min_num ** 2)
        min_num += 1
        if min_num > max_num:
            print(sum(answer))
            print(answer[0])
            break

Greedy 알고리즘

• Greedy 알고리즘이란?
  • 현재 상황에서 지금 당장 좋은 것만 고르는 방법
  • 순간 가장 좋아보이는 것을 선택하며, 현재 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
  • 문제에서 "가장 큰 순서대로" 또는 "가장 작은 순서대로"와 같은 기준을 제시해준다.

• 예제 1 ) 거스름돈 문제

1) 문제 N원을 거슬러 줘야할 때, 가장 큰 화폐 단위부터 돈을 거슬러 주어야 한다.

2) 풀이

n = 1260
count = 0

coin_types = [500, 100, 50, 10]

for c in coin_types:
    # 해당 동전으로 거슬러 줄 수 있는 개수 세기
    count += n // c
    n %= c

print(count)

• 주의점 (1) 문제를 처음 접했을 때 다양한 아이디어를 고려해야 한다. (2) 동전의 단위가 서로 배수 형태가 아니었다면 탐욕법을 사용하지 못했을 것 (만약 무작위로 주어졌다면 다이나믹 프로그래밍으로 해결할 수 있음)

실전예제 1. 큰 수의 법칙

• 특징

• 다양한 수로 이루어진 배열이 있을 때, 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙

• 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번 초과하여 더해질 수 없음

1) 문제 첫째 줄에 N, M, K의 자연수가 주어지며, 각 자연수는 공백으로 구분한다. 둘째 줄에 N개의 자연수가 주어진다. 공백으로 구분한다. 입력으로 주어지는 K는 항상 M보다 작거나 같다. 첫째 줄에 큰 수의 법칙에 따라 더해진 답을 출력한다.

2) 풀이 1

n, m, k = map(int, input().split())
data = list(map(int, input().split()))

data.sort()
first = data[n-1]
second = data[n-2]

result = 0

while True:
    for i in range(k):
        if m == 0:
            break
        result += first
        m -= 1
    if m == 0 :
        break
    result += second
    m -= 1

print(result)

3) 주의점 이 문제를 풀기 위해서는 반복되는 수열을 파악해야 한다. m의 크기가 커졌을 경우 시간 초과를 막기 위해 좀 더 효율적으로 해결법을 생각해야 한다.

4) 풀이 2

n, m, k = map(int, input().split())
data = list(map(int, input().split()))

data.sort()
first = data[n-1]
second = data[n-2]

# 가장 큰 수가 더해지는 횟수
count = int(m / (k+1)) * k
count += m % (k+1)

result = 0
# 가장 큰 수 더하기
result += count * first

# 중복되지 않게 두 번째로 큰 수 더하기
result += (m-count) * second

print(result)

실전예제 2. 숫자 카드 게임

1) 특징 -> 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 최종적으로 뽑는 게임 -> 각 행마다 카드 한장씩 뽑아서 그 중에서 가장 큰 수를 찾아라 -> N x M 형태로 카드가 놓여있다. -> 행을 먼저 선택하고 가장 낮은 카드를 뽑을 것을 고려하기

즉, 각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾는 것

2) 풀이

n, m = map(int, input().split())

result = 0
for i in range(n):
    data = list(map(int, input().split()))

    # 현재 들어온 줄에서 가장 작은 수를 찾기
    min_value = min(data)

    # 각각의 가장 작은 수 중에서 "가장 큰 수" 찾기
    result = max(result, min_value)

print(result)

실전예제 3. 1이 될 때 까지

1) 문제 어떠한 수 N이 1이 될 때 까지 2개의 과정 중 하나를 반복적으로 수행하려고 한다. 단 두번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.

• N에서 1을 뺀다.
• N을 K로 나눈다.

N, K가 주어질 때 N이 1이 될때까지 과정을 수행해야하는 최소 횟수를 구하라.

2) 풀이 1

n, k = map(int, input().split())
result = 0

while n >= k:
    # n이 k로 나누어떨어지지 않는다면 n -= 1
    while n % k != 0:
        n -= 1
        result += 1

    # k로 나누기
    n //= k
    result += 1

# 마지막으로 남은 수에 대하여 1씩 빼기
while n > 1:
    n -= 1
    result += 1

print(result)

3) 풀이 2

n, k = map(int, input().split())
result = 0

while True:
    target = (n // k) * k
    result += (n - target)
    n = target

    if n < k:
        break

    result += 1
    n //= k

# 남은 수에 대하여 1씩 빼기
result += (n - 1)
print(result)

Deep L-layer neural network

심층 신경망은 2가지 이상 숨겨진 층을 가지고 있는 모델이다. 신경망의 층을 세는 경우, 입력값의 층을 세지 않는다. 결과값 그대로의 층의 수를 센다.

Why deep representations?

신경망의 크기가 단순이 큰 것보다 깊고, 숨겨진 레이어가 많은 것이 중요하다.

음성인식 시스템을 만들 때 숨겨진 레이어가 많은 심층신경망같은 경우, 초기의 층에서 낮은 레벨의 간단한 특성을 배울 수 있게 만들고, 그 후의 층에서는 간단한 특성을 합칠 수 있도록 하고, 좀 더 복잡한 단어나 문장과 발음을 감지할 수 있도록 만든다.

Forward and Backward Propagation

Forward Propagation과 Backwark Propagation에 대한 개념 정리이다. 강의를 해주시는 Andrew Ng의 필기를 캡쳐한 것이다.

Parameters vs HyperParameters

• HyperParameters

  learning rate iteration(기울기 강하에 대한 iteration) 숨겨진 레이어의 개수 L activation functions 등등 Hyperparameter의 여러 종류가 있다.

좋은 Hyperparameter의 값을 알아내는 것은 매우 어렵다. 따라서 여러번 반복해서 시도해봐야한다. 오늘날의 하이퍼파라미터 최적값으로 튜닝한다하더라도, 그 값은 계속해서 변할 것이다. 그렇기때문에 다른 값들을 시도해보고, cross-validation set와 같은 것을 통해 평가하여 가장 잘 맞는 값을 찾아나가야한다.

마무리

4주차 강의를 모두 수강했다. 처음에 잘못 이해한 것 같은데, 다른 강의를 통해 CNN, RNN을 배우는 것이었고, 해당 강의는 신경망 모형에 대한 수학적인 강의, 이론적인 강의 내용이었다. 영어로 수학 강의를,, 그것도 딥러닝 강의를 듣는 것은 쉽지 않았다. 하지만 설명을 잘해주시고, 온라인 강의 특성상 멈춰가며 이해하고 다음 강의를 들을 수 있어서 나의 속도로 공부를 할 수 있었다. 다음에도 다른 강의를 수강할 것이다.

Neural Networks Overview

신경망은 sigmoid unit을 쌓아 합쳐서 구성할 수 있다.

Neural Networks Representation

1) Input Layer x1, x2, x3

2) Hidden Layer 동그라미 4개의 unit

3) Output Layer 동그라미 1개의 unit, y hat값을 생성하는 역할

4) Activation 입력층이 x값을 숨겨친 층으로 전달하고, 또다른 숨겨진 층으로 전달한다. 다음 층에서 숨겨진 층은 또다른 activation을 생성한다.

Computing a Neural Network's Output

Hidden Layer는 unit안에 2가지 절차로 이루어진다. 첫번째는 Z값을 구하고, 두번째는 Z의 시그모이드 함수로 activation을 산출한다. Hidden Layer를 각각 계산하는 것은 비효율적이니 벡터화해서 matrix로 계산을 할 수 있다.

Activation functions

• 활성함수 그래프

sigmoid와 tanh

신경망을 생성할 때, 1) 은닉층에서 어떤 활성함수를 사용할 것인가 2) 신경망의 출력 유닛들은 어떻게 할것인가 두 가지를 정할 수 있다.

tanh함수(hyperbolic tangent function)는 sigmoid함수보다 항상 더 좋은 성능을 발휘한다. 왜냐하면 값이 항상 +1에서 -1 사이에 위치하면서, 활성함수의 평균값이 hidden layer에서 계산되고, 이 값이 0에 가깝기 때문이다.

반면, 출력층일 때는 tanh함수가 성능이 떨어진다. y hat은 0과 1사이의 출력값을 가지기 때문이다.

이진분류인 경우 sigmoid 활성함수를 사용한다. 이런 경우에는 출력층에 sigmoid함수를 사용하게 된다.

sigmoid, tanh단점

Z가 매우 크거나 매우 작을 때, gradient의 값이 매우 작은 값이 된다는 단점이 있다. 이런 경우는 함수의 기울기가 거의 0이 된다. 그래서 gradient descent 알고리즘을 느리게 만든다.

ReLU 정리

공식은 a=max(0,z)이다. z가 양수이면 기울기는 1이고, 음수이면 기울기는 0이다. 따라서 z가 0일때, 기울기를 0 또는 1로 취급할 수 있다. 따라서 활성함수로 사용하기에 아주 적합하다. 어떤 것을 사용해야할지 잘 모른다면 ReLU를 추천한다. 학습 속도가 아주 빠를 것이다.

ReLU 단점

z가 음수일 때 미분값이 0이라는 것이다. 이를 보완하는 leaky ReLU가 있는데, 이것은 z가 음수일 때 약간의 기울기를 가져서 0의 값을 가지지 않는 함수이다.

Why do you need non-linear activation functions?

기존 선형 분류기라는 한계로 인해 XOR과 같은 non-linear한 문제를 해결할 수 없었다. 입력값에 대한 출력값이 linear하게 나오지 않았기 때문에 hidden layer에 activation function을 도입해서 선형분류기를 비선형 시스템으로 만들 수 있었다.

즉, Multiple Layer Perceptron은 활성 함수를 이용한 non-linear시스템을 여러개의 층으로 쌓는 개념이다.

Random Initialization

• symmetry breaking 문제 신경망에서 weight를 임의로 초기화하는 것은 중요하다. 하지만 모든 weight를 0으로 변경하고 기울기 강하를 적용하면 작동하지 않는다. 모두 0으로 초기화를 한다면 hidden layer에 있는 모든 activation이 똑같은 함수를 산출하기 때문이다.

• symmetry breaking 문제 해결법 이에 대한 해결책은 parameter를 임의로 초기화하는 것이다. w1=np.random.randn으로 설정하면 gaussian random variable이 생성된다. 보통 weight를 초기화할 때 임의의 작은 값을 사용한다. 왜냐하면 tanh나 sigmoid 등 함수가 결과값 층에 있는 경우, weight가 너무 크면 z의 값이 매우 크거나 매우 작게 된다. 그러면 learning 속도를 늦추게 된다.

Gradient Descent

• 복습 비용함수는 파라미터 W, b가 전체 training set에서 얼마나 잘 작동하는지 측정하는 함수

• gradient descent J(W,b)를 최소화하는 값을 찾을 때, training set에서 파라미터가 얼마나 잘 작동하는지 알 수 있다. 로지스틱 회귀분석에서 parameter의 적합한 값을 찾으려면 W, b를 최초값으로 초기화해야한다. 일반적으로 0으로 초기화시키기도 하지만, 무직위수로 초기화 시키는 방법도 있다.

  기울기 강하를 할 때 처음 시작점에서 시작해서 가장 기울기가 높은 내리막길 방향으로 내려가게된다. 이를 반복해서 최적점에 도달하게 된다. 비용함수 J인 경우, 어느 방향으로 이동할지 여부를 알아내야한다. 위의 설명은 파라미터가 W 한가지일 경우 gradient descent이다.

  LR의 경우는 J(W,b)로, W의 값과 b의 값을 계속 업데이트 해주면서 최적값을 찾아가는 과정인 것이다.

Computation graph

신경망의 결과값을 계산하고, 순전파 또는 역전파를 통해 기울기나 derivative를 계산한다. 즉, 일반적으로 생각하는 순 방향으로 계산하는 것은 computation graph방식인 것이다.

Python and Vectorization

Vectorization

• vectorization 코딩에서 for loop를 제거하는 기술이다. 좀 더 빠른 연산을 위해 vectorization을 도입한 것이다. LR에서 기울기 강하의 single iteration을 도입하여 vectorize한다.

Broadcasting in Python

다른 크기의 행렬이 있을 때, 파이썬이 행렬의 크기를 맞춰서 연산을 해준다. A: (m x n) 행렬 B: (1 x n) 행렬 또는 (m x 1) 행렬 연산 모두 가능

Binary Classification

로지스틱 회귀를 통해 아이디어를 전달한다. 고양이 사진으로 예를 들어본다. 이미지를 인식하기 위해서 고양이일때는 1, 고양이가 아닐 때는 0으로 레이블을 출력하려고 한다. 이미지를 저장하기 위해서는 R,G,B 채널에 대응하는 세 개로 분리된 행렬을 사용한다. RGB에 해당하는 각각의 특징 벡터가 있고, 만약 input이미지가 64x64픽셀로 된 이미지라면 이미지의 차원은 64x64x3이 될 것이다.

Logistic Regression

지도학습 문제에서 결과값 레이블 y가 0,1인 경우 사용되는 알고리즘이다. 즉, 이진 분류 문제의 경우이다. 선형회귀에서 사용하는 방법대로 y hat=tr(W)X+b을 사용할 수도 있지만, y hat이 0과 1사이에 있어야하므로 적합한 방식이 아니다. 그래서 Z=tr(W)x+b에 sigmoid함수를 적용한다. Z가 매우 큰 경우 Z의 시그모이드는 1에 가까운 값이 되고, Z가 매우 작으면 0에 가까운 값이 된다. 그러므로 로지스틱 회귀분석을 도입하는 경우에는 y hat이 Y=1이 되는 값을 찾는 것이 중요하다.

Logistic Regression Cost Function

• 비용함수 loss함수는 true label y를 값는 경우, 얼마나 정확히 y hat 결과를 갖는지 정의할 때 사용한다.

• Loss Function 표현이 잘 될지는 모르겠지만 작성해본다. L(y hat, y)= -(ylogyhat + (1-y)log(1-y hat)) 이 때, y=1인 경우 L(y hat, y)= -logyhat이 된다. 즉, y가 1인 경우 y hat은 1에 가까운 수가 좋은 것이다. 반대로 y=0인 경우 y hat은 0에 가까운 수가 좋은 것이다.

강의를 제대로 이해한 것인지는 모르겠는데, 자코비언 함수를 통해 로지스틱 회귀의 전체 비용함수를 나타내는 것인데, 그 parameter는 loss function의 parameter임(W, B). 그래서 이를 줄이는 것이 전체 모델의 비용 J를 줄이게 된다.

What is a neural networks?

• Deep learning 신경망 학습을 일컫는 말이다. 집값을 예측하는 예제로 설명한다. 만약, 가격 price를 예측하는 데 4가지 x인 size, bedroom, address, school quality가 있다고 가정한다. 이 x값들을 신경망의 input으로 지정하고, y값인 가격을 예측하는 것이다. 아래 그림을 보면 unit이라는 동그라미가 있는데, 이건 unit이라고 부른다. unit은 4가지의 특성을 담고 있으며 자유롭게 선택 가능하다. (아마 어떤 기준으로 선택되는지는 알기 힘들 것이다. 복잡한 데이터에서도 좋은 결과를 보여주지만, inference를 제공하기 힘든 것이 딥러닝의 단점이기 때문이다.)

Supervised Learning with Neural Networks

• 예시 1) Online Advertising 고객 정보(input)를 바탕으로 광고 클릭 여부(output) 2) Photo tagging 이미지(input)를 바탕으로 약 1000가지의 라벨링 가능(output) 3) Machine translation 영어(input)를 중국어(output)로 번역

• sequence data 시퀀스 데이터는 시간적인 요소가 있음. 일차원적인 time series 또는 시간적인 sequence에 의해 자연스럽게 표현된다. 언어 또한 sequence 데이터를 통해 자연스럽게 표현된다. 영어, 중국어와 같은 경우 단어들은 하나씩 나열되는 특성이 있기 때문이다. 시퀀스 데이터는 RNN(Recurrent Neural Network)을 가장 많이 사용한다. RNN은 시간적인 요소를 담고 있는 일차원적인 데이터를 다루는 데에 좋다.

Why is Deep Learning taking off?

• 딥러닝이 뜨는 이유는? 딥러닝 네트워크 개념 자체는 수십년동안 존재해왔다고 한다. 데이터의 양이 방대해짐에 따라서 딥러닝의 performance가 향상되고 있다. 데이터가 적을 때는 SVM, Logistic Regression의 performance는 딥러닝의 performance와 차이가 없다. 하지만 데이터의 양이 점점 커질수록 그 차이는 매우 크다. 이러한 이유로 딥러닝이 뜨는 것이다. 하지만 데이터의 수가 그렇게 크지 않다면, 기존 머신러닝 방법이 더욱 효과적일 것임.

• large-sized Deep learning의 조건 1) 큰 신경망을 학습할 환경 구축 2) 데이터가 아주 많아야함

신경망의 발전이 빠르게 이루어질 수 있었던 것은 네트워크의 변화가 빠르게 이루어졌기 때문이다. sigmoid함수가 ReLu함수로 대체되었기 때문에 빠르게 발전할 수 있었다.

• Sigmoid 함수 시그모이드 함수의 문제점은 머신러닝에 적용시키는 경우, 함수의 기울기가 거의 0에 가까운 값이 되므로 학습 속도가 매우 느려진다. gradient descent(기울기 강하)를 도입하는 경우 기울기가 0이면 개체가 매우 느린 속도로 변하기 때문이다. 또, 함수의 기울기가 0이 되면 gradient vanising문제가 발생한다. 0을 곱하면 0이 되기 때문에 다음 layer로 전파되지 않아 학습이 되지 않는 큰 문제가 발생한다.

• ReLu 함수 기울기는 모든 양수에 대해서 1이기 때문에 기울기가 0으로 줄어드는 확률이 감소된다.

1주차 마무리

총 5개의 짧은 동영상이었다. 7분, 8분, 10분, 2분, 1분으로 구성되었다. 1주차라서 가볍게 딥러닝이 왜 핫한지, 신경망이 어떤 것인지 설명을 한 것 같다. 영어라서 쉽게 알아들을 수 없어서 중간중간 많이 멈춰야했다. 그래도 한글 대본이 있어서 많은 도움을 받을 수 있었다. 마지막으로 연습문제 10문제를 풀고 1주차를 마무리하겠다.

시작하기 전

• 강좌명 Neural Networks and Deep Learning by deeplearning.ai

• 강좌 선택 이유 코세라에서 인기있는 강의였고, 한글 자막이 있기 때문이다.

• 강좌 수강 계기 딥러닝에 대해서는 한 번 수업을 들은 적이 있다. 하지만 기억에 잘 남지 않는다. 이해를 제대로 하지 못했단 의미인것 같아서 강좌를 한번 더 수강하고 싶었다. 교재를 통해 개인적으로 독학을 하려 했으나, 손에 잡히지 않았다. 그래서 강좌를 선택하게 되었다.

과거에 어떤 분이 마지막 만남때 했던 말이 있었다. 코세라 강의로 AI, 머신러닝 공부를 많이 한다. 너희들도 했으면 좋겠다. 실천에 옮길지는 모르겠지만,,,이라고 하셨다.

그 때의 기억이 강렬하게 남아서 코세라 강의를 들어야겠다고 다짐했고, 실천에 옮겼다.

1주차

• 과정

1. Neural Networks and Deep Learning
2. Improving Deep Neural Networks : Hyperparameter tuning, Regularization and Optimization
3. Structuring your Machine Learning project
4. Convolutional Neural Networks
5. Natural Language Processing : Building sequence models

사이트 바로 가기 : 프로그래머스-폰켓몬

문제

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. 홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.

1. 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택
2. 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택
3. 첫 번째(3번), 네 번째(3번) 폰켓몬을 선택
4. 두 번째(1번), 세 번째(2번) 폰켓몬을 선택
5. 두 번째(1번), 네 번째(3번) 폰켓몬을 선택
6. 세 번째(2번), 네 번째(3번) 폰켓몬을 선택

이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다. 당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

풀이

def solution(nums):
    answer=0
    N=len(nums)//2
    ponketmon=list(set(nums))
    if len(ponketmon)>N:
        answer=N
    else:
        answer=len(ponketmon)
    return answer

마무리

코드를 작성하다보면 set을 정말 유용하게 잘 쓰는 것 같다.

사이트 바로 가기 : 이진 변환 반복하기

문제

문제 설명 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 함수를 완성해주세요.

풀이

def solution(s):
    answer=[0,0]
    cnt, zero=0,0
    while True:
        if s=="1":
            break
        else:
            zero+=s.count("0")
            s= format(len(s.replace("0","")),"b")
            cnt+=1
    answer[0]=cnt
    answer[1]=zero

    return answer

마무리

프로그래머스에 접속해서 새롭게 업데이트된듯한 문제를 보았다. 프로그래머스에 2단계 문제도 손쉽게 전부 다 푸는 날이 오길 바라며,,

사이트 바로가기 : 1546번 평균

문제

세준이는 기말고사를 망쳤다. 세준이는 점수를 조작해서 집에 가져가기로 했다. 일단 세준이는 자기 점수 중에 최댓값을 골랐다. 이 값을 M이라고 한다. 그리고 나서 모든 점수를 점수/M*100으로 고쳤다.

예를 들어, 세준이의 최고점이 70이고, 수학점수가 50이었으면 수학점수는 50/70*100이 되어 71.43점이 된다.

세준이의 성적을 위의 방법대로 새로 계산했을 때, 새로운 평균을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 같다. 둘째 줄에 세준이의 현재 성적이 주어진다. 이 값은 100보다 작거나 같은 음이 아닌 정수이고, 적어도 하나의 값은 0보다 크다.

출력

첫째 줄에 새로운 평균을 출력한다. 실제 정답과 출력값의 절대오차 또는 상대오차가 10-2 이하이면 정답이다.

풀이

N=int(input())
score=list(map(int, input().split()))
print(sum([i/max(score)*100 for i in score])/len(score))

사이트 바로가기 : 1453번 피시방 알바

문제

세준이는 피시방에서 아르바이트를 한다. 세준이의 피시방에는 1번부터 100번까지 컴퓨터가 있다.

들어오는 손님은 모두 자기가 앉고 싶은 자리에만 앉고싶어한다. 따라서 들어오면서 번호를 말한다. 만약에 그 자리에 사람이 없으면 그 손님은 그 자리에 앉아서 컴퓨터를 할 수 있고, 사람이 있다면 거절당한다.

거절당하는 사람의 수를 출력하는 프로그램을 작성하시오. 자리는 맨 처음에 모두 비어있고, 어떤 사람이 자리에 앉으면 자리를 비우는 일은 없다.

입력

첫째 줄에 손님의 수 N이 주어진다. N은 100보다 작거나 같다. 둘째 줄에 손님이 들어오는 순서대로 각 손님이 앉고 싶어하는 자리가 입력으로 주어진다.

풀이

N=int(input())
seats=list(map(int, input().split()))
s=len(list(set(seats)))
print(N-s)

사이트 바로가기 : 1312번 소수

문제

피제수(분자) A와 제수(분모) B가 있다. 두 수를 나누었을 때, 소숫점 아래 N번째 자리수를 구하려고 한다. 예를 들어, A=3, B=4, N=1이라면, A÷B=0.75 이므로 출력 값은 7이 된다.

입력

첫 번째 줄에 A와 B(1≤A, B≤100,000), N(1≤N≤1,000,000)이 공백을 경계로 주어진다.

출력

A÷B를 했을 때, 소숫점 아래 N번째 수를 출력한다.

풀이

A,B,N=map(int, input().split())
A%=B
for i in range(N-1):
    A=(A*10) % B

print((A*10) // B)

• 처음 접근했던 2가지 방법은 런타임 에러를 표시했다.

  # 런타임 에러 1
  A,B,N=map(int, input().split())
  try:
    print(int(str(A/B)[N+1]))
  except:
    print(0)
  

```python
# 런타임 에러 2
A,B,N=map(int, input().split())
print(int(((A/B)*(10**N))%10))

마무리

이번 문제는 많이 오래 걸렸다. 수학적인 부분을 생각하느라.... 런타임에러를 두번 겪고나서 수학적으로 접근하느라 오래걸렸다. 나에겐 좀 어려운 문제인걸루,,

사이트 바로가기 : 1357번 뒤집힌 덧셈

문제

어떤 수 X가 주어졌을 때, X의 모든 자리수가 역순이 된 수를 얻을 수 있다. Rev(X)를 X의 모든 자리수를 역순으로 만드는 함수라고 하자. 예를 들어, X=123일 때, Rev(X) = 321이다. 그리고, X=100일 때, Rev(X) = 1이다.

두 양의 정수 X와 Y가 주어졌을 때, Rev(Rev(X) + Rev(Y))를 구하는 프로그램을 작성하시오

입력

첫째 줄에 수 X와 Y가 주어진다. X와 Y는 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

풀이

x,y=input().split()
revx=x[::-1]
revy=y[::-1]
print(int(str(int(revx)+int(revy))[::-1]))

마무리

역순 인덱싱을 기억하고 있어서 쉽게 풀 수 있었다. Python의 장점인 것 같다.

사이트 바로가기 : 1356번 유진수

문제

유진수는 어떤 수를 10진수로 표현한 뒤 그 수를 두 부분으로 나눴을 때, 앞부분 자리수의 곱과 뒷부분 자리수의 곱이 같을 때를 말한다.

예를 들어, 1221은 유진수이다. 12와 21로 나눴을 때, 앞부분 자리수의 곱 1x2는 뒷부분 자리수의 곱 2x1과 같기 때문이다. 1236도 마찬가지로 유진수이다. 하지만, 1234는 아니다. 수를 나눌 때 항상 연속된 자리수를 나눠야하고, 각 부분에 적어도 한자리는 있어야 한다.

예를 들어, 12345는 총 4가지 방법으로 나눌 수 있다. 1-2345, 12-345, 123-45, 1234-5 어떤 수 N이 주어질 때, 이 수가 유진수인지 아닌지 구하는 프로그램을 작성하시오.

입력과 출력

• 입력 첫째 줄에 수 N이 주어진다. 이 수는 2,147,483,647보다작거나 같은 자연수이다.

• 출력 첫째 줄에 N이 유진수이면 YES, 아니면 NO를 출력한다.

풀이

from functools import reduce
N=input()
length=len(N)


check='NO'
for i in range(1,length):
    one=[int(a) for a in N[:i]]
    two=[int(b) for b in N[i:]]

    a=reduce(lambda x, y: x*y, one)
    b=reduce(lambda x, y: x*y, two)

    if a==b:
        check="YES"
        break
print(check)

마무리

import를 쓰고 싶지 않았는데 결국 써버렸다. 리스트 안에서 곱셈을 처리해주는 함수를 만들고, 이를 어떻게 적용할지 생각하는데 방법이 잘 떠오르지 않았다.

Plotly란?

Plotly는 Python으로 시각화를 할 수 있는 무료 오픈소스 그래프 라이브러리이다. Plotly JavaScript library기반으로 Jupyter notebooks에 표현하거나, Dash를 사용해서 분석 어플리케이션을 구축할 수 있다. (Dash부분은 나중에 더 알아보도록 하겠다.) Plotly설명서를 참고하여 시각화 라이브러리를 Learning by Doing 해볼 것이다.

장점

1. 코드의 간편함 matplotlib보다 코드 자체가 가볍다. 물론 seaborn 또한 matplotlib보다는 단순하다. 아직 plotly를 접한지 며칠 되지 않았기 때문에 받아들이기에 편한 순서로는 seaborn > plotly > matplotlib이다.

2. 색감 개인적인 취향으로는 seaborn보다 plotly의 시각화가 더욱 보기가 좋다. 하지만, seaborn에 만족한다면 굳이 plotly를 사용할 필요는 없을 것 같다.

설치

Windows에서 Jupyter Notebooks를 사용해서 실습을 진행하려고 한다. 2021-01-01 기준으로 plotly 버전은 4.14.1이다. 주피터노트북 버전 5.3이상, ipywidgets 버전 7.2이상이면 작동된다.

!pip install plotly==4.14.1

업그레이드가 필요할 경우는 다른 라이브러리 업그레이드 방식과 동일하게 입력해주면 된다.

!pip install plotly --upgrade

실습데이터

데이터

서울시 업종별 내외국인 신한카드 매출데이터 서울시 빅데이터 캠퍼스에서 찾은 신한카드 매출데이터이다. 해당 데이터를 활용해 가벼운 시각화를 진행해볼 예정이다.

• 지역 : 서울 전역

• 기간 : 2017.01 ~ 2020.10

• 데이터 설명 서울시 내에 위치한 가맹점의 카드이용 건을 대상으로 내국인은 개인카드(신용카드/체크카드) 및 법인카드 이용 내역을 포함하고, 외국인은 외국인의 카드이용 내역을 포함합니다. 단 “내국인(집계구) 유입지별”은 개인카드(신용카드/체크카드) 이용내역만 포함합니다.

  내국인의 매출금액과 매출건수는 블록 단위로 일/요일/시간대 별, 집계구 단위 일/성/연령 별, 일/유입지 별 63개 업종에 대하여, 외국인의 매출금액과 매출건수는 블록 단위로 일/시간대 별, 일/국가 별 56개 업종에 대하여 집계하였습니다.

  내국인 업종에서는 온라인거래, 세금공과금, 통신요금, 보험료, 대학등록금 등을 제외하였고, 외국인 업종에서는 온라인거래, 세금공과금, 통신요금, 보험료, 대학등록금, 가정생활서비스, 교육/학원 등을 제외하였습니다.

  빅데이터 캠퍼스에서 제공하는 본 데이터는 다른 기관에서 제공하는 데이터 보다 공간단위가 더 작은 집계구와 블록 단위로 제공하고 있습니다.

plots

Plotly 사용법 설명서를 참고하여 차트들을 활용해볼 것이다. 아직 구체적으로 어떤 시각화를 하면 좋을지는 생각하지 못했는데, 가볍게 EDA하는 느낌으로 실습해볼 예정이다.

사이트 바로가기 : 1252번 이진수 덧셈

문제

두 개의 이진수를 입력받아 이를 더하는 프로그램을 작성하시오.

입력

첫째 줄에 두 개의 이진수가 빈 칸을 사이에 두고 주어진다. 각 이진수는 1 또는 0으로만 이루어져 있으며, 0으로 시작할 수도 있다. 또한 각 이진수의 길이는 80을 넘지 않는다.

풀이

a,b= input().split()

a=int('0b'+a,2) b=int('0b'+b,2) c= format(a+b,'b') print(c)

사이트 바로가기 : 1259번 팰린드롬수

문제

어떤 단어를 뒤에서부터 읽어도 똑같다면 그 단어를 팰린드롬이라고 한다. 'radar', 'sees'는 팰린드롬이다.

수도 팰린드롬으로 취급할 수 있다. 수의 숫자들을 뒤에서부터 읽어도 같다면 그 수는 팰린드롬수다. 121, 12421 등은 팰린드롬수다. 123, 1231은 뒤에서부터 읽으면 다르므로 팰린드롬수가 아니다. 또한 10도 팰린드롬수가 아닌데, 앞에 무의미한 0이 올 수 있다면 010이 되어 팰린드롬수로 취급할 수도 있지만, 특별히 이번 문제에서는 무의미한 0이 앞에 올 수 없다고 하자.

풀이

while True:
    word = input()
    palindrom = word[::-1]
    if word=='0':
        break

    if word==palindrom:
        print('yes')
    else:
        print('no')

마무리

무의미한 0이 앞에 올 수 있는 경우라면 어떻게 풀지 생각해봐야겠다.

사이트 바로가기 : 1157번 단어공부

문제

알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다.

풀이

word=input()
word=word.upper()
wordlist=list(set(word))
cnt=[]
for w in wordlist:
    cnt.append(word.count(w))

m=max(cnt)
if cnt.count(m)==1:
    print(wordlist[cnt.index(m)])
else:
    print("?")

마무리

테스트케이스를 봤을 때, 결과값이 모두 대문자로 나왔기 때문에 모두 대문자로 바꿔서 풀었다. 문제가 짧았고, 비슷한 문제를 풀어본 경험이 있었기에 빠르게 풀 수 있었다. 좋은 코드인지는 모르겠지만...

부족한 코딩 실력을 조금이나마 채우기 위해 문제를 많이 접하고, 풀어보는 것이 좋겠다고 생각했다. 코딩테스트 대비용이기도 하고 손이나 머리를 조금씩 굴리기 위한 용도로 문제를 풀기로 했다. 어떻게든 도움이 될 것이다.

solved.ac

solved.ac란?

solved.ac는 백준 사이트에 있는 문제들에 태그와 난이도를 붙이는 커뮤니티 프로젝트이다. 현재는 약 1만개의 문제에 난이도 정보를 제공하고 있다고 한다.

난이도 정보

난이도는 플래티넘 이상인 유저들만 난이도를 평가할 수 있다. 레벨은 Bronze, Silver, Gold, Platinum, Diamond, Ruby로 구성되어있다. 각 레벨은 5단계로 또 구분지어진다. 숫자가 작을수록 높은 단계이다. 패기있게 브론즈 1단계를 선택했다.

더하기 사이클 - Python

• 사이트 바로가기 : 더하기 사이클

  문제

  0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, 주어진 수의 가장 오른쪽 자리 수와 앞에서 구한 합의 가장 오른쪽 자리 수를 이어 붙이면 새로운 수를 만들 수 있다. 다음 예를 보자.

26부터 시작한다. 2+6 = 8이다. 새로운 수는 68이다. 6+8 = 14이다. 새로운 수는 84이다. 8+4 = 12이다. 새로운 수는 42이다. 4+2 = 6이다. 새로운 수는 26이다.

위의 예는 4번만에 원래 수로 돌아올 수 있다. 따라서 26의 사이클의 길이는 4이다.

N이 주어졌을 때, N의 사이클의 길이를 구하는 프로그램을 작성하시오.

풀이

N=int(input())
cnt=0
start=N

while True:
    ten=N//10
    one=N%10
    if (ten+one)<10:
        new=int(str(one)+str(ten+one))
        cnt+=1
    elif (ten+one)>=10:
        new=int(str(one)+str((ten+one)%10))
        cnt+=1

    if start==new:
        print(cnt)
        break
    else:
        N=new

마무리

실력이 좋은 편이 아니기 때문에 문제를 푸는데 시간이 오래 걸렸다. 처음엔 바로 문자열로 접근해서 문제를 풀다보니 무한루프에 빠졌었다. 알고보니 N<10일 경우에 대한 조건을 잘못 이해해서 코드를 잘못 작성했던 것이었다. 그래서 처음부터 다시 생각해서 10의 자리의 수와 1의 자리의수 2가지로 나누어 접근하는 방법을 생각했다.

늘 하는 실수인 것 같다. 처음부터 문제에 대한 이해를 잘 하고, 손을 움직이는 습관을 들여야겠다.