www.acmicpc.net/problem/1009 1009번: 분산처리 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000) www.acmicpc.net 분명히 쉬운문제 같은데 매우 풀기 까다로운 문제였다. 당장 내일 같은 문제를 만단다더라도 헷갈릴것같다. 핵심아이디어 a**b개의 데이터를 1~10번 컴퓨터로 차례로 처리할 때, 마지막 데이터는 몇번 컴퓨터가 처리하는가를 묻는 문제이다. 컴퓨터는 총 10대이므로, a**b가 1이면 1번컴퓨터, 20이면 10번컴퓨터, 115면 5번컴퓨터가 마지막 컴퓨터가 된디ㅏ. 즉, a**b의 1의자리 값만 알면 마지막 데이터를 처리하는 ..

www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 핵심 아이디어 문제와 입력 형식을 보자마자, 위상정렬로 풀 수 있는 문제임을 알 수 있다. 위상정렬 기본 템플릿을 적용하여 풀면된다. const readline = require('readline'); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const soluti..

www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 핵심아이디어 문제에서 요구한 구현사항을 그대로 구현하기만 하면된다. 각 정점에 대해, ~보다 작은 수/~보다 큰 수를 구한뒤 더 했을때 n-1개가 되면 자신의 위치를 정확히 알고 있는 점을 이용한다. ~보다 작은 수/~보다 큰 수는 어떻게 구하는가? 각 정점간의 relation을 dfs의 edge처럼 사용하여 탐색하며 카운팅해주면 된다. 끝이다. const readline = require('readline');..

www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 비슷한 알고리즘으로는 LIS가 있는데, LIS가 기억나지 않아서 급하게 찾아보았던 문제였다 ㅜㅜ 핵심아이디어 주어진 수열에서, 증가하는 부분수열 중 가장 합이 큰 것을 구하는 문제이다. 당연히 모든 경우의 수를 탐색할 수 없으므로, dp를 사용해야한다. dp[i] 를 i번째 까지의 수에서 가장 큰 증가하는 부분수열의 합이라고 정의한다. 그럼 dp의 초기..

www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 핵심 아이디어 가장 작은 사이클을 가지는 경로의 전체 가중치를 구하는 문제이다. 여기서 사이클을 판단하는 방법으로는 union find를 생각했었는데, 그 보다 더 간단한 방법이 있었다. 바로 '플로이드 와샬'방법을 사용하는 것! 일반적으로 플로이드 와샬 알고리즘을 사용할때에는 i->i인 경로, 즉 matrix[i][i]는 INF으로 통일한다. 하지만 i->i경로 matrix[..

www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 핵심 아이디어 해당 위치에서의 경로가 존재하는지 판단하는 문제로, 플로이드 와샬 알고리즘으로 해결할 수 있다. 플로이드 와샬 알고리즘은 dp 개녕을 깔고 들어가는데, 모든 정점to정점을 순회하되, 중간지점인 k를 두어서, k를 거쳐하는 경로가 더 짧은 경우에 matrix값을 갱신시켜주는 역할을 한다. const readline = require('readline'); const rl = readline.createInterface({ input: pro..

www.acmicpc.net/problem/10818 10818번: 최소, 최대 첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다. www.acmicpc.net 핵심아이디어 머리식힐겸 풀어볼만한 아주 간단한 문제이다. 하지만 Javascript(nodejs)로 풀때 Math.max(...array) 를 사용한 후에 제출하면 분명 런타임에러가 뜰것이다.. 이 문제의 함정은 N이 1,000,000까지 있으며, Math.max를 사용하면 오버플로우가 난다는 것이다. 결국엔 배열에서 max,min 을 리턴하는 함수를 따로 만들면 쉽게 해결 ..

www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 핵심아이디어 일반 다익스트라 문제에서 경로탐색 기능이 추가된 문제이다. 모든 정점에서 다익스트라 알고리즘을 돌리되, 이전 정점을 기록해놓는 path 배열을 만들어두고 다익스트라 알고리즘이 모두 수행된 뒤에, path로 역추적하며 경로를 파악하면 된다. 'use strict'; const readline = require('readline'); const rl = readline.createInterface({ input..