수학과의 개발자 도전기

1. 10844번: 쉬운 계단수

-문제: https://www.acmicpc.net/problem/10844

: 숫자가 한개일 때 쉬운 계단수를 못 구한하지 않나?라는 생각에 쉬운 계단수라는 개념이 처음에 이해가지 않았음. 

숫자가 한개일 때는 그냥 하나로 세고, 숫자길이 2일 때부터 생각하면됨. 이후 3부터는 숫자 길이 1,2일 때의 반복임을 이용하면된다.

-정답 풀이:

n=int(input())
dp=[[0 for i in range(10)] for j in range(101)]

#숫자가 무엇이든간에 자릿수가 1이면 계단수 1개임을 의미함 
for i in range(1,10):
    dp[1][i]=1
    
for i in range(2,n+1):
    for j in range(10):
        #i위치에 0이 오면 전행의 1의 개수와 동일하다(1의 -1이 0)
        if j==0:
            dp[i][j]=dp[i-1][1]
        #i위치에 9가오면 이전위치에 8밖에 못옴. 전행의 8의 개수와 동일    
        elif j==9:
            dp[i][j]=dp[i-1][8]
        else:
            dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]
print(sum(dp[n])% 1000000000)

-그리고 오타 조심하기!!!  print를 priint라고 서서 NameError 엄청냄,,

2. 2193번: 이친수

**처음으로 풀이 안보고 맞힌 문제(피보나치 유형), 겉모습은 다르지만 점화식을 구해보면 피보나치 구조를 가지므로, 구현해서 답을 구함.

복잡해보이지만 알고보면 단순한 문제 

-문제: https://www.acmicpc.net/problem/2193

-정답풀이:

• for문의 끝 인덱스가 n+1인 이유: 길이가 n인 이진수를 구하므로 n번째 인덱스 값을 출력해야하기 때문이다

-틀린풀이: 초기값이랑, 인덱스 조심(이거 꼭 제대로 하고 넘어가기)

3. 11727번: 2xn 타일링2(ssafy공부할 때 있었던 문제)

-문제:https://www.acmicpc.net/problem/11727

: 인덱스를 잘못구해서 오류가 많았음. 점화식은 옳게 구함-> 인덱스 똑바로 정하는 연습하기. 해당문제 다시 풀어봐야함

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

점화식은 각 항의 값을 직접 구해서 규칙성을 찾으려했음 

-정답 풀이:

• 마지막에 10007로 나누는 거 잊지말기 
• dp 초기값 설정하는데 오류발생(dp=[0 for i in range(n)]이라고 설정해서 되도록이면 끝값으로 크게 설정하기)
• 이것도 n번째 인덱스 값을 출력해야함

1. 1912번: 연속합 

:max 두번 사용하는 아이디어는 얻었으나, 시간초과로 풀지 못함 -> 빠른 속도로 구현하는 방법 익히기 

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

-정답: 

==> i+1번째 값(d[i+1])이랑 이전 누적값(m[i])이랑 합을 비교해서 최댓값 넣고, 그중에서 최댓값 출력하기 

-시간초과 풀이(사실 틀릴 수도 있음):

2. 2156번: 포도주 시식 

-문제: https://www.acmicpc.net/problem/2156

==> 계단 오르기와 비슷한 유형의 문제 공부하자!!

-정답 풀이: 

3. 2748번 : 피보나치 수2

-문제 :  https://www.acmicpc.net/problem/2748

==> 이전 피보니치와 같은 문제라고 생각해 재귀함수로 구현했으나 시간초과했음 

==> 이럴땐 리스트에 접화식 append하는 형식으로 진행하면 됨

-정답 풀이:

-틀린풀이

: 인덱스 문제로 틀림. 인덱스도 주의하자.

• for문의 마지막 인덱스가 n이 아니라 n+1d인 이유: 문제 설명에 보면 n=17일때, F17을 구하는 것이므로 총 18개의 숫자출력함. 따라서 n+1까지 인덱스 구해야함

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