코딩 테스트 문제 및 풀이49 [JS] 코딩 테스트 문제 : 동전 교환 [배낭(KnapSack) 알고리즘] 문제 : 동전 교환(냅색 알고리즘)문제 설명다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다. ▣ 입력설명첫 번째 줄에는 동전의 종류개수 N(1각 동전의 종류는 100원을 넘지 않는다. ▣ 출력설명첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다. ▣ 입력예제 131 2 515 ▣ 출력예제 13설명 : 5 5 5 동전 3개로 거슬러 줄 수 있다.오답 노트function solution(m, coin) { let answer = 0; let answerArr = []; sortArr = coin.sort((a, b) => b - a); for (const c of sortArr).. 2024. 5. 29. [JS] 코딩 테스트 문제 : 계단오르기 [동적계획] 문제 : 계단오르기문제 설명철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다. 그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가? ▣ 입력설명첫째 줄은 계단의 개수인 자연수 N(3≤N≤45)이 주어집니다. ▣ 출력설명첫 번째 줄에 올라가는 방법의 수를 출력합니다. ### **▣ 입력예제 1** 7 ▣ 출력예제 121내코드// BFS 활용 방식// 아래 방식의 단점은 중복된 계산을 반복할 수 있습니다.function solution(n) { let answer = 0; const steps = [1, 2]; let que =.. 2024. 5. 22. [JS] 코딩테스트 문제 : 섬나라 아일랜드 [DFS] 문제 : 섬나라 아일랜드(DFS 활용) 문제 설명 N*N 의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다입니다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요. 1 1 0 0 0 1 0 0 1 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 1 1 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 만약 위와 같다면 ▣ 입력설명 첫 번째 줄에 자연수 N(3= 0 && X < board.length) { // 이동할 좌표에이어진 섬이 있는 경우 이동한 위치좌표를 기준으로 추가 탐색을 위해 함수를 재귀적으로 호출 if (board[Y][X] === 1) { console.. 2024. 4. 23. [JS] 코딩 테스트 문제 : 송아지 찾기 [BFS : 상태트리탐색] 문제 : 송아지 찾기(BFS : 상태트리탐색) 문제 설명 현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다. 현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요. ▣ 입력설명 첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000 까지이다. ▣ 출력설명 점프의 최소횟수를 구한다. 답은 1이상입니다. ▣ 입력예제 1 5 14 ▣ 출력.. 2024. 4. 23. [JS] 코딩 테스트 문제 : 이진트리 넓이 우선 탐색 [BFS] 문제 : 이진트리 넓이 우선 탐색(BFS) 문제 설명 아래 그림과 같은 이진트리를 넓이 우선 탐색해보세요. 넓이 우선 탐색 : 1 2 3 4 5 6 7 넓이 우선 탐색 (BFS) 설명 트리나 그래프를 순회할 때 레벨 순서대로 탐색하는 알고리즘입니다. BFS를 구현할 때는 큐(queue)를 사용하여 각 노드를 탐색 순서대로 저장하고 처리합니다. 상태 트리 탐색, 최단 거리 계산 등에 활용 할 수 있다. 내코드 function solution() { let answer = ""; // 탐색한 노드들의 순서를 문자열로 저장할 정답 변수 // 너비 우선 탐색을 처리할 재귀함수 // num : 현재 레벨의 가장 낮은 수를 의미하는 인자 // lever : 현재 트리에서 탐색할 노드의 레벨을 의미하는 인자 func.. 2024. 4. 5. [JS] 코딩 테스트 문제 : 미로탐색 [DFS] 문제 : 미로탐색(DFS) 문제 설명 7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요. 출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다. 격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면 출발 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 0 1 1 1 0 1 1 0 0 1 0 0 0 0 0 도착 위의 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지이다. ▣ 입력설명 7*7 격자판의 정보가 주어집니다. ▣ 출력설명 첫 번째 줄에 경로의 가지수를 출력한다. ▣ 입력예제 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0.. 2024. 4. 2. [JS] 코딩 테스트 문제 : 경로 탐색 [인접리스트] 문제 : 경로 탐색(인접리스트) 문제 설명 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 1 2 3 4 5 1 2 5 1 3 4 2 5 1 3 4 5 1 4 2 5 1 4 5 총 6 가지입니다. ▣ 입력설명 첫째 줄에는 정점의 수 N(1 listArr[s].push(e)); console.log(listArr); // 재귀함수 DFS // current : 현재 노드 번호 1부터 시작하므로 1이 기본값 // chkArr : 현재까지 방문한 노드 순서대로 저장한 배열 시작값은 1 이므로 [1] 이 기본값 function DFS(current = 1, chkArr = [1]) { if.. 2024. 3. 22. [JS] 코딩 테스트 문제 : 경로 탐색 [인접행렬] 문제 : 경로 탐색(인접행렬) 문제 설명 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 1 2 3 4 5 1 2 5 1 3 4 2 5 1 3 4 5 1 4 2 5 1 4 5 총 6 가지입니다. ▣ 입력설명 첫째 줄에는 정점의 수 N(1 (graph[s][e] = 1)); console.log(graph); // 재귀함수 DFS // current : 현재 노드 번호 1부터 시작하므로 1이 기본값 // chkArr : 현재까지 방문한 노드 순서대로 저장한 배열 시작값은 1 이므로 [1] 이 기본값 function DFS(current = 1, chkArr = [1]) { // n 번.. 2024. 3. 19. [JS] 코딩 테스트 문제 : 수열 추측하기 [순열, 이항계수, 파스칼 삼각형] 문제 : 수열 추측하기 [순열, 이항계수, 파스칼 삼각형] 문제 설명 가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다. 3 1 2 4 4 3 6 7 9 16 N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오. 단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다. ▣ 입력설명 첫째 줄에 두개의 정수 N(1≤N≤10)과 F가 주어진다. N은 가장 윗줄에 있는 숫자의 개수를 의 미하며 F는 가장 밑에 줄에 있는 수로 1,000,0.. 2024. 2. 28. [JS] 코딩 테스트 문제 : 조합의 경우수(메모이제이션) [스택] 문제 : 조합의 경우수(메모이제이션) 문제 설명 조합 즉 서로 다른 n개중에 r개를 선택하는 경우의 수를 구할 때 nCr = n! / ((n-r)! * r!) 다음과 같은 공식으로 계산합니다. 이 공식을 쓰지 않고 다음 공식을 사용하여 재귀를 이용해 조합 수를 구해주는 프로그램을 작성하세요. nCr = (n-1)C(r-1) + (n-1)Cr ▣ 입력설명 첫째 줄에 자연수 n(3 2024. 2. 1. [JS] 코딩 테스트 문제 : 동전교환 [DFS] 문제 : 동전교환 문제 설명 다음과 같이 여러 단위의 동전들이 주어져 있을 때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다. ▣ 입력설명 첫 번째 줄에는 동전의 종류 개수 N(1 2024. 1. 30. [JS] 코딩 테스트 문제 : 중복순열 구하기 [재귀함수] 문제 : 중복순열 구하기 문제 설명 1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력합니다. ▣ 입력설명 첫 번째 줄에 자연수 N(3 2024. 1. 29. 이전 1 2 3 4 5 다음
