알고리즘 4일차

(2021. 06. 17)

13번 - 영화감독숌 666

이 문제는 문제를 제대로 이해하는 것이 중요하고 브루트포스 개념을 적용하는 문제이다. 브루트포스 개념은 모든경우의 수를 전부 찾아서 조건에 맞는 사항을 찾아내는 개념 정도로 이해하면 될 것 같다. 666이 들어있는 수 중에 1번째가 666, 2번째가 1666 ~ 7번째는 7666이 아니라 6660 이라는점 이런 부분을 주의해서 정말 숫자의 크기를 전부 차례로 돌면서 666만 들어있으면 된다.

풀이

• While 문을 따라서 666 문자열이 있으면 n번째를 찾으면서 숫자는 하나씩 키우는 방식으로 검색한다.

N = int(input())
first = 666
while 1:
    if '666' in str(first):  # first 안에 666 들어있는지 확인
        N = N - 1  # 666이 있다면 N 을 하나씩 뺌
        if N == 0:  # 0 이되면 N 번째로 작은 종말 숫자라는 의미로 반복문 종료시킴
            break
    first = first + 1  # 근데 그 숫자에 666이 없으면 1을 더해가면서 first를 바꾸고 666 나올때까지 돌림 = 이렇게 모든 경우를 다따지는게 브루트 포스 개념
print(first)

• 포인트는 무한 반복과 n 번째를 잘 체크하는 것

14번 - 달팽이 vs 막대기

달팽이가 낮에는 올라가고 밤에는 미끄러지다가 막대기 정상에 도달하는 데 필요한 일수를 구하는 문제이다. n일이 걸린다고 했을 때, 앞으로 가는 거리는 A n, 미끄러지는 거리는 B (n-1) 이고 앞으로 간 거리에서 미끄러지는 거리가 총 막대기 길이가 되는 날짜를 구하면 된다.

import math
a, b, v = map(int, input().split())

day = math.ceil((v - b) / (a - b))

print(day)

• 1차 함수로 생각해서 풀면 간편하고 올림을 쓰는 이유는 낮에 4를 이동하는 달팽이가 1만큼 움직여도 막대기에 도달하는 경우가 있기 때문에 올림을 해주면 된다. 1만큼 움직인다고 해도 결국 그 1을 움직이기 위해 다음 날 하루라는 시간을 써야 정상을 갈 수 있기 때문이다.

15번 - 약수로 원래 숫자 찾아내기

• 약수의 갯수와 1과 자기 자신을 제외한 약수가 주어질 때, 그 약수들의 주인인 원래 숫자를 역으로 찾아내는 문제이다.

• 이 문제는 약수들을 다 곱한 갑을 제곱해 준 뒤 (약수의 갯수)제곱근을 해주면 된다. 왜냐하면 원래 약수는 앞 뒤로 곱하면 본래 수가 되는데 약수가 홀수로 있는 경우 중간에 혼자 있는 경우가 생기므로 제곱을 해준다.

• 또 해당 문제에서 순서대로 약수가 주어진 것이 아니기때문에 임의의 두 숫자만을 곱해서는 답을 찾을 수 없기 때문이다.

n = int(input())
divisor_list = list(map(int, input().split()))

number = 1
for num in divisor_list:
    number *= num

real_num = (number ** 2) ** (1/n)

print(round(real_num))  # 제곱근 계산하면 정확히 정수로 나누어 떨어지지 않는 경우 있어서 반올림해야함. 예로 16찾을때 4096의 세제곱근은 15.999999 임....

• 참고로 반올림을 해야하는 경우가 있어서 마지막에 라운드 함수를 사용하였는데, 제곱근 계산하면 정확히 정수로 나누어 떨어지지 않는 경우 있어서 반올림해야한다.
• ex) 16찾을때 4096의 세제곱근은 15.999999 이라는 점...

16번 - 최대공약수, 최소공배수

• 간단하게 입력받은 두 수의 약수를 모두 찾아서 최대공약수와 최소공배수를 구해도 되고, 유클리드 호제법을 사용해서 알고리즘을 짜도 된다.

• 유클리드 호제법은 두 숫자 중 작은 한 수(B)를 두 수를 나눈 나머지로 나누고(R1) B를 R1으로 나눈 나머지 R2로 다시 R1을 나누다가 나머지가 0이 될때의 앞전 나머지가 최대공약수라는 식이다.

• 이러한 방식으로 최대공약수를 찾은 뒤 두 수의 곱에서 최대공약수를 나누어 주면 최소공배수가 나온다.

a, b = map(int, input().split())

def gcd(a, b):  # 최대공약수
    r = a % b
    while True:
        if r != 0:
            new_b = r  # b에 1번 나머지를 대입해야해서 나머지가 바뀌기전에 잠깐 저장해 둠
            r = b % r  # 새롭게 위에서 나온 나머지 = new b를 나눠줄 2번째 나머지를 구함
            b = new_b  # b에 1번 나머지를 대입해주고 과정을 반복시킴
        else:
            result = b
            break
    return result


def lcm(a, b):  # 최소공배수는 두수의 곱 나누기 최대공약수
    return int(a * b / gcd(a, b))

print(gcd(a, b), lcm(a, b), sep='\n')

17번 - 호텔 방 배정하기

n번째 손님이 왔을 때, 문제에서 제시한 조건에 맞는 가장 가까운 방을 배정할 때 방의 호수를 출력하는 문제이다.

• 규칙 1 : 손님이 n번째 일때 n을 층수(H)로 나눈 나머지가 0이면 손님 방 층수는 H가 되고, 호수는 나눈 몫이 된다.

• 규칙 2 : 나머지가 0이 아닐 때, 층수는 나머지가 되고, 호수는 목의 + 1이 된다.

• 호수가 1의 자리인 경우 자리수를 맞춰야 하므로 zfill()이라는 메서드를 사용하여 자리를 맞춰준다.

    if len(x) == 1:
        result = y + x.zfill(2)  # 두자리로 맞춰달라는 뜻
    else:
        result = y + x

• ex) x = 2 일때 x.zfill(2) = 02

• 호수를 만들어 내기 위해 각각의 숫자들은 str로 형변환하여 더해준다.

18번 - 소수구하기

12번 문제와 같은 소수를 구하는 문제이므로 12번을 참고바람

19번 - 하노이의 탑

하노이의 탑 과정과 최소 이동 횟수를 출력하는 문제인데, 설명이 잘 되어 있는 블로그 링크를 남긴다. 하노이의 탑 알고리즘

• 해당 문제는 재귀함수의 개념을 이해하고 활용하기에 적합한 문제였다고 생각된다. n번째의 어쩌고 저쩌고의 과정을 거쳐 결과를 얻기 위해서, n-1번째의 어쩌고 저쩌고의 과정이 n번째와 무슨 상관이 있는지를 찾아내는 것이 재귀함수의 설계 1번 이라는 것을 배웠다.

• 시작점, 목적지, 경유지를 설계한 후 하노이가 옮겨지기 위해 필요한 과정을 알고리즘으로 정리, 설계한 뒤 그것을 그대로 코드로 옮기기만하면 문제가 풀리는 신기한 경험이었다.

풀이

1. n번째 탑이 1이면 시작점에서 목적지로 옮긴다.

2. 1이 아니라면 n-1을 시작점에서 경유지를 목적으로 목적지를 경유지로 삼아 옮긴다.

3. n번째 탑을 시작점에서 목적지로 옮긴다.

4. n-1 번째 탑을 경유지를 시작으로 시작지를 경유해서 목적지로 옮긴다.

• 이 과정을 n이 1이 될 때까지 반복하면 탑이 모두 옮겨진다.

def count(n):
    print(2 ** n - 1)  # 하노이의 탑 횟수 구하는 식

def move(start, to):  # N개의 탑을 시작점에서 목적지로 옮기는 함수
    print(f'{start} {to}')

def hanoi(N, start, to, via):  # 하노이 함수는 N개의 탑을 시작점에서 경유지를 거쳐 목적지로 가게하는 함수
    if N == 1:  # 옮겨야하는 것이 하나일 때가 오면
        move(start, to)  # 시작점에서 목적지로
    else:
        hanoi(N-1, start, via, to)  # 1이 아니면 그 앞 전 탑을 시작을 시작으로 경유지를 목적지로 삼고 목적지를 경유해서 다시 하노이 함수를 돌림
        move(start,to)  # 목적으로하는 n 번째 탑이 경유지로 모두 옮겨 지고나면 해당 탑을 시작에서 목적지로 옮김
        hanoi(N-1, via, to, start)  # 경유지에 남은 탑을 목적지로 옮기기 위해 시작점을 경유지로 두고 하노이 함수를 실행 시킴

n = int(input())
count(n)
hanoi(n, '1', '3', '2')

포인트

• 처음에 과정을 단순한 과정으로 설계하고 알고리즘화 한다.
• 시작, 목적, 경유의 단어와 코드 속 위치를 헷갈리지 말고 표현해낸다.
• 재귀함수를 쓸 상황과 단순히 함수를 짜야하는 부분의 경계를 확실히 파악한다.
  • 예를 들어 위에서는 n번째 탑 이외에 n-1부분이 뭉텅이로 옮겨져야하는 과정이다. 즉 n번째 탑 위에 모든 탑이 경유지로 옮겨지고, 다시 모든 탑이 목적지로 가야하는 상황 2가지가 해당된다.

20번 - 좌표 정렬하기

x,y에 관한 좌표가 주어지는데 x가 기준이 아닌 y를 기준으로 오름차순 정렬하는 법에 관한 문제이다.

풀이

• 이때 처음 람다라는 개념에 관해 학습할 수 있었다.

• 람다란 익명함수 정도의 느낌으로 이름을 정해주지 않고 사고의 흐름대로 함수(특정 조건)을 걸어서 사용하는 함수이다.

a.sort(key=lambda x: (x[1],x[0]))

• sort 함수는 정렬할 때 key 값을 가지게 되는데 지정해주지 않으면 일반적인 기준으로 오름차순, 내림차순을 할 수 있다.

• 여기서 key 값을 지정해주면 해당 조건에 맞추어 정렬해 준다.

• 그 조건이 람다 함수이고 x를 인덱스 1을 우선으로 정렬하라는 의미로 작성하였다.

포인트

• 2차원 배열 리스트 풀어서 출력하는 법

for x, y in a:  # for를 한번만 써도 리스트 안에 있는 리스트의 요소를 풀어서 나타낼 수 있다.
    print(x, y)

21번 - 나무 자르기

높이 h로 나무를 잘라서 위에 잘린 나무의 합이 원하는 합보다 크거나 같을 때 최대 높이 h를 구하는 문제이다.

풀이

• 이분탐색을 사용하여 높이를 구해야한다.

• 이분탐색에는 정렬된 리스트 혹은 범위, 시작점, 끝점, 중간값이 필요한다.

ea, m = map(int,input().split())
m_list = list(map(int,input().split()))

def m_search(m):
    start = 1  # 이건 1이든 0이든 상관없음 둘다 정답처리됨
    end = max(m_list)

    while start <= end:
        mid = (start + end) // 2
        m_sum = 0

        for tree in m_list:
            if tree > mid:
                m_sum += tree - mid
            else:
                m_sum += 0

        if m_sum >= m:  # 같아 졌을 때가 여기 붙어야 그때 start가 end를 넘어서면서 for문 탈출하고 값 반환 가능 
            start = mid + 1  # + 나무가 다 짝수인데 홀수 목표값이 있으면 정확히 안 나눠떨어지므로 같다는 조건이 아니라 end값 반환하는 방법으로 해야함
        else:
            end = mid - 1
    
    return end

print(m_search(m))

포인트

• 처음 예제를 대입했을 때 답이 나와서 백준에 넣으면 계속 답이 틀렸다고 나왔었다. 처음 코드에는 목표 길이와 잘린 나무 길이의 합이 같다면 중간 값을 반환하라고 썼었는데 그것에 반례가 있었기 때문이다.

• 원하는 길이가 홀수이고 주어진 나무가 모두 짝수인 경우에는 정확히 나누어 떨어지지 않기때문에 오답이 출력되었다.

• 따라서 같아질 때가 아니라 나무가 잘리는 높이는 즉 끝점과 같으므로 끝점을 반환해주는 식으로 바꾸었다.

• while을 탈출하는 조건이 시작점이 끝점보다 커지는 순간이므로, 길이의 합이 목표값과 같거나 많아지는 그 경계점에서 시작점이 끝점보다 커지므로 반복문을 탈출하고 높이를 출력하게 된다.

중간 점검

소감

이제 드디어 40문제 중에 절반을 풀었는데, 처음에는 엄청 어려웠지만 입력값을 받는게 익숙해진 순간부터는 그래도 풀만하다는 느낌을 받고 있다. 물론 내장함수를 다루는 것이 낯설고 어떤 함수를 어떻게 잘 사용하는지 아직 모르는 것이 너무 많기 때문에 매 문제마다 구글링을 해야하지만 문제를 접근하고 필요한 함수를 검색해서 찾아내는 검색실력이 조금 늘고 있는 것같다. 개념을 공부한다는 느낌으로 찾아보면서 개념을 학습하고 문제를 풀고 있다.

다짐

지금은 혼자 힘으로 하루종일 문제를 붙잡고 있는 것이 실력향상이라고 생각되지 않는 시점같다. 예로 수학을 처음 풀때는 개념을 익힐 수 있는 예제 문제를 많이 풀어봐야 다음에 응용 문제가 나왔을 때 해당 개념을 생각해내고 머릿속에서 꺼내와서 풀 수 있는 것이기 때문에 지금은 예제 문제를 푼다는 생각으로 개념을 학습하는 목적으로 풀기로 방향을 잡았다. 물론 그 과정에서 문제를 접근하고 풀어내는 것은 스스로의 힘으로 하고 있다. 장기적으로 보고 조급하거나 초조해 하지말고 공부를 해나가는 것이 가장 중요할 것 같다.

인생 원투데이 하다가 그만할 것 아니니깐 :)