오꾸오꾸(오늘도 꾸준히 오랫동안 꾸준히)

보호되어 있는 글입니다.

문제 마트에서 장을 보고 박스를 포장하려고 합니다. 박스를 포장하는 데는 폭이 너무 좁아서, 한 줄로 서 있어야 하고, 들어온 순서대로 한 명씩 나가야 합니다. 불행 중 다행은, 인원에 맞게 포장할 수 있는 기구들이 놓여 있어, 모두가 포장을 할 수 있다는 것입니다. 짐이 많은 사람은 짐이 적은 사람보다 포장하는 시간이 길 수밖에 없습니다. 뒷사람이 포장을 전부 끝냈어도 앞사람이 끝내지 못하면 기다릴 수밖에 없는 환경입니다. 앞사람이 포장을 끝나면, 포장을 마친 뒷사람들과 함께 한 번에 나가게 됩니다. 만약, 앞사람의 박스는 5 개고, 뒷사람 1의 박스는 4 개, 뒷사람 2의 박스는 8 개라고 가정했을 때, 뒷사람 1이 제일 먼저 박스 포장을 끝내게 되고, 앞사람 1의 포장이 마칠 때까지 기다렸다가 같이..

브라우저 뒤로 가기 앞으로 가기 브라우저 뒤고 가기 앞으로 가기 문제 개발자가 되고 싶은 김코딩은 자료구조를 공부하고 있습니다. 인터넷 브라우저를 통해 스택에 대한 검색을 하면서 다양한 페이지에 접속하게 되었는데 "뒤로 가기", "앞으로 가기"를 반복하면서 여러 페이지를 참고하고 있었습니다. 그런데 새로운 페이지를 접속하게 되면 "앞으로 가기" 버튼이 비활성화돼서 다시 보고 싶던 페이지로 갈 수 없었습니다. 이러기를 반복하다가 김코딩은 스택 자료구조를 떠올리게 되었습니다. 브라우저에서 "뒤로 가기", "앞으로 가기" 기능이 어떻게 구현되는지 궁금해진 김코딩은 몇 가지 조건을 아래와 같이 작성하였지만 막상 코드를 작성하지 못하고 있습니다. 조건 새로운 페이지로 접속할 경우 prev 스택에 원래 있던 페이지..

최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미합니다. 다양한 문제 상황 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현 지점 간 연결된 도로는 그래프에서 간선으로 표현 다익스트라 최단 경로 알고리즘 개요 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산합니다. 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작합니다. 현실 세께의 도로(간선)은 음의 간선으로 표현되지 않습니다. 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류됩니다. 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복합니다. 다익스트라 최단 경로 알고리..

문제 정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다. 입력 let output = quickSort([3, 1, 21]); console.log(output); // --> [1, 3, 21] const quickSort = function (arr) { // TODO: 여기에 코드를 작성합니다. // 피벗을 처음 값으로 설정합니다. // 비교를 할 오른쪽 값과 왼쪽 값을 설정합니다. // while 반복문을 통해 왼쪽에서는 피벗보다 큰 값을 찾고 // 오른쪽에서는 피벗보다 작은 값을 찾습니다. // 왼쪽에서는 피벗보다 큰 값 과 오른쪽에서는 피벗보다 작은 값을 찾는다면 // 서로의 위치를 바꿔줍니다. // 그렇게 바꿔 나가다가 찾는 위치가 크로스 되면 작은 데이터값을 피벗으로..

문제 다음의 조건을 만족하면서 현재의 비밀번호('curPwd')를 새 비밀번호(newPwd)로 변경하는 데 필요한 최소 동작의 수를 리턴해야 합니다. 한 번에 한 개의 숫자만 변경가능하다. 4자리의 소수(prime)인 비밀번호로만 변경가능하다. 정리하면, 비밀번호가 계속 소수를 유지하도록 숫자 한 개씩을 바꿔갈 때 현재 비밀번호에서 새 비밀번호로 바꾸는 데 최소 몇 개의 숫자를 변경해야 하는지를 리턴해야 합니다. 입력 let output = primePassword(1033, 1033); console.log(output); // --> 0 output = primePassword(3733, 8779); console.log(output); // --> 3 (3733 -> 3739 -> 3779 -> 8..

문제 정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다. 입력 let output = insertionSort([3, 1, 21]); console.log(output); // --> [1, 3, 21] const insertionSort = function (arr, transform = (item) => item) { let sorted = [arr[0]]; for (let i = 1; i = transform(sorted[i - 1])) { sorted.push(arr[i]); } else { for (let j = 0; j < i; j++) { if (transform(arr[i])

문제 임의의 tree를 구성하는 노드 중 하나의 Node 객체를 입력받아, 해당 노드를 시작으로 너비 우선 탐색(BFS, Breadth First Search)을 합니다. 이 때, 탐색되는 순서대로 노드의 값이 저장된 배열을 리턴해야 합니다. 입력 let root = new Node(1); let rootChild1 = root.addChild(new Node(2)); let rootChild2 = root.addChild(new Node(3)); let leaf1 = rootChild1.addChild(new Node(4)); let leaf2 = rootChild1.addChild(new Node(5)); let output = bfs(root); console.log(output); // --> [..

다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 합니다. 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운과 보텀업)으로 구성 다이나믹 프로그래밍은 동적 계획법이라고 부릅니다. 일반적인 프로그래밍 분야에서의 동적이란 자료구조에서 동적 할당은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미 반면에 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단어 다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용할 수 있습니다. 1. 최적 부분 구조(Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 ..

문제 오름차순 정렬된 정수의 배열(arr)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다. 입력 let output = binarySearch([0, 1, 2, 3, 4, 5, 6], 2); console.log(output); // --> 2 output = binarySearch([4, 5, 6, 9], 100); console.log(output); // --> -1 const binarySearch = function (arr, target) { // TODO : 여기에 코드를 작성합니다. let low = 0 // 첫번째 인덱스 let high = arr.length - 1 // 마지막 인덱스 while(low 3으로 업데이트 된다. }else{ high = mid - ..