Algorithm42 [BaekJoon] 백준 2805번 / 나무 자르기 / 이진탐색 / Python 나무 자르기 아이디어 완전 탐색할 경우 시간복잡도는 O(N*N), 10^6 * 10^6 이므로, 시간초과! mid를 기준으로 전체 나무를 자른다. 이때, start 지점이 end 지점과 같아지거나 클때까지 반복 자른 나무의 총길이(SUM) > 가져가야하는 길이(M) start는 mid가 된다. 마치, 최소 높이로 선정하는 흐름이다. 자른 나무의 총길이(SUM) 10^6 * 20 -> 2*10^7 이진탐색 가능 자료구조 나무 리스트 .. 2023. 5. 4. [BaekJoon] 백준 1920번 / 수 찾기 / 이진탐색 / Python 이진탐색 이진 탐색을 위한 공식 st: 시작 인덱스 ed: 끝 인덱스 target: 탐색 대상 숫자 def search(st, en, target): if st == en: // Logic... return mid = (st + en) // 2 if nums[mid] 2억개) 아이디어 연속하다는 특징이 있는가? ==> .. 2023. 5. 3. [BaekJoon] 백준 알고리즘 2470번 / 두 용액 / 투포인터 / Python 문제 접근방법 투 포인터를 이용하여 효율적으로 용액을 선택해나가며 최적해를 찾는 알고리즘이다. 먼저 용액을 오름차순으로 정렬한 후 시작점 start와 끝점 end를 지정하고 두 용액의 합인 mix를 계산한다. 그리고 두 용액의 합의 절댓값이 더 작은 경우 ans와 res를 업데이트한다. 그리고 mix가 0보다 작으면 start를 증가시켜 더 큰 용액을 선택하고, 0보다 크면 end를 감소시켜 더 작은 용액을 선택한다. mix가 0이면 루프를 종료한다. 코드 """ 1. 아이디어 1) N(전체 용액 수)를 입력받아서 sort()를 통해 오름차순으로 정렬 2) for문에서 포인터(start, end)를 이동시키며 최적값(용액 합 0) 도출 2. 시간복잡도 - N(전체 용액 수)는 최대 100,000 이다. .. 2023. 4. 5. [BaekJoon] 백준 알고리즘 1806번 / 부분합 / 투포인터 / Python 문제 주의 최소 길이를 저장하는 변수인 minLength를 충분히 큰 값으로 지정한다. end 포인터? end 포인터는 고정시켜 놓는 것이 아니라, 특정 조건까지 이동시키는 것임. 해당 문제는 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 것이 목표임. 이때, start 포인터와 end 포인터를 사용하여 특정 조건까지 end 포인터를 이동시키면서 부분합을 계산하고, 그 합이 S 이상이 되는 순간 start 포인터를 이동시켜 최소 길이를 구하는 것임. 길이가 0이 될수도 있나? for문에서 start를 1씩 증가시키면서 end를 이동시켜 나가다보면 자연스럽게 처리되므로 별도의 처리를 하지 않아도 됨. 코드 """ 1. 아이디어 - for문을 통해서 투 포인터로 .. 2023. 3. 30. [BaekJoon] 백준 알고리즘 2003번 / 수들의 합 2 / 투포인터 / Python 간단한 투 포인터 알고리즘을 이용하여 풀 수 있습니다. 시작점(start)과 끝점(end)을 이용하여 구간합(interval_sum)을 구하며 end를 이동시키며 구간합이 M과 같아지면 카운트합니다. start를 이동시키면서 구간합(interval_sum)도 갱신합니다. 이 알고리즘의 시간 복잡도는 O(N)입니다. """ 1. 아이디어 - 투 포인터를 통한 계산 2. 시간복잡도 - O(N) : 10,000 < 2억개!, 출력 가능 3. 자료구조 - 수열 저장 int[] - 합계 저장 int - 경우의 수 저장 int """ import sys input = sys.stdin.readline N, M = map(int, input().split()) A = list(map(int, input().split.. 2023. 3. 30. [BaekJoon] 백준 알고리즘 2559번 / 수열 / 투포인터 / Python 문제 접근방법 해당 문제는 연속적인 부분합 중에서 가장 큰 값을 찾는 문제이다. 가장 간단하게 시간복잡도 O(N^2)의 알고리즘으로 구할 수 있다. 그 방법은 완전 탐색 방법으로, 각 구간을 시작하는 인덱스 i와 끝나는 인덱스 j에 대해, i부터 j까지의 합을 구해서 가장 큰 값을 찾는 것이다. 이를 위해서는 2중 반복문을 사용하여 모든 구간에 대해 합을 구해야 한다. 하지만 해당 문제의 N은 100_000 이하로 주어지며, 시간복잡도 O(N^2)이므로 시간초과로 이어질 수 있다.( 2억개 미만이면 가능) 소스 코드 """ 1. 아이디어 - 투포인터 활용 - for문으로, 처음 K개 합산 - 다음 인덱스 더해주고, 이전 인덱스 빼주면서 최대값 갱신 2. 시간복잡도 - 완전 탐색일 경우 O(N^2) -> .. 2023. 3. 28. 이전 1 2 3 4 ··· 7 다음
