Seung's Learning Record

난이도 : 실버2 소요시간 : 27m 사용한 풀이법 : DP 풀이 과정 입력받은 문자열을 정수형 리스트 arr[]로 변환 dp[]에는 해당 인덱스에서 가질 수 있는 최대값을 넣는다 dp[i-1]+arr[i]가 음수일 경우 최대값 생성에 방해가 되므로 해당 dp값은 0으로 초기화 원래는 여기서 풀이를 끝낼라했는데 모두 음수일 경우를 고려안하게 생각나서 dp첫번째 조건문 뒤에 arr값을 dp값으로 초기화 해주는 코드 추가 ⇒ 내가 생각해도 좀 후진 코드..ㅎ 원래는 max(dp)를 하려했으나 위 코드 추가되면서 max(arr)로 변경 다른 풀이 입력받은 문자열을 정수형 리스트 arr[]로 변환 현재합과 최대합 연산용 변수 선언 arr을 돌면서 해당 인덱스와 해당 인덱스에 현재합을 더한 것중 max를 현재합에..

난이도 : 실버2 소요시간 : 48m 사용한 풀이법 : DP 풀이 과정 dp용 리스트 선언 각 인덱스에는 1로만 표현했을경우의 개수를 넣는다. 즉, 인덱스 번호를 그대로 대입! 루프를 돌면서 DP탐색 시작 인덱스 번호보다 작은 제곱 수 중에서 가장 큰 값을 찾는다. 현재 인덱스 번호에서 해당 제곱 수를 뺀 인덱스 번호에 +1을 한 후, 대소비교를 진행한다. ex) dp[10] = dp[10-33]+1 = dp[1]+1 (11 + 3*3, 2개!) +1을 하는 이유는 앞선 dp[]값에 제곱 수의 경우가 하나 추가되는 것이기 때문 작성 코드 import math N = int(input()) dp = [x for x in range(N+1)] for i in range(1, N + 1): for j in r..

난이도 : 실버3 소요시간 : 31m 사용한 풀이법 : DP 풀이 과정 dp용 리스트 선언 후 0으로 초기화 dp 리스트는 인덱스 숫자가 1이 되기까지의 최소연산횟수를 저장하는 용도 2~n+1까지 루프 실행 dp[i] = dp[i-1]+1 : i번째 수는 i-1번째 수의 dp값에 +1을 한것을 디폴트로 둔다 만일 i가 2나 3으로 나누어 떨어진다면, i에 2를 나눈 몫의 수에 해당하는 dp값과 디폴트값을 비교하여 최소값을 선택한다 작성 코드 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[..

난이도 : 실버3 소요시간 : 23m 사용한 풀이법 : DP 풀이 과정 dp[1] = 1 => 1 dp[2] = 1+1, 2 => 2 dp[3] = 1+1+1, 1+2, 2+1, 3 => 4 dp[4] = 1+1+1+1, 1+1+2, 1+2+1, 1+3, 2+1+1, 2+2, 3+1 => 7 위의 식을 잘 보면 1로 시작하는 건 곧 1+3 인거라서 3을 이루는 덧셈의 경우의 수, 즉 dp[3]만 알면 됨 2로 시작하는건 2+2라서 dp[2]만 알면되고 3으로 시작하는건 dp[1]만 알면 됨. dp[5]를 예시로 들어보자 1+…. 일때는 4를 이루는 경우들만 알면 됨 ⇒ dp[4] == dp[5-1] 2+…. 일때는 3을 이루는 경우들만 알면 됨 ⇒ dp[3] == dp[5-2] 3+…. 일때는 2를 이루..

난이도 : 실버1 소요시간 : 1h 17m 사용한 풀이법 : DP 풀이 과정 풀이과정(백트래킹) 각 요소[i][j]는 대해서 [i+1][j],[i+1][j+1]만 더할 수 있음 해당 위치에서 이동가능한 경로를 인자로 해서 함수 재귀 진행 인자가 n과 같아지면 결과갑 리스트에 삽입 모든 경우의 수 탐색 후 리스트의 max를 출력하면 정답!! 이긴 한데 메모리 초과 뜸 풀이과정(DP) 위에꺼에서 아래꺼를 더하는 방식이 아닌 아래꺼에서 위에 값을 참조해오는 것으로 변경 =>메모리 손실 방지 참조 방식은 총 3가지 행의 첫번째 인자일 경우, 바로 위 행의 첫번째 인자값에 더하면 됨 ([i-1][0]) 행의 마지막 인자일 경우, 바로 위 행의 마지막 인자값에 더하면 됨 ([i-1][-1]) 행의 중간일 경우, 바..