[코딩테스트] 프로그래머스 - 피보나치 수(자바스크립트 풀이)
문제 설명피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어F(2) = F(0) + F(1) = 0 + 1 = 1F(3) = F(1) + F(2) = 1 + 1 = 2F(4) = F(2) + F(3) = 1 + 2 = 3F(5) = F(3) + F(4) = 2 + 3 = 5와 같이 이어집니다. 2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요. 제한 사항n은 2 이상 100,000 이하인 자연수입니다.입출력 예nreturn3255 입출력 예 설명 피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어..
2023. 12. 29.
[알고리즘] BFS 너비 우선 탐색 - 자바스크립트 코드 포함 간략한 설명
너비 우선 탐색 (BFS, Breadth-first search) 시작 정점에서 시작하여 인접한 모든 정점을 방문하는 방법이다. 재귀호출을 사용하는 DFS와 다르게 자료 구조 큐 Queue를 사용하는 방식이 일반적이다. 정점에 연결되는 모든 갈림길을 탐색을 하다보니 어떠한 시작점과 끝점이 주어졌을때 그 둘 사이의 최단 거리 구하기에 용이하다. 아래 그림을 보며 살펴보자. 그림에선 시작 정점을 ㄱ으로 본다. 시작 정점을 기준으로 인접한 정점은 ㄴ,ㄷ,ㄹ이다. 그리하여, ㄴ,ㄷ,ㄹ 정점을 방문한다. 그 후, ㄴ에 인접한 ㅁ,ㅂ,ㅅ 정점을 방문하고, ㄷ,ㄹ도 마찬가지로 인접한 정점을 차례대로 방문한다. DFS와 달리 너비를 기준으로 순회하는 방식이다. 다음 그림의 트리를 너비 우선 탐색으로 순회하여 값을 프린..
2023. 11. 14.
[자료구조] 트리 Tree - 자바스크립트(Javascript)로 구현하기
트리(Tree) 트리는 비순차적인 자료 구조로 정보 검색에 용이하다. 부모 자식 관계를 가진 다수 노드로 구성된다. 밑의 그림과 같이 트리 모양의 자료구조를 트리라고 하는 것이다. 루트 root: 트리의 최상위 노드로 루트라고 한다. 그림에서는 12값을 가진 노드에 해당한다. 서브트리: 노드와 자식 노드로 구성되어있다. 그림에선 5,3,6 / 9,8,10 / 17,14,22 등이 해당한다. 노드 위에서 트리는 노드로 구성되어 있다고 하였다. 노드는 왼쪽 자식과 오른쪽 자식의 참조(포인터)를 가리킨다. 위의 그림에서 3,6,8,10,13,15,18,23 키에 해당하는 노드들은 자식이 없으므로 왼쪽 자식 참조 값과 오른쪽 자식 참조 값이 null이 된다. 루트 노드를 그림으로 나타내면 위와 같다. 이때 노드..
2023. 9. 4.
