공부한 내용
1. DFS, BFS
- DFS
깊이 우선 탐색 (Depth Fisrt Search). 탐색 트리를 탐색할 때, 가장 깊은 노드를 우선 탐색하는 탐색방식. 실제 코드에서 구현은 스택 자료구조 또는 재귀 함수를 이용한다. 하나의 경로를 우선적으로 탐색하고, 이미 탐색한 경로를 저장할 필요가 없어 공간 복잡도가 낮은 편이다. 찾은 해가 최적해가 아닐 수 있으며, Cycle이 존재할 경우 무한루프의 위험이 있다. - BFS
너비 우선 탐색 (Breadth Fisrt Search). 탐색 트리를 탐색할 때, 현제 지점과 인접한 곳을 먼저 탐색하는 탐색방식. 실제 코드에서 구현은 큐 자료구조를 이용한다. 목표 노드까지의 최단거리를 보장하지만, 이전의 모든 경로를 기억하는데 공간이 많이 필요하다.
2. 그리디
그리디 알고리즘은 총 이득을 바라보는 것이 아닌, 판단하는 순간 순간의 이득에 집중하는 알고리즘이다. 이러한 판단 방식이 매우 직관적이며, 항상 최적해를 보장하지는 않는다. 현재의 선택이 미래에 영향을 주지 않는 경우, 입출력 제한이 너무 큰 경우 그리디 알고리즘을 고려해보자.
3. 백트래킹
앞서 배운 DFS, BFS와 같은 완전 탐색에서 추가적으로 속도를 높이기 위한 탐색기법. 현제 방문한 노드가 답일 확률이 낮을 때, 해당 노드와 이어진 노드의 탐색을 생략한다(가지치기). 얼마나 가지치기 조건을 잘 세우냐가 중요하며, 자바스크립트의 경우에 재귀의 성능이 좋지 않아 Stack, Queue 자료구조를 이용하여 구현하는 것이 좋다.
4. map, filter, reduce
map
이터러블 데이터가 있을 때, 이터러블의 각 요소마다 일정한 변경을 준 또다른 이터러블을 반환하는 함수이다.
const arr = [1, 2, 3, 4, 5];
const func = a => a + 1;
console.log(arr.map(func));
// [2, 3, 4, 5, 6]위의 Array.prototype.map()과 동일하게 동작한다. 하지만 이터러블 프로토콜을 이용해서 구현한다면, Array를 포함한 이터러블 프로토콜을 따르는 모든 데이터에 사용할 수 있다.
filter
여러 데이터 중 조건과 일치하는 요소만을 가진 이터러블을 반환하는 함수이다.
const arr = [1, 2, 3, 4, 5];
const func = a => a < 4;
console.log(arr.filter(func));
// [1, 2, 3]위의 Array.prototype.filter()와 동일하게 작동한다.
reduce
여러 요소를 가진 이터러블에서 하나의 값으로 수를 줄이는 함수이다. 파라미터는 다음과 같다.
reduce(function f(a, b), acc, iterable)
- 요소를 줄이는 계산 방식을 지닌 함수 f
- 초기 값이자 계산이 누적되는 acc
- 계산에 이용된 데이터들을 가진 iterable
const arr = [1, 2, 3, 4, 5];
const func = (a, b) => a + b;
console.log(reduce(func, 0, arr));
// 15위와 같은 reduce 함수가 있을 때, 이 함수의 동작 순서를 표기하면 다음과 같은 재귀 구조이다.
func(func(func(func(func(0, 1), 2), 3), 4), 5);위의 파라미터 중 acc는 생략이 가능하며, 만약 생략된다면 기본적으로 iterable의 첫번 째 원소가 되고 계산은 두번째 원소부터 시작한다.
reduce(func, arr);
// 아래와 같은 방식으로 동작한다.
// (func, [first, ...arr]) => reduct(func, first, arr);
// func(func(func(func(1, 2), 3), 4), 5);5. go, pipe, curry
go
앞서 본 함수형 프로그래밍의 함수들은 결과를 별도로 사용하지 않고 그대로 반환하므로 중첩하여 사용이 가능하다. 하지만 중첩이 많을수록 가독성이 떨어지며, 가장 안쪽에 위치한 함수부터 동작하므로 사람이 글을 읽는 방향과 반대방향이 된다. 이런 중첩된 코드의 가독성을 높이기 위해서 사용하는 함수가 go 함수이다. go 함수는 시작값과 함수들을 인자로 받아 인자로 받은 함수들을 차례대로 실행한 결과를 반환한다.
pipe
go와 비슷하게 동작하지만 모든 함수들의 실행 결과 값이 아닌, 모든 함수실행하는 하나의 함수를 반환한다. 선언한 함수를 반복적으로 사용할 수 있는 점이 go와 다르다.
curry
curry는 함수를 입력받고, 입력받은 인자의 개수에 따라서 다르게 동작하는 또 다른 함수를 결과물로 반환한다. 지정한 숫자만큼의 인자가 입력된다면 실행 결과를 반환하지만, 보다 적은 인자를 입력할 경우에 입력받은 인자는 저장하고 나머지 입력을 받아 결과를 반환하는 함수를 반환한다.
const add = (a, b) => a + b;
const curry_add = curry(add);
const add5 = curry_add(5);
// a와 b 두개의 인자들 중 a를 5로 저장, 나머지 입력을 받는 함수로 반환한다.
// add5 = (5, b) => 5 + b;
// add5 = b => 5 + b;
다시 볼 내용
Currying, 함수형 프로그래밍 구현(go, pipe)
느낀점
프로그래밍을 접하고 난 뒤로 명령형 프로그래밍에서 벗어난 적이 없었는데, 이렇게 함수형 프로그래밍에 대해서 배울 기회가 생겨 뜻깊다. 아무래도 사고 방식의 전환이라 평범하게 새로운 프로그래밍 언어를 배울 때와는 사뭇 다른 느낌이다. 아직도 함수를 변수에 저장하는 개념이나 표기법에서 이해가 더디다. 함수형 프로그래밍 관련 질문은 기간이 짧으니 이번주 동안은 좀 더 노력해 봐야겠다.
Reference
프로그래머스 프론트엔드 데브코스
