2024.04-4

2024.04-4

2024년 4월 22일

1. 11047번 동전 0

실버 IV

💡문제 분석 요약

원하는 값과 주어진 값으 나눗셈과 나머지로 푸는 문제.

여기서 i≥2인경우 Ai가 Ai-2라서 쉽게 풀린다.

💡알고리즘 설계

결국 500원 1개= 100원 5개 가치이므로 금액이 높은 순으로 최대한 값을 빼면서 최솟값을 구하자.

💡코드

import sys
lines= sys.stdin.read().splitlines()
n,k = map(int,lines[0].split())
coin = list(map(int,lines[1:]))
coin.sort(reverse=True)
m=0
count =0
for i in coin:
    if k>=i:
        
        count += k//i #몫
        k = k%i #나머지
        
print(count)

💡시간복잡도

N

💡 다른 풀이

굳이 sort하지 않고, range(n-1,-1,-1)로 역순으로 돌면 된다!

💡 느낀점 or 기억할정보

• 역순으로 돌땐 range(x,t,-1)로 -1를 세번째 값(증가 숫자)을 설정하자.

2. 11399번 ATM

실버 IV

💡문제 분석 요약

걸리는 시간을 예시처럼 오름차순으로 정렬하고 중복 더해주고 출력.

💡알고리즘 설계

오름차순으로 정렬 뒤, 쌓인 값을 더하자.

💡코드

import sys
input= sys.stdin.readline
n = int(input())
person = list(map(int,input().strip().split()))
person.sort()
time = 0
alltime =0
for i in person:
    alltime +=i
    time += alltime
print(time)

💡시간복잡도

O(NlogN)+N

3. 17219번 비밀번호 찾기

실버 IV

💡문제 분석 요약

입력값으로 key와 value를 매칭하고 출력.

💡알고리즘 설계

입력 값을 받고, url주소를 key로 설정한 뒤, value를 설정한다.

💡코드

#70936KB 224ms

#시간복잡도 순서대로 나열
#splitlines()로 받은 경
import sys

input= sys.stdin.read().splitlines()
n ,m= map(int,input[0].split())
saved = input[1:n+1] 
search = input[-m:]

dic ={}

for i in saved:
    site, secret = i.split()
    dic[site] = secret
    
for j in search:
    print(dic[j])

#49208KB	244ms
#readline()으로 받은 경우 

import sys
dic ={}
input= sys.stdin.readline
n ,m = map(int,input().strip().split())

for i in range(n):
    site, secret = input().split()
    dic[site] = secret
    
for j in range(m):
    search = input().strip()
    print(dic[search])

💡 느낀점 or 기억할정보

• splitlines로 리스트를 각각 생성할 경우, 메모리를 많이 잡아 먹는다. 차라리 for문으로 한번에 돌고, 숫자 n+1을 넘으면 출력하게 해야할 듯.

4. 1003번 피보나치 함수

gs

💡문제 분석 요약

함수에서 0과 1이 나오는 규칙을 알아내고 출력하는 문제

💡알고리즘 설계

0과 1이 function 3부터 그 전을 더한 값으로 구성된다.

0111235.. → 1+1=2, 2+1=3, 2+3=5

1012358…→ 1+2=3, 2+3=5…

이는 2인경우 0,1이 각각 1개이며, 3인경우 2(0,1)와 1 로 그 전의 숫자의 값을 그대로 사용하는 것을 볼 수 있다.

따라서 list에 다음 값은, 이전 값과 현재값을 더한 것으로 누적하여 채워나간다.

💡코드

import sys
dic ={}
number= int(sys.stdin.readline())

countZero = [1,0,1,1]
countOne = [0,1,1,2]

countZero.extend([0]*40)
countOne.extend([0]*40)

for j in range(3,41):
    countOne[j+1] = countOne[j]+countOne[j-1]
    countZero[j+1] = countZero[j]+countZero[j-1]
5
for i in range(number):
    n= int(sys.stdin.readline())
    print(f'{countZero[n]} {countOne[n]}')

💡 느낀점 or 기억할정보

• splitlines로 리스트를 각각 생성할 경우, 메모리를 많이 잡아 먹는다. 차라리 for문으로 한번에 돌고, 숫자 n+1을 넘으면 출력하게 해야할 듯.

2024년 4월 23일

1. 1463번 1로 만들기

실버 IIV

💡문제 분석 요약

동적 계획을 사용한 문제 풀이

💡알고리즘 설계

동적 계획법으로 푼다.(메모이제이션 활용)

요청된 숫자까지 값을 더해서 만든다.

3과 2로 나누어 떨어지면 나눠진 값+1로 설정한다.

→ ex) if 4면, 2→1을 활용하여 4→2→1이 됨. 2로 2나누면 1번, 4로 2나누면 2가 되어서 1번 + 2로 2나누면 1번 즉, dp[2] =1(2→1) 값에 +1를 해주는 꼴.

여기서 1로 빼주는 것을 어디에 넣어야 할지, 최솟값을 얻어야 하는데 어떤 값이랑 비교해야하는 지 고민이었다.

쉽게 생각하면, 6이 6→5→4→2→1인지 6이 6→2→1 인지는 min을 통해서 더 작은 값으로 업데이트 해주면 되고, 5같은 경우는 4에서 1을 더해주는 계산이 무조건 필요하기 때문에 우선적으로 이전 값에서 +1을 해주는 것을 기본 값으로 넣는다.

왜냐하면 그 전 값에서 +1를 해주면, 최솟값은 확정 지을 수 없지만 그렇게 해서 숫자를 만들 수 있기 때문이다.

3도 2+1로 만들 수 있고, 6도 5+1로 만들 수 있다. 다만 최소가 아닐 수도 있을

💡코드

import sys
n= int(sys.stdin.readline())
dp = [0]*(n+1)
for i in range(2,n+1):
    dp[i] = dp[i-1]+1
    if i%3==0:
        dp[i] = min(dp[i//3]+1,dp[i])
    if i%2 == 0:
        dp[i] = min(dp[i//2]+1, dp[i])
print(dp[n])

💡시간복잡도

for문에서 사용되는 N

💡 틀린 이유

접근 방식이 틀렸다. 사실 DP라는 것을 어렴풋이 풀면서 느꼈지만, 왜 DP지? 라는 의문이 들었다. 따라서 Dp일때 해당하는 특징을 고민했다.

DP는 일단 메모이제이션이 가장 특징이다. 즉, 썼던 값을 재활용, 중복해서 사용하느냐에 따라 DP가 될지 결정된다. 여기서 3인경우 3→1 6인경우 6→3→1 9인경우 9→3→1 로 3→1 패턴을 그대로 쓰는 것을 볼 수 있다.

그렇다면 최솟값을 넣어야하는데 어떻게 넣어야할 것인가? 어떤 값을 비교해야할 것인가가 의문이다.

여기서 1을 빼거나 2나 3으로 나누거나 3가지 조건이 있다.

💡 느낀점 or 기억할정보

• 그리디- 최적의 방법이 반례없이 끝까지 적용
• 동적 계획법: 메모이제이션 방법으로 중복 계산 값이 많을때 유용하다. 즉 문제를 나누고 재활용해서 전체 답 구하기!! 숫자가 증가할 수록, 아니면 다음 케이스에서 답을 구할때 이전 값을 사용하는지를 보자!
• 브루트 포스는 DFS,BFS가 있고, 그냥 다 보자! 라는 느낌.

2. 2579번 계단 오르기

실버 IIV

💡문제 분석 요약

동적 계획을 사용한 최댓값 구하기

💡알고리즘 설계

동적 계획법으로 푼다.(메모이제이션 활용)

조건: 1,2칸 가능, 연속 3칸 불가, 마지막 계단은 무조건 밟아야 한다.

마지막 계단을 n으로 생각하면,

n-1 + n , n-2+n 이 된다. 다만, n-1+n일때 n-2를 밟을 수 없으므로 n-3 조건을 추가해야한다.

stairs로 각 계단의 숫자를 받고 dp라는 배열에다가 메모이제이션으로 값을 누적하여 저장한다.

그렇다면 n n-1 n-3에서 n은 stairs 자체값인 stairs[n], 그리고 stairs[n-1] ( 만약 n-1이 dp면 누적값이 전부 들어오므로 안된다. 연속 될 수 있으니) 그리고 dp[n-3]

stairs[n] + dp[n-2]가 된다.

💡코드

import sys
n= int(sys.stdin.readline())
stairs = [int(sys.stdin.readline().strip()) for _ in range(n)]
if n==1:
    print(stairs[0])
elif n==2:
    print(stairs[0]+stairs[1])
else:
    dp = [0 for i in range(n)]
    dp[0] = stairs[0]
    dp[1] = max(stairs[0]+stairs[1],stairs[1])
    for i in range(2,n):
        dp[i] = max(dp[i-3]+stairs[i-1]+stairs[i], dp[i-2]+stairs[i])
    print(dp)[-1]

💡시간복잡도

for문에서 사용되는 N

💡 틀린 이유

dp라는 것을 알고 구현하려고 했지만 식이 잘못되었다. 우선 1,2,3 등 앞에서 부터 생각하려니 머리가 아팠다. 또한 하나하나 식을 써가면서 해봤지만 제대로 된 예시나 식을 세우지 못했다. 정말 비슷하게 까지 접근했지만 dp에 stairs[i]가 포함되지 않은 값을 넣었고, 계속 헷갈리다가 답을 보게 되었다.

💡 느낀점 or 기억할정보

• 1,2,3 부터 예시를 구해도 좋지만 결국 n을 뽑아내는 것이 중요하다. 단순하게 생각하자!

2024년 4월 24일

1. 2606번 바이러스

실버 III

💡문제 분석 요약

union find를 활용한 문제.

💡알고리즘 설계

연결 되어 있고, 1에게 걸려있는 모든 값을 찾는 것이기 때문에 uion&find(최고 부모)를 활용하여 1이 최고 부모인 것을 골라낸다.

연결된 컴퓨터의 최고 부모를 설정한다. 이때 1이 부모여야 하므로 가장 작은 숫자가 부모가 되게끔 union에 설정한다.

1 자신을 제외한 최고 부모가 1인 컴퓨터 갯수를 출력한다.

💡코드

import sys
n= int(sys.stdin.readline())
m = int(sys.stdin.readline())
edge = []
answer =0
def find(a,parent):
    if parent[a]!=a:
        parent[a]  = find(parent[a],parent)
    return parent[a]

def union(a,b,parent):
    a= find(a,parent)
    b = find(b,parent)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
parent = [i for i in range(n+1)]
for _ in range(m):
    com1,com2 = map(int,sys.stdin.readline().strip().split())
    union(com1,com2,parent)
for i in parent:
    if find(i,parent) == 1:answer+=1
print(answer-1)

💡시간복잡도

for문에서 사용되는 n+부모 설정 최대 n

💡 틀린 이유

보자마자 노드이므로 딕셔너리가 생각났다. 조금 더 쉬운 알고리즘이 있다는 힌트를 얻어 크루스칼에 주로 사용되는 union&find를 활용해야겠다고 생각했다.

• Union Find: Disjoint Set(공통 원소가 없는 부분 집합들)을 나타낼 때 사용하는 알고리즘. 형식은 Tree 기본적인 세팅은 자기 자신이 부모이다. 또한 최고 부모의 부모는 자기 자신이다.
  • Union(x,y)
    • x와 y의 최고 부모를 설정한다. (집합을 합치는 연산)
  • find(x)
    • x의 최고 부모를 찾는다. (x가 속한 집합의 대푯값을 찾는다)

def find(a): #결국 최고 부모는 자기 자신이므로, 
    if parent[a]!=a: #a의 부모가 최고 부모가 아니면
        #경로 압축 과정 Path Compression
        parent[a] = find(parent[a]) # 탐색했던 모든 값의 부모를 최고 부모로 재설정
    return parent[a]

def union(a,b):
    a= find(a)
    b = find(b)
    if a < b: #여기서는 더 작은 값이 부모가 되도록 설정. 변경 가능. 
        parent[b] = a
    else:
        parent[a] = b
	

1-2, 2-3 가 들어와서 1-2-3 로 연결된 경우, (2의 부모1, 3의 부모2)

parent[1,2,3] → [1,1,2]로 변했을 것이다. 이때 3-5를 위하여 find(3)를 할 경우.

parent[3] ≠3이 아니라 2이다. 그러므로 find(parent[3] = 2)를 한다.

여기서 find(2)값이 3의 부모가 된다.

parent[2]는 2가 아닌 1이므로 find(1)을 한다. 여기서 또한 find(1)값이 2의 부모가 된다.

parent[1]=1 즉 최고 부모므로, return으로 1을 돌려준다. 이후 3과 2의 부모는 1이 된다.

이렇게 하여 find(x)를 한 경우, x의 최고 부모를 찾는 동시에 call한 모든 값의 부모가 최고 부모로 설정되어 경로를 압축할 수 있다.

** 유의점은 find를 하지 않은 경우 <1-2, 2-3 가 들어와서 1-2-3 로 연결된> 이 상태가 그대로 유지되기에 parent[] 의 모든 값이 최고 부모라 단정지을 순 없다. 다만, 모든 값에 find()를 적용시켜주면 모든 부모가 최고 부모로 설정되어 parent의 모든 값이 최고부모가 된다.

💡 느낀점 or 기억할정보

• Union&find 알고리즘.

2. 9095번 1,2,3 더하기

실버 III

💡문제 분석 요약

메모이제이션을 활용한 dp문제

💡알고리즘 설계

dp[나타낼 숫자] = 1,2,3으로 나타낼 수 있는 경우의 수

의 형식으로 저장한다.

dp[i]=dp[i-1]+ dp[i-2]+ dp[i-3]를 얻어낸 뒤 진행한다. 설명은 https://jyami.tistory.com/15 이 블로그를 참조하여 구체화 하였다.

1은

| 1 | | — |

2는

| 2 1+ 1 | | — |

3은

| 3 1 + 2 1 + 2 + 1 1 + 1 + 1 | | — |

dp[4]는

| 1 + dp(3) | 2 + dp(2) | 3 + dp(1) | | — | — | — | | 1 + 3 1 + 1 + 2 1 + 2 + 1 1 + 1+ 1+ 1 | 2 + 2 2 + 1 + 1 | 3 + 1 |

dp[5]는

| 1 + dp(4) | 2 + dp(3) | 3 + dp(2) | | — | — | — | | 1 + 1 + 3 1 + 1 + 1 + 2 1 + 1 + 2 + 1 1 + 1 + 1+ 1+ 1 1 + 2 + 2 1 + 2 + 1 + 1 1 + 3 + 1 | 2 + 3 2 + 1 + 2 2 + 2 + 1 2 + 1+ 1+ 1 | 3 + 2 3 + 1 + 1 |

이처럼 n값의 이전 3개의 배열 값을 합한 것이다.

💡코드

import sys
n= int(sys.stdin.readline())
dp=[0]*12
dp[1]=1
dp[2] = 2
dp[3] = 4
for i in range(4,12): 
    dp[i]=dp[i-1]+ dp[i-2]+ dp[i-3]
    
for i in range(n):
    ans = int(sys.stdin.readline())
    print(dp[ans])

💡시간복잡도

2n

💡 틀린 이유

시행착오가 좀 많았다.

셀 수 있는 경우의 수가 수학적으로 떨어지지 않을까 하여 이것저것 대입해봤지만 나오지 않았고, 중간에 dp[3]=3으로 착각하는 바람에 다시 구했고… 어떻게 해서 저 점화식을 구했지만 얻어 걸린 느낌이었다. 즉, 설명하려고 하면 어려웠다.

앞으로 저렇게 이전 dp,그 이전 dp의 계산 값을 그대로 이용하여 써내려가보자. 그대로 활용하니 메모이제이션 가능하지 않겠나!

💡 느낀점 or 기억할정보

• dp 알고리즘이 적용되는 이유는 반복이다!

2024년 4월 25일

1. 9375번 패션왕 신해빈

실버 III

💡문제 분석 요약

수학적으로 푸는 문제 (조합)

💡알고리즘 설계

해빈이가 같은 종류의 옷을 입지 않으면서 1개 이상의 옷을 입는 경우의 수를 출력

이때 떠오른 아이디어는 a 종류의 옷을 입지 않는 경우의 수를 Ax로 추가하여 고려한다.

즉, a종류에 1,2 의 아이템이 있다면, A1,A2,Ax로 1을 입는 경우, 2를 입는경우, x아무것도 입지 않는 경우를 계산한다. 여기서 중복은 Ax * Bx처럼 두 종류의 아이템 모두 x값을 선택할 때이므로 최종 값에 1을 빼준다.

같은 이름이 들어오지 않으므로 종류만 같다면

dic[옷 종류]=갯수

의 형태로 저장한다.

갯수를 돌면서, 갯수+ 1(입지 않는 경우의 수)를 answer에 곱해준다.

답을 제출할 때 1(모두 입지 않는 수)를 answer에서 뺸다.

💡코드

import sys
from collections import defaultdict
n= int(sys.stdin.readline())
for i in range(n):
    m = int(sys.stdin.readline())
    dic =defaultdict(int)
    for j in range(m):
        name, kind = sys.stdin.readline().strip().split()
        dic[kind] +=1
    ans =1
    for count in dic.values():
        ans*=(count+1)      
    print(ans-1)

💡시간복잡도

2n

💡 헷갈렸던 이유

처음에 이 문제를 보고 이전에 비슷한 문제를 프로그래머스에서 푼 게 기억나서 그거대로 풀려고 했더니 식이 세워지질 않았다. 즉, (전체 경우의 수)-(중복해서 입는 수) 로 중복이 아닌 것을 구하려 했지만, 중복해서 입는 수가 엄청 구하기 어려웠다. 식이 안세워졌다. 따라서 포기하고 바로 직관적으로 풀었다.

💡 느낀점 or 기억할정보

• 이전 기억에 의존하는 것이 아닌 활용해서 푸는 정도로만 이용하자.

2024년 4월 26일

1. 9461번 파도반 수열

실버 III

💡문제 분석 요약

점화식을 찾아서 이전 값을 활용하는 dp문제

💡알고리즘 설계

그 다음 값이 어떤 값과 어떤 값을 활용해야 나오는지 점화식을 사용해서 알아낸 뒤에 배열을 활용해 값을 저장하여 푼다.

삼각형은 각각 이전 삼각형에 영향을 받고 있는 것을 그림을 통해 알 수 있다. 따라서 dp의 메모이제이션을 활용하여 풀었다.

dp[i] = dp[i-1] + dp[i-5]로 주어진 N의 최대 범위까지 구한 뒤, n의 값을 받고 출력 한다.

💡코드

import sys
n= int(sys.stdin.readline())
dp = [1,1,1,2,2,3,4,5,7,9,12]
a = [0 for i in range(90)]
dp.extend(a)

for i in range(8,101):
    dp[i] = dp[i-1] + dp[i-5]
for _ in range(n):
    i = int(sys.stdin.readline())
    print(dp[i-1])

💡시간복잡도

n

💡 느낀점 or 기억할정보

• 점화식을 구할 때, 규칙성을 찾아내기 위하여 비슷한 값을 증가하여 구해보자.

2. 11659번 구간 합 구하기4

실버 III

💡문제 분석 요약

점화식을 구하여 dp의 메모이제이션을 활용하여 푸는 문제

💡알고리즘 설계

구간 합을 쉽게 구할 수 있는 점화식을 구한다.

1 2 3 4를 dp에 저장하면

1 1+2 1+2+3 1+2+3+4

이럴 때 2~4번째 합은 2+3+4 = dp[3]-dp[0]가 된다.

즉 i~j구간일 때 dp[j-1] - dp[i-2]

💡코드

import sys
input = sys.stdin.readline
n, m= map(int,input().strip().split())
nums = list(map(int,input().strip().split()))
a= 0
dp = [0] * 100001
for s in range(n):
    dp[s] = nums[s]+a
    a += nums[s]

for _ in range(m):
    i,j = map(int,input().strip().split())
    print(dp[j-1]-dp[i-2])

💡시간복잡도

n

💡 느낀점 or 기억할정보

• 점화식을 구할 때, 규칙성을 찾아내기 위하여 비슷한 값을 증가하여 구해보자.

3. 11726번 2xn 타일링

실버 III

💡문제 분석 요약

점화식을 구하여 dp의 메모이제이션을 활용하여 푸는 문제

💡알고리즘 설계

점화식을 구하고, 구현한다.

직사각형을 구한 것이 크기가 확장 됨에 따라 값이 확장되는 느낌이라 이전 값이 반복 될 것이라고 생각하여 dp라고 생각하고 풀었다.

dp[i] = dp[i-1] + dp[i-2]

하나하나 구한 이후, 각 항들의 관계를 예측하여 점화식을 뽑았다.

💡코드

import sys
input = sys.stdin.readline
n = int(input())
dp = [0,1,2,3]
if n>3:
    dp.extend([0 for _ in range(3,n+1)])
if n>3: 
    for i in range(4,n+1):
        dp[i] = dp[i-1] + dp[i-2]
print(dp[n]%10007)

💡시간복잡도

n

💡 다른 풀이

list를 만들고 초기 값을 넣은 뒤, 거기에 100007로 나눈 값을 list에 append를 한다.

이때 l[-2] + l[-1]으로 더해주는데, -2는 뒤에서 2값, -1은 뒤에서 1 값이므로 즉, 현재 만들어진 list가 n이 들어가기 전이므로 맨 마지막 값은 n-1일 것이기 때문이다.

💡 느낀점 or 기억할정보

• 점화식을 구할 때, 규칙성을 찾아내기 위하여 비슷한 값을 증가하여 구해보자.

4. 11726번 2xn 타일링 2

실버 III

💡문제 분석 요약

점화식을 구하여 dp의 메모이제이션을 활용하여 푸는 문제

💡알고리즘 설계

점화식을 구하고, 구현한다.

직사각형을 구한 것이 크기가 확장 됨에 따라 값이 확장되는 느낌이라 이전 값이 반복 될 것이라고 생각하여 dp라고 생각하고 풀었다.

dp[i] = dp[i-1] + dp[i-2]

하나하나 구한 이후, 각 항들의 관계를 예측하여 점화식을 뽑았다.

💡코드

import sys
input = sys.stdin.readline
n = int(input())
dp = [1,3,5,11]
for i in range(n):
    dp.append((dp[-2]*2+dp[-1])%10007)
print(dp[n-1])

💡시간복잡도

n

2024년 4월 27일

1. 17626번 Four Squares

실버 III

💡문제 분석 요약

메모이제이션을 활용한 dp문제

💡알고리즘 설계

dp[숫자] = 제곱 수로 나타낼 수 있는 숫자 합의 최솟값

규칙은

dp[2] = $1^2$ + $1^2$ = 2

dp[3] = $1^2+1^2+1^2$ = 3

dp[4]= $2^2+2^2$ = 2

dp[5] = dp[4]+dp[1] = 2

5는 제곱수 1과 4로 각각 뺏을 때 4,1이 나오고 dp[4]와 dp[1]에 +1

dp[6]에서 6은 1과 4로 뺏을 때 5와 2가 나오고, dp[5]=2, dp[2]=2이므로 여기에 +1한 값 즉, 3

dp [11]은 1,4,9를 각 빼면 dp[10],dp[7],dp[9], 여기에 각각 1을 더하면 3,5,3이므로 최솟값인 3이 정답.

다만 pypy3으로 돌려야 한다.

💡코드

import sys
n= int(sys.stdin.readline())
dp=[0]*12
dp[1]=1
dp[2] = 2
dp[3] = 4
for i in range(4,12): 
    dp[i]=dp[i-1]+ dp[i-2]+ dp[i-3]
    
for i in range(n):
    ans = int(sys.stdin.readline())
    print(dp[ans])

💡시간복잡도

n

💡 틀린 이유

dp인것 같았으나 어떤 규칙이 있는지 알지 못했다. 처음에는 나눈 값을 내림으로 하여 제일 가까운 제곱수를 빼는 방식으로 했으나 예외가 발생하였다. dp값을 제곱수로 나타내는 것까지 고민했으나 이것을 어떻게 조합해야 최솟값을 발생하는 지 몰라서 답을 보았다.

답은 dp에 제곱수들의 합의 최소 수량을 넣어 구한다.

💡 느낀점 or 기억할정보

• 다양하게 점화식을 뽑아내보자. 값 자체인지 값을 활용한 값인지..