목록백준 (74)
체뚱로그
풀이 시간: 2:00:35 시간 복잡도: O(nlogk) - 이진탐색의 범위가 1 ~ k이면서, for문에서 1 ~ n까지의 합을 계산 공간 복잡도: O(1) - 입력값 저장 변수와 이진탐색을 위한 변수만 사용하고 있음 참고 코드: https://st-lab.tistory.com/281 문제 접근법 예제 입력 1과 같이, n = 3, k = 7일 때, 3*3 배열 A에서 각 위치의 i, j를 곱한 값을 배열 B에 저장한다. A[3][3] 1x1 = 1 1x2 = 2 1x3 = 3 2x1 = 2 2x2 = 4 2x3 = 6 3x1 = 3 3x2 = 6 3x3 = 9 B[3*3] = B[9] 1 2 2 3 3 4 6 6 9 이때, 배열 B의 원소들을 오름차순으로 정렬했을 때의 B[k]값을 구해야 한다. 예제..
풀이 시간: 1:36:56 시간 복잡도: O(mlogn) - 이진 탐색(O(logN) -> 이때 N은 탐색 범위의 크기)을 m번 수행 공간 복잡도: O(n) - name과 power 배열의 크기가 각각 n 참고 코드 https://cjh5414.github.io/binary-search/ https://leeeegun.tistory.com/4 본 문제는 이진 탐색(binary search) 알고리즘을 사용하여 문제를 해결했다. 전체 코드 #include using namespace std; int n, m; // 칭호 개수 n, 캐릭터의 개수 m string name[100000]; // 칭호를 저장하는 배열 int power[100000]; // 칭호에 대한 전투력을 저장하는 배열 // name과 po..