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) 까지의 범위는 해당 문자열을 붙여넣던 말던 항상 값이 변하지 않는다. 앞서 문자열을 붙여넣..
실버골드 랜덤디펜스 BFS를 사용해서 풀어보았다. https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 처음에는 S에서 시작해서 T로 문자열을 하나씩 붙여가면서 완탐을 돌릴 생각을 했는데, S.length() 가 1이고 T.length()가 50인경우에는 메모리초과가 발생하게 된다. 그래서 미리미리 불가능해보이는 경우의 수는 쳐낼생각을 해야 하는데, 생각을 정 반대로 바꿔서 T에서 시작해서 S로 문자열을 하나..
백랜디 도중에 만난 문제 세종정보올림피아드에서 비슷한 유형의 문제를 접했던 기억이 있어서 "케이크처럼" 쉽게 풀어보았다. https://www.acmicpc.net/problem/1374 1374번: 강의실 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net 강의 시작시간과 종료시간을 기준으로 탐색하면 10억번의 탐색을 필요로 하고, 시간초과를 받음이 매우 직관적으로 보인다 강의의 시작시간과 종료시간 사이에는 그 강의가 항상 있음이 보장 되기 때문에, 그 중간 시간에 대해서 탐색할 필요가 없다는게 시간 절약 방법의 핵..
백준랜덤디펜스 도중에 만난 문제 예전에도 지문을 한번 읽었던거같은데 바로 아이디어 떠올릴수있는거보면 실력이 늘긴 늘은거같아서 흐뭇하다 https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net lis임을 관찰해내기 어려워서 골드4라고 하는데, 개인적으로는 좀 빠르게 찾아낼 수 있었다. 처음에는 머지소트를 사용해서 교차횟수를 세는 문제인가? 라는 생각을 하고 시작했다. 근데 이 문제는 버블정렬처럼 인접한 두 원소를 swap 하는게 아니고, 저 멀리 떨어져있는 것들..
풀이법이 신기해서 가져와본 문제. 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번 빌딩"을" 볼 수 있는 빌딩들의 개수 로..
ㅂUSACO 문제풀이 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 힌트를 유심히 봐야할 필요가 있는 문제 얼핏 보기에는 매우 dfs/bfs 문제같이 생겨먹었지만 위 사진에서의 두번째 힌트에서 보듯 dfs/bfs로는 "Y" 자 탐색을 진행할 수 없기 때문에 다른 접근이 필요하다. 전체 판이 25칸으로 만들어져 있고, 이중에 '소문난 칠공주'의 7개 칸이 반드시 자리하고 있어야 하기 때문에, "브루트포스 알고리즘" 이라는 태그에 맞게 25개 칸 중..
오늘의 USACO(6) https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net [s,e] 구간의 합이 N이 되도록 하는 s,e 쌍의 갯수를 구하는 문제. 처음에 문제를 보고 들었던 생각은 누적합 배열 이었고, 그래서 구간을 편의상 (s,e] 로 조정한 다음, N의 범위 천만까지의 연속된 자연수의 합을 담아두는 prefix 배열을 만들어서 prefix[e] - prefix[s] 로 (s,e] 구간의 자연수의 합을 구하려는 생각을 했..