문제를 풀기 위한 아이디어 1번 컴퓨터부터 시작하여 경로를 거치게 되는 정점을 모두 구하는 문제이다. DFS 방법으로 풀어도 되고 BFS 방법으로 풀어도 무방하다. 예제의 경우 DFS로 풀면 1→2→3→5→6 순으로 거치게 되고, BFS로 풀면 1→2→5→3→6 으로 거치게 된다. 내가 작성한 코드 1. DFS로 푼 방법 let fs = require("fs"); let input = fs.readFileSync("/dev/stdin").toString().split("\n"); const vertexNumber = Number(input[0]); // 컴퓨터의 수 : 7 const edgeNumber = Number(input[1]); // 간선의 수 : 6 input.shift(); input.shi..

합병정렬(병합정렬, Merge Sort) - 전체 데이터를 하나의 단위로 분할한 후 분할한 것들을 다시 병합하는 정렬 방식 - 분할 정복 알고리즘에 속함 (분할 정복 : 어떤 문제를 그대로 해결할 수 없을 때 작은 문제로 분할해서 푸는 방법) 시간 복잡도 O(NlogN) - 최선이든 최악이든 같음 장점 - 어떠한 경우에도 좋은 성능을 보장한다. - 중복된 데이터의 순서가 바뀌지 않는 stable한 정렬이다. 단점 - 30 개 이하의 숫자를 정렬할 때는 삽입 정렬과 별 차이가 없음 - 정렬하는데 추가 메모리가 필요함 (in-place 알고리즘이 아님) 구현 function mergeSort(array) { if (array.length < 2) { return array; } let pivot = Math..

삽입 정렬 삽입 정렬이란? 배열을 순차적으로 검색하면서 정렬되지 않은 항목들을 배열의 왼쪽의 정렬된 부분으로 이동시킨다. 동작 과정 예를 들어 [3, 7, 2, 5, 1, 4]의 배열을 오름차순으로 정리한다고 하면 첫번째 숫자는 놔두고 두번째 자리 숫자부터 뽑아서 그 숫자가 첫 숫자보다 크면 첫 숫자 오른쪽에, 작으면 왼쪽에 넣는다. 세번째 자리 숫자를 뽑아서 앞의 두 숫자와 크기를 비교해서 알맞은 자리에 넣는다. 이렇게 끝까지 계속 한다. 시간 복잡도 Worst Case: O(n^2): 정렬이 하나도 안되어있는 경우 Best Case: O(n): 이미 정렬이 되어있는 경우 공간 복잡도 O(1) 장점 메모리가 절약된다. (배열을 새로 만들 필요 없이 주어진 배열 안에서 정렬시키면 되기 때문, in pla..

내가 작성한 코드 (자바스크립트) let fs = require("fs"); let input = fs.readFileSync("/dev/stdin").toString().split("\n"); const size = Number(input[0]); class Heap { constructor() { this.items = []; } //swap swap(index1, index2) { let temp = this.items[index1]; this.items[index1] = this.items[index2]; this.items[index2] = temp; } //parentIndex parentIndex(index) { return Math.floor((index - 1) / 2); } //left..

[백준] 11729. 하노이 탑 이동 순서 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 34398 16760 13013 48.547% 문제 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5개인 경우의 예시이다. 입력 첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤..

[백준] 11653. 소인수분해 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 26265 14154 11200 53.331% 문제 정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. 출력 N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다. 예제 입력 1 72 예제 출력 1 2 2 2 3 3 예제 입력 2 3 예제 출력 2 3 예제 입력 3 6 예제 출력 3 2 3 예제 입력 4 2 예제 출력 4 2 예제 입력 5 9991 예제 출력 5 97 103 내가 작성한 코드 (자바스크립트) let fs = require('fs'); let inpu..