WEEK01 알고리즘 TIL(3월15일 토요일)

https://github.com/prtky/JungleBackjoon
해당링크를 들어가면 코드와 주석만 보실수 있습니다.

14번 문제(2577) 숫자의 개수

세 개의 자연수 A, B, C가 주어질 때 A × B × C를 계산한 결과에 0부터 9까지 각각의 숫자가 몇 번씩 쓰였는지를 구하는 프로그램을 작성하는 것이다. 일단 3자리를 받을 수 있는 인풋을 받고 곱한다. 그럼 값이 나올 것인데 나온 값을 쪼개서 리스트화한다.(len쓰면 될 것 같다) 리스트에서 0~9까지 추출해서 갯수를 센다.

A = int(input())
B = int(input())
C = int(input())
ABC = A * B * C

x = []
for i in str(ABC):
    x.append(i)
    
cnt0 = x.count("0")
print(cnt0)
.
.
.

원래는 각 숫자를 카운트하는 부분을 일일이 반복 했었다. 너무 단순 무식하게 써서 for문으로 바꿀 방법을 찾고 있다. for문은 1부터 9까지 반복하는데, 그걸 str형식이랑 비교해서 추출할 수 있는지 몰랐다.
인터넷에서 글 찾고, 고민 고민하다가 GPT한테 물어 봤는데 반복하는 i를 str으로 변환해서 카운트하면 되는 간단한 문제였다...

for i in range(10):
    print(x.count(str(i)))

노션에 정리된 내용을 기반으로 어제 15일의 TIL을 벨로그에 작성했다.

15번 문제(15596) 정수 N개의 합

정수 n개가 주어졌을 때, n개의 합을 구하는 함수를 작성해야한다. 파이썬의 경우 다음과 같다.

• Python 2, Python 3, PyPy, PyPy3: def solve(a: list) -> int
  • a: 합을 구해야 하는 정수 n개가 저장되어 있는 리스트 (0 ≤ a[i] ≤ 1,000,000, 1 ≤ n ≤ 3,000,000)
  • 리턴값: a에 포함되어 있는 정수 n개의 합 (정수)

sum(a)를 쓰면 합을 구한다. 파이썬에서는 타입 힌트를 줄 수 있다고 한다. 리스트 형을 int 형으로 내보내야하니, 다음과 같이 써서 리스트인 a를 리턴으로 int형이 온다고 타입 힌트를 주면 된다.

def solve(a: list) -> int:
    return sum(a)

# 문제엔 형태가 정해져 있어서 이렇게 썻지만 간단하게 쓸수 있다.
def solve(a):
    return sum(a)

맨첨엔 좀 어렵게 풀었는데, sum(a)만 알면 할 수 있는 쉬운 문제였다.

16번 문제(11654) 아스키 코드

물론 이 아스키 코드를 매칭시켜서 도서관처럼 입력된 데이터 중 아키코드 값을 불러오는 형식을 쓸수도 있다. 그러면 굉장히 데이터 양도 많아지고 코딩하기 쉽지 않다. 파이썬에서는 ord() 함수를 쓰면 아스키 코드를 추출할 수 있다. ord(인풋값)의 형태가 된다. 여기서 ord는 ordinal position(문자의 순서 위치 값)의 약자이다. 아스키 코드로 값을 변환해준다.

i = input()
ASCIICODE = ord(i)
print(ASCIICODE)

만약, 반대로 아스키코드를 문자나 순자로 바꾸고 싶으면 ord자리에 chr을 쓴다음 print(f"{}")로 포맷팅된 문자열을 연결하면 된다. 여기서 새롭게 알게된 사실인데 문자열로 되어 있는 함수를 프린트하려면 print(f"{함수명}")을 쓴다는 사실이다.

17번 문제(2675) 문자열 반복

문자열 S를 입력받은 후에, 각 문자를 R번 반복해 새 문자열 P를 만든 후 출력하는 프로그램을 작성하시오. 즉, 첫 번째 문자를 R번 반복하고, 두 번째 문자를 R번 반복하는 식으로 P를 만들면 된다. S에는 QR Code "alphanumeric" 문자만 들어있다. QR Code "alphanumeric" 문자는 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ\$%*+-./: 이다.
일단 케스트 T를 받아서 range에다 입력한다. 이후 리스트에 첫번째값과 두번째값을 map을 통해 받는다. 두번째 값을 리스트로 나누어서 첫번째 값만큼 각각 반복시킨다.

T = int(input())

for _ in range(T):
    R = 0   # 전체 반복될 때마다 문자를 반복해야될 수를 초기화한다. 
 
    x = list(map(str,input().split()))  # 리스트를 str 값으로 먼저 받고 r값을 int로 변환하면 될 것 같다.
    for _ in x:
        R = int(x[0])   # 두번째 줄의 첫번째 요소를 뽑아옵니다. 반복횟수를 지정해 줍니다.
        S = list(str(x[1]))   # 추출한 두 번째 문자 값을 리스트 형식으로 쪼개서 넣는다.
    print(''.join([i * R for i in S]))  # 각 문자열 반복은 join을 통해 표현합니다. R은 반복횟수, S는 반복할 문자열입니다.
    
# 코드를 더 줄일 수 있는 방법을 GPT를 통해 알아보았다. 알고 보니 리스트로 나눠서 할 필요 없고 
# 입력값 그대로 나눠서 쓸 수 있었다. 
T = int(input())

for _ in range(T):     # T번만큼 반복한다.
    R, S = input().split()  # 인풋값을 리스트로 받을 필요없이 공백으로 두값을 받는다. 각각 함수는 R, S로한다.
    R = int(R)   # 반복횟수를 지정해 주는 R을 정수형으로 바꿔준다.(반복시키기위해)
    print(''.join([i * R for i in S]))  # 각 문자열 반복은 join을 통해 표현합니다. R은 반복횟수, S는 반복할 문자열입니다.

맨처음에 두번째 줄 입력값을 밖에다 놔둬서 두번째 줄을 정해진 T만큼 반복 출력하지 못했다. 하지만, GPT 힌트를 통해 수정하게되었고, 간단한 코드도 알게 되었다.
한 번에 입력 받고 출력할 수 있어야되는줄 알았는데, 각각 입력받고 출력해도 됐다.

12시10분 ~ 35분
맛있는 식사 떡만둣국을 먹었다.

1시
17번 문제의 내용을 보충했다.

18번 문제(1152)단어의 갯수

영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열에는 몇 개의 단어가 있을까? 이를 구하는 프로그램을 작성하시오. 단, 한 단어가 여러 번 등장하면 등장한 횟수만큼 모두 세어야 한다.
str으로 문자열을 받고 그걸 split 공백으로 나눈 갯수를 세면 되지 않을까 싶다.
여기서 주핵심은 리스트도 마찬가지만 요소의 갯수를 세려면 len(요소명) 을 사용하면된다.

x = input().split()
print(len(x))  # 요소의 갯수는 len을 쓴다!!

# 더욱 간단히 나타내면 다음과 같다.
print(len(input().split()))

19번 문제(2908) 상수

상수는 수를 다른 사람과 다르게 거꾸로 읽는다. 예를 들어, 734와 893을 칠판에 적었다면, 상수는 이 수를 437과 398로 읽는다. 따라서, 상수는 두 수중 큰 수인 437을 큰 수라고 말할 것이다. 두 수가 주어졌을 때, 상수의 대답을 출력하는 프로그램을 작성하세요.
파이썬에는 reversed라는 요소를 뒤집을 수 있는 함수가 있다. 이 함수를 사용해 요소를 뒤집은 다음에 두 개의 요소를 비교하여 max로 큰 수를 뽑으면 될 것 같다.

x, y = list(input().split())
reverse_x = reversed(x)  # reversed를 통해 뒤집어진 리스트의 값을 받는다.
reverse_y = reversed(y) # reverse는 리스트를 뒤집고 리턴 값이 없어 none이 나온다.
print(max(''.join(list(reverse_x)), ''.join(list(reverse_y)))) 
# reversed는 뒤집어진 리스트의 값을 리턴하므로 list로 묶어줘야 일반적인 값이 나온다. 
# 뒤집어진 각각의 숫자를 join을 통해 합친다음에 max로 둘중 큰 수를 출력한다.

여기서 reverse와 reversed의 차이가 헷갈리는데,
reverse는 리턴값이 없어서 그 자체로 표현이 된다. 함수의 값으로 쓰기 힘들다.
reversed는 뒤집어진 리스트 값의 리턴값을 주기 때문에 함수에 list와 함께 저장해줄 수 있다.

20번 문제(2869) 달팽이는 올라가고 싶다
굉장히 오랜시간 생각하고 코드 구현을 어떻게 해야되나 고민이 많이 되었다. A는 낮에 올라가는 거리, B는 밤에 내려오는 거리, V는 도달해야되는 거리이다. 대강 생각해보면 A값에서 B값을 빼면 하루동안 간 거리인데, 이걸 낮에 올라간 거리부터 더해야한다. 왜냐하면, 낮에 이미 올라가 있으면 끝나기 때문이다. 최종적으로 더한 값이 V보다 크거나 같으면 끝난다.(if문을 써야하지 않을까...) GPT에 물어보니 마지막날 같은 경우 총 필요한 이동거리에 A를 미리 빼서 계산을 하면 더 효율적으로 계산 가능하다고 한다.

A, B, V = map(int, input().split())  # 각 입력값을 먼저 받는다.

LAST_DAY_remaining = V - A # 마지막 날을 제외한 거리(나중에 1일 더하면된다)
daily_move = A - B  # 하루동안 움직인 거리

# 잘 생각해보면 마지막 날을 제외한 남은 거리에 하루동안 움직일 수 있는 거리를 나눴을때
# 나머지가 0이면 그 날짜에서 +1만 해주면 되고 나머지가 생기면 한 날짜를 더 더한 후 마지막날 한 날을 더하면 된다.
# (거리가 부족하다는 것이니까)
if LAST_DAY_remaining % daily_move == 0:
     days = LAST_DAY_remaining // daily_move
else:
    days = (LAST_DAY_remaining // daily_move) + 1
    
print(days + 1)

해당 문제는 GPT의 도움을 많이 받았다. 구현자체가 쉽지 않았고 수학적 접근을 하는게 힘들었다.
특히, 마지막 날짜 제외한 거리에서 움직이는 거리를 나눠서 나머지가 나오면 +1을 한다는 생각이 굉장히 스마트하다. 나중에 다시한번 풀어봐야겠다.(그때도 할 수 있을지…)

21번 문제(1978) 소수 찾기

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성해야합니다.
일단 소수의 특징이 잘 기억이 안나서 찾아보았다. 간략히 보면 본인외에 나누어 지는 수가 있으면 안된다. GPT의 도움과 블로그의 도움을 많이 받아 작성했다. 수학적, 프로그래밍적 지식 부족...

N = int(input())
data = list(map(int,input().split()))
count = 0

for x in data:   # x는 본인 수를 의미한다.
    for i in range(2, x+1):  # 2부터 본인 수까지 나눈다. range의 마지막수는 -1이므로 +1을 해야 본인 수까지 온다.
        if x % i == 0:    # 만약 해당 숫자가 나누었을때 몫이 0이되는 수
            if x == i:    # x와 i 같은 수 이 말은 즉슨 본인 외에 나누어 지는 값이 없을때 이므로 소수이다.
                count += 1  # 값을 1 올려준다.
            break
    
print(count)

소수의 특징은 본인 수 외에 나누어지는 수가 없다는 특징이 있다. 그래서 2부터 시작해서 본인 수까지 모두 나눠서 0되고 그 나눠지는 수가 본인인지 확인해야하므로 if절이 두개이다. 모든 과정을 충족하면 count 값에 +1을 해주어 결과를 내보낸다.

★★★ 22번 문제(9020) 골드바흐의 추측

골드바흐의 추측은 2보다 큰 짝수가 주어졌을 때, 해당 수는 두개의 소수의 합으로 표현할 수 있다는 것이다. 이러한 과정에서 나온 두 소수를 골드바흐 파티션이라고하고, 그 n을 구하는 문제이다. 2보다 큰 짝수에 대응하는 더하는 수가 소수면 결과로 표현시키면 되는거 아닌가? 라고 했지만 아니었다. 우선적으로 소수를 판별할 수 있는 에라토스네스의 체를 함수로 구현해야한다.

def is_prime(n):   #소수 판별 함수
    if n < 2:      # 1은 소수가 아님
        return False
    for i in range(2, int(n ** 0.5) + 1):  
        # 2부터 √n까지 반복, 시간 복잡도를 줄이기위해서 범위를 줄인 것이다.
        # 해당 부분이 나는 굉장히 헷갈리는데, 직접해보니 √n까지만 처리해도 해당 숫자까지의 검사를 마칠 수 있다.
        # 원래처럼 n을 대입해서 계산하면 계산할 필요없는 경우까지 계산한다.
        if n % i == 0:  # 나누어떨어지면 소수가 아님
            return False
    return True  # 위 조건을 모두 통과하면 소수

T = int(input())  # 테스트 케이스 개수 입력

for _ in range(T):
    N = int(input())  # 짝수 N 입력

    for a in range(N // 2, 1, -1):  # N의 절반부터 작은 방향으로 1씩 줄이면서 탐색
        b = N - a  # a + b = N을 만족해야 함
        if is_prime(a) and is_prime(b):  # 체를 통해 둘 다 소수인지 확인
            print(a, b)
            break  # 가장 차이가 작은 쌍을 찾으면 종료

GPT의 도움을 많이 받았다. 수학을 안한지 오래되서(통신 공학수학만해서...) 에라토스네스의 체로 소수를 구하는 함수는 꼭 다시 써보면서 외워야겠다. 골드바흐의 추축과 에라토스네스의 체는 이론부터 어려운 것 같다.

23번 문제(1065)한수

일단 등차수열이 기억이 안나서 유튜브로 속성 강의를 듣고 있다. 등차수열은 연속 수의 차이가 일정한 수열이다. 수학교육과 동료분의 도움을 많이 받았다. 한수는 앞뒤 자리를 비교해서 일정한 간격이면 한수이다. 근데 숫자가 1개이거나 2개일때는 앞뒤로 비교할 수가 없기 때문에 모두 한 수가 된다. 이제 3자리 수부터 앞뒤수가 일정한지 확인해야한다. 예를 들어 123이나 135는 한수이다. 공차가 0이어도 등차이므로 111도 한수이다.

def han_number(n):
    if n < 100:   # 100전까지는 모두 한수 이므로 True이다.
        return True
    if n == 1000:   # 1000은 한수가 아니므로 예외처리한다.
        return False
    a, b, c = map(int,str(n))  # 1000보다 작거나 같은 자연수 N이므로 3자리 숫자만 비교하면된다.
    return (a-b) == (b-c)   # 실제로 각 자리를 추출해서 빼서 비교한다. 

n = int(input())
count = sum(han_number(i) for i in range(1, n+1))  
# 입력된 수까지 함수에 넣어서 True값 반환(한수 갯수를 센다)
# 해당부분이 생각하기 쉽지 않은것 같다. 함수와 함께 for문을 써도 되는지 몰랐다.
print(count)

한수라는 개념을 잡는데에도 30분은 걸린 것 같다. 또한 이걸 반복문과 함께 써서 True값을 추출할 생각하는게 쉽지 않은 것 같다.

24번 문제(2628) 종이자르기

문제를 이해하긴했는데, 어떻게 코드를 짤지 고민중이다. 내일 와서 해보겠다.

토요일인데도 알고리즘 문제를 풀다보니 하루가 다갔다. 난 자료형분석이나 알고리즘 경험자가 아니기 때문에 다른 사람들보다 더욱 노력해야한다. 문제가 점점 어려워지는데 긴 시간을 투자하여 풀어낼 수 있도록 해보겠다.