동적 계획법

[CS스터디]220707 자료구조 - 3

BST의 최악의 경우의 예와 시간복잡도에 대해서 설명해주세요. 한쪽으로 몰리는 경우(계속해서 작은 수가 들어오는 경우, 계속해서 큰 수가 들어오는 경우)가 최악의 경우 평균적으로는 O(logN)인 시간 복잡도가 이 경우엔 O(N)으로 증가함! 피보나치 수열을 코드로 구현하는 방법에 대해서 설명해주세요. 재귀 or 동적 계획법(탑다운, 바텀업 방식이 있음) 재귀 단순한 재귀로 구현할 경우, 시간 복잡도가 너무 크게 나올 수 있기 때문에 동적 계획법을 활용하여 구현하는게 좋음 ! 동적 계획법 Top-Down 말 그대로 위에서 아래로 진행하면서 답을 구하는 방식, 흔히 재귀 호출을 이용해 구현. 100번째 피보나치 수를 찾기 위해 99번째, 98번째 수를 찾고, 그들을 찾기 위해 97번쨰, 96번째 수를 찾는..

[프로그래머스]정수 삼각형 - Java

문제 https://programmers.co.kr/learn/courses/30/lessons/43105?language=java 풀이 DP 문제임. DP 문제는 보면 뭔가 DP 문제 같은데 어케 푸는지 모르는 경우가 허다한 것 같음 ㅠ 근데 오랜만에 맞춰서 좀 좋았음 ㅎㅎㅎㅎㅎ 삼각형의 위에서 부터 내려오면서 더해주는게 아니라 새로운 2차원 배열을 만들어서 거꾸로, 그니까 밑에서 부터 올라가면서 비교하면서 새로운 배열에 최대값을 저장해주는 식으로 풀었음! 어떻게 푸는지 떠올리기만 하면 쉽게 풀리는게 DP의 매력아닌 매력인 것 같음! 코드 // 코딩테스트 연습 - 동적계획법 - 정수 삼각형 // https://programmers.co.kr/learn/courses/30/lessons/43105?lan..