choi95의 TIL📝

문제 철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는 (1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1, 2 + 2) 로 5가지이다.그렇다면 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇가지인가? 코드 function solution(n) { let answer = 0; function DFS(sum) { if(sum > n) return; //cut-edge if(sum === n) { answer++; return; } else { DFS(sum + 1); DFS(sum + 2); } } DFS(0); return answer; } console.log(solution(7)); 오답 해당 문제는 깊..

문제 문제풀이 https://choi95.tistory.com/126 [DFS]미로 탐색 문제 문제풀이 https://choi95.tistory.com/39 봉우리 문제 지도 정보가 N*N 격자판에 주어진다. 각 격자에는 그 지역의 높이가 쓰여있습니다. 각 격자판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자 choi95.tistory.com 해당 문제는 이전에 포스팅 했던 미로 탐색 문제와 매우 유사하지만 다음과 같은 차이점이 있다. 탐색 방향이 '좌 우 상 하' 외에도 대각선까지 포함되어야 한다. 여러 갈래의 길을 구하는 미로 탐색은 한번 탐색했던 길을 갔던 지점으로 체크한 뒤에 백트래킹을 할 경우를 대비해 다시 재귀 호출을 마친 뒤에 가지 않았음으로 초기화 해주지만 해당 문제에서는 정해져 있는 섬을 ..

문제 현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다. 현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요. 문제풀이 이때 중요한 점은 한번 방문했던 지점은 더 이상 참조 및 순회하지 않음으로써 시간 복잡도를 줄이는 것이다. 최단 경로를 구하기 위해서는 다음과 같이 각 지점에 대한 거리를 거리의 정보를 저장하고 있는 배열에 저장하였다. 코드 function solution(s,..

문제 https://choi95.tistory.com/110?category=854389 [DFS]이진트리 순회 문제 아래 그림과 같은 이진트리를 전위순회, 중위순회, 후위순회를 돈 결과를 출력하세요. 개념 트리(Tree) 노드(node)로 이루어진 비선형 자료 구조 트리는 하나의 루트(root) 노드를 갖고 있음 루 choi95.tistory.com 이전 깊이 우선 탐색한 이진트리를 이번에는 넓이 우선탐색으로 구현해보고자 한다. 문제풀이 너비 우선 탐색(BFS_Breadth-First Search) 루트 노드(Root Node) 또는 다른 임의의 노드를 정점으로, 인접한 노드를 먼저 탐색하는 방법 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법 적용 예..

문제 문제풀이 https://choi95.tistory.com/39 봉우리 문제 지도 정보가 N*N 격자판에 주어진다. 각 격자에는 그 지역의 높이가 쓰여있습니다. 각 격자판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자 는 봉우리 지역이다. 봉우리 지역이 몇 개 있 choi95.tistory.com 해당 문제는 이전에 풀었던 봉우리 문제 풀이와 흡사하다. 상하좌우를 나타내는 별도의 이동 방향 배열을 선언하여 주고 현재 보드의 위치에서 해당 배열을 이용하여 상하좌우를 순회하며 갈 수 있는 길인지 아닌지 확인해주면 된다. 여기서 중요한 점은 봉우리 문제는 중첩 for문을 수행하여 좌표의 방향을 결정 짓었다면 이번 문제에서는 재귀 호출을 통해서 해당 요구 사항을 충족시켰다. 코드 function solutio..

문제 https://choi95.tistory.com/124 [인접 행렬]경로 탐색 문제 문제풀이 인접행렬 인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식 arr[i][j]: 노드 i(행)에서 j(열)로 가는 간선이 있으면 1, 아니면 0_단방향그래프의 경우 인접 행렬의 특성 choi95.tistory.com 문제풀이 이전 경로 탐색을 구하는 과정에서 인접 행렬을 사용하여 정점으로 가는 가지 수를 구하였다. 하지만 각 정점에 대해서 다음 정점으로 갈 수 있는 후보군을 행(현재 정점)과 열(다음 정점)에 저장한다면 탐색 과정에서불필요한 인덱스 요소까지 일일히 확인하면서 순회해야 되는 문제가 발생한다. 현재는 열(다음 정점)의 수가 적어 크게 상관은 없으나 후보군이 무수히 많지만 그 중 실제 ..

문제 문제풀이 인접행렬 인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식 arr[i][j]: 노드 i(행)에서 j(열)로 가는 간선이 있으면 1, 아니면 0_단방향그래프의 경우 인접 행렬의 특성을 고려하여 문제에서의 경로 경우수에 만족하는 인접 행렬을 생성할 경우 다음과 같이 표현할 수 있다. 행을 기준으로 열로 이동했을 때 경로가 있다면 1을, 아니면 0을 배열 내에 할당한다. 각 행은 정점(현재 있는 위치), 각 열은 다음 행선지 후보군 이라고 정리할 수 있다. 이를 노드를 통해 깊이 탐색 과정으로 바꿔 그려 본다면 다음과 같이 나온다. 코드 function solution(n, arr) { let answer = 0; let graph = Array.from(Array(n + 1), (..

문제 문제풀이 먼저 해당 문제를 풀기 위해서는 파스칼의 삼각형을 실행한 결과값이 이항계수를 이용해 계산한 최종값과 같음을 알아야 한다. 다음 그림에서 본 바와 같이 파스칼의 삼각형을 실행한 결과 값은 (1 × 1) + (2 × 3) + (3 × 3) + (4 × 1)이며 N이 4일 경우에 수열 순서가 어떻든 간에 {1 3 3 1}의 범위 내에서 결과값이 산출된다. 또한 이를 좀 더 구하기 편한 이항 계수로 표현한다면 3C0 3C1 3C2 3C3로 바꿀 수 있다. {1 3 3 1}을 이항 계수로 구해두지 않을 경우 순열을 구할 때마다 매번 파스칼의 삼각형 과정을 거쳐야 하는데 이는 시간 복잡도 상 매우 비효율적이다. 코드 function solution(n, f) { let answer = []; let ..