Algorithm272 [ 자바스크립트(JavaScript) ] section08 - 1 - 재귀함수 📍 section08 - 1 - 재귀함수 이번 섹션은 재귀 함수와 완전 탐색(깊이 우선 탐색: DFS)을 배운다. 이전부터 재귀 파트는 어려움을 많이 호소했는데, 이번 섹션을 통해 감을 되찾았으면 좋겠다. 첫 번째 문제는 자연수 N이 입력됐을 때 재귀 함수를 이용하여 1부터 N까지 출력하는 문제다. 이전에 코드업에서 python으로 한번 풀어봤다. 예전에 재귀 문제를 풀었을 때는 하단 before 방법처럼 호출된 재귀 함수를 적고 return이 나오면 다시 올라가는 방법을 사용했는데, 이것의 단점은 재귀가 깊어지면 어떤 코드에서부터 다시 진행해야 하는지 헷갈려서 많은 어려움을 겪었다. 하지만 강의 선생님께서 after 방법처럼 현재 호출된 재귀 함수와 호출된 코드라인을 적어두면 다시 돌아왔을 때 어디서부.. 2021. 9. 15. [ 자바스크립트(JavaScript) ] section07 - 12 - 마굿간 정하기(결정 알고리즘) 📍 section07 - 12 - 마구간 정하기(결정 알고리즘) 문제: N개의 마구간이 수직선상에 있다. 각 마구간은 x1, x2, x3, ..., xN 의 좌표를 가지며 마구간 간에 좌표가 중복되는 일은 없다. 현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않는다. 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶다. 입력: 첫째줄에 자연수 N과 C의 공백을 사이에 두고 주어지고 둘째줄에 마구간의 좌표가 차례로 주어진다. 출력: 첫 줄에 가장 가까운 두 말의 거리를 출력하시오. // 입력 5 3 1 2 8 4 9 // 출력 3 이 문제를 왜 Parametric Search 으로 풀어야 하는지 생각해보면, 가장 가까운 두 말의 거리가 최대가 될 때까지 .. 2021. 9. 15. [ 자바스크립트(JavaScript) ] section07 - 11 - 뮤직비디오(결정 알고리즘) 📍 section07 - 11 - 뮤직비디오(결정 알고리즘) 이분탐색 알고리즘을 응용해서 푸는 문제다. 보통 이분탐색을 이용한 문제는 파라메트릭서치(Parametric Search) 알고리즘의 방법으로 풀게 되는데, 이는 값의 최댓값 혹은 최솟값을 구하여 결정문제로 바꾸어 풀 수 있다. 결정 알고리즘과 같은 문제는 탐색 범위가 큰 상황에서의 탐색을 가정하는 경우가 많으므로 탐색 범위가 20,000,000(이천만)을 넘어가면 이진 탐색으로 접근해보자. 범위가 10,000,000(천만) 이상으로 넘어가면 이진 탐색처럼 O(logN)의 속도를 내야 하는 알고리즘을 떠올려야 풀 수 있는 경우가 많다. 파라메트릭 서치의 주요 특징은 범위 내에서 조건을 만족하는 값이 있더라도 거기서 끝나는 것이 아니라 그것보다 더.. 2021. 9. 14. [ 자바스크립트(JavaScript) ] section07 - 10 - 이분검색 📍 section07 - 10 - 이분검색 이분검색은 시간 복잡도가 O(logN)으로 선형 검색인 O(N)보다 빠른 특징을 가지고 있다. 대량의 데이터를 탐색할 때 효과적인데, 예를 들어 1,000,000개의 데이터에서 특정 값을 찾는다고 가정하면, 반복문을 사용해 선형적으로 탐색하면 최악의 경우 백만번을 돌아야 하지만 이진탐색(binarySearch)을 이용하면 최대 11번까지 돌면 된다. 하지만, 이진탐색은 오름차순 혹은 내림차순으로 정렬되어있어야 찾을 수 있는 전제조건이 있다. while문의 범위는 lt a - b); while (lt target) rt = mid-1; else lt = mid+1; } } 2021. 9. 13. [ 자바스크립트(JavaScript) ] section07 - 9 - 결혼식 📍 section07 - 9 - 결혼식 피로연 장소에 동시에 존재하는 최대 인원수를 구하여 그 인원을 수용할 수 있는 장소를 빌리려고 한다. 만약, 입력이 13 15라면 13시 정각에 피로연장에 존재하고 15시에는 존재하지 않는다. 피로연장에 동시에 존재하는 최대 인원을 출력하는 문제다. 이 문제도 greedy로 풀 수 있는 문제인데, 회의실 배정처럼 입력을 정렬을 하되, 정렬 기준을 결혼식에 등장하는 시간(s), 결혼식장에서 나가는 시간(e)으로 나눠서 오름차순으로 정렬을 해야 한다. 입력을 타임라인 형식으로 그려보면 다음과 같다. 여기서 주의할 점은 나간시간(e)은 포함하지 않으므로 오름차순으로 정렬할 때 들어오는시간(s)과 나가는시간(e)이 동일하면 e가 먼저 오게 설정한다. 피로연에 등장하는 시간.. 2021. 9. 13. 이전 1 ··· 6 7 8 9 10 11 12 ··· 55 다음
