관련 문제 BOJ 가장 긴 증가하는 부분 수열 4 가장 긴 증가하는 부분 수열 (LIS) 가장 긴 증가하는 부분 수열 : 수열의 원소를 순서대로 선택할 때 가장 긴 오름차순인 수열 코드로 구현하기 import java.io.*; import java.util.*; public class Main { static int N; static int[] A; static int[] dp; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); StringTokeni..
Problem Solving/Algorithm
이번 알고리즘 스터디에서 DP를 했는데.. 알고리즘 숙제를 하면서 느낀 점.. 나 혹시 탑다운 DP를 모르나..? 그래서 DP에 대해 다시 정리해보았다. (이전글 +a 해서 재업로드) Dynamic Programming 이란? DP의 핵심 컨셉은 한 번 같은 인자를 넣었을 때 동일한 결과가 나오는 경우 이 결과가 필요할 때마다 다시 연산하지 않고 저장해뒀다가 다시 사용한다. 즉, 한 번 푼 것은 다시 풀지 않는다. 재귀를 이용하여도 문제의 결과를 도출할 수 있다. 하지만 재귀는 다음과 같은 문제점이 있다. 반복적으로 동일한 데이터를 계산한다. 스택에 호출 경로 데이터를 계속 쌓아두어서 stack overflow가 발생할 수 있다. DP에서는 Memoization이라는 기법으로 연산한 결과를 저장하고 연산..
sin sin : 땅과 각도가 x인 빗면을 d만큼 걸어 올라갈 때, 높이는 d의 sin x 배 sin 30º = 1/2, sin 90º = 1, sin 0º = 0 sin 150º = sin 30º = 1/2 sin (-30º) = - sin 30º cosine : co 각의 sine co각 : 90º를 만드는 각 (ex. 30º의 코각? 60º) -> cos 60º = sine 30º 라디안(radian) 각도법 vs. 호도법 각도법 : 원주를 360 등분 한 것의 하나를 1도로 정하여 각을 표현 (일반적으로 ~º 라고 하는 것) 호도법 : 호의 길이를 이용하여 각도를 재는 방법 1 라디안 = 호의 길이가 반지름과 같게 되는 만큼의 각 절대적인 각도로 57.3º에 해당 제 2 코사인 법칙 (직각삼각형 ..
