redco
2022.03.10
@redco님이 새 포스트를 작성했습니다.
이분 탐색 응용_3일차 Quiz
def max_length(arr, target):     start = 0                                            end = max(arr)                                         while(end - start >= 0):         n = 0                                                    mid = (start + end) // 2                 for i in arr:             n += (i // mid)                 if (n == target):             result = mid             break         elif(n > target):                 start = mid + 1             else:             end = mid - 1            print(result)      arr = [215, 513, 712, 803] target = 10 max_length(arr, target) 렌선개수: 200
redco
2022.03.08
@redco님이 새 포스트를 작성했습니다.
시간 복잡도 구하기_2일차 Quiz
1️⃣ C언어 int a = 0, b = 0; for (i = 1; i < N; i++) { a = a + i } for (j = 2; j < M; j++) { b = b + j } 코드설명: for반복문을 사용하여 첫번째는 N-1번, 두번째는 M-2번 각각 반복된다. 시간 복잡도: N과 M모두 상수이므로 각각의 시간 복잡도는 O(n)이고 전체 코드 역시 O(n)+O(n)=2O(n)=O(n)의 원리에 따라 O(n)의 시간 복잡도를 가진다.(Big-O표기법의 상수항을 무시하는 특성, 선형적으로 증가) 2️⃣ C언어 a = 0, b = 0; for (i = 0; i < N; i++) { for (j = 0; j < N; j++) { a = a + j; } } for (k = 0; k < N; k++) { b = b + k; } 코드설명: 첫번째 반복문은 중첩 for문을 사용하여 N^2번 반복되고, 두번째 반복문은 N번 반복된다. 시간 복잡도: 각각의 시간 복잡도는 O(n^2), O(n)이지만 전체 코드로 볼 때 시간 복잡도는 O(n^2)+O(n)=O(n^2)으로 O(n^2)의 시간 복잡도를 가진다.(Big-O표기법으로 시간 복잡도를 나타낼 때는 최고차항만 표기하고 상수항은 무시한다.)