체뚱로그

풀이 시간: 3:25:29 시간 복잡도: O(nlogS) - S는 배열의 합(sum)을 의미, for문을 통해 0 ~ n까지 선형 탐색 공간 복잡도: O(n) - n은 배열의 크기 참고 코드 https://leesh111112.tistory.com/356 https://ohcode.tistory.com/17 https://8156217.tistory.com/46 본 문제는 정말 헷갈리는 문제였다. 결국 못풀고 솔루션을 참고하게 되었는데, 솔루션을 보고도 한참 헤맸던 문제이다. 특히 저 check 함수가 이해가 처음에 잘 되지 않아서 내 나름대로 코드를 이해하면서 주석을 달아보았다. 까먹지 않기를. 전체 코드 #include #include // INT_MAX 사용 using namespace std; i..

풀이 시간: 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..