devrabbit22 님의 블로그

백준 - [단계별로 풀어보기 시간 복잡도] 24266 알고리즘 수업 - 알고리즘의 수행 시간 5

이번 문제는 반복문이 세 번 사용된 알고리즘이다. 이전 문제인 24265처럼 반복문의 실행 횟수가 서로 다른 구조가 아니라, 세 개의 반복문이 모두 동일한 범위에서 반복된다.일반적으로 반복문이 하나 사용될 때마다 시간 복잡도는 n만큼 증가하게 된다. 따라서 반복문이 세 번 사용되었다면 실행 횟수는 n × n × n이 되고, 이는 n³ 형태가 된다. 여기서 알 수 있는 사실은 시간 복잡도는 O(n³)이며, 최고차항의 차수는 3이 된다. 추가로 이 문제를 풀면서 처음에는 Math.Pow를 사용해 n³을 계산했지만 틀렸다는 결과를 받게 되었다. 그 이유는 Math.Pow 연산의 반환 타입이 double이기 때문이다.백준에서는 정수 형태의 출력이 필요하기 때문에 실수형 값이 출력되면 오답이 된다. 따라서 Mat..

백준 - [단계별로 풀어보기 시간 복잡도] 24265 알고리즘 수업 - 알고리즘의 수행 시간 4

이번 문제는 기존의 시간 복잡도 문제와 달리 수학 공식을 활용하여 실행 횟수를 계산해야 하는 문제이다.알고리즘 구조를 보면 이중 반복문이 사용되지만, 두 반복문의 실행 횟수가 서로 다르다.for i = 1 to n-1 for j = i+1 to n예를 들어 n = 7일 때 i는 1부터 6까지 총 6번 반복된다. 그리고 j의 반복 횟수는 다음과 같이 줄어들게 된다.더보기i = 1 → j : 2 3 4 5 6 7 (6번) i = 2 → j : 3 4 5 6 7 (5번) i = 3 → j : 4 5 6 7 (4번) i = 4 → j : 5 6 7 (3번) i = 5 → j : 6 7 (2번) i = 6 → j : 7 (1번)따라서 j의 반복..