알고리즘25

• 

  [c++] 백준 - 도로 네트워크(lca) 1. 문제 2. 입 출력 3. 예제 4. 문제 해설 이 문제는 lca를 이용한 문제였다. 문제 자체에서 가장 root노드가 무엇인지 주진 않았지만 1번 노드를 root로 삼아 (왜냐하면 1번 노드는 항상 나오기 때문이다.) 트리를 구성하고 그 후 효율적인 lca풀이를 이용하면 충분히 구할 수 있는 문제이다. 이 문제는 또한 lca를 구성하는 과정에서 구간의 최댓값과 최솟 값을 저장하며 가야하는 문제이다. 따라서 dp문제의 성향이 강하다고 할 수 있겠다. 우선 효율적인 lca 풀이를 위해 tree를 구성해준다. 나는 bfs를 통해 트리를 만들어주었다. void makeTree() { depth[1] = 1; q.push({ 1 }); while (q.size()) { int curr = q.front();.. c++/알고리즘 2023. 3. 3.

• 

  [c++] 백준 - 2014 소수의 곱 (우선순위 큐) 1. 문제 2. 입출력 및 예제 3. 문제 해설 우선순위 큐를 이용해 푸는 문제였다. 처음에는 아무런 생각도 하지 못하고 있다가 알고리즘 분류를 봤더니 우선순위 큐 분류에 있는 것을 확인한 후 풀 수 있었던 문제이다. 이 문제의 핵심아이디어는 다음과 같다. 우선 주어진 수들을 모두 우선순위 큐 안에 집어 넣는다. 우리는 오름차순으로 수를 구해야하므로 우선순위 큐는 오름차순으로 선언해준다. #include #include #define ll long long priority_queue pq; 그 후 오름차순 우선 순위 큐에 집어넣고 pq.top()에 해당하는 값들을 계속 원래 입력으로 받았던 소수에 곱을 해주면서 다시 우선순위큐에 집어넣어주면 그 횟수를 N번 반복했을 때의 pq의 top이 정답이 된다. 4.. c++/알고리즘 2023. 2. 16.

• 

  [C++] 백준 - 11779 최소비용구하기2 (다익스트라) 1. 문제 2. 입출력 및 예제 3. 문제 해설 백준 - 1916 최소비용 구하기 문제와 비슷한 문제이다. 하지만 추가된 것은 몇 개의 노드를 거치면서 왔는 지에 대한 정보와 지나온 path에 대한 정보도 출력을 해야한다는 것이다. 처음에 예제 답안을 살펴보면 경로가 1 3 5로 나와있는 것을 확인할 수 있다. 하지만 위의 그래프를 그려보면 1 3 5 뿐만 아니라 1 4 5도 된다는 것을 알 수 있다. 그리고 경로에 대한 제약사항은 존재하지 않는다. 따라서 이 문제는 도달할 수 있는 경로가 여러가지일 경우에는 그냥 아무거나 출력하면 되는 문제였다. 여태까지 많은 경로를 기억했다가 출력하는 문제들을 풀어본 결과 경로를 기억하는 문제들은 대게 그 경로에 추가되는 로직이 있기 마련이다. 또한 위의 문제는 다익.. c++/알고리즘 2023. 2. 15.

• 

  [c++] 백준-10999 구간합구하기2 (세그먼트트리, lazy_loading) 1. 문제 2. 입출력 및 예제 3. 문제 해설 이 문제는 백준 2042 구간합구하기 문제와 거의 동일하다. 단 하나 차이점이 있다면 이 문제에서는 단 하나의 수를 교체하는 것이 아니라 2번째 수부터 8번째 수를 9로 변경해 등과 같이 구간이 업데이트 된다는 점이다. 이 경우 최악의 시간복잡도는 처음부터 끝 구간을 변경하는 경우가 되고 update하는 데 드는 시간이 O(NlogN)이 된다. 이 문제에서 N은 백만이고 O(NlogN) 은 백만 * 1000 = 10억 번의 연산을 해야한다는 것이다. 대략적으로 c++언어로 1초라는 제한시간안에 통과하려면 1억번 정도의 연산을 수행해야하는데 위의 연산 횟수는 터무니 없다고 할 수 있다. 따라서 이 문제는 일반적인 세그먼트 트리의 update를 적용해서는 안된.. c++/알고리즘 2023. 2. 15.

• 

  [c++] 백준 - 11066 파일 합치기 (dp) 1. 문제 2. 예제 입출력 3. 문제 해설 다이나믹 프로그래밍 문제이다. 나는 한 번 최소의 값을 구하는 과정을 생각해보았다. 내가 풀어본 대부분의 dp문제 중 이 문제는 dp[x][y]를 x번째에서 y번째까지의 파일 합치기의 최소값을 기억해두는 문제였다. (백준-전구)에서 사용한 dp배열과 비슷하다. 대부분 이렇게 x ~ y에서의 최소 값을 dp배열에 저장하면 중간에 k라는 구간을 두어 for문을 반복하며 최소 값을 찾아내는 형태로 많이 나온다. 이 문제 또한 동일했다. dp문제 정의 dp배열 정의 : dp[x][y] : x번째 파일에서 y번째 파일까지 합치기의 최소 값 점화식 : dp[i][i+j] = min(dp[i][j] , dp[i][k] + dp[k+1][i+j]) k 는 i부터 i+j-1까.. c++/알고리즘 2023. 2. 14.

• 

  [c++] 백준 - 1520 내리막길 (DFS + DP) 1. 문제 2. 입출력 및 예제 3. 문제 해설 상하좌우가모두 탐색이 가능하다. 그리고 제약조건이 존재한다. 바로 현재 위치보다 낮은 수로만 이동할 수 있다는 점이다. 기본적으로는 dfs탐색을 해야할 거 같았다. 결국 자신의 네 방향 중 자신보다 낮은 수가 존재한다면 이동 횟수는 상관없이 이동할 수 있는 것이고 결국 오른쪽 맨 아래 칸에 도달할 수 있는 지에 대한 여부가 중요했기 때문이다. 따라서 나는 상태를 3가지로 나누었다. -1 : 아직 방문하지 않은 곳이다. 0 : 방문한 경우이다. 0보다 큰 수 : 현재 지점에서 목적지까지 도달 할 수 있는 경우의 수가 존재하는 곳이다. 처음에는 이 문제를 백트래킹으로 접근했는데 시간초과가 났다. 물론 4가지 방향 ^ (500 * 500)이 최악의 경우라 당연히.. c++/알고리즘 2023. 2. 14.

• 

  [c++] 백준-스도쿠 1520 - 백트래킹 1. 문제 2. 입출력 3. 예제 입 출력 4. 문제 해설 우리가 흔히 알고 있는 스도쿠 문제를 백트래킹을 이용해서 푸는 문제였다. 생각해보면 우리가 스도쿠를 푸는 과정도 백트래킹과 같다. 내가 문제를 푼 과정은 다음과 같다. 입력을 받는다. rows라는 2차원 배열에 각 행마다 1 ~ 9가 나왔는 지에 대한 정보를 저장해준다. cols라는 2차원 배열에 각 열마다 1 ~ 9가 나왔는 지에 대한 정보를 저장해준다. square라는 2차원 배열에 각각의 작은 4각형마다 1 ~ 9가 나왔는 지에 대한 정보를 저장해준다. vector에 0에 해당하는(우리가 구해야하는) 좌표를 저장해주었다. 깊이 우선탐색을 이용한다. 깊이 우선 탐색을 이용해 1 ~ 9까지 순서대로 그 칸에 해당하는 rows배열과 cols배열 .. c++/알고리즘 2023. 2. 13.

• 

  [c++] 백준-행렬곱셈순서 (dynamic programming) 1. 문제 2. 입출력 및 예제 3. 문제 해설 dp문제이다. 그리고 여태까지 dp배열을 채우던 방식과는 조금 다른 형태이다. 대부분의 dp문제에서는 가로 방향으로 dp배열을 채우거나 세로 방향으로 dp배열을 채워갔다. 하지만 이 문제는 대각선으로 채워가야하는 문제이다. dp문제를 풀 때는 세 가지 과정을 거쳐야한다고 했다. dp 배열의 정의 점화식 찾기 초기값 설정 나는 dp[i][i]를 i번째 배열에서 j번째 배열까지의 곱셈 연산 최소 횟수로 정의했다. 내가 생각한 점화식은 다음과 같다. 우선 행렬곱셈에 대해 알아보면 5 * 3 , 3 * 2, 2 * 6과 같이 세 행렬이 존재할 때 1번째로 가능한 곱셈의 경우는 앞의 두 행렬을 먼저 계산하고 마지막 행렬을 계산하는 것이다. 2번째로 가능한 곱셈의 경.. c++/알고리즘 2023. 2. 9.

• 

  [c++] 백준-집배원 한상덕(이분탐색 , 투포인터) 1. 문제 2. 입출력 및 예제 3. 문제 해설 이 문제는 난이도가 플레5였기 때문에 맞출 수 있었던 거 같다. 생각 자체는 어렵지 않았지만 이렇게까지 해야한다고...? 라는 생각이 들었다. 만약 골드하위나 실버였다면 분명 이게 아니라 다른 방법이 있을거야..라고 계속 생각만 했을 거 같았다. 이 문제의 핵심은 고도차를 최소로 모든 집을 방문해야한다는 것이다. 또한 문제를 읽어보니 N이 50으로 아주 작았다. 대부분의 경우 N이 작으면 완전탐색으로 풀어야하는 경우가 많지만 map으로 나타내면 50*50의 노드를 갖기 때문에 완전탐색의 경우의 수로 풀릴 것 같진 않았다. 따라서 생각해낸 아이디어는 이것이다. 입력받은 고도를 모두 담아 중복을 제거하고 sort한다. 우체국의 고도와 집의 고도 중 가장 큰 것.. c++/알고리즘 2023. 2. 8.

• 

  [c++] 백준-LCA2 (Least Common Ancestor) 1. 문제 2. 입출력 및 예제 3. 문제 해설 백준 - lca와 문제는 같다. 그러나 달라진 점이 있다면 노드의 개수가 10000개로 늘었다. 그리고 알아내야하는 노드의 쌍의 수도 늘었다. 이 문제는 그러면 이전 lca문제처럼 bfs나 dfs로 tree의 depth를 알아낸다. depth가 더 큰 쪽을 parent배열을 이용해 작은쪽과 depth를 맞춘다. 한칸 씩 올리다가 만나는 것이 lca에 해당한다. 위의 알고리즘을 사용하면 시간초과가 나게 된다. 그래서 이 문제는 dp를 적용해 lca + dp를 사용해야한다.... 어떤 문제건 두 가지 알고리즘이 섞이면 어렵지만 이 두개는 어려운 것이 두 개가 섞여 더 어려웠다. 한 번에 풀지는 못하고 이 문제의 핵심 아이디어를 찾아 본 후 구현할 수 있었다. .. c++/알고리즘 2023. 2. 8.

• 

  [c++] 백준-1865 웜홀 (벨만포드) 1. 문제 2. 입 출력 3. 예제 4. 문제 해설 벨만 포드 알고리즘을 이용해서 (음의 가중치가 있기 때문이다! 웜홀) 음의 사이클이 존재하는 지를 판단하면 되는 문제였다. 이 문제는 그러나 일반적인 벨만포드 알고리즘과는 다른 점이 두 가지가 존재한다. 웜홀이 아닌 도로의 경우 양방향 도로이다. 출발 노드가 정해져있지 않다. 벨만포드 알고리즘은 모든 간선을 노드 수 -1 만큼 탐색하면서 한 노드로부터 다른 노드들의 최단 거리를 갱신해가는 알고리즘이다. 원래는 간선의 시작 노드에 해당하는 노드를 방문한 적이 없다면 continue를 통해 넘기는 로직이 존재한다. 왜냐하면 시작 노드가 존재하기 때문에 시작노드로부터 간선이 도착한 적이 있어야 최단 경로를 계산할 수 있기 때문이다. 하지만 이 문제에서는 시작.. c++/알고리즘 2023. 2. 7.

• 

  [c++] 백준 - 특정한 최단 경로 1. 문제 2. 입출력 및 예제 3. 문제 해설 처음 이 문제를 읽었을 때 잘못 이해해서 얼마나 고생을 했던지... 나는 v1, v2를 이어주는 간선을 무조건 지나야한다는 줄 알고 처음에는 1 ~ v1, v2의 다익스트라를 1번 수행하고 N ~ v1,v2를 수행해서 1 ~ v1 + v1 ~ v2 + v2 ~ N과 1 ~ v2 + v2 ~ v1 + v1 ~ N 값 중 더 작은 값을 구하려고 했다. .. 다익스트라 2번이면 되었기 때문이다. 하지만 계속 틀렸다...! 그래서 왜일까 문제를 다시 읽어보니 v1, v2를 이어주는 간선을 무조건 지나가야 하는 것이 아니라 v1, v2를 그냥 지나가기만 하면 되었다. ... 그래서 생각 방향을 바꾸어 다시 생각을 해보니 이 문제가 오히려 갔던 길을 다시 가도 된다고.. c++/알고리즘 2023. 2. 6.