명왕성의 공전기록

https://www.acmicpc.net/problem/1063 문제는 체스판에서 말을 움직이는 문제로, 비교적 자주 볼 수 있는 문제다. 조금 다른 점은 이 문제는 '말' 뿐만 아니라, '돌'도 주어지는데, 이 '돌'은 '말'이 미는 방향으로 움직일 뿐더러 이 또한 좌표 밖으로 벗어나서는 안된다는 제약이 주어진다. 나는 다음과 같이 문제 풀이 방식을 수립했다. 1. 먼저 처음 '말'과 '돌'의 위치로 주어지는 좌표가 'A8'와 같은 체스 좌표로 주어지기 때문에, 해당 체스 좌표를 x,y 좌표로 || x,y 좌표를 체스 좌표로 바꿀 수 있는 함수(정답 제출 시 필요)를 구현하고 2. '말'과 '돌'이 명령어에 따라 이동하는 좌표가 유효한 위치인지 확인할 수 있는 함수 구현, 3. 각 명령어에 따라 좌표..

https://www.acmicpc.net/problem/3107 해당 문제는 문제에서 주어진 규칙대로 구현하는 문제다. 1번 규칙을 해결하기 위해서 생략된 0을 채워줄 함수를 하나 만들었고 2번 규칙은 쌍 클론(::)이 사용되어 생략된 내용이 있는 경우와 그렇지 않은 경우에 따로 접근해 해결했다. 소스 코드는 다음과 같다. const fs = require('fs') const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt") .toString().trim() // 0이 생략된 문자열에 0을 채워주는 함수 const padStartAct = (arr) => { return arr.map((el)=> { return..

https://www.acmicpc.net/problem/3036 문제는 다음과 같이 이어진 링이 있다고 할 때, 첫 번째 링을 돌릴 시 다음 링이 몇 바퀴 도는지 출력하는 문제다. 먼저 수학적인 접근을 해본다. 예제 1과 같은 예시로 8, 4, 2의 링이 있다고 할 때, 첫 번째 반지름 8인 링의 둘레는 16π 이다. (모든 링이 16π를 만족할 만큼 회전해야 한다는 의미기도 하다.) 이때 반지름 4인 링의 둘레는 8π 로 2바퀴(2/1)가, 반지름 2인 링의 경우 4π로 4바퀴(4/1)가 답이 된다. (밑에서는 둘레를 구한 뒤 계산하지는 않는다.) 사실 해당 문제에서 가장 중요한 포인트는 '기약분수' 형태로 답안을 제출하는 것인데, 우리는 중학교 때 배웠던 것처럼 최대공약수를 구한 뒤, 분자와 분모..

https://www.acmicpc.net/problem/5567 해당 문제는 '친구 관계 리스트'를 통해 '친구의 친구까지'의 인원들을 구하는 문제다. 그렇기에 관계 리스트를 '각 노드마다 연결된 그래프'로 구현하고, '친구의 친구까지' 이므로 '1과 연결된 노드들', '1과 연결된 노드들과 연결된 노드들'을 정답으로 제출하면 된다. 소스 코드는 다음과 같다. const fs = require('fs') const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt") .toString().trim().split('\n') // 이때 N은 총 노드 수 / _ 은 리스트의 길이 / rest 는 관계를 나타내는 데이터 co..

https://www.acmicpc.net/problem/15988 해당 문제는 DP, 즉 다이나믹 프로그래밍을 통해 해결해야 하는 문제다. 다이나믹 프로그래밍이란, 상대적으로 복잡하고 큰 연산을 통해 해결해야 할 문제를 작은 단위로 쪼개어 해결함으로써 중복 계산을 피하며 최적화된 결괏값을 구하는 방식을 의미한다. 그리고 이때, 중복 계산을 피하기 위해 작은 단위의 계산을 저장해두는데 이때 이를 메모라이징이라 한다. 1, 1, 2, 3, 5, 8, 13... 과 같이 바로 뒤에 있는 수와 2번째로 뒤에 있는 수를 더해 만들어지는 피보나치 수열의 경우 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예로 불린다. 피보나치 수열을 만드는 로직은 다음과 같다. function fibonacci(n) { con..

https://www.acmicpc.net/problem/11478 문제는 단순한 편이다. 중복 처리는 지난 포스팅에서 활용했던 set() 을 사용하면 되고, 문자열 자르는 것은 substr 메서드를 활용했다. 이전까지는 대부분 slice를 활용해 문자열을 잘랐는데 왜 substr 메서드를 사용했느냐 묻는다면, slice 메서드는 slice(시작 인덱스, 끝 인덱스) 로 문자열을 자르는 것이고 substr 메서드는 substr(시작 인덱스, 자를 길이) 로 문자열을 자르는 것이기 때문에 이런 문제에서 더 직관적일 것이라는 생각이었다. 2023.01.13 - [개발/JavaScript] - JS - 반복문 심화2 (map / filter / sort / slice / substring / substr/sp..

https://www.acmicpc.net/problem/2563 문제는 주어진 입력값으로 영역을 구하는 문제다. 100 * 100 사이즈의 배열을 생성하고 반복문으로 영역이 포함되는 좌표를 '색종이가 덮은' 영역으로 처리해줄 수 있지만, 이 경우는 '덮은 영역 처리', '덮은 영역 확인'으로 두 번의 연산이 필요하기에 그리 좋은 방식은 아니다. 때문에 나는 좌표를, 중복된 데이터를 허용하지 않는 Set() 생성자를 활용해 문제를 해결했다. const fs = require('fs') const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt") .toString().trim().split('\n') function ..

https://school.programmers.co.kr/learn/courses/30/lessons/42577 해당 문제는 주어진 배열에서 특정 단어가 다른 단어에 대해 '접두어'로 쓸 수 있을 때 false, 접 두어로 쓸 수 있는 단어가 없을 때는 true를 반환하는 문제다. 문제 자체는 간단해 보이나 주어지는 배열의 길이가 백만이기 때문에 시간 복잡도에 의한 실패에 유의해야 한다. 내가 생각한 방식은 다음과 같다. 먼저 해시로 활용할 객체를 만든다. 이후 길이가 긴 단어가 짧은 단어의 접두어가 될 수는 없으므로 길이가 짧은 순으로 정렬한 배열을 만든다. 정렬한 배열은 인덱스 순으로 해시 테이블에 추가하는 과정을 거치는데, 이때 반복문을 통해 앞에서부터 한글자씩 가져와 해당 단어가 이미 해시 테이..