https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 처음에 문제를 잘못 이해했다. 원소가 중복되는 갯수가 K 이상인 경우로 경계 조건을 오인했다. 예를 들어 5 5 2 2 2라는 값이 들어오면, 중복되는 것이니 총 5개의 원소가 중복된다고 판단했다. 그런데 실제 문제는 약간 다르다. 중복되는 원소가 있는 경우, 중복된 원소들 중 최대 갯수가 K이상인 경우를 발라내는 것이었다. 예를 들어 5 5 2 2 2 라고 하면, 현재 중복된 값은 ..
https://www.acmicpc.net/problem/13913 숨바꼭질3에서 경로를 출력해야하는 문제다.경로를 출력하는 방법은 여러가지가 있다. que에 경로를 함께 기억한다. 경로 배열을 만들고, 각 배열에 올 수 있는 가장 빠른 경로를 업데이트 한다 이렇게 할 경우, 2번은 메모리 초과가 발생했다. 따라서 1번 방법으로 접근했다. 1번 방법으로 접근했을 때, 모든 경로를 숫자로 직접 입력해두었을 때 간단한 연산임에도 불구하고 어마어마한 시간이 필요했다. 돌이켜보면 10만개를 다 돌릴 수도 있는데, 10만개에 대한 주소를 모두 Path로 가지고 있다면 그 String을 넘겨주는 것과 메모리는 장난이 아닐꺼다. "100000 99999 99998 ... 1... 이렇게 온다고 생각해보면 ..
https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 수빈이는 움직이고, 동생은 움직이지 않는다. 따라서 수빈이가 움직이는 경우만 잘 처리해주면 된다. 기본적인 BFS 문제인데, 하나 조심해야할 부분은 순간이동을 하게 되면 이동하는데 필요한 시간이 0초라는 것이다. 따라서 순간이동하는 경우도 가장 뒷쪽으로 넣은 경우, 수빈이가 동생을 만나는 모든 경우의 수에 대해 최소값을 기록해야 정답이 된다. 반대로 Deque을 ..
https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 이분 그래프가 어떤 그래프인지 문제에 있는 설명으로 알 수가 없어, 검색을 하고 풀었다.문제의 핵심은 전체 그래프가 2개의 그룹으로 나누어 질 수 있는지 보면 된다. 예를 들어 처음 탐색을 시작하는 그래프의 그룹을 1이라고 가정하면, 그 다음으로 탐색 되는 그래프의 그룹은 2가 된다. 그리고 그 다음으로 탐색 되는 그래프의 그룹은 1이 된다. 이 경우를 만족하는지를 판별하면 된다. 모든 노드에 대..
https://www.acmicpc.net/problem/2638 6개월 전에 처음 풀었던 문제다. 그 때는 1트만에 해결했는데, 이번에 다시 풀어보니 15트를 했다. 문제를 너무 어렵게 생각했던 것이 문제였다. 이 문제의 핵심은 공기가 내부인지 외부인지를 판단하는 로직이다. 처음 접근했을 때, 이 컨디션을 정의하기 위해 'BFS로 탐색한 공기의 갯수 < 둘러싼 치즈의 갯수'인 경우 모두 내부 공기로 설정을 했다. 이렇게 했을 때, 체크하지 못한 경우의 수가 너무 많았다. 가장 대표적인 것은 0,0부터 시작해서 삥 둘렀는데 치즈와 맞닿은 공기보다 치즈가 더 많은 경우가 존재한다는 것이다. 위 경우가 대표적이다. 0,0부터 시작해서 삥 둘렀는데 모든 공기는 외부 공기다. 그런데 0과 접촉하는 1의 갯..