프로그래밍/알고리즘2 시간 복잡도에 대해 알아보자 시간 복잡도란 무엇인가?시간 복잡도(Time Complexity)는 알고리즘의 실행 시간이 입력 데이터의 크기와 어떻게 변하는지를 수학적으로 분석한 것이다.알고리즘의 효율성 및 최적화 등을 평가할 때 사용되며, 프로그램이 실행되는 데 걸리는 시간을 예측할 수 있다.만약 컴퓨터가 초월적인 존재라 어떤 스파게티 코드를 짜든 항상 빠른 성능을 보여준다면 아무리 비효율적인 코드라고 해도 일단 작동된다면 사용했을것이다. (물론 가독성은 중요하다!)하지만 컴퓨터는 한정된 공간과 연산 속도를 가졌고 이를 효율적으로 사용하기 위해서는 최적화된 알고리즘을 사용해야하며 이 알고리즘을 시간 복잡도를 통해 분석하는 것이다. 시간 복잡도 분석의 필요성성능 평가동일한 문제를 해결하는 여러 알고리즘 중, 실행 시간이 짧고 효율적인.. 2024. 12. 10. 동적 계획법(DP) 에 대해 알아보자 동적 계획법(Dynamic Programing)동적 계획법은 복잡한 문제를 풀기 위한 알고리즘 설계 기법 중 하나로, 문제를 작은 하위 문제(subproblem)로 나누고, 이 하위 문제의 해를 재활용하여 전체 문제를 푸는 방법이다.이러한 동적 계획법은 분할 정복(Divide & Conquer) 알고리즘과 매우 유사한데 큰 문제를 작은 하위 문제로 나눈다는 공통점이 있다. 차이점이라면 작은 하위 문제로 나눈때 독립된 하위 문제로 나눌것인지(분할 정복), 중복되는 하위 문제로 나눈것인지(동적 계획법)에 차이가 있다.핵심 개념동적 계획법의 중요한 개념은 다음과 같다.최적 부분 구조(Optimal Substructure) 하위 문제의 해가 큰 문제의 해를 구할 수 있어야 한다예: 피보나치 수열 F(n)=F(n.. 2024. 11. 21. 이전 1 다음
