728x90 🥇Baekjoon Solutions73 [C++] 백준 14852번: 타일 채우기 3 https://www.acmicpc.net/problem/14852 14852번: 타일 채우기 3 첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 중요풀이 다이나믹 프로그래밍을 사용하여 반복되는 행동을 for문 또는 재귀를 통해서 풀이를 진행합니다. dp[i]는 3*dp[i-2](1*2 두개, 1*1 두개 + 1*2한개 경우 2개 따라서 3가지) + 2*dp[i-1](1*1 두개, 2*1한개) 점화식은 dp[i] = 3 * dp[i - 2] + 2 * dp[i - 1] + (2 * dp[i-3] + ... + 2 * dp[0])이 나옵니다. 소스코드 #include using namespace std; int dp[1000001]; long long.. 2021. 8. 28. [C++] 백준 2812번: 크게 만들기 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 중요풀이 이 문제는 그리디 알고리즘을 활요한 문제입니다. 앞에서부터 순차적으로 보았을 때 다음 자리 숫자보다 현재 자리 숫자가 작다면 현재 자리 숫자를 제거해주는 식으로 루프를 진행해주고 이 과정이 끝나고도 K자리를 다 빼지 않았다면 남은 K의 숫자만큼의 자리를 뒤에서부터 빼주는 과정을 반복합니다. 소스코드 #include #include using namespace std; int main() { int N, K, i = 0; string num; vectorv; cin .. 2021. 8. 27. [C++] 백준 11657번: 타임머신 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 중요풀이 벨만-포드 알고리즘을 사용하는 대표적인 예제 문제입니다. 노드 사이에 가중치가 음수값을 갖기 때문에 다익스트라 알고리즘이 아닌 벨만-포드 알고리즘을 사용해줍니다. 거리 값이 INF이 아닌 노드들을 체크하여 이동할 수 있는 간선의 가중치를 계산하여 더 작은 값으로 갱신해 줍니다. 여기서 음의 가중치를 갖는 간선이 있다면 그 구간을.. 2021. 8. 27. [C++] 벨만-포드(Bellman - Ford) 알고리즘 벨만-포드 알고리즘이란? 벨만-포드 알고리즘은 가중치 방량 그래프에서 최단 경로 문제를 푸는 알고리즘입니다. 다익스트라 알고리즘에서 간선의 가중치가 음수일 수 없었던 것에 반해 벨만-포드 알고리즘은 가중치를 음수 값으로 갖는 것이 가능합니다. 다만 속도 측면에서 다익스트라 알고리즘이 벨만-포트 알고리즘에 비해 빠른 속도를 갖습니다. 과정은 어떤 한 정점에서 어떤 다른 정점으로 갈 때 그 정점의 개수가 N개면 최대 N-1개의 간선을 사용해야 합니다. 그렇게 시장 정점에서 각 정점까지 가는 가는 최소 가중치합을 간선의 선택개수를 N - 1개까지 증가시키며 비교해주면 됩니다. 그렇게 최소 값들을 유지시키면 됩니다. 마지막으로 N - 1 번째 시행했을 때 남은 값들을 출력합니다. 예시 코드 #include #i.. 2021. 8. 26. [C++] 백준 10159번: 저울 https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 중요풀이 플로이드 와샬 알고리즘을 활용하여 문제풀이를 진행합니다. 서로 비교가 가능한 노드들을 체크하여 최종적으로 전체에서 비교 가능한 노드와 자기자신으로 오는 경우를 빼줍니다. 소스코드 #include #include using namespace std; int INF = 200001;// 노드가 최대 100, 간선의 수가 최대 100,000개 이기 때문에 최소 1000.. 2021. 8. 24. [C++] 백준 11404번: 플로이드 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 중요풀이 가장 기본적인 플로이드 와샬 알고리즘을 활용한 문제입니다. 소스코드 #include using namespace std; int INF = 10000001;// 노드가 최대 100, 간선의 수가 최대 100,000개 이기 때문에 최소 10000001으로 설정 int node[101][101]; int dp[101][101]; void floydWarshall(int n) { //그래프 초.. 2021. 8. 24. [C++] 플로이드 와샬(Floyd Warshall) 알고리즘 개념 플로이드 와샬 알고리즘이란? 다익스트라 알고리즘이 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이라면 플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘입니다. 핵심 아이디어는 거쳐가는 정점을 기준으로 최단 거리를 구하는 것입니다. 예시코드 int node[n + 1][n + 1];//입력받기 int dp[n + 1][n + 1];//다이나믹 프로그래밍 void floydWarshall(int n) { //그래프 초기화 for (int i = 1; i 2021. 8. 24. [C++] 백준 20040번: 사이클 게임 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 중요풀이 union-find 알고리즘을 활용하여 풀이를 진행한 대표적인 문제입니다. union-find 알고리즘을 적용한다면 무난하게 풀어지는 문제입니다. 소스코드 #include using namespace std; int parent[500001]; int find(int index) { if (parent[index] == index)return index; return parent[i.. 2021. 8. 23. [C++] 백준 17472번: 다리 만들기 2(좋은 문제) https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 중요풀이 이 문제는 삼성 코딩테스트에 출제되었던 기출문제입니다. 중요 알고리즘이 2개나 사용되는 아주 좋은 문제인 것 같습니다. 사용되는 알고리즘은 크루스칼 알고리즘(최소 스패닝 트리)와 BFS(너비 우선 탐색)이 있습니다. #include #include #include #include using namespace std; //좋은 문제 : 여러가지 알고리즘 혼합 int l.. 2021. 8. 23. 이전 1 2 3 4 5 6 ··· 9 다음 728x90
