체뚱로그

풀이 시간: 02:17:06 시간 복잡도: O(n√n) -> n에 대하여 n 이하의 모든 제곱수에 대한 연산 수행 공간 복잡도: O(n) -> 크기 n인 배열 dp 참고 https://beginnerdeveloper-lit.tistory.com/55 https://hongjw1938.tistory.com/47 https://ip99202.github.io/posts/백준-17626-Four-Squares/= 문제 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 5^2과 1^2의 합이다; 또한 4^2 + 3^2 + 1^2으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는..

풀이 시간: 2:43:12 시간 복잡도: O(U!*U) - 모든 우산 위치에 대한 순열 O(U!) 각 순열에 대한 이동 경로 계산 O(U) 공간 복잡도: O(n*n + U) - 정사각형 격자의 크기 n*n과 우산 위치 저장을 위한 벡터 참고 코드: https://littlesam95.tistory.com/entry/BOJGold-4-백준-22944-죽음의-비C 이 문제는 정답률이 낮은 만큼 매우 복잡하면서도 재밌는 문제였다. 사실 백준을 다시 시작한지 얼마 되지 않았기 때문에 아직 알고리즘에 대한 이해도 부족하고 C++ 문법도 많이 부족했다. 특히 이번 문제를 풀면서 새로 알게된 문법들이 많았다. 다음에는 다른 문제를 풀 때 이 문법들을 활용해서 답을 좀 더 효율적으로 구현하고 싶다. pair 클래스 사..

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