Doby's Lab

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net Solved By: Flood-Fill 저번 포스팅과 이어지는 문제입니다. Flood-Fill이 무엇인지 배웠다면 이것을 사용하여 시간문제를 해결할 수도 있습니다. 1인 칸에서 0의 개수를 세는 BFS는 다른 1인 칸에서도 개수를 셀 수 있기 때문에 꽤 오래 걸립니다. 하지만, 4가지 방향을 확인했을 때, 어떤 0이 어떤 영역에 속하는지 알고, 그 영역의 크기를 안다면 각 1..

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net Solved By: Flood-Fill 벽 부수고 이동하기4(16946) 문제를 풀려다가 시간 초과가 나서 해결 방법을 찾다가 Flood-Fill Algorithm의 존재를 알게 되었습니다. Flood-Fill이란 주어진 시작점으로부터 연결된 영역을 찾는 알고리즘, 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘을 의미합니다. 이 영역을 BFS를 통해 구할 수 있는데 '왜 16946문제에서 시간을..

https://www.acmicpc.net/problem/2358 2358번: 평행선 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 각 점의 좌표가 주어진다. 만약 입력에 서로 같은 두 점이 주어지면, 그 두 점을 이용하여 직선을 만들 수 있다. 좌표는 절댓값이 231보 www.acmicpc.net Solved By: Map 한 점을 여러 번 선택할 수 있기 때문에 예를 들어 x좌표가 같은 것이 2개 이상이라면 하나의 직선을 만들 수 있습니다. 즉, 점들을 모아서 중복되는 x값들이 2개 이상, 혹은 중복되는 y값들이 2개 이상이 확인된다면 하나의 직선으로 카운트합니다. 허나, 좌표의 절댓값이 2^31보다 작은 정수이므로 배열을 사용할 수 없습니다. 그러므로 map을 사용하여..

https://www.acmicpc.net/problem/7575 7575번: 바이러스 첫 번째 줄에는 감염된 프로그램의 개수 N 과 바이러스 코드 추정을 위한 최소 길이를 나타내는 정수 K 가 주어진다. 단, 2 ≤ N ≤ 100이고, 4 ≤ K ≤ 1,000이다. 두 번째 줄부터 각 프로그램에 대한 www.acmicpc.net Solved By: KMP 길이가 K이상인 코드가 반복되어 나타난다면 바이러스라 판단하므로 길이가 K인 코드가 반복되어 나타나도 바이러스라고 판단할 수 있습니다. N개의 코드 중, 첫 번째 코드( == code[0])를 비교 코드로 두고, code[0]에서 길이가 K인 코드들을 구합니다. -> compareCode 그리고, 나머지 코드들 (code[1] ~ code[N - 1]..

https://www.acmicpc.net/problem/1701 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 www.acmicpc.net Solved By: KMP 주어진 문자열 S에서 2번 이상 반복되는 부분 문자열 중 최대 길이를 찾아야 합니다. 즉, 2번만 반복되어도 문제의 조건을 만족합니다. 이 점을 이용하여 KMP에서 pattern의 prefix와 suffix의 최대 일치 길이를 구하는 방법을 사용해봅시다. 이 방법을 사용하는 이유는 pattern이라는 문자열에서 prefix와 suff..

https://www.acmicpc.net/problem/16172 16172번: 나는 친구가 적다 (Large) 첫 번째 줄에는 알파벳 소문자, 대문자, 숫자로 이루어진 문자열 S가 주어진다. (1 ≤ |S| ≤ 200,000) 두 번째 줄에는 성민이가 찾고자 하는 알파벳 소문자, 대문자로만 이루어진 키워드 문자열 K가 www.acmicpc.net Solved By: KMP 주어진 문자열에서 숫자를 제외하고 다시 문자열을 만들어서 패턴과 KMP를 통해 패턴이 문자열에 속해있는지 찾습니다. #include #include using namespace std; vector getPi(string p){ vector pi(p.size(), 0); for(int i = 1, j = 0; i < p.size()..

https://www.acmicpc.net/problem/9253 9253번: 스페셜 저지 답이 맞으면 YES, 틀리면 NO를 출력한다. www.acmicpc.net Solved By: KMP 3번째로 주어지는 문자열이 pattern이라고 하면, pattern이 a와 b에 존재하는지 KMP를 통해 확인할 수 있습니다. #include #include using namespace std; vector getPi(string p){ vector pi(p.size(), 0); for(int i = 1, j = 0; i 0 && p[i] != p[j]) j = pi[j - 1]; if(p[i] == p[j]) pi[i] = ++j; } return pi; } b..

https://www.acmicpc.net/problem/16916 16916번: 부분 문자열 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net Solved By: KMP 첫 KMP 문제였습니다. 설명으로 적어내긴 어렵고, 아직 확실히 정복하지는 못 한 거 같습니다. 그래도 이해한 대로 주석을 달아두었습니다. #include #include using namespace std; // '문자 매칭에 실패했을 때, 얼만큼 건너뛰어야 하는가?'를 알기 위해 사용 // 주어진 패턴(문자열)의 0 ~ i 부분 문자열까지 // 접두사와 접미사의 최대 일치 길이를 담은 배열 v..