https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 난이도 : 골드 4 태그 : 자료 구조, 분리 집합 설명 0 a b 일때는 a와 b를 합집합하고, 1 a b 일때는 a와 b가 같은 집합에 속하는지 확인하는 문제입니다. 즉, 원소들간에 그룹을 만들고, 그룹을 하나씩 합쳐가며, 1 연산일때 두 원소가 같은 그룹 내에 존재하는지 확인하면 됩니다. 해당 문제는 분리 집합과 Union - Find 알고리즘을 사용..

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 난이도 : 골드 3 태그 : 구현, 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색, 시뮬레이션 설명 외부 공기와 접촉하는 칸이 두 곳 이상이면 치즈가 녹습니다. 이때, 모든 치즈가 녹으려면 얼마만큼의 시간이 필요한지 구하는 문제입니다. DFS, BFS 중 어느것을 사용해도 무방하나, 저는 DFS를 사용하여 풀이하였기에, 본 포스팅에선 DFS를 사용한 접근법과 풀이를 서..

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 난이도 : 골드 4 태그 : 가장 긴 바이토닉 부분 수열 설명 가장 긴 증가한는 부분수열(LIS, Longest Increasing Subsequence), 가장 긴 감소하는 부분수열(LDS, Longest Decreasing Subsequence)과 비슷하게 가장 긴 증가했다가 줄어드는 부분 수열을 찾는 문제입니다. 첫 접근은 다이나믹 프로그래밍 배열 두개를 사용하여, 하나는 쭉 증가하다가, 다른 하나는 어느 순간..

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 그래프 탐색, 트리, 재귀 설명 입력으로 pre order(전위 순회)가 주어지고, 이를 트리 형태로 변환하여 post order(후위 순회)하여 방문한 노드 순서대로 출력하는 문제입니다. 소스코드 전체 소스코드 import java.io.BufferedReader import java.io.InputStreamReader val sb = S..

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 벨만-포드 설명 1번 도시에서 출발해 나머지 도시로 가는 최단경로를 구하는 문제입니다. 다만, 음의 간선이 존재하므로 다익스트라는 사용하기 어렵습니다. 음의 간선이 있다는 것을 보고, 어떻게 풀어야하나... 하며 최단경로 알고리즘을 찾아보다가, 음의 간선일때의 쓰는 최단경로 알고리즘인 벨만-포드..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 난이도 : 골드 5 태그 : 다이나믹 프로그래밍, 슬라이딩 윈도우 설명 이전 값들을 이용하여, 최대값 및 최소값을 구하는 다이나믹 프로그래밍 문제입니다. 소스코드 전체 소스코드 import java.io.BufferedReader import java.io.InputStreamReader import java.util.StringTokenizer import kotlin.math.max import kotlin..

https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 난이도 : 골드 4 태그 : 자료구조, 스택, 문자열 설명 문제의 지문에 문자열의 길이는 1~1,000,000 로 명시되어 있습니다. 가장 쉽게 풀 수 있는 방법은 replaceAll 메소드를 사용하는 것 이겠지만, 문자열의 길이를 보니 시간초과, 메모리 초과 등이 날 것이 당연하네요. 따라서, 저는 Stack 자료구조를 사용하여 해당 문제를 풀이하였습니다. 스택에 하나씩 문자열을 ..

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 난이도 : 골드 5 태그 : 그래프 탐색, 그래프 이론, 다이나믹 프로그래밍 설명 DFS를 사용하여, 직전 파이프의 형태 (가로, 세로, 대각선)을 참고하여 풀이할 수 있는 문제입니다. 처음엔 DFS 없이 DP만을 사용하여 풀이하려고 했으나, 생각보다 잘 되지 않아서, 마침내 그래프 탐색 문제인걸 깨닫고 푼 문제였습니다. 소스코드 전체 소스코드 import java.io...

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 데이크스트라, 플로이드-워셜 설명 각 정점에서 m 만큼의 비용 안에 갈 수 있는 정점들의 아이템 값의 최대값을 구하는 문제입니다. 한 정점과 연결된 다른 정점을 순차적으로 탐색하는 방식으로 DFS, 다익스트라 알고리즘을 사용해 풀이할 수도 있지만, 본 포스팅에서는 플로이드 - 워셜 알고리즘을 사용하여 풀이하겠습니다. 소스코드 인풋값 세팅 val MAX_VALU..

https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 난이도 : 골드 3 태그 : 그래프 탐색, 그래프 이론, 너비 우선 탐색 설명 이전에 많이 해보았던 상하좌우 4방향으로 이동하는 BFS 문제에, 체스의 나이트 방향으로 움직일 수 있는 조건이 더해진 문제입니다. 단, 나이트 이동의 경우 k번이라는 제약조건이 있으므로, 말 이동을 k번 이하로 사용하면서 최단 경로로 목표지점에 도달하는게 핵심입니다. 소스코드 Data Class - P..