Doby's Lab

https://www.acmicpc.net/problem/14942 14942번: 개미 자연수 n이 주어진다. n은 방의 개수이다. (1 ≤ n ≤ 105) 다음 n개의 줄에는 차례대로 현재 각각의 개미가 보유하고 있는 에너지 값이 주어진다. i+1번째 줄에는 i번째 방에 있는 개미가 가진 에너 www.acmicpc.net Solved By: LCA, Sparse Table 1번 방까지 가야 하고, 경로가 n - 1개 있으며 한 방에서 다른 방으로 갈 수 있는 경로는 존재하며 유일하다 했으므로 이는 root node가 1인 트리를 의미합니다. 그리고, 각 방에서 주어진 에너지를 가지고, 1번 방까지 도달해야 하니 어떤 노드로부터 시작해서 1번 방으로 가는 길에 에너지를 다 쓰거나 남은 상태로 도착하게 되..

https://www.acmicpc.net/problem/5847 5847번: Milk Scheduling Farmer John's N cows (1

https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net Solved By: Topological Sort or Dijkstra 우선적으로 최장 경로를 구해야 하기 때문에 Dijkstra가 떠올랐습니다. >> 가중치들을 음수로 바꾸어 최장 경로를 구하는 테크닉 사용 + Topological Sort를 사용하여 최장 경로를 구할 수 있습니다. Topological Sort의 기본 원리를 기억하며 문제를 풀어갑니다. [기본 원리]..

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net Solved By: Flood-Fill 저번 포스팅과 이어지는 문제입니다. Flood-Fill이 무엇인지 배웠다면 이것을 사용하여 시간문제를 해결할 수도 있습니다. 1인 칸에서 0의 개수를 세는 BFS는 다른 1인 칸에서도 개수를 셀 수 있기 때문에 꽤 오래 걸립니다. 하지만, 4가지 방향을 확인했을 때, 어떤 0이 어떤 영역에 속하는지 알고, 그 영역의 크기를 안다면 각 1..

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net Solved By: Flood-Fill 벽 부수고 이동하기4(16946) 문제를 풀려다가 시간 초과가 나서 해결 방법을 찾다가 Flood-Fill Algorithm의 존재를 알게 되었습니다. Flood-Fill이란 주어진 시작점으로부터 연결된 영역을 찾는 알고리즘, 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘을 의미합니다. 이 영역을 BFS를 통해 구할 수 있는데 '왜 16946문제에서 시간을..

https://www.acmicpc.net/problem/2358 2358번: 평행선 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 각 점의 좌표가 주어진다. 만약 입력에 서로 같은 두 점이 주어지면, 그 두 점을 이용하여 직선을 만들 수 있다. 좌표는 절댓값이 231보 www.acmicpc.net Solved By: Map 한 점을 여러 번 선택할 수 있기 때문에 예를 들어 x좌표가 같은 것이 2개 이상이라면 하나의 직선을 만들 수 있습니다. 즉, 점들을 모아서 중복되는 x값들이 2개 이상, 혹은 중복되는 y값들이 2개 이상이 확인된다면 하나의 직선으로 카운트합니다. 허나, 좌표의 절댓값이 2^31보다 작은 정수이므로 배열을 사용할 수 없습니다. 그러므로 map을 사용하여..

https://www.acmicpc.net/problem/7575 7575번: 바이러스 첫 번째 줄에는 감염된 프로그램의 개수 N 과 바이러스 코드 추정을 위한 최소 길이를 나타내는 정수 K 가 주어진다. 단, 2 ≤ N ≤ 100이고, 4 ≤ K ≤ 1,000이다. 두 번째 줄부터 각 프로그램에 대한 www.acmicpc.net Solved By: KMP 길이가 K이상인 코드가 반복되어 나타난다면 바이러스라 판단하므로 길이가 K인 코드가 반복되어 나타나도 바이러스라고 판단할 수 있습니다. N개의 코드 중, 첫 번째 코드( == code[0])를 비교 코드로 두고, code[0]에서 길이가 K인 코드들을 구합니다. -> compareCode 그리고, 나머지 코드들 (code[1] ~ code[N - 1]..

https://www.acmicpc.net/problem/1701 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 www.acmicpc.net Solved By: KMP 주어진 문자열 S에서 2번 이상 반복되는 부분 문자열 중 최대 길이를 찾아야 합니다. 즉, 2번만 반복되어도 문제의 조건을 만족합니다. 이 점을 이용하여 KMP에서 pattern의 prefix와 suffix의 최대 일치 길이를 구하는 방법을 사용해봅시다. 이 방법을 사용하는 이유는 pattern이라는 문자열에서 prefix와 suff..