PS

https://www.acmicpc.net/problem/2660아주 간단한 BFS 이용 문제였다. 주어진 간선 조건들에서 각 노드마다 BFS레벨 카운팅을 실시하고, 가장 레벨이 작은 노드들을 모아 출력해주는 방식으로풀이하였다.

https://www.acmicpc.net/problem/2617그래프의 활용과 탐색을 어떤 식으로 응용할 지 결정하면 그다지 어렵지않은 문제였다. 주어진 문제의 입력은 전형적인 그래프 구조의 간선 정보의 입력과 같다.다만, 2 1 과 같은 형식으로 주어질 경

https://www.acmicpc.net/problem/12851이전에 숨바꼭질 시리즈 문제를 0-1 BFS 로직을 이용하여 풀이해본 적 있기에비슷한 관점으로 접근하였다. 다만, K에 도달하였을 경우의 수를 카운팅해야하기에 K는 방문 표시를 하지 않고 넘어가

https://www.acmicpc.net/problem/1781우선순위큐를 활용하여 가장 많은 컵라면 수를 받을 수 있는 문제의조합 경우를 구하는 문제였다. 최소, 최대 경우를 제한된 시간안에 도출해야한다는 점에서 우선순위큐를 활용해야 한다는 점은 캐치하였으

https://www.acmicpc.net/problem/1351DP를 구현함에 있어 HashMap을 활용하는 문제였다.통상적인 DP 문제는 배열을 활용하여 구현하나, 이 문제의 경우 주어진 $N$의 최대값이 $10^{12}$(1조)이기 때문에 배열로 구현할

https://www.acmicpc.net/problem/15665처음에 이 문제를 접근할 때 이전의 N과 M 시리즈를 풀이했던 경험을 바탕으로별 생각없이 동일한 논리로 로직을 작성하였었다.처음 작성한 로직은 문자열 List 형태로 답안들을 저장하고 dfs 로

https://www.acmicpc.net/problem/1890전형적으로 DP를 사용하여 풀이하는 문제였다. 처음에 문제 조건을 제대로 파악하지 못해0을 만나면 방문을 중지해야 하는 처리를 하지 않아 시간 초과를 계속 마주했었다.한 지점에서 다른 지점으로 이

https://www.acmicpc.net/problem/13549이 문제를 예전에 0-1 BFS로 풀이했던 기억이 있는데 오랜만에 다시 보니틀림으로 재채점 되어 있어 다시 풀이하였다.다익스트라를 이용하여 -1, +1, \*2 각각의 세 방향 이동시 유효한인

https://www.acmicpc.net/problem/1918스택을 활용하여 풀이할 수 있는 대표적인 문제였다.우선 스택에는 연산자만을 조건에 따라 push/pop 하며 피연산자는그대로 출력한다.문자에 따른 로직의 구성은 다음과 같다. ( : 그대로 pus

https://www.acmicpc.net/problem/2583전형적인 BFS를 이용하여 풀이하는 문제였다. 문제에서 주어진 좌표 공간이 코드에서의좌표와 반전되어 있어 로직에서 다르게 표현해야 하나 고민할 수 있지만, 그저 상하로 반전되어 있는 형태이기 때문

https://www.acmicpc.net/problem/2468BFS를 이용하여 간단하게 풀이할 수 있는 문제였다. 로직의 전개는 다음과 같다.입력을 받으며 높이를 Set에 삽입한다. 중복 없이 주어진 높이값을 저장할 수 있다.유의할 점은 아무 곳도 잠기지

https://www.acmicpc.net/problem/5014bfs를 이용하여 풀이할 수 있는 간단한 문제였다. S 에서 탐색을 시작하여 S+U 나 S-D 중 1~F 까지의 유효한 인덱스 범위안에존재하며 방문하지 않은 정점으로 탐색을 진행하며 G 에 도달하

https://www.acmicpc.net/problem/1956주어진 문제에서는 최소 비용 사이클을 구해야 한다. 따라서 모든 경로에 대한최소 비용을 구하는 플로이드-워셜을 활용할 수 있었다.전형적인 플로이드 워셜 로직에서 i==j 인 경우(사이클인 경우)에

https://www.acmicpc.net/problem/17182처음에 이 문제를 접했을 때 플로이드-워셜과 다익스트라 두 가지 관점으로 접근을 하려 했었다.하지만 모든 정점을 방문하는 경로에서 시작점외 다른 정점에서 여타 정점까지 도달하는 최소 비용도 도출

https://www.acmicpc.net/problem/12865동적 계획법을 활용하여 풀 수 있는 정석적인 문제인 배낭 문제이다.먼저 메모이제이션을 구현하기 위해 dp 란 2차원 배열을 정의하였다.행 : $i$번째 행은 $i$ 번째 고를 물건을 의미한다.열

https://www.acmicpc.net/problem/1068뭔가 처음 문제를 접하였을 때 유니온 파인드에서 부모를 찾는데 쓰는 로직을 응용하면풀이가 쉬울 것 같다는 생각으로 접근을 하였다.우선 각 노드의 부모를 저장하는 parents 배열과 각 노드의 자

https://www.acmicpc.net/problem/139130-1 BFS와 다익스트라로 풀이할 수 있는 숨바꼭질 시리즈 문제이다.다른 문제와 다르게 이 문제에서 추가된 요구는 최단 경로 비용과 더불어최단 경로를 출력하는 것이었다. 이를 위해선 최단 경로

https://www.acmicpc.net/problem/1719플로이드-워셜 알고리즘을 조금만 응용하면 풀 수 있는 문제였다.우선 플로이드-워셜을 실현하기 위해 경로별 최단 비용을 저장하는 2차원dist 배열과 경로 $i \\rightarrow j$ 에서 $

https://www.acmicpc.net/problem/1759백트래킹을 이용하여 풀이할 수 있는 간단한 문제였다.암호를 구성할 문자들을 저장할 values 배열과 암호를 구성하는데사용할 arr 배열을 정의하였다. 이후 dfs를 이용한 백트래킹을 통해dept

https://www.acmicpc.net/problem/15486https://www.acmicpc.net/problem/14501위 실버 3의 퇴사 문제로 시작되는 퇴사 시리즈의 두번째 문제이다.문제 조건은 퇴사1 문제와 같으나, $N$의 범위가

https://www.acmicpc.net/problem/15681로직을 구현하는 것은 어렵지 않았는데 계속 메모리 초과가 나서 골치를 먹었던 문제였다.makeTree는 노드 간의 연결관계를 표현한 graph를 바탕으로 재귀적으로 트리를 구성한다.countSu

https://www.acmicpc.net/problem/6593BFS를 활용하여 풀 수 있는 전형적인 문제였다. 주어진 3차원 공간에서 동,서,남,북,상,하로탐색을 진행하며 E 에 도달할 시 탐색에 걸린 시간을 반환하는 식으로 bfs 로직을구성하였다. 유의할

https://www.acmicpc.net/problem/1240최단 경로 관련 알고리즘을 알고 있다면 쉽게 풀이할 수 있다고 생각되는 문제다.단순히 트리를 그래프로 표현하고 주어진 두 정점 사이의 거리를 계산하는 문제였다.bfs 로직을 이용하여 풀이했고, 시

https://www.acmicpc.net/problem/15988DP는 정말 언제 풀어도 어려운 것 같다. 로직에서 dp\[N]은 1,2,3으로 N을 표현하는 경우의 수를 나타낸다.$N$이라는 수가 주어졌을때 1,2,3 의 합으로 $N$을 나타내기 때문에,

https://www.acmicpc.net/problem/5427https://velog.io/@mj3242/%EB%B0%B1%EC%A4%80-4179-%EB%B6%88위 문제와 같은 로직으로 풀이할 수 있는 문제였다.다만, 이 문제에서는 각각의 테스

https://www.acmicpc.net/problem/9251이 문제는 주어진 두 문자열에서 가장 긴 공통 문자열의 길이를 도출하는 문제이다.우선 주어진 두 문자열의 길이를 바탕으로 메모이제이션을 실현할 배열 dp 를 선언하였다. dp\[i]\[j]는 문자

https://www.acmicpc.net/problem/13168플로이드-워셜을 응용하여 풀이할 수 있는 문제였다. 까다로운 부분이 있었다면기존의 정점을 번호로 표현하는 여타 문제들과 다르게 정점이 문자열의 형태(도시이름)으로주어지고, 교통수단의 종류에 따라

https://www.acmicpc.net/problem/14217BFS나 다익스트라를 이용하여 풀이할 수 있는 문제였다. 필자는 다익스트라로 풀이했다.그래프의 간선 정보가 갱신된 후 각 도시별로 수도를 방문하는데 필요한 최소 도시 수를 구하는 문제이다. 양방

https://www.acmicpc.net/problem/11780플로이드-워셜로 구한 모든 최단 경로와 경로의 비용을 출력하는문제였다. 최단 경로를 어떤 형태로 저장할 지가 관건이었는데별도의 nodeMap이라는 2차원 배열에 $i\\rightarrow j$

https://www.acmicpc.net/problem/9205문제 조건만 잘 이해하면 전형적으로 BFS를 통해 풀이할 수 있는 문제였다.이동할 수 있는 위치 각각을 정점으로 보면, 박스에 한 번에 담을 수 있는맥주 20병\*50 미터=1000미터가 한 번에

https://www.acmicpc.net/problem/7511유니온 파인드를 이용하여 풀이할 수 있는 문제였다.두 사람의 경로를 찾는다는 조건은 유니온 파인드에서 집합을 트리로 표현하였을때두 노드가 같은 트리내에 속하는지(루트가 같은지 확인하는) 연산으로

https://www.acmicpc.net/problem/1976유니온 파인드를 이용하여 풀이할 수 있는 문제였다.0-1 행렬 형태로 들어오는 노드들의 관계를 유니온 파인드 연산을 이용하여 분리집합으로표현한 뒤 방문하는 도시들의 루트를 find 연산을 통해 찾

https://www.acmicpc.net/problem/4195유니온 파인드 로직을 이용하여 풀이할 수 있는 문제였다.최적화된 유니온 파인드의 parent 배열은 parent\[i]가 음수일 때 그 절댓값이i를 루트로 하는 집합의 노드 수를 표현할 수 있으므

https://www.acmicpc.net/problem/17352유니온 파인드를 이용하여 풀이할 수 있는 간단한 문제였다.입력으로 들어오는 N-2개의 관계에 포함되는 섬들을 union 연산을 통하여 같은 루트로설정해준뒤 서로 다른 루트를 가지는 두 개의 노드

https://www.acmicpc.net/problem/24391유니온 파인드 연산을 이용하여 풀 수 있는 단순한 문제였다.관계를 받아 연결된 건물끼리 union 연산을 통해 같은 집합에 속하도록 설정해준 후강의 시간표의 건물들을 하나씩 받으며 parent값

https://www.acmicpc.net/problem/5214BFS나 다익스트라 알고리즘을 활용하여 풀이할 수 있는 문제였다.처음에 단순히 하이퍼링크 노드 정보만 모아두는 Map을 따로 선언하고BFS 로직내에서 노드마다 속한 하이퍼링크를 통해 방문할 수 있

https://www.acmicpc.net/problem/4803유니온 파인드를 이용하여 풀이할 수 있는 문제였다.트리의 조건을 충족하기 위해선 사이클이 존재하지 않아야 되는데parent 를 $2 \\times (N+1)$ 의 2차원 배열로 설정하고 paren

https://www.acmicpc.net/problem/2206BFS 내부적으로 벽을 부순 경우에 따라 방문 처리를 다르게 설정하는 로직을 추가하여풀이할 수 있는 문제였다.문제 조건에 따라 생각을 해보면 벽을 부순 경로는 벽을 부수지 않은 경로보다 짧을 때가

https://www.acmicpc.net/problem/20955유니온 파인드를 이용하여 풀이할 수 있는 문제였다. 입력으로 들어오는 두 정점을유니온 연산으로 하나의 집합으로 형성해주고, 만약 두 정점이 같은 루트내에 이미속해있는 경우 사이클이 존재하는 것이

https://www.acmicpc.net/problem/1245DFS를 이용해 풀이할 수 있는 문제였다. 산봉우리의 조건을 세심히 체크해야 하는데이 부분이 부족하여 오답을 몇 번 마주하였다.문제에서 얘기하는 산봉우리의 정의는 다음과 같다.같은 높이의 격자들로

https://www.acmicpc.net/problem/2668DFS와 문제 조건을 적절히 그래프로 형성해주면 쉽게 풀이할 수 있는문제였다.처음에 이 문제를 접하였을 땐 $N$의 수중에 $k$개를 선택하는 DFS를이용한 조합을 활용하는 접근으로 문제를 폴이했

https://www.acmicpc.net/problem/2146BFS를 응용하여 풀이할 수 있는 문제였다. 로직의 전개는 다음 순서로 이뤄진다.바다를 -1, 땅을 0으로 초기화하여 저장한다.각 좌표를 검사하여 0인 경우 paintBfs 함수를 통해 땅 영역에

https://www.acmicpc.net/problem/14267본래 유니온 파인드를 이용하여 접근했으나 입력값을 처리함에 있어 까다로운부분이 있어서 트리를 그래프 형태로 표현하고 DFS를 통해 자식들의 reward를갱신해주는 방식으로 로직을 구성하였다.로직

https://www.acmicpc.net/problem/1600원숭이는 상하좌우로 이동하거나 말처럼 이동할 수 있다.다만, 여기서 생각해야할 점은 $K$번만큼 말처럼 이동했을 경우의 경로와그 외의 경로를 구분하여 방문 처리를 해주어야 한다는 점이다. $K$번

https://www.acmicpc.net/problem/14442벽 부수고 이동하기 시리즈의 두번째 문제였다. 이전과 달리 벽을 $K$번까지 부술수 있다는 조건이 추가되었다.조건을 충족시키기 위해 경로를 벽을 부순 횟수에 따라 도출할 수 있도록visited를

https://www.acmicpc.net/problem/2665java가 아닌 c++로 풀이해보았다.다익스트라로 풀이할 수 있는 전형적인 문제였다.map에 검은방을 1, 흰방은 0으로 값을 넣고 dist 배열을 INT_MAX로초기화한다음 그저 좌표별로 다익스

https://www.acmicpc.net/problem/4485다익스트라로 쉽게 풀이할 수 있는 문제였다.그저 map에 주어진 도둑루피 정보를 전부 저장한 후 다익스트라를 돌리면dist\[N-1]\[N-1]에 최소 비용이 도출된다.로직의 시간복잡도는 $O(E

https://www.acmicpc.net/problem/18223다익스트라로 쉽게 풀이할 수 있는 문제였다.문제에서 결국 요구하는 것은 최단 경로에 건우가 위치한 정점이 포함되어 있니? 인데,생각을 해보면 다익스트라 알고리즘의 정의는 아래와 같다.한 시작

https://www.acmicpc.net/problem/1647문제에서는 주어진 간선들중 일부를 택하여 마을을 두 개로 분리하는데이 때 채택한 간선들의 합이 최소가 되는 것을 요구하고 있다.크루스칼 알고리즘https://en.wikipedia.org

https://www.acmicpc.net/problem/16398$N$개의 행성을 최소의 비용으로 연결하는 MST를 도출하면 되므로 크루스칼로풀이할 수 있는 문제였다.문제를 풀이함에 있어 유의할 점은 $N$이 최대 1000이고 가능한 $C$의 최대값이1억이므

https://www.acmicpc.net/problem/13418오르막길을 가장 많이 선택하는 경우오르막길을 가장 적게 선택하는 경우위 두 가지 경우로 나누어 MST를 형성하는 과정에서 오르막길의 개수를 카운팅하여그 제곱의 차이를 도출하면 되는 문제였다.비용

https://www.acmicpc.net/problem/1922크루스칼로 쉽게 풀이할 수 있는 문제였다. 간선을 표현하기 위해 Edge라는클래스를 정의하고, 입력을 받으며 간선을 비용 기준 최소힙에 저장한 후크루스칼 알고리즘을 통해 MST를 도출하여 최소 비

https://www.acmicpc.net/problem/6497크루스칼을 통해 풀이할 수 있는 간단한 문제였다.문제에서 요구하는 것은 주어진 간선중 MST를 형성하는 간선을 제외한나머지 간선들의 비용 합이기 때문에, 전체 간선들의 비용합에서 크루스칼 로직을실

https://www.acmicpc.net/problem/21924크루스칼을 이용해 풀이할 수 있는 간단한 문제였다.문제에서 요구하는 것은 아래와 같다.주어진 전체 간선 비용 합 - MST 구성 간선 비용 합따라서, 입력을 받으며 간선 비용의 합을 구하고 크루

https://www.acmicpc.net/problem/22116크루스칼을 이용하여 풀이할 수 있는 문제였다. 우선 1차원 parent 배열을활용하기 위해 좌표 x, y를 N\*y+x 수식을 통하여 인덱스로 매핑하고parent를 N\*N사이즈로 선언하였다.이

https://www.acmicpc.net/problem/1774크루스칼을 통해 풀이할 수 있는 문제였다.좌표 정보를 저장하기 위해 Node, 간선 정보를 저장하기 위해 Edge 클래스를정의하였다. 이후 우주선들의 좌표 정보를 입력받으며 저장하고, 우주선간의

https://www.acmicpc.net/problem/1368크루스칼로 풀이할 수 있는 문제였다.로직의 발상은 간단하다. 한 정점(논)에서물을 직접 파는 경우다른 정점(논)에 연결하는 경우이렇게 두 경우를 고려하여 비용을 계산해야 하는데, 이 때 물을직접

https://www.acmicpc.net/problem/10423크루스칼을 이용해 풀이할 수 있는 간단한 문제였다.문제 조건만 보면 구현이 복잡할 것 같지만 아주 간단하다.우선 발전소가 설치된 $K$개의 도시들을 가상의 도시 0과 비용인 0인 간선을설정하여

https://www.acmicpc.net/problem/1167DFS를 활용하여 풀이할 수 있는 문제였다. 트리의 지름을 구하는 로직을검증하는 과정은 아래 링크를 참고하자.참고https://velog.io/@zioo/%ED%8A%B8%EB%A6%AC

https://www.acmicpc.net/problem/11265플로이드-워셜로 풀이할 수 있는 간단한 문제였다.손님이 최단 경로로 이동하였을때 파티가 준비되는 시간(C)안에 도달할 수 있는지구하는 것이 문제의 요구사항이다.따라서 플로이드-워셜을 이용해 모든

https://www.acmicpc.net/problem/11909다익스트라를 이용하여 풀이할 수 있는 간단한 문제였다.문제에서 한 좌표에서 이동할 수 있는 위치는 가로로 한 칸, 세로로 한 칸이다.이에 맞추어 다익스트라내에서 좌표별 비용을 갱신하면 되며, 특

https://www.acmicpc.net/problem/27211BFS를 이용하여 풀이할 수 있는 간단한 문제였다.기존의 상하좌우 방향으로 BFS 탐색을 진행하며 최단 경로 비용을 구하는문제들의 조건에서 인덱스 범위를 넘어서는 경우만 문제 조건에 따라 특수적

https://www.acmicpc.net/problem/2589BFS를 이용하여 간단히 풀 수 있는 문제였다.문제에서는 육지중 한 지점에서 다른 지점까지 가장 긴 최단 경로를 구하는요구하고 있다. 모든 육지 지점에서 BFS를 통해 다른 육지 지점을 탐색하며가

https://www.acmicpc.net/problem/5972다익스트라를 이용해 쉽게 풀이할 수 있는 문제였다.단순히 간선 정보를 통해 양방향 그래프를 설정해주고 다익스트라 로직을 통해dist\[N]을 도출하여 답을 구하였다.로직의 시간 복잡도는 다익스트라

https://www.acmicpc.net/problem/21278플로이드-워셜을 이용하여 풀이할 수 있는 간단한 문제였다.로직 설명우선 플로이드-워셜에 사용할 2차원 배열 map 을 int 최대값으로 초기화해준다.(자기 자신에 대한 경로 제외, map\[i]

https://www.acmicpc.net/problem/2219플로이드-워셜로 풀이할 수 있는 간단한 문제였다.문제에서 요구하는 것은 모든 정점까지 이동하는데 드는 비용이 가장 최소인정점 i를 구하는 것이다.따라서, 플로이드-워셜을 통해 모든 정점간 최단 경

https://www.acmicpc.net/problem/2224플로이드-워셜로 풀이할 수 있는 간단한 문제였다.우선 주어진 영어 대소문자 입력값을 인덱스로 표현하기 위해 플로이드 워셜에사용되는 map을 52 x 52의 크기로 선언하고, 0~25까지의 인덱스로

https://www.acmicpc.net/problem/9505다익스트라로 풀이할 수 있는 간단한 문제였다.전투선 클래스 이름에 따라 각 위치별 비용을 설정하기 위해 map H x W 배열을설정하였고, costMap 자료구조를 통하여 이름과 비용 관계를 저장

https://www.acmicpc.net/problem/15789유니온 파인드로 풀이할 수 있는 간단한 문제였다.자세한 로직에 관한 설명은 코드에 주석으로 첨부하였다.로직의 시간복잡도는 복잡도가 가장 큰 연결 정보를 처리하는 부분에서 $O(Ma(N))$으로

https://www.acmicpc.net/problem/10282다익스트라로 풀이할 수 있는 간단한 문제였다.문제의 의존성에 조건에 따르면 주어지는 그래프는 방향 그래프이다.간선 정보를 저장하고 주어진 감염된 정점 c를 시작점으로 하여 다익스트라를 실행한 후

https://www.acmicpc.net/problem/18405BFS를 이용하여 풀이할 수 있는 간단한 문제였다.Point라는 클래스를 정의하여 BFS 탐색시 바이러스 값, level를관리할 수 있도록 하였다. 우선 입력을 받으며 바이러스를 Point를이용

https://www.acmicpc.net/problem/1584다익스트라로 풀이할 수 있는 간단한 문제였다. 우선 안전/위험/죽음의 지역을 구분하기 위해 map이라는 2차원 배열을정의해주었다. 또한, 다익스트라 로직을 구성하기 위한 dist 2차원 배열도정의

https://www.acmicpc.net/problem/16562유니온 파인드로 풀이할 수 있는 문제였다.문제의 답은 각 친구 무리에서 가장 작은 친구비의 합을 구하는 것이다.따라서 parent를 $2 \\times (N+1)$의 2차원 배열로 정의하고 pa

https://www.acmicpc.net/problem/17250유니온 파인드를 이용하여 풀이할 수 있는 간단한 문제였다.유니온 파인드시 사용되는 parent 배열을 $2 \\times (N+1)$의 형태로선언하고, parent\[0]에 해당 분리집합에 속하

https://www.acmicpc.net/problem/18116유니온 파인드를 이용하여 풀이할 수 있는 간단한 문제였다.최적화된 유니온 파인드 로직을 사용하여 풀이했으며 두 부품이주어지는 I 쿼리의 경우 union 연산으로 처리를, Q 쿼리의 경우find

https://www.acmicpc.net/problem/15809유니온 파인드를 이용하여 풀이할 수 있는 간단한 문제였다.nums는 각 국가별 병력을 저장한다. 유니온 파인드 연산을 활용하여두 국가가 연합할 경우 연산을 수행하며 루트가 되는 노드의 nums

https://www.acmicpc.net/problem/20040유니온 파인드로 풀이할 수 있는 전형적인 문제였다.입력 노드들을 유니온 파인드 연산으로 처리하며 이미 같은 분리집합 내에속한 노드들에 대한 입력이 주어졌을 때 사이클이 발생한 것이므로순서를 기록

https://www.acmicpc.net/problem/25187유니온 파인드로 풀이할 수 있는 간단한 문제였다.연결된 물탱크 집합내에서 청정수가 담긴 물탱크 수가 고인물이 담긴 물탱크 수보다많을 때 청정수를 얻을 수 있다. 이 조건을 표현하기 위해 cost

https://www.acmicpc.net/problem/28118유니온 파인드 연산을 통해 풀이할 수 있는 간단한 문제였다.주어진 문제 조건에서 이미 연결 경로가 존재하는 기둥 사이에는 작업에 비용이 필요하지않다. 따라서 유니온 파인드 연산을 통해 빔이 존재

https://www.acmicpc.net/problem/2458플로이드 워셜을 이용하여 풀이할 수 있느 문제였다.문제에서 주어진 그래프는 방향 그래프이다. 이 그래프에서 주어진 조건대로간선에 1의 가중치를 부여하여 방향 그래프를 설정하였을때 키 순서를 알 수

https://www.acmicpc.net/problem/12834다익스트라로 풀이할 수 있는 간단한 문제였다.정의된 한 사람의 거리 $d_i$의 합을 구하는 것이 문제의 요구다.팀원의 위치에서 KIST, 씨알푸드 위치까지의 최단 거리는 팀원의 위치를시작점으로

https://www.acmicpc.net/problem/23793다익스트라로 풀이할 수 있는 간단한 문제였다.경로 $X\\rightarrow Y \\rightarrow Z$의 최단 거리는 $X$를 시작점으로 다익스트라를 수행하여 구한 dist\[y]의 값과

https://www.acmicpc.net/problem/10159플로이드 워셜을 통해 쉽게 풀이할 수 있는 문제였다.주어진 예제 그래프를 먼저 앞 정점 $\\rightarrow$ 뒤 정점 방향의 그래프로 표현하면 형태가 아래 그림과 같다.주어진 그래프의 각

https://www.acmicpc.net/status?user_id=mj3242&problem_id=12875&from_mine=1플로이드 워셜을 통해 풀이할 수 있는 간단한 문제였다.주어진 조건을 그래프에 대입해보았을 때 친구관계에서 가장 먼 거리 $\\t

https://www.acmicpc.net/problem/16958플로이드 워셜을 이용하여 풀이할 수 있는 문제였다.우선 좌표 정보와 특별한 도시 여부를 표현하기 위한 Point 클래스를 정의하였다.이후 입력시 이 Point 클래스를 통해 도시 정보들을 Lis

https://www.acmicpc.net/problem/11085유니온 파인드를 이용해 풀이할 수 있는 간단한 문제였다.우선 간선(길)을 표현하기 위해 Edge 클래스를 정의하였다. 입력을 받으며 Edge를 형성하여비용 기준 최대힙에 저장한다. 이후 유니온

https://www.acmicpc.net/problem/14497다익스트라 또는 0-1 BFS로 풀이할 수 있는 문제였다.다익스트라의 경우 dist 를 $N \\times M$ 2차원 배열의 형태로 정의한뒤 시작점을 0, 도착점을 1로 비용 설정해주어 ma

https://www.acmicpc.net/problem/13905크루스칼을 이용해 풀이할 수 있는 문제였다.주어진 간선들의 정보를 비용 기준 최대힙에 저장한다. 크루스칼 로직에선 MST를 구성할 때이 힙을 이용하여 비용이 큰 간선부터 채택한다. 그리고 $s$

https://www.acmicpc.net/problem/20168골목 대장 호석 시리즈의 첫번째 문제이다. 백트래킹 + 브루트포스 방식으로도 풀이할 수 있다고 하지만, 필자는 이분 탐색 + 다익스트라의 구성으로 풀이했다.다익스트라 로직내에서는 고정된 특정 비

https://www.acmicpc.net/problem/20182다익스트라를 응용하여 풀이할 수 있는 문제였다.골목 대장 호석 시리즈의 첫 문제인 골목 대장 호석 - 기능성의 경우와 마찬가지로이분 탐색과 다익스트라의 조합으로 접근하였으나 시간 초과가 발생하였

https://www.acmicpc.net/problem/1613플로이드 워셜로 풀이할 수 있는 간단한 문제였다.주어지는 사건의 전후 관계를 전 $\\rightarrow$ 후 방향의 형태로 그래프를 형성해준다. 이후, 플로이드 워셜을 돌리며 모든 사건(정점)간

https://www.acmicpc.net/problem/16202크루스칼 알고리즘을 이용하여 풀이할 수 있는 문제였다.주어진 게임의 규칙에 따르면 매 턴마다 그래프에서 가장 가중치가 작은 간선을제거하고 MST를 형성할 수 있을 경우 MST의 총 비용을 구하고

https://www.acmicpc.net/problem/4386크루스칼을 이용하여 간단히 풀이할 수 있는 문제였다.정점간 위치가 좌표로 주어지는 상황에서 MST를 형성해주면 되는 문제였다.좌표를 표현하기 위해 Point 클래스를 산정하였으며 주어진 모든 좌표

https://www.acmicpc.net/problem/9344크루스칼을 이용하여 풀이할 수 있는 간단한 문제였다.문제에 조건에 따르면 MST를 형성하며 입력에 주어진 $p-q$ 도로가 MST에포함되는지를 도출하는 것이 관건이다. 이에 따라 크루스칼 로직을

https://www.acmicpc.net/problem/1414크루스칼을 이용해 풀이할 수 있는 문제였다.문제 조건에 따라 다솜이가 기부할 수 있는 랜선 길이의 최댓값은아래와 같이 재정의할 수 있다.기부 가능한 최댓값 = 모든 랜선의 길이 - MST 형성 랜

https://www.acmicpc.net/problem/14621크루스칼을 이용하여 풀이할 수 있는 간단한 문제였다.주어진 문제 조건에서 모든 대학교로 이동이 가능(2번 조건)과 최단 거리(3번 조건)은 MST를 구해야 한다는 말로 해석할 수 있다. 다만,

https://www.acmicpc.net/problem/14950크루스칼로 풀이할 수 있는 간단한 문제였다.기존의 MST 문제들과 다른 점은 간선을 하나 채택할 때마다 비용이 $W$ 만큼 증가한다는 조건이었다. 이를 구현하기 위해 크루스칼 로직을 실행하며 M

https://www.acmicpc.net/problem/27945크루스칼을 이용해 풀이할 수 있는 간단한 문제였다.주어진 문제에선 노점이 여는 날($t_i$)가 간선의 가중치로 주어지는데 이 가중치가날짜($d$)를 넘지 않는 선에서 최대의 $d$를 구하는 것

https://www.acmicpc.net/problem/28119크루스칼을 이용해 풀이할 수 있는 간단한 문제였다.특정 순서에 따라 차례로 건물에서 회의를 진행할때 건물 간 총 이동 시간의최소값을 구하는 문제였다. 하지만, 순간이동 이라는 조건이 붙기 때문에

https://www.acmicpc.net/problem/10749크루스칼을 이용해 풀이할 수 있는 간단한 문제였다.팀마다 고유한 ID가 주어지고 각 팀간 경기를 하였을때 합산 점수는 각 팀의 ID를$XOR$ 연산하여 구할 수 있다. 경기가 진행될 때마다 한

https://www.acmicpc.net/problem/14548다익스트라를 통해 풀이할 수 있는 간단한 문제였다.다익스트라에 사용되는 dist 배열의 크기를 주어질 수 있는 최대 데이터셋의 개수(N=500)의 2배인 1000으로 설정하여 들어올 수 있는 최

https://www.acmicpc.net/problem/20010주어진 문제에서 구해할 것은 다음 두 가지이다.MST를 구성하는 간선들의 비용 합MST내에서 임의의 두 마을을 잇는 최단 경로 중 가장 비용이 큰 경로의 비용(maxCost)MST를 구성하는 간

https://www.acmicpc.net/problem/16393크루스칼을 통해 풀이할 수 있는 간단한 문제였다.MST를 구성하는 간선들의 정보를 구하여 출력해야 하기 때문에크루스칼 로직안에서 주어진 간선 정보를 바탕으로 MST를 구성하며채택된 간선들을 Li

https://www.acmicpc.net/problem/4722크루스칼로 풀이할 수 있는 간단한 문제였다.도시들의 정보가 x,y 꼴의 좌표로 주어지고 이 도시들을 최소한의 비용으로 이을 수 있는 MST의 총 비용을 구하는 것이 문제의 조건이었다.우선 좌표 정

https://www.acmicpc.net/problem/20007다익스트라를 통해 풀이할 수 있는 문제였다.각 집까지의 최단 거리는 다익스트라를 통해 도출할 수 있고, 유의할 점은거리가 가까운 집부터 방문을 해주어야 하기 때문에 dist 배열을 한 번 정렬하

https://www.acmicpc.net/problem/10021크루스칼을 통해 풀이할 수 있는 간단한 문제였다.좌표로 주어지는 밭의 정보를 저장한 후 밭들간의 거리를 계산하여 간선을형성해 비용 기준 최소힙에 저장한 후, 해당 힙을 이용하여 크루스칼 로직을

https://www.acmicpc.net/problem/7439크루스칼로 풀이할 수 있는 간단한 문제였다.도시의 정보가 좌표로 주어지고 도시들을 도로로 연결하려할 때, 기존에 지어진도로에 더해 비용이 최소로 들어가도록 새로 지어지는 도로들의 좌표 정보를 구하

https://www.acmicpc.net/problem/27039플로이드-워셜을 통해 풀이할 수 있는 간단한 문제였다.$P$개의 목초지중 소들이 머무는 $N$개의 목초지가 있고, 각 소들의 목초지에서가장 작은 총 비용으로 도달할 수 있는 목초지를 찾는 것이

https://www.acmicpc.net/problem/23743크루스칼을 통해 풀이할 수 있는 간단한 문제였다.주어진 문제의 조건을 풀어서 살펴보면최소 1개의 방에 탈출구가 설치되어야 하고, 나머지 방이 그와 이어져 있어야 함해당 경로를 가장 적은 비용으로

https://www.acmicpc.net/problem/10568플로이드 워셜로 풀이할 수 있는 문제였다.테스트 케이스는 케이스별로 행성은 p개의 이름과 3차원 좌표 형태의 위치,w개의 행성 이름으로 주어지는 웜홀 정보(단방향임에 주의!)와 q개의출발 행성,

https://www.acmicpc.net/problem/28473크루스칼을 통해 풀이할 수 있는 문제였다.기존에 간선의 비용이 크루스칼에서 MST를 구성하는데 우선시 되는 기준이었다면이 문제에서는 간선 정보에 z 라는 1~9 범위의 숫자가 추가되고 이 숫자가

https://www.acmicpc.net/problem/6091크루스칼을 통해 풀이할 수 있는 문제였다.각 정점간 최단 경로 비용이 주어진 인접 행렬을 입력받아 MST를 형성하고이를 인접 리스트의 형태로 표현하는 것이 문제의 요구사항이었다.답을 도출하기 위해

https://www.acmicpc.net/problem/5818크루스칼을 이용해 풀이할 수 있는 간단한 문제였다.주어진 문제에서 스파이는 정보를 직접 파견을 나가 얻거나, 다른 스파이를 통해 전달받을 수 있고, 모든 스파이가 파악한 정보를 공유할 수 있는 상

https://www.acmicpc.net/problem/1374우선순위큐를 통해 풀이할 수 있는 간단한 문제였다.강의가 연이어서 한 강의실에 강의될 수 있으려면앞선 강의의 끝나는 시간 <= 뒤이은 강의의 시작 시간위 조건이 충족되어야 한다. 문제에서는

https://www.acmicpc.net/problem/1379우선순위큐를 활용하여 강의실 순서를 배치하는 로직은 아래 글을 참고강의에 인덱스를 붙여 배정된 강의실 번호와 매핑해주기 위해 Map을 활용하였다.강의실 문제를 풀이하였던 로직내에서 새로운 강의실이

https://www.acmicpc.net/problem/22252우선순위큐와 해시맵을 사용하여 풀이할 수 있는 문제였다.주어진 쿼리에 대하여 정보 고릴라들을 표현하기 위해 고릴라 이름(String)을 키로 하는 HashMap을 이용하였다. 해당 맵은 값으로

https://www.acmicpc.net/problem/21773우선순위큐를 활용해 풀이할 수 있는 간단한 문제였다. 프로세스를 표현하기 위해 id, time, priority 필드를 가진 Process클래스를 정의하고, 문제에서 주어진 실행시킬 프로세스를

https://www.acmicpc.net/problem/21939자바에서 키를 기준으로 키-값 쌍 데이터를 정렬된 형태로 저장하는 TreeMap을이용하여 풀이할 수 있는 문제였다.주어진 문제에서 구현함에 있어 가장 까다로운 연산이 solved 였던 것 같다.

https://www.acmicpc.net/problem/14427TreeMap과 HashMap을 이용하여 풀이할 수 있는 문제였다.우선 수열의 원소를 표현하기 위해 인덱스와 값을 필드로 가지는 Element 클래스를정의하였다. 또한, $N$개의 원소중에 가장

https://www.acmicpc.net/problem/2887크루스칼을 통해 풀이할 수 있는 문제였다.주어진 문제를 풀이하기 위해 관건이 되는 부분은 간선을 형성하는 로직이었다.모든 $x$, $y$, $z$의 각 $x_A$, $x_B$ 꼴의 조합을 통해 간

https://www.acmicpc.net/problem/1185크루스칼을 이용해 풀이할 수 있는 문제였다.처음 이 문제를 풀이할 당시, 크루스칼을 이용해 MST를 형성하고 해당 MST를그래프 탐색 내지는 다익스트라를 통해 비용을 도출하여 답을 구하는 접근으로

문제 https://www.acmicpc.net/problem/11562 리뷰 출발지와 도착지를 입력 받고 최단 경로를 답한다는 점에서 직관적으로 플로이드-워셜로 접근해야 한다는 느낌을 받았다. 로직의 구성은 간단하다. 간선 $i\rightarrow j$를 입력받을

https://www.acmicpc.net/problem/14574크루스칼과 DFS를 통해 풀이할 수 있는 문제였다.매일 둘씩 대결을 하므로 $N$명의 요리사가 존재할 때, $N-1$번의 대결이 펼쳐져야하고 시청률의 합이 최댓값이 되어야 한다. 이 조건은 대결

https://www.acmicpc.net/problem/3055BFS를 통해 풀이할 수 있는 문제였다.주어진 맵의 정보를 받아 S에서 D까지 도달 가능한 지 BFS를 통해 도출하는 것이문제의 조건이다. 유의할 점은 물의 위치가 하나가 아닐 수 있다는 것이다.

https://www.acmicpc.net/problem/23034크루스칼과 BFS를 활용하여 풀이할 수 있는 문제였다.먼저 T를 구하기 위해서 우선 주어진 모든 간선에서 MST를 구성하여모든 정점을 연결하는데 필요한 최소한의 간선만을 남겨야 한다.이를 위해

https://www.acmicpc.net/problem/13424플로이드 워셜 혹은 다익스트라로 풀이할 수 있는 간단한 문제였다.필자는 플로이드 워셜이 더 풀이가 간단히 나올듯 하여 플로이드 워셜을 이용해로직을 구성하였다.전체 방중 $K$명의 친구가 모이기에

https://www.acmicpc.net/problem/9694다익스트라를 이용해 풀이할 수 있는 문제였다.거리를 최소화하며 최고 위원(M-1)까지 도달하는 조건은 간단하게 친밀 관계를그래프로 형상화한 뒤 다익스트라를 이용하여 최단 거리를 도출하면 되었다.중

https://www.acmicpc.net/problem/2406크루스칼을 통해 풀이할 수 있는 문제였다.문제의 조건을 유심히 봐야하는데 네트워크에 고장이 나더라도 컴퓨터끼리연결이 되어있도록 만드는 것이 최종 목표이다. 따라서, 모든 컴퓨터들은 기본적으로본사

문제 https://www.acmicpc.net/problem/23286 리뷰 플로이드-워셜 알고리즘을 이용하여 풀이할 수 있는 문제였다. 주어진 문제의 조건중 가장 높은 허들 높이의 최솟값이라는 조건을 잘 이해하지 못해 상당히 애를 먹었다. 결론적으로 그냥 말그대로

문제 https://www.acmicpc.net/problem/13265 리뷰 DFS나 BFS로 풀이할 수 있는 문제였다. 필자는 DFS로 풀이하였다. 문제의 조건에 따라 DFS를 통해 현재 탐색 중인 정점과 다른 색으로 다음에 탐색할 정점들을 색칠하는데, 만약 연

문제 https://www.acmicpc.net/problem/16965 리뷰 BFS를 통하여 풀이할 수 있는 문제였다. 먼저 각 구간을 나타내기 위해 시작점(s)과 끝점(e)을 필드로 가지는 클래스 Pair를 산정하였다. 이 구간들은 List에 저장하였으며 구간의

1863번: 스카이라인 쉬운거현재까지의 건물 높이값보다 낮은 높이가 들어올 경우 무조건 스카이라인이 바뀐다.따라서 낮은 높이가 들어올 경우스택이 비지 않을 때까지 한 빌딩과 해당 빌딩과 같은 높이의 빌딩을 같은 빌딩으로 취급하며 제거높이가 0인 경우는 빌딩으로 취급하지

7490번: 0 만들기오름차순 수열(1 2 3 … N 의 형태)이 주어지면 수열 사이 숫자에 + , - , 공백중 하나를 삽입하여 수식을 만들고 그 계산 결과가 0인 경우만을 구하여 ASCII 순서에 따라 출력해야 한다. 경우의 수를 구해야 한다는 측면에서 백트래킹을

https://www.acmicpc.net/problem/16724주어진 맵에서는 회원이 특정 좌표에 위치했을 때 갈 수 있는 방향이 정해져 있다. 따라서 좌표의 방향 값에 따라 모일 수 있는 지점이 정해져 있다. 우선 이런 방향에 따른 탐색은 DFS를 통해

https://www.acmicpc.net/problem/1027우선 주어진 빌딩을 순서가 $x$고 높이가 $y$인 $(x,y)$꼴의 좌표 형태로 저장할 것을 고려하였다. 문제에서 주어진 $N$의 최대가 50이므로, , 그리디 방식으로 모든 두 쌍의 정점 사이

https://www.acmicpc.net/problem/14719문제 조건을 통해 정의한 ‘고인물’의 개념은 다음과 같다.임의의 두 블록 사이 블록들이 두 블록보다 전부 작을 때 물이 고일 수 있다. 이 때 고이는 물의 양은 두 블록중 크기가 더 작은 블록과

https://www.acmicpc.net/problem/20437초반에 너무 복잡한 방식으로 접근하여 애를 먹었던 문제였다. 결국 문제에서 주어진 조건을 만족하는 문자열은 특정 문자를 $K$개만 포함한다. 이 조건에 집중하여 다음 전개로 로직을 구성하였다.

https://www.acmicpc.net/problem/20055≤ 써줘야 될 꺼를 ≠로 써줘서 로직 맞게 짜놓고 졸라 헤맸다;처음에는 두 개의 덱을 이용하여 돌아가는 컨베이어 벨트의 윗면,아랫면을 표현하고 이를 이용해 로직을 구성하였다. 하지만, 연이은

https://www.acmicpc.net/problem/22251문제의 조건에서 관건이 되는 부분은 다음 2가지였다.디스플레이를 어떤 형태로 표현하여 숫자를 디스플레이로 변환할 것인지?모든 디스플레이를 다 껐다 켜보며 경우를 구할 경우 시간복잡도가 기하급수적

문제 https://www.acmicpc.net/problem/17406 풀이 주어진 문제의 조건에서 회전의 순서가 달라지면 결괏값이 달라진다. 회전 순서의 경우의 수는 $K!$로 순열의 형태인데, $K=6$인 최악의 경우에도 720 남짓의 값으로 백트래킹을 통해

https://www.acmicpc.net/problem/17136문제를 처음 접했을 때 탐색의 범위가 $10 \\times 10$으로 매우 작으므로, 완전탐색으로 풀이가 가능할 것으로 생각했다.최소 개수의 색종이로 1인 범위를 커버하는 것이 관건이므로, 큰

https://www.acmicpc.net/problem/11559이 문제에서 고전했던 부분들은 다음과 같다.그룹마다의 연쇄를 카운팅하는 것이 아니라 연쇄가 발생하는 경우를 카운팅하는 것이다.연쇄가 발생하는 경우를 카운팅하는 것이기 떄문에 같은 턴에서 서로 다

https://www.acmicpc.net/problem/14925정사각형의 기준 지점을 맨 오른쪽 아래 칸으로 생각한다.정사각형이 성립하려면 자신의 위, 아래, 대각선을 포함하는 범위내에 장애물이 없어야 한다.$dp(r,c)$는 좌표 $(r,c)$까지의 가장