복습노트 복습노트

문제 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net N * M의 크기의 지도가 있다. 각 지도 칸은 정수가 쓰여있고, 주사위를 동서남북으로 굴려서 주사위의 윗면의 숫자를 출력하는 문제이다. 주사위는 예를 들어 위와 같이 전개도를 가진다. (주사위의 윗면이 1, 밑면이 6이다.) 주사위는 맨처음에 N * M 지도의 [x][y]의 위치에 존재해 있다. 주사위를 굴렸을 때, 이동한 칸에 쓰여 있는 수가 0이면, 주사위의 바닥면에 쓰여 있는 수가 칸에..

문제 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net N * N 크기의 공간에서 아기 상어가 먹이를 먹지 못할 때 까지 최소 시간을 구하는 문제이다. 아기 상어는 상하좌우 움직일 수 있고 한 칸 움직일 때 마다 1초가 지난다. 아기 상어는 항상 가장 가까운 먹이를 먹는다. 아기 상어의 크기는 처음에 2이고 먹이는 자신의 크기보다 작거나 0보다 클 경우 먹을 수 있다. 자신의 크기와 같은 먹이는 먹지는 못하고 이동만 가능하다. 반면에 자신의 크기보다 큰 먹이가 있는 곳은 지나갈 수 없다. 만약 먹을 수 있..

문제 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net v개의 정점과 e개의 간선정보를 입력 받아 최소 스패닝 트리를 출력하면 되는 문제이다. M개의 간선정보가 주어지는데 예를 들어 1 2 3 으로 들어오면 1번 정점과 2번 정점이 간선 비용이 3으로 연결 되어 있다는 의미이다. static class tuple{ int x; int y; int cost; tuple(int x, int y, int cost){ this.x = x; this.y = y; this.c..

문제

문제 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 노드의 갯수 n, 간선의 정보 m개, 시작 노드 v를 입력받아 DFS와 BFS 한 결과를 출려하면 되는 문제이다. 그동안 C++로 알고리즘을 풀다가 처음으로 JAVA로 구현하다 보니 헷갈리는 부분이 많아 정리한다. C++ 에서는 2차원 벡터로 구현하면 된다. 1) 인접 행렬 구현 arr[a][b] = 1 (a에서 b로가는 간선이 있다.) arr[a][b] = 0 (a에서 b로 가는 간선이 없다.) for(int i = ..

문제 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 문자열 S가 주어지면 부분 문자열 P에서 최소 DNA문자{A, C, G, T} 의 각각의 개수를 만족하는 부분문자열의 개수를 구하는 문제입니다. 예를 들어 S = AAACCTGCCAA 이고 P = 4, {A, C, G, T} = {1, 1, 1, 0}이라면 "GCCA" 가 조건을 만족한다. 문자열의 길이가 최대 1000000이므로 완전탐색을 하게 되면 시간초과가 납니다. 따라서 시작 인덱스와 끝 인덱스를 옮기는 "슬라이딩 윈도우" 방법..

문제 2567번: 색종이 - 2 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변 www.acmicpc.net 100 * 100 인 공간에서 길이가 10인 정사각형 색종이 좌표가 n개 주어졌을 때 n개의 색종이의 둘레를 구하는 문제입니다. 단순히 가로와 세로의 길이만 구하면 되는 문제 같지만 왼쪽 그림과 같이 중간에 구멍 둘레도 구해야 하기 떄문에 까다로운 문제입니다. 아이디어만 생각하면 간단한 문제입니다. 100 * 100 이차원 공간에서 색종이로 덮힌 공간은 1로 채우고, 1로 채운 공간을 4방향으로 순회하면서 0인 갯수를 세어주면 둘레가 됩니다. import j..

문제 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net n이 주어지면 1 ~ n 까지의 연속된 수들의 합이 n인 경우의 수를 구하는 것입니다. 예를 들어 n = 15이면 {1, 2, 3, 4, 5}, {456}, {7, 8}, {15} 총 4가지 입니다. 투포인터를 사용했습니다. import java.util.Scanner; public class boj_2018 { public static void main(String[] args) { Scanner sc = new Scanner(Sys..