수학과의 개발자 도전기

1. 2579번: 계단오르기

문제: https://www.acmicpc.net/problem/2579

-정답 풀이: 

마지막 계단을 밟아야 하므로 마지막 값인 s[i]을 항상 더해야함 . 상황은 아래처럼 두가지가 있다 

case 1 : 마지막 이전 계단을 밟고 있는 경우

case 2: 마지막 이전 계단을 밟지 않고 있는 경우 

-점화식:

-틀린 풀이: 

시작부분부터 올라가는 걸로 풀어서 문제 조건(마지막 계단을 꼭 밟아야한다)을 만족 안 할 수도 있음.

고로 마지막 계단 입장에서 생각해야함-> 역시나 점화식을 생각하는 것이 관건

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

문제: https://www.acmicpc.net/problem/11053

처음들어본 가장 긴 증가하는 수열

여기서는 리스트를 두개 만들어서 수열의 개수를 넣는 것이 관건이었다.

-정답 풀이:

:값이 큰 것 중에 a인덱스 값이 작은 수에 한하여 숫자를 누적하고, 이후에 하나씩 증가하는 방식

-틀린 풀이:

뭔가 맞는 것 같은데 append를 썼는데 계속 IndexError가 발생했다. 왜인지 생각해봐야할듯

->NOPE. 문제에서는 정보가 하나의 리스트로 다 주어졌기 때문에 반복문에 append하면 안됨. 초기값 잘못 받았음!!(2022.06.02)

3. 1932번 : 정수 삼각형 

문제: https://www.acmicpc.net/problem/1932

-정답 풀이

: 5번까지는 어느정도 작성 했는데  밑부분을 생각하는 것이 어려웠음. 

삼각형 가장 마지막 까지 규칙대로 더했을 때 가장 큰 값을 출력하면됨

i 번째 행렬에서 0번 컬럼와 (i-1)컬럼은 바로 위의 값과 더하면 되므로 아래 if,elif 문과 같이 작성하면 되고,

나머지는 전 행의 대각선 왼쪽,오른쪽 값과의 합 중에 최댓값을 넣으면 된다

-틀린 풀이:

위에서부터 아래로 더해나갔는데 i+1행에서 값을 더하는 것이 어려웠음. 아무튼 이렇게 생각하거나, 작성하면 안된다는 것을 알게됨 

1. 9095번 

출처: https://www.acmicpc.net/problem/9095

-> 동적 프로그래밍에서는 점화식 구하는게 가장 중요하다는 걸 알게됨

-> 예제 값을 이용해서 관계를 구하고, 점화식 작성하면됨 

i=1일 때, 더하기 표한 방법 1 -> hap(1)=1

i=2일 때, 더하기 표한 방법 2(1+1,2) -> hap(2)=2

i=3일 때, 더하기 표한 방법 4(1+1+1,1+2,2+1,3) -> hap(3)=4

hap(4)=7= 1+2+4

-점화식: hap(n) =hap(n-1)+hap(n-2)+hap(n-3)

-방법1 : 재귀함수 이용

-방법 2: 리스트에 append(python에서 재귀함수가 안 될때가 있으니 이 방법을 잘 봐두자)

2. 10870번 : 피보나치 함수 구현.

문제: https://www.acmicpc.net/problem/10870

-정답: 

3. 11726번

문제: https://www.acmicpc.net/problem/11726

-점화식을 구하는데는 성공해서 재귀함수로 구현하려 했으나 에러 발생 -> 재귀함수 이용하지 않고 구현하는 방법 익히기 

-점화식: s(i) = s(i-1) +s(i-2)

-풀이1: 재귀함수 이용

-풀이2 : 리스트 이용해서 풀어보자!!

4. 1149번

문제: https://www.acmicpc.net/problem/1149

- 원리는 생각 했는데 코드로 옮기는데 실패 -> 코드로 표현하는 방법 역시 공부하자

-원리: 1. 첫번째 줄에서 최소 값 구하기 2. 이전 줄 선택된 컬럼 빼고 나머지에서 최소값 구하기 (컴퓨터 적으로 생각하는데 부족함이 있는 것 같음)

-풀이 :

• part01

• part02 

• 백준 코딩테스트 매일 3문제씩 푸는 것이 목표(동적프로그래밍,그리디,탐색 50문제씩 푸는 것)

동적 계획법을 사용해야하는 문제

• 초기값으로 설정할 값이 명확
• 기존에 연산된 값을 재사용하는 메모이제이션이 있어야 함 

• 메모이제이션: 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술

1. 2839번 

문제: https://www.acmicpc.net/problem/2839

-내가 작성한 틀린 풀이 

• 조건문으로 풀면 복잡해짐 

n=int(input())
cnt=0

#5의 배수일때 
if n%5==0:
    cnt= n//5
    
#3의 배수일때 
elif n%3==0:
    if (n//5)+1 < (n//3):
        cnt = (n//5)+1
    else: 
        cnt=n//3
        
#3,5의 배수 아니지만 합으로 표현가능할 때        
elif (n%5)%3==0:
    a=n//5
    b=(n%5)
        
#3,5의 합으로 나타낼 수 없을 때 
else:
    cnt=-1
    
print(cnt)

-정답 풀이 

•  5를 기준으로 계산해야 최소값을 구할 수 있다는 것은 생각했는데, #10,11 라인을 생각을 못했다. 참고해서 알아두기 

2. 1463번: 하나도 모르겠음,,  -> 코드 계속 보면서 이해하기위해 노력하기 

문제: https://www.acmicpc.net/problem/1463

-정답 출처: https://infinitt.tistory.com/247

3. 1003번 

문제: https://www.acmicpc.net/problem/1003

- 초기값 설정하기 

=> 위의 표를 리스트로 옮기면 다음과 같다. 

- 문제 풀이 핵심 원리: 

- 10번 문장이 들어있는 이유: zero의 길이보다 짧은 리스트(num이 1,2,3일경우 )가 입력되었다면 기존의 값을 반환하면 되기 때문이다.