선택은 나의 것

문제 SWEA 7087 : 문제 제목 붙이기 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 접근 n개의 문자열을 받을 때 가장 앞글자의 알파벳만 기억해주면 된다. 따라서 eng라는 배열에 A~Z의 등장 횟수를 저장해 줬다. eng의 0번째('A')부터 26번째('Z')까지 가는 도중에 등장 횟수가 0인 알파벳이 있다면 그대로 종료해 준다. A, B, C, ... , Z가 순서대로 한 번씩 등장해야 하기 때문이다. 코드 // algorithm study // SWEA_[D3]7087_문제 제목 붙이기 #include using namespace std; int main() { int test_case, n; c..

문제 BOJ 2304 : https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 접근 주어진 기둥들을 모두 사용하여 지붕을 지을 때 가장 작은 창고 면적을 구하는 문제이다. 가장 주목해야 하는 조건은 비가 올 때 물이 고이지 않도록 어떤 부분도 오목하게 들어가서는 안 된다는 것이다. 먼저 지붕에 오목한 부분이 없도록 지으려면 지붕의 높이가 낮아졌다가 다시 높아지면 안 된다.(┗ ┛이런 모양새가 되므로 비가 오면 물이 고일 것이다.) 따..

문제 BOJ 13565 : https://www.acmicpc.net/problem/13565 13565번: 침투 문제 인제대학교 생화학연구실에 재직중인 석교수는 전류가 침투(percolate) 할 수 있는 섬유 물질을 개발하고 있다. 이 섬유 물질은 2차원 M × N 격자로 표현될 수 있다. 편의상 2차원 격자의 위�� www.acmicpc.net 접근 석교수가 만든 섬유가 outer side부터 inner side까지 전류가 침투할 수 있는지 알아보는 문제이다. 전류가 통하는 격자는 0으로 통하지 않는 격자는 1로 나타낸다. 따라서 outer side와 닿는 부분인 0번째 격자들을 시작으로 dfs를 돌아 inner side와 닿는 n - 1번째 격자까지 도달할 수 있는지를 알아보면 답을 찾을 수 있다..

문제 BOJ 1305 : https://www.acmicpc.net/problem/1305 1305번: 광고 첫째 줄에 광고판의 크기 L이 주어지고, 둘째 줄에 현재 광고판에 보이는 문자열이 주어진다. L은 백만보다 작거나 같은 자연수이다. www.acmicpc.net 접근 문제를 읽고 가장 먼저 떠오른 방법은 Brute-Force(완전 탐색)를 이용한 방법이었다. 하지만 Brute-Force는 O(N*M)의 시간복잡도를 가지는데, 문제에서 L(문자열 길이)의 최댓값이 백만이기 때문에 Brute-Force를 통해 구현하면 무조건 시간 초과가 날 것이다. 풀이 방법이 마땅히 떠오르지 않아 문자열과 관련된 알고리즘을 알아보다 KMP에 대해 알게 되었다. KMP알고리즘이란 접두사와 접미사를 활용하여 효율적으로..