링크: https://www.acmicpc.net/problem/1976문제\(n\)개의 도시 사이의 연결 상태가 인접 행렬로 주어지고 여행 계획에 있는 \(m\)개의 도시가 주어질 때, \(m\)개의 도시를 모두 방문할 수 있는가를 묻는 문제이다. 다시말하면, \(m\)개의 도시가 모두 연결되어있는가를 확인하면 된다. 이 문제는 서로소 집합(Disjoint-Set)으로 간단하게 해결할 수 있다. 각 도시들의 연결 상태만 확인하면 되므로, 연결된 도시들을 집합으로 묶어서 표현한 후 마지막에 주어지는 \(m\)개의 도시들이 모두 같은 집합에 속하는 지 확인하면 정답이기 때문이다.코드

링크: https://www.acmicpc.net/problem/1613이전 풀이: http://joonas-yoon.blogspot.com/2016/04/1613.html문제알고 있는 사건의 전후 관계를 방향성이 있는 간선으로 보면, 서로 다른 두 사건을 유추한다는 것은 어떤 방향으로건 일단 연결이 되어있는가를 물어보는 것이다. 방향 그래프에서 정점 a에서 b로 갈 수 있는 경로가 있는 지 물어보는 문제이다. a에서 b로 가는 경로가 있으면 앞에 있는 사건이 먼저 일어난 것이므로 -1b에서 a로 가는 경로가 있다면 1, 경로가 없다면 0을 출력하면 된다. 문제는 이러한 물음이 한두번이 아니라 s번(최대 50,000번) 물어보기 때문에, 경로를 빠르게 찾을 수 있어야한다. n이 400으로 작으므로 플로이..

링크: https://www.acmicpc.net/problem/9465예전 풀이: http://joonas-yoon.blogspot.com/2014/08/9465.html풀이한 스티커(칸)를 선택하면 인접한 칸은 선택할 수 없게 된다.그럼 대각선만 남게 되는데, 그 대각선 칸도 위 선택을 반복하게 된다. A B C DE F G H 만약 위와 같이 있다고 생각해보자. A를 고른다면 C, D, F, G, H 중에 골라야한다. E를 고른다면 B, C, D, G, H 중에 골라야한다.바로 다음 칸(열)에만 영향이 있고, 그 이후의 C, D, G, H를 고민하는 것은 변함이 없다. 즉 어떤 i번째 열을 볼때, i+2번째 이후의 열은 영향이 없다는 뜻이다. i번째 열에서 고민할 점은 3가지이다. 1. 고르지 않는..

링크: https://www.acmicpc.net/problem/1939 문제어떤 정점 S에서 다른 정점 E까지 가는 경로에서 등장하는 간선의 가중치의 최대값을 구하는 문제입니다. 최단 경로를 살피는 것이 아니라, 최대한 무거운 것을 옮기기 위한 다리만 선정한 경로를 만들어야하므로 최소 스패닝 트리의 반대인 최대 스패닝 트리가 떠오릅니다. 일반적으로 크루스칼 알고리즘은 최소 스패닝 트리를 위해 사용되지만, 이 경우에는 반대로 최대 스패닝 트리를 위해 사용할 수 있을 것 같습니다. (음수 가중치도 없으니 가능해보입니다.) 연결되지 않은 간선 중 가중치가 가장 큰 간선을 선택하면서 스패닝 트리를 만들어가면, 어떤 정점 S와 다른 정점 E이 같은 "연결된 집합"에 속하는 그 순간에 우리가 원하는 경로가 완성됩..

링크: https://www.acmicpc.net/problem/10799문제스택 문제로 유명한 한국정보올림피아드(KOI) 2015 지역본선 문제, 쇠막대기입니다. 사실 스택 없이 풀리는 문제지만요.문제를 읽어보면 쇠막대기의 왼쪽 끝은 여는 괄호, 오른쪽 끝은 닫힌 괄호로 표시하여, 레이저 "()"에 의해 잘려진 막대기 조각이 총 몇 개인지 구하는 문제입니다.잘못된 모양은 없다고 하니 스택으로 별다른 검증은 안해도 됩니다.풀이먼저 풀이의 중간 단계를 생각해봅시다. 문자열 "((()()))"은 쇠막대기가 2층으로 쌓인 형태일 것이고, 위 사진처럼 레이저(노란색 점선)에 의해 잘려나갈겁니다. 여기서 첫 번째 레이저에 집중해봅시다.첫 번째 레이저가 발사된다면 1층에서 2조각, 2층에서 2조각으로 나뉘어서 총 ..

링크: https://www.acmicpc.net/problem/16236문제매번 어떤 물고기를 먹어야 할 때, 현재 위치를 중심으로 BFS를 한다.조건에 만족하는 물고기가 있다면 가장 위, 가장 왼쪽에 있는 물고기를 고른 후 그 위치로 이동한다.현재 아기 상어의 크기는 물고기를 먹은 양만 알면 크기를 알 수 있기 때문에 미리 구해서 사용했다. (먹을 때마다 갱신해도 상관없음)코드

링크: https://www.acmicpc.net/problem/16235문제시뮬레이션여름과 겨울은 양분을 더하는 것밖에 영향을 안 미치기 때문에 같이 처리할 수 있다.링크드리스트로 정렬된 상태 유지 + 나무 개수를 압축하여 표현나무의 개수를 압축해도 수명이 끝난 나무를 확인하는 것 때문에 시간복잡도는 거의 변화가 없어서 고민이 많았는 데, 항상 크기가 1인 나무들이 생기므로 링크드리스트의 앞과 뒤만 잘 관리하면 된다는 것을 Nada님의 코드를 보고 깨달았다.코드

링크: https://www.acmicpc.net/problem/11058출력 결과에 영향을 미치는 연산이 A를 그냥 누르는 거랑(+1), Ctrl-V (+복사했던 크기) 인데 클립보드에 복사해놓은 크기때문에 재귀로 짜는데 애를 먹었다. 복사한 크기만큼 늘어나기 때문에, Ctrl-V 를 하기 위해서는 이전에 Ctrl-A, Ctrl-C 가 꼭 필요하다. 문제에 적힌 연산을 순서대로 A, S, C, V 라고 한다면 \(N=6\)인 경우는 아래와 같이 가능하다. AAAAAAAAASCVAASCVVASCVVV 이 정도가 의미있는 타이핑인거같다. 타이핑을 \(n\)번한 것을 \(f(n)\)이라 하자. 그럼 위 4줄은 각각 \(f(5)+1\), \(f(3)∗2\), \(f(2)∗3\), \(f(1)∗4\) 이다. $..