https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 2458, 키 순서 📌 난이도 : Gold 4 📌 알고리즘 : 플로이드 워셜 이번 문제는 이해하는데 많은 시간이 소요되고 구현까지도 꽤 많은 시간이 걸린, 개인적으로 복잡한 문제였다. 풀이를 간략하게 설명하자면 먼저사람들을 정점으로 간주한다. 모든 정점간의 거리를 INF 로 초기화 해주고주어진 연결관계를 이어주고, 플로이드 워셜을 통해 특정 사람이 모든 사람과의 거리를 체크해서 값을 갱신해준다. 2..

https://www.acmicpc.net/problem/1489 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 14891, 톱니바퀴 📌 난이도 : Gold 5 📌 알고리즘 : 구현 이번 문제는 생각할게 많은 구현문제다.회전할 톱니바퀴와 방향이 주어졌을 때, 모든 톱니바퀴의 맞닿는 좌측과 우측을 모두 조회해야 한다. 🧩 프로세스 📚 초기화 및 선언 : 톱니바퀴의 12시방향부터 4개를 순서대로 입력받아 넣어준다. (int) public static void input() throws IOException {..

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 2638, 치즈 📌 난이도 : Gold 3 📌 알고리즘 : DFS & BFS 이번 문제는 골드 3의 난이도지만 그렇게 어려운 문제는 아니였다. 외부공기와 외부공기가 유입되지 않는 구간만 잘 체크하면 된다! 문제를 잘 읽어보면 모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다 는 말이 있다. 그렇다면 치즈가 아닌 공기가 유입될 수 있는 지역에서 DFS 로 모든 공기를 탐색하..

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 1937, 욕심쟁이 판다 📌 난이도 : Gold 3 📌 알고리즘 : DFS, DP 이번 문제는 모든 구간에 대해 무지성으로 DFS를 돌렸다가 가차없이 시간초과가 나와서 DFS + DP로 해결한 문제이다. 🧩 프로세스 📚 초기화 및 선언 : 숲의 크기 N을 기반으로 숲의 정보들을 입력한다. 📚 탐색 : 이동할 수 있는 칸의 수를 저장할 DP를 기반으로 탐색을 진행하며 최대값을 갱신해준다...

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 1167, 트리의 지름 📌 난이도 : Gold 2 📌 알고리즘 : DFS & 그래프이론 이번 문제는 임의의 두 점 사이의 거리 중 가장 긴 것, 지름을 구하는 문제이다. 모든 정점에 대하여 탐색을 진행하며 거리의 최대값을 구하면 되지만 정점의 개수가 100,000개 까지이다 보니 시간초과가 발생한다.그렇기에 다른 방안을 생각해보자. 임의의 정점에서 제일 멀리있는 정점의 길을 따라가..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 14502, 연구소 📌 난이도 : Gold 4 📌 알고리즘 : BFS & DFS 이번 문제는 Multi-Source BFS 문제이다. 벽 3개를 두어서 안전 공간을 최대한 확보하는 것이 중요하다. 그렇기에 빈 공간에 차례로 벽 3개를 두는 경우를 탐색하며 BFS 로 안전 공간을 구하는 로직을 구현하겠다. 🧩 프로세스 📚 초기화 및 선언 : 빈 공간을 확인할 int[] blank 를 선언해준다. 이는 전체 넓이..

https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 2251, 물통 📌 난이도 : Gold 5 📌 알고리즘 : 그래프이론, BFS 이번 문제는 본인 기준으로 어려워서 이해하는데만 한 시간 이상이 걸린 것 같다. 이 문제를 읽고 그래프와 BFS 를 떠올리기가 쉽지 않았고 그에 맞는 구조체를 구현하는게 쉽지 않았다. 🧩 프로세스 📚 State, 물의 이동을 표현할 구조체 : 물을 붓고 나서의 양을 구하는 클래스이다. 생성자로 A,B..

https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 20922, 겹치는 건 싫어 📌 난이도 : Silver 1 📌 알고리즘 : 투포인터 이번 문제는 투포인터 문제이다. 루프 안에서의 범위 설정에 주의해야 한다. 🧩 프로세스 📚 초기화 및 선언 : 정수 N 과, 중복의 수 K를 입력받고 N개만큼의 int[] 를 생성해서 값을 넣어준다. 또한 수의 중복값을 확인하기 위해 int[] arr 을 생성해준다. N 의 범위 때문에 new int[100,..