Algorithm

[2579] 계단 오르기 -Python

/* 문제 */ 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.마지막 도착 계단은 반드시 밟아야 한다. 따라서 첫 번째 ..

[1912] 연속합 - Python

Dynamic Programming(DP, 동적 계획법)은 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 푸는 방법이다. 포인트는 중복되는 작은 문제들의 결과를 저장해 놓고 재활용하는 것이다. DP라는 이름때문에 어떤 방법인지 한 번에 알기 어려운데, '기억하며 풀기'라고도 하고 '하나의 문제는 단 한 번만 풀도록 하는 알고리즘'으로 정리할 수도 있다. 1912번 문제는 DP를 활용하여 풀 수 있다. /* 문제 */ n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하..

[2447] 별 찍기 - JavaScript

/* 문제 */ 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다. N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 다음과 같다. 처음에는 각 단계에서 이전 단계의 결과물이 새로운 패턴 한 칸이 된다는 점을 이용해 문제를 풀려고 했다. 크기가 3인 리스트를 선언하고 각 요소를 첫째 줄, 둘째 줄, 셋째 줄로 설정해 계산한 후 마지막에 출력하는 방식이었다. 첫째 줄과 셋째 줄은 이전 단계의 결과물을 3번..

[2941] 크로아티아 알파벳 - JavaScript

/* 문제 */ 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 예를 들어, ljes=njak은 크로아티아 알파벳 6개(lj, e, š, nj, a, k)로 이루어져 있다. 단어가 주어졌을 때, 몇 개의 크로아티아 알파벳으로 이루어져 있는지 출력한다. dž는 무조건 하나의 알파벳으로 쓰이고, d와 ž가 분리된 것으로 보지 않는다. lj와 nj도 마찬가지이다. 위 목록에 없는 알파벳은 한 글자씩 센다. 단어가 몇 개의 알파벳으로 이루어져 있는지만 출력하면 되기 때문에 전체 단어의 길이에서 한 글자로 취급되는 크로아티아 알파벳의 수를 빼주기만 하면 된다고 생각했다. 그렇게 작성한 첫 번째 코드는 // 틀린 코드 const fs = r..

[2775] 부녀회장이 될테야 - JavaScript

로직은 잘 짰다고 생각했는데 생각지도 못한 곳에서 실수를 해서 시간을 많이 쓴 문제다. /* 문제 */ 평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다. 이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다. 아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다. 처음에는 ..

[15552] 빠른 A+B - JavaScript (Node.js 시간 초과 해결)

10950번과 입출력은 동일하지만 시간 제한이 1초로 더 짧은 문제다. //10950 const fs = require("fs"); const input = fs.readFileSync("./dev/stdin").toString().split("\n"); const n = parseInt(input[0]); for (let i = 0; i < n; i++) { tem = input[i + 1].split(" "); console.log(parseInt(tem[0]) + parseInt(tem[1])); } 따라서 위의 코드를 입력하면 시간 초과가 떠버린다. console.log()로 입력의 갯수만큼 출력을 반복하는 것이 시간 제한에 걸리기 때문이다. 따라서 const fs = require("fs"); ..

[14681] 사분면 고르기 - JavaScript (Node.js EACCESS 에러 수정)

하던대로 fs 모듈을 이용해 문제를 풀고 있었는데, EACCES: permission denied 라는 에러가 뜨면서 채점이 진행되지 않았다. //초기 코드 const fs = require("fs"); const input = fs.readFileSync("input.txt").toString().split("\n"); const a = parseInt(input[0]); const b = parseInt(input[1]); ... 구글링 결과 14681 문제는 fs 모듈을 이용하면 에러가 발생하기 때문에 readline 모듈을 사용해야 한다고 한다. readline 모듈은 사용해 보지 않아서 헤맸었는데 앞으로 사용할 일이 많을 것 같으니 fs와 readline을 모두 숙지하고 있어야겠다. //수정된 ..

JavaScript로 백준 문제 풀기(Node.js 사용)

백준에서는 JS를 지원하지 않기 때문에 Node.js를 이용해 문제를 풀어야 한다. Node.js란 Node.js 노드 개념 이해하기 자바스크립트 JavaScript 런타임 이벤트 Node.js 노드 개념 이해하기 JavaScript 런타임 - 노드는 다양한 자바스크립트 애플리케이션을 실행할 수 있으며, 서버를 실행하는데 제일 많이 사용된다. 이벤트 기반 이벤트 루프 논블로킹 I/O 싱글 hanamon.kr JS로 입력을 받을 수 없기 때문에 Node.js의 fs 모듈을 이용해 input을 입력한다. 1001번 문제인 두 정수 A와 B를 입력받은 다음, A-B를 출력하는 프로그램을 Node.js로 풀어보자. var fs = require('fs'); var input = fs.readFileSync('/..