https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 두 공장을 잇는 가중치의 최솟값이 최대가 되게 하는 문제. 이렇게말하니까 되게 어려워보인다;; 문제의 핵심은 중량제한이 낮은 다리는 굳이 건널 이유가 없다는 발상. 중량제한이 높은 다리들만 이용해서 두 공장을 연결할 수 있다면 정답에 쉽게 도달할 수 있을것이다. "두 공장을 연결할 수 있다면" >> 유니온파인드를 이용해서 두 공장이 연결됬..
상당히 까다로웠던 문제 좀 푸는데 오래걸렸다 https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 구하고자 하는 걸리는 날을 T라고 할때, 매일매일 vis배열을 초기화하면서 호수를 탐색하면 시간초과나 메모리초과를 받게 된다. 첫째날에 대부분을 미리 탐색해 놓고, 두번째 날부터는 얼음과 물의 경계선에 해당하는 부분에서만 탐색을 진행해주면 연산량이 극적으로 감소하면서 시간초과 / 메모리초과 둘다 잡히는듯. 큐 두개를 활용해서..
유니온 파인드 == disjoint set 문제 소프트웨어 마에스트로 코테에 나왔다고 들어서 한번 다시 풀어보는 중이다. https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 여행이 가능한지 안 가능한지만 묻고 있고, 여행 경로의 길이에 제한이 없기 때문에 특정 여행 경로로 두 도시가 이어질 수 있는지, 즉 모든 여행 계획에 속한 도시가 같은 도시집합 상에 포함되는지를 판별하면 되는 문제다. 여행 계획에 속한 도시들에 대해서 find() 를 진행하고..
https://www.acmicpc.net/problem/13506 13506번: 카멜레온 부분 문자열 문자열 S의 부분 문자열 T 중에서, 접두사(Prefix)도 될 수 있고, 접미사(Prefix)도 될 수 있고, 두 경우가 아닌 위치에도 등장하는 T를 카멜레온 부분 문자열이라고 한다. 문자열 S가 주어졌을 때, 카 www.acmicpc.net 접두사와 접미사가 같으면서 세군데 이상에서 등장하는 부분문자열을 구하는 문제. 메모리초과와 시간초과 둘다 낭낭하게 받아본 문제 되시겠다 생각보다 제한이 빡빡하지 않나 하는 생각이 든다. 일단 문자열의 길이를 N이라 했을때 fail[N-1] 을 통해서 접두사와 접미사가 같은 최대 길이 부분문자열을 구할 수 있고, 이 부분문자열을 KMP를 돌려서 3개 이상 탐색되는..
KMP 연습문제 https://www.acmicpc.net/problem/1787 1787번: 문자열의 주기 예측 P8 = 6, P7 = 6, P6 = 4, P5 = 4, P4 = 2, P3 = 2, P2 = 0, P1 = 0 www.acmicpc.net 실패함수를 활용해 구한 값과 정확히 정반대를 요구하는 문제. 접두사와 접미사가 같아지는 최소 길이를 구해서 문자열의 전체 길이와 빼면 문제에서 요구하는 "추정할 수 있는 주기 중 가장 긴 것의 길이" 를 구할 수 있다. 실패함수에서 뒤로 돌아가고자 할때 j = fail[j-1]; 사용하는 이 구문에서 착안하고 while(dp[i] && fail[dp[i]-1]) dp[i] = fail[dp[i]-1]; 계속 뒤로 돌아가게끔 while문을 사용해서 작성해..
https://www.acmicpc.net/problem/7575 7575번: 바이러스 첫 번째 줄에는 감염된 프로그램의 개수 N 과 바이러스 코드 추정을 위한 최소 길이를 나타내는 정수 K 가 주어진다. 단, 2 ≤ N ≤ 100이고, 4 ≤ K ≤ 1,000이다. 두 번째 줄부터 각 프로그램에 대한 www.acmicpc.net KMP 3일차 그 두번째 문제 문제가 복잡하게 생겼는데 구현 자체는 그리 복잡하지는 않다. 입력되는 문자열 중 하나에서 길이가 K인 부분문자열 S'를 분리한 뒤, 다른 모든 문자열에 이 S' 이 포함되어있는지 세어주면 되는 문제이다. KMP 알고리즘을 적용하면 생각보다 나이브하게 풀리니까 부분문자열 분리하거나 할때 괜히 복잡하게 고민하지 말고 그냥 O(N)으로 분리해주도록 하자..
https://www.acmicpc.net/problem/1701 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 www.acmicpc.net KMP를 뇌에 박기위한 연습 3일차 실패함수 배열을 활용하는 문제였다. 접두사와 접미사가 같아지는 최대 길이가 fail[k] 일때, 접두사와 접미사가 같아지면서 두번 이상 나오는 문자열의 조건을 충족하기 때문에, 실패함수 배열에서의 최대값이 문제에서 요구하는 정답이 된다. 접미사는 가변적으로 바뀔수 있는 반면 접두사는 문자열의 제일 앞을 항상 포함하고 있기 때..
https://www.acmicpc.net/problem/13705 13705번: Ax+Bsin(x)=C 첫째 줄에 정수 A, B, C가 주어진다. (0 =B 이므로 f'(x) 는 모든 x에 대하여 0 이상임을 확인할 수 있다. f(x)가 증가하는 함수이기 때문에, 이분탐색을 통해서 답을 구해줄 수 있고, 이렇게 해결할시 보다 쉬운 버전인 14786번을 해결할 수 있다. 웃긴게 요구하는 정확도 자체는 14786이 더 높다;;; 테스트케이스의 ..
https://www.acmicpc.net/problem/11585 11585번: 속타는 저녁 메뉴 수원이와 친구들은 저녁 메뉴를 잘 선택하지 못한다. 배가 고픈 수원이가 보다 못해 메뉴를 정하곤 하는데 이마저도 반대에 부딪히는 경우에는 수원이가 원형 룰렛을 돌려 결정하곤 한다. 이 원 www.acmicpc.net 바로 전에 풀었던 10266 - 시계 사진들과 상당히 유사한 문제 환형으로 이어지는 문자열에서 다른 문자열이 몇번 포함되는지 체크하는 문제이다. 환형을 일일히 구현하기는 상당히 복잡하기 때문에 그냥 문자열 A와 B가 있을때 A를 두번 이어붙인 A' 속에 B가 몇번이나 포함되는지 세면 된다. 몇번이나 포함되는지 세는것은 kmp 알고리즘의 구현에 해당한다. 조심해야할 부분으로써 1 A A 와 같이..
KMP 알고리즘을 장기기억에 남기기위해서 텀을 두고 풀고있다 아직까지는 기억해내는듯 https://www.acmicpc.net/problem/10266 10266번: 시계 사진들 상근이는 보통의 시계와는 다른 독특한 시계 사진 두장이 있습니다. 시계는 n개의 동일한 길이와 목적을 가진 시계 바늘들을 가지고 있습니다. 애석하게도 시계의 숫자들은 희미해져 각 시계 바 www.acmicpc.net 시곗바늘의 위치가 36만 등분된 각도값으로 주어질 때, 시계 1번을 적절히 회전하여 시계 2번을 만들 수 있는지 묻는 문제이다. 시곗바늘의 위치를 36만칸 짜리 배열에다 저장해서, 시곗바늘이 있는 곳의 배열 값을 1이라고 했을때 배열을 주우우욱 나열해놓고 보면 0과 1로 만들어진 36만자 짜리 문자열이 된다. 그러면..