본문 바로가기

알고리즘/동적프로그래밍

 (13)
백준 - 계단 오르기 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. https://github.com/ROUTINE-STUDY/Algorithm 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능 초보 알고리즘 스터디 / 누구나 참여 가능 :runner:. Contribute to ROUTINE-STUDY/Algorithm development by creating an account on GitHub. github.com 문의는 댓글 바람. 문제 출처 :https://www.acmicpc.net/problem/2579 [문제 설명] [접근 방법] 다이나믹 프로그래밍 거..
백준 - 연속합 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/1912 [문제 설명] 동적프로그래밍으로 연속부분최대곱 문제를 보다가 전에 이거랑 비슷한 문제가 있었다는 생각이 들어서 풀었다. [자바] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; class Main { public static void main(String[] args) throws IOException { // 입력 받기 BufferedRe..
백준 - 이름 궁합 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/15312 [문제 설명] 이름 알파벳으로 궁합 맞추기 [접근 방법] 처음엔 Deque를 이용해서 풀었는데, 삭제 연산 때문에 시간이 오래 걸렸다. 두번째엔 그냥 배열을 이용하여 풀었다. 풀어보니 굳이 시간이 오래 걸리는 자료구조를 사용할 필요 없어 보였다. 배열은 인덱스로 메모리에 직접 접근하므로, 시간 복잡도도 빨라졌다. 전체 시간복잡도는 O(N!)이 아닐까 싶다. (연산하는 원소가 N,N-1,N-2, ... ,5,4,3,2,1순으로 하강하니까) [내 답안 수정하..
2747 피보나치 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. [처음 생각한 접근 방법] 오늘 문제는 Dynamic Programming의 예제를 풀어보았습니다. 피보나치의 경우 f(n) = f(n-1) + f(n-2)라는 점화식이 나오는데 이를 구현하는 문제입니다. Dynamic Programming을 이용하면 매번 f(n) 값을 구할 필요가 없습니다. f(n)의 값을 한 번 구하면 그 값을 배열에 저장해놓았다가, 다시 이 값을 찾을 때 배열에 저장 되어 있는 값을 리턴하면 됩니다. import java.io.BufferedReader; import java.io.IOException; impo..
509. Fibonacci Number 문제출처 피보나치 수열이 있을 때 수열의 n번째 값을 구하는 문제. 옛날에 수학시간에 봤던 기억은 났지만 기억이 잘 안나서 그냥 주어진 F(n)식을 이용해서 풀었다. [처음 푼 코드] class Solution { public int fib(int n) { if (n == 0) return 0; if (n == 1) return 1; int[] arr = new int[31]; arr[0] = 0; arr[1] = 1; for (int i = 2; i

티스토리툴바