[2025 1학기 알고리즘 스터디] 이서영 #2주차

*파이썬으로 풀었습니다

- 1463: 1로 만들기

- 2579: 계단 오르기

- 11053: 가장 긴 증가하는 부분 수열

 

 

1463: 1로 만들기

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

 

1. Greedy 

3으로 나눌 수만 있다면 무조건 최선이라 생각했습니다.

import sys
input = sys.stdin.readline

N = int(input())
count = 0

while N!=1:
    if N % 2 != 0 and N % 3 != 0:
        N-=1
        count+=1
    elif N % 3 == 0 and N % 2 != 0:
        N = N//3
        count+=1
    elif N % 3 != 0 and N % 2 == 0:
        N = N//2
        count+=1
    else:
        N = N//3
        count+=1
print(count)

역시 바로 반례 출현

 

1-2. 정교하게 탐욕

import sys
input = sys.stdin.readline

N = int(input())
count = 0

while N!=1:
    if N % 2 != 0 and N % 3 != 0:
        N-=1
        count+=1
    elif N % 3 == 0 and N % 2 != 0:
        N = N//3
        count+=1
    elif N % 3 != 0 and N % 2 == 0:
        if (N-1) % 3 == 0:
            N-=1
            count+=1
        else:
            N = N//2
            count+=1
    elif N % 3 == 0 and N % 2 == 0:
        N = N//3
        count+=1
print(count)

?? 바로 제출해줍니다.

ㅜㅡㅜ

반성 후 DP에 대해 공부해줍니다.🪖

 

DP

 

Dynamic Programming

-> 큰 문제를 여러 개의 작은 문제로 나누어, 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용

 

재귀 방식과 유사합니다. 하지만 차이점!

재귀는 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산이 될 수 있습니다.

 

DP의 사용 조건

 

1) 겹치는 부분 문제

-> 동일한 작은 문제들이 반복하여 나타나는 경우에 사용 가능 

 

2) 최적 부분 구조

-> 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우에 사용 가능

 

DP의 구현 방법

 

1) Bottom-Up

-> 아래부터 계산을 수행하고 누적시켜 큰 문제를 해결하는 방식

 

2) Top-Down

-> 위에서부터 바로 호출을 시작하여 dp[0] 상태까지 내려간 다음 결과 값을 재귀를 통해 전이시켜 재활용

 

 

문제풀기

dp = [0] * (N+1)
dp[i] = 숫자 i를 1로 만들기 위한 최소 연산 횟수

for i in range(2,N+1) #dp[2]부터 dp[N]까지 차례로 구함

for i in range(2,N+1):
    dp[i] = dp[i-1]+1
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3]+1)

 

N이 10일 때

dp[10] = dp[9] + 1

하지만 10이 2로 나누어 떨어지니

dp[10] = min(dp[10], dp[5] +1)  여기서 dp[10]은 dp[9] + 1

 

dp[10]을 구하려면 dp[9]와 dp[5]를 알아야합니다.

∴ 2부터 차례대로 dp[2], dp[3], ... ,dp[5], ... ,dp[9]를 구하는 것

 

import sys
input = sys.stdin.readline

N = int(input())
dp = [0] * (N+1)

for i in range(2,N+1):
    dp[i] = dp[i-1]+1
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3]+1)

print(dp[N])

 

* elif는 앞의 if가 False일 때만 실행되기에 i가 2와 3 모두 나눠떨어질 경우 //3 쪽 조건이 무시됨 꼭 if로

^0^

 

 

 

2579: 계단 오르기

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

 

 

마지막 계단을 꼭 밟아야합니다.

DP를 생각해주면

i가 마지막 계단, dp[i]가 최고 점수라 할 때, dp[i]를 아래처럼 설정 해 줄 수 있습니다.

dp[i] = max(dp[i-2] + stairs[i], dp[i-3] + stairs[i-1] + stairs[i])
# 그 전 칸을 포함했을 때와, 건너 뛰었을 때 중 최대를 고르게 합니다
# i-3이 있으니 i가 1일 때랑 2일 때는 따로 설정해줍니다!

 

for i in range(3,n):
    dp[i] = max(dp[i-2]+stairs[i], dp[i-3]+stairs[i-1]+stairs[i])

반복문을 사용하여 그 계단 까지의 최대값을 알게하고 위로 올라갈수록 밑의 값을 재활용 해줍니다.

 

import sys
input = sys.stdin.readline

n = int(input())
stairs = [int(input()) for _ in range(n)] #계단 점수를 리스트로 입력받게

if n == 1: #계단이 1개 일 때 따로 설정
    print(stairs[0])
    exit() #바로 코드 끝내기
elif n == 2: #계단이 2개 일 때
    print(stairs[0]+stairs[1])
    exit()

dp = [0]*n #계단이 3개일 때부터 dp를 활용해줍니다.
dp[0] = stairs[0]
dp[1] = stairs[0] + stairs[1]
dp[2] = max(stairs[0]+stairs[2], stairs[1]+stairs[2])


for i in range(3,n):
    dp[i] = max(dp[i-2]+stairs[i], dp[i-3]+stairs[i-1]+stairs[i])

print(dp[n-1]) #인덱스니 n-1로 출력

^0^

 

 

 

11053: 가장 긴 증가하는 부분 수열

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

첫번째 시도

import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

dp = [0] * N
dp[0] = 1

for i in range(1,N):
    if A[i]>A[i-1]:
        dp[i]=dp[i-1]+1
    else:
        dp[i]=dp[i-1]

print(dp[N-1])

 

놓쳤던 점

-> 바로 직전 수와 비교해서 작은 수가 껴있을 때를 생각 못 했습니다.

4로 출력되어야하는데 5로 출력 ㅜㅡㅜ

 

두번째 시도

import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

dp = [1] * N

for i in range(N):
    for j in range(i):
        if A[i] > A[j]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

 

i까지의 '증가하는 부분 수열 최대 길이'를 구하기 위해 이중 반복문을 사용해줍니다.

또한 max함수를 사용해서 더 큰 값을 선택하도록 해줍니다.

 

 

2주차 후기

예전엔 브1-실5 문제까지는 알고리즘에 대한 개념 존재를 몰랐어서 머리 끙끙하면 풀렸지만 스터디 문제는 도저히 풀 방법이 생각 안 나서 검색을 해보면 처음 보는 말들이 나오고, 그것들은 따로 개념이 있다는 것을 알게 되었습니다. 결국 수학과 같이 알고리즘도 풀이를 위한 개념이 존재하고, 개념의 종류가 엄청엄청 다양하며, 문제의 수준이 높아질 수록 개념 없이는 풀 수 없는 문제가 대부분이구나를 느꼈습니다. 

결론 : 난 바보니까 무작정 풀려고 하지말고 노션의 스터디 계획에 나와있는 개념을 확인하고 공부를 한 뒤에 문제를 풀자..