이 험난한 세상에서어어~

문제 설명 trie 문제집으로 분류되어 있기는 하지만, 구현 문제다. 그리고 굳이 trie를 안 써도 풀린다... 아무튼 해당 문제에서 특이한 점은 주어진 행렬이 이어져 있다고 생각해야 한다는 점이다. 예를 들어서 (0,0)에서 한 칸 위로 올라가면 (-1,0)이 된다. 그렇다면 해당 좌표는 탐색하지 않는 것이 옳지만, 행렬이 이어져 있다고 생각해야 하니 (2,0)을 탐색해줘야 한다. 즉, 좌표가 0보다 작으면 n-1 혹은 m-1의 위치로 들어가고 n 혹은 m의 위치가 되면 0으로 들어가야 한다는 것이다. 그리고 대각선도 탐색해야 한다는 것을 잊어서는 안 된다. 그리고 출력 부분도 조심해야 한다. 문제에서는 신이 좋아하는 문자열은 중복될 수 있다고 했다. 그러므로 중복된 문자열 또한 해당 문자열의 결과 ..

문제 설명 나무들이 주어졌을 때, 해당 나무가 전체 나무에서 몇 %를 차지하는지 구하는 문제이다. 이때 출력은 알파벳 순으로 한다. 여기서 주의할 점은 전체 종의 몇 %가 아니라 입력받은 나무의 몇 %인지를 의미하는 것이다. https://www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 문제 풀이 첫 번째 접근 문자열 집합과 마찬가지로 trie에 분류되어 있는 문제이다. 근데 굳이 trie로 풀 필요는 없을 거 같은... 아무튼 나는 trie로 문..

문제 설명 N개의 문자열로 이루어진 집합 S가 주어질 때, M개의 문자열 중 집합 S에 있는 문자는 총 몇 개인지 구하는 문제이다. https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 난 trie 알고리즘을 연습하고 싶어서 풀었던 문제인데, 사실 굳이 trie 안 써도 되는 문제이긴한다. 문제 풀이 첫 번째 접근 trie알고리즘을 이용해서 풀었다. trie 알고리즘이란 간단하게 말해서 문자열을 검색해주는 것인데, 나..

문제 설명 방향성 없는 그래프가 주어질 때 1부터 n까지 v1과 v2를 지나서 가는 최단 경로를 구하는 문제이다. https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 풀이 첫 번째 접근 다익스트라로 풀어주면 되지만 v1과 v2를 지나가야 한다는 것이 문제이다. 여기서 갈 수 있는 경로는 1에서 v1, v2, n이거나 1에서 v2, v1, n이다. 간단하게 생각해주면 되는데, 일단 1부터 시작하는 다..

문제 설명 해커 yum3이 어느 네트워크 시설의 한 컴퓨터를 해킹했다. 특이하게도 한 컴퓨터가 감염되면 연결되어 있는 다른 컴퓨터도 전염되는 방식인데 웜인가? a가 b라는 컴퓨터에 의존했다면 b 컴퓨터가 감염이 되면 a 컴퓨터 또한 일정 시간 뒤에 전염이 되어 있는 방식이다. yum3이 해킹한 컴퓨터와 각 컴퓨터의 의존성이 주어질 때, 총 몇 대가 감염되고 얼마나 시간이 걸리는지 구하는 문제다. https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 문제..

문제 설명 길이가 N인 컨베이어 벨트가 있고 길이가 2N인 벨트가 있다. 벨트가 한 칸씩 이동하는데, 2n 번째 벨트는 1로 이동하는 돌아가는 형태이다. 로봇은 컨베이어 벨트에만 존재할 수 있는데, 만일 로봇이 어느 순서든 n칸에 위치한다면 해당 로봇을 내려준다. 또한 로봇은 1번 칸에서만 올릴 수 있다. 참고로 벨트의 내구도는 로봇이 이동하거나 로봇을 올렸을 때마다 1씩 감소한다. 내구도가 0인 칸의 개수가 k개 이상이면 종료하는데, 몇 단계에서 종료되는지를 구하는 문제다. 1. 벨트가 움직이면 로봇도 함께 한 칸씩 움직인다. 2. 제일 먼저 컨베이어 벨트에 올라간 로봇부터, 벨트의 회전 방향 대로 한 칸 씩 움직일 수 있다. 만일 이동할 수 없으면 이동하지 않는다. 2-1. 이동할 수 없는 경우의 수..