https://www.acmicpc.net/problem/2021 2021번: 최소 환승 경로 첫째 줄에 역의 개수 N(1≤N≤100,000), 노선의 개수 L(1≤L≤100,000)이 주어진다. 다음 L개의 줄에는 각 노선이 지나는 역이 순서대로 주어지며 각 줄의 마지막에는 -1이 주어진다. 마지막 줄에는 출발 www.acmicpc.net 디스코드방에서 추천받아서 풀어본 문제 일단 "최소" 라는 단어에서 다익스트라라는 감을 잡았다. 근데 같은 노선끼리는 이동거리를 0으로 해석해줄 수가 있어서, 사실상 같은 노선을 싹 뭉뚱그려서 하나의 무언가로 봐주는 과정이 필요하다 유니온 파인드 비슷한 느낌으로 노선 L개를 N+1번부터 각 노선당 한개의 노드를 할당해줬고, 각 역에서는 갈수있는 노선들을 이어줬다. 즉 ..
KMP P2 자력솔 헉!!!! https://www.acmicpc.net/problem/2401 2401번: 최대 문자열 붙여넣기 어떤 긴 문자열이 주어지고 여러 개의 짧은 문자열들이 주어질때 이때 짧은 문자열을 긴 문자열에 붙여 넣을때 가장 길게 붙여 넣는 경우를 찾아라. 단 이때 짧은 문자열들끼리는 교차 할 수 없 www.acmicpc.net 일단 처음 보고 한 생각은 KMP를 쓰더라도 브루트포싱은 힘들겠구나 였다. 문자열을 중복으로 넣을수 있다는 점에서 완탐을 하면 확실하게 시간초과임이 와닿을듯? 근데 이 문제는 긴 문자열 S에 어떤 짧은 문자열 s를 매칭 시킬 때, 매칭된 위치가 k라고 하면 S의 [0,k) 까지의 범위는 해당 문자열을 붙여넣던 말던 항상 값이 변하지 않는다. 앞서 문자열을 붙여넣..
백랜디 도중에 만난 문제 세종정보올림피아드에서 비슷한 유형의 문제를 접했던 기억이 있어서 "케이크처럼" 쉽게 풀어보았다. https://www.acmicpc.net/problem/1374 1374번: 강의실 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net 강의 시작시간과 종료시간을 기준으로 탐색하면 10억번의 탐색을 필요로 하고, 시간초과를 받음이 매우 직관적으로 보인다 강의의 시작시간과 종료시간 사이에는 그 강의가 항상 있음이 보장 되기 때문에, 그 중간 시간에 대해서 탐색할 필요가 없다는게 시간 절약 방법의 핵..
풀이법이 신기해서 가져와본 문제. https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 2의 제곱수 리터 만큼의 물이 들어있는 물병의 갯수가 K개 이하가 되도록 물병을 합쳐보는 문제. 처음에는 1리터짜리 물병 a개, 2리터짜리 물병 b개. 4리터짜리 물병 c개.... 이렇게 갯수별로 저장해보려고 했었는데 지나치게 뜬구름 잡는 내용인가 싶어서 태그를 까봤다. 태그에 "비트마스킹" 이 있는게 좀 결정적이었다고 생각한다. 위의 방법대로 갯수대로 저장을 하면, ..
이분 매칭 연습 문제 https://www.acmicpc.net/problem/11377 11377번: 열혈강호 3 첫째 줄에 직원의 수 N과 일의 개수 M, 일을 2개할 수 있는 직원의 수 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있 www.acmicpc.net 열혈강호 2와 기본적인 사고의 틀을 공유한다. 하지만 열혈강호 2처럼 문제를 접근한 뒤 매칭 수가 N+K개일때 탈출시키는 방법으로 구현하면 K명보다 더 많은 인원이 일을 2개 하는 경우가 존재해 틀렸습니다를 받게 된다. 각 직원마다 정점을 2개로 하는 접근방법은 똑같이 가져가되, 정점 그룹을 두개로 나눠서, 1 M >> K; for(..
USACO https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net N이 8만으로 크기 때문에 O(N^2) 시간복잡도를 가지는 프로그램으로는 이 문제를 해결할 수 없다. 풀이가 떠오르지 않아서, stack 자료구조를 사용한다는 힌트를 태그 분류를 통해 얻고 시작했다. 기존의 K번 빌딩에서 볼 수 있는 빌딩 옥상의 개수를 확인하려면, K보다 큰 인덱스에 대해 탐색을 해야 하는데, 문제를 거꾸로 뒤집어서 K번 빌딩"을" 볼 수 있는 빌딩들의 개수 로..