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/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 핵심아이디어 bfs와 dp를 적절히 섞어쓰면 되는 문제이다. 예전에 python으로 풀었는데 지금 풀어보려하니 아이디어가 잘 떠오르지 않았다. dp[x][y] 를 x,y좌표까지 도달할때 소모해야 하는 최소 검은방의 개수로 정의하고 bfs를 돌리면된다. 그리고 이때에는 visited를 사용하면 안되는데 그 이유는, 각 방의 최소값을 계속 판단하여 dp값을 업데이트해주어야 하는데, visited으로 초반에 방문처리를 해버..

www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 핵심아이디어 전형적인 DFS문제라서 딱히 언급할 것이 없다. 연결된 모든간선에 대해 dfs를 수행하되, 방문처리를 한 노드는 방문하지 않으면 된다. 'use strict'; const readline = require('readline'); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const solut..

문제 서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까? 입력 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. 출력 첫째 줄에 자연수 N의 최댓값을 출력한다. 핵심 아이디어 서로다른 n개의 수를 합쳤더니 s가 되었고, s가 주어진다. 이때 최대 n을 구하면 되는데, 최대 n을 만드려면 최대한 작은 수를 여러번 사용하기만 하면된다. 하지만 서로 다른 자연수여야 하므로, 1부터 1씩 증가해가며 더해주다가 s가 넘어가는 시점에 멈추고 1을 빼주면된다. 예를 들어서 s=200일때 1부터 20까지 차례로 더해보면 1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190 210 순으로 증가함을 알 ..

www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이 www.acmicpc.net 우선순위 큐를 사용하는 간단한 문제인데, python에서는 heap 라이브러리가 있어서 쉽게 풀 수 있었으나, javascript에는 우선순위 큐를 직접 구현하여 해결해야한다는 것 때문에 조금 낮설었다. 앞으로 코딩테스트를 하면, 자바스크립트에서 제공하지 않는 라이브러리로 문제를 해결해야할 일이 많아질 텐데 템플릿을 복사해가며 문제를 해결해야할 것 같다는 생각을 했다. 아래는 MinHeap소스코드..

문제 일 년 동안 세계일주를 하던 영식이는 여행을 하다 너무 피곤해서 근처에 있는 코레스코 콘도에서 하룻밤 잠을 자기로 하고 방을 잡았다. 코레스코 콘도에 있는 방은 NxN의 정사각형모양으로 생겼다. 방 안에는 옮길 수 없는 짐들이 이것저것 많이 있어서 영식이의 누울 자리를 차지하고 있었다. 영식이는 이 열악한 환경에서 누울 수 있는 자리를 찾아야 한다. 영식이가 누울 수 있는 자리에는 조건이 있다. 똑바로 연속해서 2칸 이상의 빈 칸이 존재하면 그 곳에 몸을 양 옆으로 쭉 뻗으면서 누울 수 있다. 가로로 누울 수도 있고 세로로 누울 수도 있다. 누울 때는 무조건 몸을 쭉 뻗기 때문에 반드시 벽이나 짐에 닿게 된다. (중간에 어정쩡하게 눕는 경우가 없다.) 만약 방의 구조가 위의 그림처럼 생겼다면, 가로..

문제 정렬되어있는 두 배열 A와 B가 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다. 출력 첫째 줄에 두 배열을 합친 후 정렬한 결과를 출력한다. 핵심 아이디어 언어에 따라 전략을 다르게 짜야하는데, python은 그냥 배열2개를 더해서 sorted를 해주면되고, javascript같은 경우는 시간초과가 난다. A,B가 정렬되어 있으므로 앞 원소부터 비교해가며 정답배열에 차곡차곡 쌓는 방법을 써야한다. 이때 앞 원소를 pop해주는 방식..