문제를 풀기 위한 아이디어 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..

문제를 풀기 위한 아이디어 시간 제한은 2초이므로 대략 2억번의 연산까지 허용된다고 생각하고 풀어야 한다. 정확한 답을 구해내려면 완전탐색 유형으로 접근하여 모든 경우의 수를 다 따져본 후 가장 최선의 답을 고르면 되겠지만, 입력이 최대 10만이므로 이 방법은 효율적이지 않다. 따라서 위의 문제를 풀기 위해서는 현재 상황에서 지금 당장 좋은 것만 고르는 그리디 알고리즘으로 풀어야 한다. 그리디 알고리즘이 언제나 최적의 해를 보장하는 것은 아니지만 많은 문제에 대한 해를 보다 효율적으로 구해낼 수 있다. 위의 문제는 그리디 알고리즘의 대표적인 유형 중 하나인 활동선택 문제에 해당한다. * 활동 선택 문제 : 한 번에 하나의 활동만 처리할 수 있는 하나의 강의실에서 제안된 활동들 중 가장 많은 활동을 처리할..

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

[백준] 1978. 소수 찾기 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 68479 32271 26470 48.212% 문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 입력 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. 출력 주어진 수들 중 소수의 개수를 출력한다. 예제 입력 1 4 1 3 5 7 예제 출력 1 3 예제 입력 2 (내가 추가함) 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42..

[백준] 1011. Fly me to the Alpha Centauri 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 512 MB 54495 15400 12180 29.537% 문제 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다. 그가 탑승하게 될 우주선은 Alpha Centauri라는 새로운 인류의 보금자리를 개척하기 위한 대규모 생활 유지 시스템을 탑재하고 있기 때문에, 그 크기와 질량이 엄청난 이유로 최신기술력을 총 동원하여 개발한 공간이동 장치를 탑재하였다. 하지만..

[백준] 2839. 설탕배달 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 128 MB 157729 50157 39561 32.945% 문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다. 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 ..