어흥

문제 링크: https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 한 줄씩 주어진다. 비숍을 놓을 수 있는 곳에는 1, 비숍을 놓을 수 없는 곳에는 0이 빈칸을 사이에 두고 주어진다. www.acmicpc.net 1. 주의할 점 - 처음에 비숍을 안넣는게 최선일 수 있다 - 체스판과 관련된 문제는 흑백으로 나눠서 생각하도록 한다 -> 시간복잡도가 줄어든다 2. 구현 - 백색 칸과 흑색 칸을 구분해서 흑색칸일 때 최대 + 백색칸일 때 최대를 구한다 - 해당칸이 비숍을 놓을 수 있는 칸인 ..

문제 링크: https://www.acmicpc.net/problem/16973 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 왼쪽 위칸은 (Sr, Sc)에 있을 때, 이 직사각형의 가장 왼쪽 위칸을 (Fr, Fc)로 이동시키기 위한 최소 이동 횟수를 구해보자. 격자판의 각 칸에는 빈 칸 또는 벽이 있다. 직사각형은 벽이 있는 칸에 있을 수 없다. 또한, 직사각형은 격자 www.acmicpc.net 1. 주의할 점 - 이동할 때, 범위를 벗어나지 않도록 한다 - 이동할 때, 다음 위치가 1이면 가지않는다 - 이미..

문제 링크: https://www.acmicpc.net/problem/7682 7682번: 틱택토 문제 틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 두 번째 사람이 O를 놓는다. 어느 때든지 한 사람의 말이 가로, 세로, 대각선 방향으로 3칸을 잇는 데 성공하면 게임은 즉시 끝난다. 게임판이 가득 차도 게임은 끝난다. 게임판의 상태가 주어지면, 그 상태가 틱택토 게임에서 발생할 수 있는 최종 상태인 www.acmicpc.net 1. 주의할 점 - 만들어질 수 있는 O,X의 개수인가 (ex. O 2개, X 7개) - 도중에 끝나는 경우, 반드시 한가지 ..

문제 링크: https://www.acmicpc.net/problem/1944 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어진다. 1은 미로의 벽을 의미하고, 0은 지나다닐 수 있는 길, S는 로봇이 출발하는 위치, K는 열쇠의 위치가 주어진다. S는 1개, K는 M개가 주어진다. S와 K에서만 복제를 할 수 있음에 유의한다. www.acmicpc.net 1. 주의할 점 - MST 알고리즘에 대해 알고 있어야 한다. - 시작점을 따로 기억하고 S 또한 K와 같은 Node로 취급한다 - S 와 K 모두 No..

문제 링크: https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) www.acmicpc.net 1. 주의할 점 - 최소 3번의 다익스트라 알고리즘을 사용해야 한다 - 반드시 지나야 하는점으로 시작점, 도착점 형태로 들어올 수 있다 2. 구현..

문제 링크: https://www.acmicpc.net/problem/1701 1701번: Cubeditor 문제 Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 끝에 새로운 에디터를 만들게 되었고, 그 에디터의 이름은 Cubeditor이다. 텍스트 에디터는 찾기 기능을 지원한다. 대부분의 에디터는 찾으려고 하는 문자열이 단 한 번만 나와도 찾는다. Cubelover는 이 기능은 Cube www.acmicpc.net 1. 주의할 점 - KMP 알고리즘에 대해 알고 있어야 한다 2. 구현 - Substr함수를 통해 입력 받은 문자의..

문제 링크: https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 일치한다면, i를 출력하는 식이다. www.acmicpc.net 1. 주의할 점 - KMP 알고리즘에 대하여 알고 있어야 한다 - 공백 문자도 받을 수 있어야 한다 - 애매하게 알고 있다면 이전 게시글을 참고한다 https://imnotabear.tistory.com/117 [백준 16916] 부분 문자열 (JAVA) 문제 링크: https://www.acmicpc.net/problem/16916 16916..

문제 링크: https://www.acmicpc.net/problem/16916 16916번: 부분 문자열 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 1. 주의할 점 - KMP 알고리즘에 대해 알고 있어햐 한다 2. 구현 - 문자열 P와 S를 입력 받는다 - getPi()함수를 통해 접미사와 접두사의 일치 길이를 나타내는 배열을 반환한다 - KMP 알고리즘을 통하여 진행한다 - KMP 알고리즘에 대해 간략히 설명을 하면 다음과 같다 Origin의 문자열은 i를 통해 문자를 가리키고, Pattern의 문자열은 j를 통해 문자를 가리킨다 Origin[i] == ..