inflearn78 [ 자바스크립트(JavaScript) ] section08 - 2 - 재귀함수를 이용한 이진수 출력 📍 section08 - 2 - 재귀함수를 이용한 이진수 출력 10진수 N을 2진수로 변환하는 문제이다. 저번에 풀었던 재귀함수에서 조금 응용하면 쉽게 풀 수 있는 문제다. 백준에도 비슷한 문제가 있었는데 이진수와 관련한 문제인 백준 3460 - 이진수 문제였다. 재귀를 이용할 때 초보자는 if-else문을 사용하는것이 더 이해하기 쉽다고 선생님께서 말씀하셨다. 이진수를 구하려면 어떤 수를 몫이 0이 될 때까지 2로 계속 나누면서 나머지를 누적하는데 이때, 나머지를 거꾸로 누적해야 이진수가 된다. 예를 들어 11을 이진수로 표현한다고 가정하면 다음과 같이 계산하면 된다. 그리고 answer코드를 DFS 함수 위에 선언하냐 밑에 선언하냐에 따라 값이 달라지는데 DFS 위에 선언하게 되면 나머지가 반대방향으.. 2021. 9. 16. [ 자바스크립트(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. 이전 1 ··· 3 4 5 6 7 8 9 ··· 16 다음
