남남이루의 고군분투 🌳

문제 : 연속된 부분 수열의 합 프로그래머스 문제 바로가기 조건 1. 오름차순으로 정렬된 배열 조건 2. 배열의 길이 ≤ 1,000,000 요구사항 : 구간합이 특정 값이 되었을 때, 구간의 인덱스를 반환하라 단, 여러 구간이라면 길이가 짧은 구간을 채택하고, 길이마저 같다면 시작인덱스가 작은 구간을 채택하라. 접근 배열의 크기가 10^6이기 때문에 O(n^2) 알고리즘은 사용할 수 없다. 정렬된 배열의 특성을 최대한 이용한다. 구간합에 관한 문제이기 때문에 투포인터를 사용할 수 있다. (이진탐색은 특정 값을 찾는 데 사용) 내 풀이 def solution(sequence, k): sp = 0 ep = 1 tot = sequence[0] sequence+=[0] answer = [] chance = 1 ..

그리디와 이분탐색 왜 이분 탐색 다음에 그리디 알고리즘이 나왔느냐- 둘다 분할 정복, 재귀함수를 사용한다는 공통점이 있어 결이 비슷하기 때문이다. 그리디란? 그리디 알고리즘의 경우, 가장 좋은 해부터 찾아내고 나머지는 쪼개는 방식으로 진행한다. 밥먹을 때 제일 맛있는 반찬부터 먹는 욕심쟁이를 닮은 알고리즘 이랄까. 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법으로, 이것이 전체로 봤을 때도 최선이길 바라는 알고리즘이다. 따라서 적용할 수 있는 문제의 조건이 조금 까다로운 편이다. 비슷해 보여도 그리디를 쓸 수 있는 문제가 있고, 아닌 게 있다. 예를 들어, 동전을 사용해 어떤 금액을 표현하는 문제는 그리디로 풀리는데, 동전의 단위가 배수-약수관계가 아니면 그리디 알고리즘을 쓸 수 없다...