잡다한 IT 지식

태그 잊지 않고 붙이세요#Algorithm #sw_expert_academy #D3 #Solved문제 링크제한사항첫 줄에 테스트케이스의 수 T가 주어진다. 1다음 줄부터 테스트 케이스의 별로 T, T_end, k가 주어진다.1문제 정리함정 문제다. 문제 초반에 python 코드를 주고 비용이랑 이전 비용 차이 cost 함수 등 많은 정보를 주지만 다 필요 없는 내용이다.우리가 구할 값은 T에 K를 몇 번 곱하면 T_end보다 작아지느냐다.예제 1은 1000 0.1 0.8이 주어진다. 여기서 1000에 0.8^42의 값이 0.1보다 작아진다.접근 방법단순하게 반복문으로 T_end보다 작아질 때까지 곱한다. 이걸로 통과된다.복잡도시간복잡도는 x를 반복횟수라고 생각했을 때$T * k^x $x $O({ln(Te..

태그 잊지 않고 붙이세요#sw_expert_academy #binary_search #D3 #Solved문제 링크제한사항11문제 정리이분 탐색 과정 중에 왼쪽 오른쪽을 번갈아 검색한 경우의 개수를 구해라.접근 방법단순한 이분 탐색 구현 문제다. 단, flag 값을 통해서 이전에 왼쪽을 탐색했는지 혹은 오른쪽을 탐색했는지 판별하면 된다.A가 정렬이 필요하므로 NlogN이 필요하고 추가적으로 M개 원소를 이진 탐색하므로 M*logN이 필요하다.복잡도시간복잡도: 정렬 + M개 원소를 이진탐색 = O(N * logN) + O(M * logN) = O(N * logN + M * logN) = O((N + M) * logN)공간복잡도: O(N + M)코드T = int(input())# 여러개의 테스트 케이스가 주어..