명왕성의 공전기록

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를 반환하는 문제다. 문제 자체는 간단해 보이나 주어지는 배열의 길이가 백만이기 때문에 시간 복잡도에 의한 실패에 유의해야 한다. 내가 생각한 방식은 다음과 같다. 먼저 해시로 활용할 객체를 만든다. 이후 길이가 긴 단어가 짧은 단어의 접두어가 될 수는 없으므로 길이가 짧은 순으로 정렬한 배열을 만든다. 정렬한 배열은 인덱스 순으로 해시 테이블에 추가하는 과정을 거치는데, 이때 반복문을 통해 앞에서부터 한글자씩 가져와 해당 단어가 이미 해시 테이..

https://www.acmicpc.net/problem/1487 해당 문제는 판매자가 최대 이윤을 남길 수 있는 판매가격을 구하는 문제이다. 소비자의 희망 구매 가격과 배송비를 고려하여 문제를 풀어야 한다. 아래는 반복문 고차함수(forEach), 와 누산 고차함수(reduce)를 이용한 풀이를 소개한다. const fs = require('fs') const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt") .toString().trim().split('\n') function solution(data) { let [_, ...arr] = data.map(el=> el.split(' ').map(Number)) ..

https://www.acmicpc.net/problem/11586 해당 문제는 주어지는 '심리상태'에 따라 값을 출력하는 문제이다. (난이도 자체는 쉬운 편) 다만 '심리상태'에 따라 조건 분기를 해줘야 하는데 이 경우에 불필요하게 반복되는 코드가 많아져 코드를 읽기가 불편할 수가 있다. 이를 타파하기 위해 객체 안에 함수를 저장하여 조건분기를 했는데, 먼저 이를 적용하지 않은 코드를 살펴본다. const fs = require('fs') const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt") .toString().trim().split('\n') function solution(data) { const [_..

https://www.acmicpc.net/problem/1388 // 입력 4 4 |--| |--| |--| |--| // 출력 6 문제에 제시된 예제를 사용하기에는 너무 단순하거나 오히려 길고 복잡하기에, 해당 블로그에서는 원활한 설명을 위해 예제를 만들었다. 문제에서 말했던 것처럼 연결된 막대기는 하나의 막대로 보기 때문에 좌우측 4개로 이어진 막대기 각각 하나씩, 가운데 2개로 이어진 막대 4개. 즉 총 6(2+4)개가 되는 것이다. 해당 문제를 풀이는, 특정한 점에서부터 막대의 시작과 끝을 처리한 뒤 이를 하나의 막대로 취급하기 위해 DFS 알고리즘으로 구현하였다. 2023.06.01 - [개발/algorithm] - 프로그래머스 - Lv.2 타겟넘버 / 깊이 우선 탐색(DFS)와 너비 우선 탐..