남남이루의 고군분투 🌳

프로그래머스 lv.2 양궁 대회문제 바로가기문제 요약어피치가 양궁을 먼저 다 쐈다. 화살의 수와 어피치의 과녘 현황을 입력값으로 줬을 때, 라이언이 어떻게 과녘을 맞춰야 최대 점수차이로 이길 수 있는지 반환해라.주의할 점최대 점수 차이가 같을 경우, 낮은 점수에 많이 맞은 경우를 답으로 처리한다.배열에 해당하는 과녘은 10점 과녘부터 0점까지 순서대로 주어진다.문제 접근완전 탐색에 조기종료 조건이 가능하므로 DFS를 사용한 백트래킹과녘의 수가 고정되어 있기 때문에 점수 현황을 고정 길이의 배열로 만들어서 과녘의 선택/ 미선택 두개의 정보를 담을 수 있다.조기 종료 조건 (유망함수)남은 화살이 더이상 없을 때.과녘의 끝에 다다랐을 때.오답노트1. recursive overflow 에러 발생.- DFS 접근..

다익스트라가 사용되는 때알고리즘 접근법 중 다익스트라는 가중치가 있는 그래프에서 최소 비용 경로를 구할 때 주로 사용한다. 파이썬에서의 다익스트라는 큐에서 가장 최소값을 꺼내기 위해 내장 라이브러리인 heapq를 사용하면 됐었지만 기본 자바스크립트에서는 heap을 지원하지 않기 때문에 직접 구현해서 쓸 수 있다.다익스트라의 구현큐에서 가장 최소값을 꺼내기 위해 heap이 아닌 우선순위큐를 구현해서 할 수도 있지만, 두 방식은 시간 복잡도에 큰 차이가 있다.구체적인 구현 방식을 서술해보자면, 우선순위 큐(Priority Queue)는 요소의 추가(삽입, push) 혹은 제거(꺼내기, pop)때 마다 정렬을 새로 해줘야 한다. 자바스크립트의 내장 sort는 N*logN 의 비용이 들고, 제거할 때 조차 배열..

문제 : 연속된 부분 수열의 합 프로그래머스 문제 바로가기 조건 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 ..

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