문제 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 풀이 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 구한다. 소스 코드 const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt"; const input = require("fs") .readFile..
문제 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 풀이 지도의 크기 n * m 이며 0은 갈 수 없는 땅, 1은 갈 수 있는 땅, 2는 목표지점을 나타낸다. 각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다. 목표지점에서 시작하는 BFS를 수행하여 갈 수 있는 모든 땅을 탐색하며 해당 땅에서 목표지점까지의 거리를 구한다. queue에 좌표를 저장할 때 cnt를..
문제 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 2중 for문으로 값이 1인 위치를 찾는다. 이 때 총 단지수를 1증가시키고 해당 위치에서 시작하는 BFS를 수행한다. BFS를 통해 방문할 수 있었던 위치의 수를 반환한다. 한 번 방문한 위치는 다시는 방문할 수 없도록 값을 0으로 변경한다. 소스 코드 class Queue { constructor() { this.data = []; this.head = 0; this.tail = 0; } push(item) { this.data[this.tail++..
문제 15787번: 기차가 어둠을 헤치고 은하수를 입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)가 주어진다. 이후 두 번째 줄부터 M+1번째 줄까지 각 줄에 명령이 주어진다. www.acmicpc.net 풀이 N개의 기차의 20개의 열을 모두 0으로 초기화한다. M개의 명령을 모두 수행하여 기차의 상태를 변경한다. set 자료구조를 통해 중복되는 기차의 상태를 제거한다. 소스 코드 const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt"; const input = require("fs") .readFileSync(filePath) .toString() .trim() ..
문제 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net 풀이 플로이드 와샬 알고리즘을 통해 모든 노드간 최단 거리를 구한다. 2곳에 치킨집이 존재할 수 있는 케이스를 모두 탐색해 최단 시간의 총합을 구한다. 소스 코드 const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt"; const input = require("fs") .readFileSync(filePath) .toString() .trim() ..
문제 17276번: 배열 돌리기 각 테스트 케이스에 대해 회전 연산을 마친 후 배열의 상태를 출력한다. n줄에 걸쳐 각 줄에 n개의 정수를 공백으로 구분하여 출력한다. www.acmicpc.net 풀이 회전이 발생하는 4가지 행을 각각 그룹화 한다. 이 때 여러 그룹에 중복으로 사용되는 인덱스가 존재한다. 문제에서 주어진 각도 d 를 통해 회전을 몇 번 반복해야 되는지 구한다. 시계 방향과 반시계 방향에 따라 회전을 다르게 구현한다. 반시계 방향은 가장 앞의 행을 가장 뒤로 이동시킨다. 시계 방향은 가장 뒤의 행을 가장 앞으로 이동시킨다. 소스 코드 const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt"; const inp..
문제 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 도시에 있는 치킨집 중에서 M개를 제외한 나머지 치킨집을 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성한다. 즉, 도시의 치킨 거리의 최소값을 구한다. map 배열을 생성할 때, 집의 위치와 치킨집의 위치를 각각 저장한다. 조합 알고리즘으로 M개로 이루어진 치킨집 조합을 모두 구한다. 치킨집 조합 중 치킨 거리의 최소값을 구한다. 소스 코드 const filePath = process...
문제 1025번: 제곱수 찾기 첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 표에 적힌 숫자가 1번 행부터 N번 행까지 순서대로 한 줄에 한 행씩 주어진다. 한 행에 적힌 숫자는 1번 열부터 M번 열까지 순서대로 주어지 www.acmicpc.net 풀이 N * M인 2차원 배열이 주어졌을 때, 행의 번호와 열의 번호가 선택한 순서대로 등차수열을 이루는 서로 다른 1개 이상의 칸을 선택하여 정수를 만든다. 만들 수 있는 정수 중 가장 큰 완전 제곱수를 출력하고 완전 제곱수를 만들 수 없는 경우 -1를 출력한다. 4중 for 문을 통해 배열의 모든 위치에서 가능한 모든 등차를 탐색한다. while 문을 통해 주어진 등차로 위치를 증가시키며 완전 제곱수인지 확인한다. 소스 코드 const file..
문제 1548번: 부분 삼각 수열 세 수 x, y, z가 x+y>z, x+z>y, y+z>x의 관계를 만족하면, 세 수는 삼각관계에 있다고 한다. 마찬가지로 길이가 N인 수열 B(b[0], b[1], ..., b[n-1])의 모든 b[i], b[j], b[k]가 삼각관계에 있으면 이 수열은 삼각 www.acmicpc.net 풀이 수열의 크기가 N 일 때, 가장 긴 부분 삼각 수열의 길이를 출력한다. 수열이 오름차순으로 정렬되어 있을 때, 수열 a, b, c, d 에 대해서 a + b > d 이면 반드시 a + b > c를 만족한다. 수열의 길이가 2 이하인 경우, 항상 삼각 수열이다. i는 수열의 첫 부분, j는 수열의 마지막 부분에서 시작한다. 소스 코드 const filePath = process.p..
문제 2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net 풀이 검은색이 이겼을 경우에는 1을, 흰색이 이겼을 경우에는 2를, 아직 승부가 결정되지 않았을 경우에는 0을 출력한다. 또한, 검은색 또는 흰색이 이겼을 경우에는 연속된 다섯 개의 바둑알 중에서 가장 왼쪽에 있는 바둑알의 좌표를 출력한다. 오목판의 모든 인덱스를 탐색하며 1 또는 2인 위치를 찾는다. 해당 위치를 기준으로 아래 방향, 오른쪽 방향, 오른쪽 위 방향, 오른쪽 아래 방향으로 각각 탐색을 수행한다. 연속된 바둑알이 5개를 초과하는지 확인하고 이..