백준8 [9935 문자열 폭발] 문제 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 접근 및 풀이 처음에 이 문제를 봤을 때는 너무나 당연하게 Cpp의 경우 find, Java의 경우 contains를 사용해 폭발 문자열이 존재하지 않을 때까지 기준 문자열에서 폭발 문자열을 삭제하면 되지 않나 싶었다. 하지만 그렇게 간단할 리가 있나.. 그렇게 접근하고 풀게 되면 당연하게 메모리초과 혹은 시간초과가 발생하게 된다. 그렇다면 어떻게 해야하는가? 만만한 게 스택이.. 2021. 7. 5. [21278 호석이 두 마리 치킨] 문제 https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net 접근 및 해결 1. 각 정점에 대해서 나머지 정점들까지의 최소 거리를 구한다. (플로이드-워샬) 2. 최대 100개의 정점이므로 3중 for문을 사용해 각 정점(집)에서 선택된 치킨 집 2개와의 최소 거리를 구한다. 3. 2에서 최소 값을 구하면 정답! #include #define INF 987654321; using namespace std; int N, M.. 2021. 6. 23. [1446 지름길] 문제 - www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하이고, D는 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주 www.acmicpc.net 분석 및 해결 단순한 bfs 문제였다. 지름길이 항상 |지름길 도착 위치 - 지름길 시작 위치| 보다 짧은 것은 아니라는 점을 주의해야 한다. 따라서, bfs를 통해 지름길을 이용하는 경우, 이용하지 않는 경우 모두에 대해서 탐색을 시도했다. 각 위치마다 모두 지름길을 가지고 있을 수도 있지만, 그렇지 않은 경우가 더 많을 거 같아 Map을 사용해서 graph를 구현했다. 소스 코드 impo.. 2021. 4. 15. [18119 단어 암기] 문제 - www.acmicpc.net/problem/18119 18119번: 단어 암기 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주 www.acmicpc.net 분석 및 해결 기억하고 있는 알파벳의 상태가 매번 바뀌며, 알고 있는 알파벳 상태를 기준으로 N개의 쿼리에 대해 탐색을 실행해야 한다. 따라서, 쿼리의 개수 최대 10,000개, 각 쿼리의 최대 길이 1,000, 알고 있는 알파벳 상태의 변화 최대 10,000번이므로 최대 10의 11승으로 단순하게 반복문을 돌리게 되면 시간 초과가 발생하게 된다. 이런 경우, 비트마스킹을 사용하게 되면 탐색 시간을.. 2021. 4. 14. [1715 카드 정렬하기] 문제 - www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 분석 및 해결 비교 횟수를 최소로 하기 위해서는 비교하는 대상 A, B의 합이 항상 가장 작아야 한다. 이 말은 즉, 카드들 중에서 가장 작은 묶음 2개를 선택하면 된다. 비교 이후, 합쳐진 카드 묶음은 새로운 카드 묶음이 되고, 하나의 카드 묶음이 될 때까지 앞의 과정을 반복해주면 된다. 우선순위 큐를 사용해 합쳐진 카드 묶음을 카드 묶음 목록에 추가함과 동시에 정렬이 되게 하면 문제를.. 2021. 4. 10. [2075 N번째 큰 수] 문제 - www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 분석 및 해결 처음에 봤을 때는 뭔가 대단한 수학적 사고를 요하는 것 같았지만, 우선순위 큐를 이용해 쉽게 풀 수 있었다. 2차원 배열의 모든 원소를 우선순위 큐에 삽입하고, N번만큼 뽑아내면 된다. 소스 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Collections; import java.util... 2021. 4. 6. [7795 먹을 것인가 먹힐 것인가] 문제 - www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 분석 및 해결 쉽게 말해 A배열 모든 원소에 대해서 B배열에서 자신보다 작은 원소들의 개수의 합을 구하는 문제이다. 지난 번에 포스팅한 '순위 검색'에서의 이분 탐색을 적용해 해결했다. 소스 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Array.. 2021. 4. 6. [14503 로봇청소기] 문제 - www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 분석 단순 시뮬레이션 문제이다. 크게 1단계, 2단계가 존재한다. 이에 따라 1단계, 2단계에서 해야하는 일들을 함수로 정의해주었다. 1단계 - solution, 2단계 - stepTwo 로 정의하였다. 각 과정에 해당하는 부분을 주석으로 적어두었기 때문에 자세한 해설을 넘어가도록 하겠다. #include #include using namespace std; int N, M, direction, an.. 2021. 3. 17. 이전 1 다음
