𝚔𝚎𝚎𝚙 𝟿𝚘𝚒𝚗𝟿

코딩 테스트시간 복잡도빅 오 표기법big-O (빅 오 표기법) : O() => 최악의 경우, worst case점근적 상한선입력 크기가 무한대로 갈 때점근적 상한(아무리 나빠도시간이 이보다 덜 걸림. 즉, 최악의 시나리오)주로, 빅 오 표기법을 사용함계산 방법가장 큰차수 만 고려 : 예) n2 + n + 1 => O(n2)계수는 1 로 함 : 예) 3n => O(1n) => O(n)작은 차이는 무시 : 예) O(n-1) => O(n)규모가 큰 것 만 고려 : 예) O(2n + n2) => O(2n)크기 순서$$ O(1) ⏩ 오래 걸림 공간 복잡도코딩 테스트에서 문제가 되는 경우는 많지 않음.재귀 구현할 때 정도? 입력방법: 첫째 줄에 정수의 개수 N (= 10,000,000), 둘째 줄부터 N개의 줄에 ..

한 번 해결된 부분 문제의 정답을 메모리에 기록하여 한 번 계산한 답은 다시 계산하지 않도록 하는 문제 해결 기법. 다이나믹 프로그래밍은 점화식을 그대로 코드로 옮겨서 구현할 수 있다. 점화식이란 인접한 항들 사이의 관계식을 의미한다. 조건 최적 부분 구조(Optional substructure) 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음 중복되는 부분 문제(Overlapping Subproblem) 동일한 작은 문제를 반복적으로 해결해야 함 예시 (문제 링크 추가 예정) 다이나믹 프로그래밍을 이용한 소스코드를 작성하는 방법 두가지 1. Top-down : 메모이제이션 (Memoization) 재귀 함수를 이용하여 큰 문제를 해결하기 위해 작은 문제를 호..