나만의 개발블로그

이친수 문제의 경우엔 하나씩 작성해보면서 풀어보니 쉽게 규칙을 찾아 빠르게 풀게 되었음. a와 b에 누적 합을 활용한 풀이 방법 n = int(input()) a, b = 1, 1 for _ in range(2, n): a, b = b, a+b print(b) 배열로 누적 합을 활용한 풀이 방법 n = int(input()) dp = [0]*(n+1) dp[0:3] = [0, 1, 1] if n < 3: print(dp[n]) else: for i in range(3, n+1): dp[i] = dp[i-1]+dp[i-2] print(dp[-1])

DP를 활용한 누적 값을 이용해 푼 풀이 처음에 공식을 찾기 위해 2*4를 진행했을 때는 8개라고 생각해서 dp[n-2] + dp[n-1] 로 생각해 a,b = b, a+b 라고 생각했는데 위의 코드로 진행해보니 n=8의 경우 터무니도 없는 값이 나와 어떻게 해야하나 생각했다가 다시 조사해보니 2*4가 11개가 되어 dp[n-2]*2 + dp[n-1]로 진행해보니 원하는 값이 나왔다. 여기서 주의할 점은 조건문을 사용하지 않고 출력을 하게 되면 n이 1,2가 나올 경우의 값을 출력하지 못하기에 조건 분기를 아래와 같이는 아니더라도 해줘야할듯! n = int(input()) a, b = 1, 3 if n == 1: print(1) elif n == 2: print(3) else: for _ in range..

역시 수학 공식을 좀 알고 있어야 편하게 알고리즘을 풀 수 있다는 것을 조금 느꼈다... 처음 접한 방법으로는 당연히 조합으로 생각해서 combinations로 구한 다음 길이를 조회해야겠다라고 했지만 시간을 보니 0.5초이기도 하고 해당 방법은 너무 오래 걸릴 것이라는 것을 인지해서 다른 방법이 있을까 하고 짱구를 굴렸지만... 쉽지 않았고 조합 공식을 찾아보니 첫 번째 코드를 구현할 수 있었다. 우선 nCm 조합의 경우 n! / (n-m)! * m! 이 되고 현재 다리 놓기 문제에서는 m이 더 크고 n으로 된 조합의 개수를 찾기에 mCn의 경우가 되어 아래처럼 구현하게 되었음. # 공식을 활용한 풀이 import sys from math import factorial input = sys.stdin...

초기에 생각한 로직으로는 아래와 조금 차이가 있었는데 우선 가장 중요했던 dp에 추가하며 누적합을 시키는 대상 선정으로 현재가 i 라고 했을 때 li[i]+li[-2]+dp[i-3] 와 li[i]+dp[i-2] 중 가장 큰 값만을 출력하도록 했었는데 다른 반례들을 찾아보았을 때 6개 포도주가 있을 경우 1,1,0,0,1,1 의 경우에는 위의 로직으로 셈을 한다면 3이라는 결과가 나오게 된다. 그래서 li[i]+li[-2]+dp[i-4] 를 한 값과도 비교를 해서 더 넓은 범위의 조사를 할 수도 있다는 것을 이해하게 됨 또한 기존 dp의 값으로는 dp[0] = li[0] 으로만 넣고 풀었는데 위에 추가한 로직으로 인해 dp[2] 값까지 추가를 해줘야 하게 되었고 dp[3] 의 값은 내가 생각하기로 경우론 ..

단순히 문제에 나와있는 P(10)까지의 규칙을 확인해보면 해당 위치의 세 번째와 두 번째 위치 전의 값을 더한 값이 현재 위치의 값이 되기에 dp를 활용해서 풀었으며, li를 초기화하지 않고 전역에 놔두며 계속 추가함으로써 n-1번째 값이 현재 li에 있다면 바로 출력해 불필요한 시간을 줄이도록 하는 코드를 작성. li = [1, 1, 1]+[0]*97 for i in range(int(input())): n = int(input()) if li[n-1] != 0: print(li[n-1]) continue for j in range(3, n): li[j] = li[j-3]+li[j-2] print(li[j])

DP를 계속 풀면서 느낀 점으로 더 큰 값을 누적하며 dp를 쌓아 올려갈 때 비교해야 하는 대상 선정이 가장 중요한 것 같다. 처음 해당 문제를 접했을 때 li[i]+dp[i-1] 과 비교할 대상으로 dp[i-1]를 선택했는데 이유는 지금까지 누적한 값의 가장 큰 값 + 현재 값과 현재 값을 더하지 않은 누적 값을 비교해야 하는 거 아닐까? 라는 생각으로 접근했을 때 접근 방법에 대한 문제가 있다고 판단. 그래서 지금까지 누적한 값 + 현재 값과 현재 값부터 다시 시작하기 위한 현재 값만을 비교 후 더 큰 값을 현재 dp 값에 저장하여 문제를 해결 위의 로직을 기반으로 계속해서 각각의 위치에서 시작했을 때 가장 큰 값과 비교가 가능한게 아닐까라는 생각을 함. import sys input = sys.st..

DP를 사용해 이전의 값 중 가장 큰 값을 누적하며 더해가는 풀이 import sys input = sys.stdin.readline n = int(input()) li = [list(map(int,input().split())) for _ in range(n)] dp = [[0]*(i+1) for i in range(n)] dp[0] = li[0] for i in range(1,n): for j in range(i+1): if j == 0: dp[i][j] = dp[i-1][j] + li[i][j] elif j == i: dp[i][j] = dp[i-1][j-1] + li[i][j] else: dp[i][j] = max(dp[i-1][j] + li[i][j], dp[i-1][j-1] + li[i][j]..

문제로는 재귀로 푸는 횟수랑 DP로 푸는 횟수를 말했지만 제출해보니 사실상 둘 다 DP로 푸는 방법이고 재귀로 푸는 DP와 반복문을 통해 중첩해가는 DP로 문제가 구성되어 있다. def fib(n): if dp[n]: return dp[n] else: x = fib(n-1)+ fib(n-2) dp[n] = x return x n = int(input()) dp = [0]*(n+1) dp[1] = dp[2] = 1 fib(n) print(dp[n], n-2) 문제 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍으로 구하는 알고리즘을 배웠다. 재귀호출에 비해 동적 프로그래밍이..

유저가 입력한 데이터를 변수에 담는 방법 controller input 데이터를 담을 변수를 생성 후 TextEditingController() 위젯을 담아주고 var inputData = TextEditingController(); TextField에 controller: input 데이터 담은 변수 이름 을 작성해주면 child: TextField( controller: inputData ,style: TextStyle(fontSize: 30),), 자동으로 변경되는 input 데이터에 대한 value 값이 담겨지게 된다. (이건 좀 편하네) 해당 데이터의 값을 출력하고자 한다면 변수.text를 하면 된다 print(변수.text) onChanged() React에서 사용하는 것과 유사 onChang..

자식 위젯이 부모 위젯의 state 사용 Props를 하는 방법의 단계 보내기 전송할 클래스 즉 하위 위젯, 자식 위젯의 인자 값으로 이름: state 값 을 전송 ex) return Modal( 작명: 보낼 state값 ); 등록하기 받는 클래스에서 인자 값으로 state를 등록 이후 변수 공간에 다시 한번 등록해주기 여기서 JavaScript의 const 역할처럼 변하지 않는 변수 타입으로 Read-Only 만 할 경우엔 final을 붙여주면 된다. 사용하기 그냥 사용하기 현재는 title을 전송해서 Contact라는 변수를 하위 클래스로 전달 후 사용하는 코드 작성 import 'package:flutter/material.dart'; void main() { runApp( MaterialApp( ..