백준 #11049 행렬 곱셈 순서 DP를 활용하는 문제. 이전까지 DP를 쓰는 문제는 top-down 방식을 썼는데(구현이 쉬워서) 실행 속도에 차이가 큼을 알고 나서는 bottom-up 방식을 쓰려고 한다. dp[i][j] = i부터 j까지의 최소 행렬 곱셈 개수 = min(dp[i][k] + dp[k + 1][j] + i번째 행렬의 세로 * ...

백준 2146 다리 만들기 BFS를 활용하는 문제. 하나의 섬 좌표를 모두 큐에 넣은 뒤 가장 빨리 다른 섬을 만나는 경우를 구한다. 모든 섬에 대한 최솟값을 구하면 된다. 백준 #7576 토마토 토마토 문제와 비슷한다. #include <iostream> #include <bits/stdc++.h> #include <...

백준 #1238 파티 지향 그래프에서 한 정점까지의 왕복 거리가 최대인 다른 정점을 구하는 문제. 다익스트라를 사용하여 풀 수 있다. #include <iostream> #include <bits/stdc++.h> #include <vector> #include <queue> #include <alg...

백준 #11779 최소비용 구하기 2 어느 정점에서 다른 정점까지 가는 최소비용과 도달하는 데 방문한 정점의 수와 정점을 출력하는 문제. 다익스트라 알고리즘을 사용하여 풀 수 있다. 경로가 수정될 때마다 직전에 방문한 정점을 prevVisited 배열에 저장한 후, 역순으로 출력한다. #include <iostream> #include...

백준 #11399 ATM 정렬을 활용하는 문제. 오름차순으로 정렬 후 cumulative sum을 모두 더해주면 된다. #include <iostream> #include <bits/stdc++.h> #include <vector> #include <algorithm> using namespace std...

백준 #13459 구슬 탈출 빨간 구슬과 파란 구슬이 있는 판을 10 회 이하로 기울여 빨간 구슬이 구멍에 빠지게 할 수 있는지 구하는 문제. BFS를 사용하여 가능한지의 여부를 구할 수 있다. 구슬이 두 개여서 한 번 기울일 때마다 두 구슬의 좌표를 각각 구해주고 겹치지 않게 해주어야 한다. 백준 #13460 구슬 탈출 2 위 문제가 이 문...

백준 #14890 경사로 길이가 L, 높이가 1인 무한 개의 경사로를 갖고 지나갈 수 있는 행과 열의 개수를 구하는 구현 문제. 각각의 행 또는 열을 루프를 돌며 검사하여 길을 만들 수 있는지 확인한다. 높이가 2 이상 차이가 나는 인접 칸이 있을 경우 false. 높이가 1이상 차이가 나는 경우 낮은 쪽의 길이 L만...

백준 #3085 사탕 게임 서로 다른 인접한 사탕의 두 위치를 바꿔 가장 긴 행 또는 열의 길이를 구하는 구현 문제. #include <iostream> #include <cstdio> #include <algorithm> using namespace std; int N; char board[50][50]; int...

백준 #1976 여행 가자 Union Find를 활용해 도시가 서로 연결돼있는지를 판별하는 문제. 도시가 연결돼있으면 서로 merge하고, 방문할 도시가 전에 방문한 도시와 같은 집합에 속해있는지를 판별한다. #include <iostream> #include <bits/stdc++.h> using namespace std...

백준 #2502 떡 먹는 호랑이 피보나치 수열이 일차방정식의 미지수의 계수가 되는 문제. 계수를 구해 방정식의 해를 구한다. #include <iostream> #include <bits/stdc++.h> #include <memory.h> using namespace std; int dp[31]; int co...