Algorithm (7) 썸네일형 리스트형 [Algorithm] 재귀함수 개념과 동작방식 1. 재귀함수 재귀함수는 자기 자신을 호출하는 함수를 말한다. 반복문을 조금 더 간결한 코드로 풀어낼 때 사용한다. 스스로를 호출하는 함수이기 때문에 반드시 종료조건을 써줘야 하며, 무한루프 되지 않도록 주의해야 한다. 1) 재귀함수 구현(자바스크립트) 자연수 N이 입력되면 재귀함수를 이용하여 1부터 N까지 출력하는 프로그램을 작성하세요. function solution(n){ function DFS(L){ if(L === 0) return; else { DFS(L-1); conosle.log(L); } } } //1, 2, 3 자바스크립트에서 재귀함수를 구현하는 방법은 간단하다. 자기 자신을 호출하는 함수를 사용하면 된다. 위 예시를 살펴보면 DFS 함수 내에서 스스로를 호출한 것을 확인할 수 있다. .. [Algorithm] 이진탐색 알고리즘 (Binary Search Algorithm) 1. 이진탐색(Binary Search) 이분탐색이라고도 불리는 이진탐색 알고리즘은, 정렬된 배열 내에서 대상 값의 위치를 찾는 검색 알고리즘이다. 대상 값을 배열의 중간 요소와 비교한 후, 동일하지 않으면 절반을 제거하고 이를 성공할 때까지 반복한다. 정렬된 배열을 앞에서부터 하나하나 순차적으로 탐색하는 것을 순차탐색이라 하는데, 이러한 순차탐색보다 좀 더 빠르게 위치를 찾을 수 있다. 이진탐색의 시간복잡도는 O(log(n))이다. (순차탐색의 시간복잡도는 O(n)) 2. 이진탐색 구현 function solution(target, arr) { let answer; arr.sort((a, b) => a - b); //인덱스번호 let lt = 0, rt = arr.length - 1; while (lt.. [Algorithm] 탐욕 알고리즘 (Greedy Algorithm) 1. 탐욕 알고리즘(Greedy Algorithm) 탐욕 알고리즘은 선택의 순간마다 그 이후를 고려하지 않고, 현 시점에서 가장 최적인 방법을 선택하는 알고리즘을 말한다. 순간마다 최적인 방법을 선택하기 때문에 항상 최적의 결과값을 배출하진 않는다. 그러나 다른 알고리즘보다 평균적으로 속도가 빠르고, 어느 정도 최적에 근사한 답을 알려준다. 2. 문제 : 회의실 배정 한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들 려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하 면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중 단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작.. [Algorithm] 버블정렬 알고리즘(Bubble Sort Algorithm) 1. 버블정렬(Bubble Sort) 버블정렬은 인접한 항목의 각 쌍을 비교하여 순서를 정렬하는 알고리즘이다. 6 5 3 1 8 7 2 4 > 6, 5 교환 5 6 3 1 8 7 2 4 > 6, 3 교환 5 3 6 1 8 7 2 4 > 6, 1 교환 5 3 1 6 8 7 2 4 > 6, 8 교환x 5 3 1 6 8 7 2 4 > 8, 7 교환 5 3 1 6 7 8 2 4 > 8, 2 교환 5 3 1 6 7 2 8 4 > 8, 4 교환 5 3 1 6 7 2 4 8 위처럼 한 번의 반복이 끝나면 가장 큰 숫자가 맨 마지막에 오게 된다.(오름차순 기준) 이를 모든 숫자를 서로 비교할때까지 반복하면 된다. O(n^2)의 시간복잡도를 갖으며, 매우 단순하지만 성능이 좋지 않기 때문에 잘 사용하지 않는다. 2. 버.. [Algorithm] 선택정렬 알고리즘(Selection Sort Algorithm) 1. 선택정렬 선택정렬은 정렬 알고리즘 중 하나로, 내부 비교 정렬이다. 가장 앞의 값을 기준으로 배열 내에서 최소값을 찾고, 해당 값을 가장 앞의 값과 교환한다. 이를 반복하면서 배열을 정렬하는게 선택정렬이다. O(n^2)의 시간복잡도를 갖기 때문에 성능이 떨어지지만 메모리가 절약된다는 장점이 있다. 또한 데이터가 중복된 경우에도 위치가 바뀔 수 있는 Unstable 정렬이다. 따라서 데이터가 큰 경우보다, 메모리가 제한되는 경우에 사용하는 것이 좋다. 2. 선택정렬 구현 function solution(arr) { let answer = arr; for (let i = 0; i < arr.length; i++) { let idx = i; for (let j = i + 1; j < arr.length;.. [Algorithm] 슬라이딩 윈도우 알고리즘(Sliding Window Algorithm) 1. 슬라이딩 윈도우 알고리즘(Sliding Window Algorithm)이란? 슬라이딩 윈도우 알고리즘은 고정 사이즈의 윈도우를 이동시키면서, 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘을 말한다. 이때 윈도우 안에 있는 데이터는, 양 끝에 있는 원소들만 변화한다. 2. 예시 현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 N일 동안의 매출기록을 주고 연속된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다. 만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면 12 15 11 20 25 10 20 19 13 15 연속된 3일간의 최대 매출액은 11+20+25=56만원입니다. 여러분이 현수를 도와주세요. //내코드 function solution(k, .. [Algorithm] 투 포인터 알고리즘 (Tow Pointer Algorithm) 1. 투 포인터 알고리즘(Tow Pointer Algorithm)이란? 투 포인터 알고리즘은 말 그대로 두 개의 포인터 위치를 기록하며 처리하는 알고리즘을 말한다. 주로 정열된 배열에서 목표 값에 해당하는 요소를 찾을때 많이 사용한다. 투 포인터 알고리즘에는 서로를 향해 두 포인터를 움직이는 것과 같은 방향으로 두 포인터를 움직이는 것, 2가지 유형이 있다. 1) 서로를 향해 두 포인터를 움직이는 유형 두 개의 포인터를 시작과 끝에 설정하고, 포인터가 만날때까지 서로를 향해 이동한다. 2) 같은 방향으로 두 포인터를 움직이는 유형 두 개의 포인터를 같은 위치에 설정하고, 동일한 방향으로 포인터를 이동한다. 2. 예제 오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램.. 이전 1 다음
