18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 1. 문제 설명 2. 구현 아이디어 1 - 맞았습니다 !! 문제에서 계속 언급한 것처럼 '최단 거리'를 구하는 문제이기 때문에 다익스트라 알고리즘 or 플로이드-와샬 알고리즘을 사용해야겠다고 생각할 수 있었다. 출발 도시 번호가 주어지고 특정 노드로부터 다른 노드의 최단 거리를 구해야 함 입력으로 주어지는 n, m, k가 각각 30만, 100만, 30만으로 작지 않음 1번만으로도 다익스트라 ..

2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 1. 문제 설명 2. 구현 아이디어 1 - 틀렸습니다 문제를 풀면서 덩어리가 몇 개인지 구해야 한다는 점에서 BFS/DFS 문제임을 알 수 있었다. 위 사진에서 높이가 2인 빙산이 녹으면서 0이 되고, 높이가 4인 빙산은 2가 되었다. 모든 빙산은 다 같이 줄어드는 것이기 때문에 높이가 4인 빙산 주변의 0인 칸을 셀 때 2→0인 빙산이 포함되지 않도록 주의해야 한다 !! 문제를 풀기 위해 아래와 같은 풀이 과정을 떠올렸다. 1. 입력을 받으면서 빙산의 좌..

2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 1. 문제 설명 2. 구현 아이디어 1 - 맞았습니다 !! 연속으로 3잔을 모두 마실 수 없다는 점을 유의해서 풀면 되는 문제이다. 이제까지 마신 최대 포도주의 양을 계산하고, 연속으로 마신 잔의 수에 따라 현재 위치에 있는 포도주를 마실지 말지 결정하는 것이 DP 문제에서 나오는 자주 나오는 로직이여서 DP를 사용하여 문제를 풀 수 있다고 생각할 수 있었다. 각 위치의 포도주의 양을 담은 배열을 arr라고 하고 dp[i] = 0~i번째 위치에 있는 포도주까지 고..

1. 부분 수열과 증가하는 부분 수열이란? 부분 수열 부분 수열이란 주어진 수열의 일부 항을 원래 순서대로 나열하여 얻을 수 있는 수열을 의미한다. 만약 { 3, 2, 5, 2, 3, 1, 4 } 라는 수열이 있다면 {3}, {2}, {2, 5}, {3, 5, 3, 1} 등이 해당 수열의 부분 수열이 되며, 수열 자체도 자기 자신의 부분 수열에 포함된다. 증가하는 부분 수열 증가하는 부분 수열은 부분 수열들 중에서도 그 수가 오름차순으로 증가하는 부분 수열을 의미한다. 위에 있던 수열의 증가하는 부분 수열은 {2, 5}, {2, 3, 4} 등이 있고, 원소가 하나일 때도 증가하는 부분 수열에 포함된다. 이번 포스트에서 소개할 가장 긴 증가하는 부분 수열은 그 중에서도 가장 길이가 긴 것을 의미한다. 가장..

2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 1. 문제 설명 예제 1에서 1번부터 5번 회원의 점수는 각각 3점, 2점, 2점, 2점, 3점이다. 그러므로 가장 작은 점수는 2점이 되고, 점수가 2점인 2, 3, 4번 회원 총 3명이 회장 후보가 되는 것이다. 2. 구현 아이디어 1 - 틀렸습니다. 1. 현재 노드에서 가장 거리가 먼 노드까지의 거리가 해당 회원의 점수가 된다. 2. 모든 회원의 점수를 배열에 저장하고, 배열의 최솟값(=score)을 찾는다. 3. 값이 score인 원소의 index를 ca..

10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 1. 문제 설명 2. 구현 아이디어 - 메모리 초과 문제 설명에 있는 예제 입력에 그린 것처럼 컴퓨터끼리의 관계를 그래프로 표현할 수 있고, 여기서 s초를 간선의 값이라고 생각하면 최초로 해킹 당한 컴퓨터부터 다른 컴퓨터까지의 최단 경로를 탐색하는 문제라고 생각할 수 있다. 한 노드에 대해서만 최단 경로를 생각하면 되기 때문에 다익스트라 알고리즘을 사용해보자. 다익스트라 알고리즘의 개념에 대해서는 아래 포스트에 정리해두었다. 최단거리 알고리즘 - 다익스트라 & 플로이..