csmoon1010의 SW 블로그

0. 문제유형 : Dynamic Programming(동적계획법) 1. 문제이해 programmers.co.kr/learn/courses/30/lessons/12980 코딩테스트 연습 - 점프와 순간 이동 OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈 programmers.co.kr (1) 주요 요구사항 ① 2가지 액션을 통해 N만큼 떨어진 장소로 이동 - 점프 : 앞으로 K칸 이동. 건전지가 K만큼 사용. - 순간이동 : (현재까지 온 거리) * 2 만큼 이동. 건전지 사용 없음. ② 2가지 액션을 취해 건전지 사용량을 최소화 = 최대한 점프의 횟수를..

1. 문제 이해 - 피보나치 수의 정의 : F(0) = 0, F(1) = 1일 때, F(n) = F(n-1) + F(n-2)가 적용되는 수 ex> 0 1 1 2 3 5 8 13 . . . - n번째 피보나치 수를 1234567로 나눈 나머지를 리턴 2. 전략 (1) 첫번째 시도 : 재귀함수를 이용 int Fibonacci(n){ if(n == 0) return 0; else if(n==1) return 1; else return Fibonacci(n-1) + Fibonacci(n-2); } - 문제점 : 불필요한 중복 계산이 들어감(Fibonacci(n-1)을 구할 때 Fibonacci(n-2)를 한 번 더 구함) → 시간 초과 (2) 두번째 시도 : int 배열에 0~n번째 피보나치 수를 차례로 저장 ..

1. Dynamic Programming이란? : 복잡한 문제를 "작은 문제"로 나누어 푸는 방법 - "작은 문제"에서 최적의 결과 → 전체의 최적의 결과 - 앞에서 구한 결과를 다음 계산 때 이용하는 방향 (재사용) 2. 방식 1) 하향식 알고리즘(Top-Down) : 큰 문제에서 재귀함수를 호출하여 푸는 방식 → "작은 문제"가 중복되어 풀림 ex> 막대 자르기 문제 : 어떻게 잘라야 최대 이익으로 팔 수 있는가(길이에 따라 가격 책정이 다름) Function cutRod(p, n){ if(n = 0) return 0; q

1. 문제 이해 - int[][] land : N행 4열의 배열 - 다음 규칙을 만족하여 얻을 수 있는 점수의 최대값을 return 1) 1행에 1칸의 땅을 선택 2) 같은 열의 칸을 연속해서 선택은 불가 2. 전략 1) Dynamic Programming(동적 계획법) 이용 n행에서의 점수 최대값 = max{ (0~n-1행까지의 최대값) + (n행 후보1), (0~n-1행까지의 최대값) + (n행 후보2), ...} - 상향식 알고리즘 : 작은 문제(0행부터 내려오기)부터 풀기 시작 - 재귀적 성질 : 0~n-1행까지 어떻게 오든 최적의 계산값(여기서는 최대값)을 활용 → 계산 결과를 land에 저장하여 누적 1 2 3 5 5 6 7 8 4 3 2 1 1 2 3 5 5 + 5 = 10 5 + 6 = 1..