본문 바로가기

🔅코딩테스트 공부🔅/❗그 외 추가 공부4

[구간 합] 접두사 합 구간 합의 시간복잡도는 O(NM)이다. N,M의 데이터가 커지면 시간복잡도가 증가하게 되어 문제가 발생한다. 이럴 경우 구간 합 혹은 누적 합 계산을 빠르게 하기 위해 접두사 합을 이용하면 된다. 접두사 합은 리스트의 맨 앞부터 특정 위치까지의 합을 미리 구해놓은 것이다. 아래를 코드를 실행시키면 sum value = [0, 10, 30, 60, 100, 150] 이 되며 sum_value[right] - sum_value[left-1] 을 해주면 빠르게 구할 수 있다. n = int(input()) data = [10,20,30,40,50] sum_value = 0 prefix_sum = [0] for i in data: sum_value += i prefix_sum.append(sum_value) l.. 2023. 2. 26.
❗문제 메모 - 그래프❗ 해결한 문제의 양이 증가하면서 좋은 문제를 양치기만 하고 끝내면 안 될 것 같다는 생각이 들었다. 이 게시물에 푼 문제들에 대한 간단한 기록을 남겨보고자 한다. ## 노란색 복습 필요 x ## 초록색 복습 필요 o ## 빨간색 복습 진행 했으나 아직도 어려움 ## 보라색 개중요 ## 회색 잘 풀었는데 다시 보면 좋을 듯? 깊이 우선 탐색 / 넓이 우선 탐색 백준 2468번 안전영역 (실버1) / 2667번 단지번호 붙이기(실버1) 문제를 풀며 단지번호 붙이기와 유사하네? 라는 생각이 들었다. 우선 안전영역 문제는 비가 점점 차오른다고 가정했을 때, 각자 떨어져 있는 안전영역의 개수를 세고 -> 비가 점점 차오르던 각각 시기의 안전영역 개수 중 가장 큰 값을 return 하는 문제이다. 단지번호 붙이기는 .. 2023. 2. 23.
[수학] 피보나치 수 구현하는 여러 방법 1. 피보나치 수 첫 번째 항을 0, 두 번째 항을 1로 한 후, 이후의 항들은 이전의 두 항을 더한 값으로 이루어진 수열 2. 재귀함수 이용하기 => 비효율 n = int(input()) def fibo(n): if n == 0 or n == 1: return n else: return fibo(n-1) + fibo(n-2) print(fibo(n)) 3. 행렬 이용하기 n = int(input()) def fibo(n): f1 = 0 f2 = 1 for i in range(2, n+1): f3 = f1 + f2 f1 = f2 f2 = f3 return f2 print(fibo(n)) 4. list 이용하기 n = int(input()) def fibo(n): arr = [0,1] for i in ra.. 2023. 2. 13.
[수학] 에라토스테네스의 체(with python) 백준 1978번 솔루션을 구글링해보니 '에라토스테네스의 체'를 이용한 풀이가 종종 보였다. 참고 링크 :https://gururuglasses.tistory.com/80 [ Algorithm ] 에라토스테네스의 체 ( Python )( 소수를 구하는 방법) 고대 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이다. 이 방법은 체로 치듯이 수를 걸러낸다고 해서 '에라토스테네스의 체' 라고 불린다.소수를 구하는 방법은 여러가지가 존재하지 gururuglasses.tistory.com 에라토스테네스의 체? O(NloglogN)의 시간복잡도를 이용해 소수를 찾는 방법으로 2부터 N까지의 모든 소수를 찾는 방법이다. 다수의 소수를 찾을 때 유용하나 메모리가 많이 필요하다는 단점이 있다. 따라서 n이 1,000.. 2023. 1. 21.

티스토리툴바