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/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 핵심 아이디어 bfs를 사용하는 문제이다. 기존 NxN 보드에서 사용하는 것과 달린 일직선에서 적용한다는 점만 다르며, +1, -1, *2 되는 지점을 큐에 넣어서 탐색하면된다. "use strict"; const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, outp..

www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. www.acmicpc.net 핵심 아이디어 dfs/bfs 방식으로 풀 수 있는 문제이고 입력 크기가 작기에 dfs로 풀어도 상관없다. dfs는 재귀적으로 더이상 탐색할 노드가 없을 때 재귀를 탈출하게 되는데, 그 점을 이용하여 재귀를 탈출할때마다 방문했던 수를 배열에 추가해주고 출력하면된다. 'use strict'; const readline = require('readline'); const rl = readline.createInterfa..

문제 민오는 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다. 어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게 되었다. 예를 들어 1번 문제를 풀고 나면 4번 문제가 쉽게 풀린다거나 하는 식이다. 민오는 다음의 세 가지 조건에 따라 문제를 풀 순서를 정하기로 하였다. N개의 문제는 모두 풀어야 한다. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. 가능하면 쉬운 문제부터 풀어야 한다. 예를 들어서 네 개의 문제가 있다고 하자. 4번 문제는 2번 문..

문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. 출력 M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. 핵심 아이디어 이분탐색으로 찾으면된다! 최악의 경우 N,M이 각각 100000개 이므로 일반적인 방법으로는 시간초과가 나기 때문이다. 'use strict..

문제 서로 다른 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 순으로 증가함을 알 ..

문제 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 있다. 문자열의 시작과 끝은 공백이 아니다. ''가 문자열에 있는 경우 번갈아가면서 등장하며, '

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