![]()
contentsdatad이분 탐색 알고리즘, 백준 1920번 2024.07.31 이분 탐색은 정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법 범위를 절반으로 줄여나가는 건 이분 탐색의 탐색법입니다. 선형 탐색은 O(N)에 동작하고 이분탐색은 O(lg N)에 동작하기 때문에 N이 커지면 커질수록 큰차이의 속도가 발생한다. 이분 탐색의 구현 방법 이분 탐색의 구현은 1. 배열을 먼저 정렬을 시킨다. 2. start와 end 변수를 적립해준다. 그래서 start는 맨 처음 end는 맨 뒤로 나누어 전체 범위를 나타내도록 한다..3. 범위를 절반으로 줄이기 위해서 mid = (start+end)/2 지점으로 ..
Contentsdated투 포인터 backjoon 1644 ,2003,25592024.07.22 투 포인터는 말 그래도 포인터 두개를 정해서 리스트에서의 계산 범위를 줄여주는 알고리즘을 수행한다. 이것을 수행하는 이유는 계산 시간을 획기적으로 줄여주기 때문이다. 실제로 필자는 이중 for문을 이용해서 쉽게 문제가 풀릴거 같아서 이중 for문으로 투포인터 문제를 접근했으나 시간 초과 오류가 계속 해서 나왔다. 이중 for문의 경우 시간 복잡도가 O(n2)인데 반해 투포이너는 log (n)의 수준에서 머물기에 획기 적인 것이다. 투포인터의 핵심은 start와 end의 포인터를 지정해서 list 자체는 그대로 두고 start와 end 포인터들만 움직이는 것이다. backjoon 2003#시간 초과한 풀..
![]()
contentsdated라인 스위핑 개념 + 백준 2017번 2024.07.20 라인 스위핑(line Sweeping) 알고리즘은 선 하나를 여러 가지 상황에서 움직이면서 문제를 해결하는 것이다. 즉 한 번만 전체 공간을 스캔하면서 마주치는 요소들에 대해 판단기준이 되는 기준을 적용해 주면 정답이 정답이 구해지는 형태이다. 정렬된 요소들을 한 번만 순회하면 연산 하면 정답이 나오는 구조 이다, backjoon 2107번import sysinput = sys.stdin.readlinen = int(input())lines = []for _ in range(n): lines.append(tuple(map(int, input().split())))lines.sort()left = lines[0][..
![]()
contentsdated그리디 알고리즘 소개 (바크킹)backjoon 1931, 2217, 1026 2024.07.18 Greedy = 지금 가장 최적인 답을 근시안 적으로 택하는 알고리즘 = 관찰을 통해서 탐색 범위를 줄이는 알고리즘 이상적인 알고리즘 풀이 1. 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다. 2. 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명한다. 3. 구현해서 문제를 통과한다. 현실적인 알고리즘 풀이 1. 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다. 2. 탐색 범위를 줄여도 올바른 결과를 낸다는 강한 믿음을 가진다. ..
