Doby's Lab

https://www.acmicpc.net/problem/14490 14490번: 백대열 n과 m이 :을 사이에 두고 주어진다. (1 ≤ n, m ≤ 100,000,000) www.acmicpc.net 1) 문자열로 입력받아서 while문을 통해 정수로 바꿔주기 2) stoi()를 이용해 문자열 -> 숫자 3) 유클리드 호제법을 이용하여 최대공약수 구하기 4) 두 수에 나눠준 몫을 출력 #include #include using namespace std; int gcd(int a, int b) { if (a % b == 0) { return b; } return gcd(b, a % b); } int main() { string value; cin >> value; string a, b; int cnt =..

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 두 개의 다익스트라 알고리즘을 선언하여 문제를 풀 수 있었다. 우선 문제를 두 개로 나누어 생각할 수 있다. 1) 갈 때 시간 2) 돌아올 때 시간 3) 두 값 합한 것 중 최댓값 도출 1) 갈 때 시간 갈 때의 시간은 여러 노드들로부터 다익스트라를 돌려봤다. 그리고 X까지 가는 데에 드는 비용들을 배열에 저장해두었다. for (int i = 1; i N >> M >..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net (https://yabmoons.tistory.com/364) 이번 포스팅은 링크에 걸어둔 다익스트라 포스팅을 정리한 포스팅으로 자세한 설명은 링크에 되어있다. [다익스트라 개념 정리] 시작 노드 -> 도착 노드로 가는 최소 비용(가중치)을 구하는 알고리즘 1. 첫 노드 방문 체크 2. 방문한 노드와 연결되어 있는 노드들 거리 업데이트 3. 방문한 노드와 연결..

https://draw-code-boy.tistory.com/47 [자료구조] 우선순위 큐 (Priority Queue) 개념, C++ STL 우선순위 큐란 큐의 한 종류로 말 그대로 우선순위대로 큐에 데이터를 집어넣는다. (여기서 말하는 우선순위란 값의 크기의 오름차순 혹은 내림차순 등 사용자가 정할 수 있다.) 일반적인 큐는 draw-code-boy.tistory.com 저번에 우선순위 큐를 다룬 적이 있다. 이번 다익스트라를 공부하면서 우선순위 큐로도 구현할 수 있는 것을 공부했는데 이번 기회에 저번에 남았던 궁금증을 해결해보려 한다. 왜 비교 연산자가 반대로 작용할까? 답은 쉽게 구할 수 있었다. (https://hydroponicglass.tistory.com/169) #include #incl..

https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 지난번에 풀었던 RGB 거리 문제와 다른 조건이 딱 하나 걸려있다. (RGB 거리 https://draw-code-boy.tistory.com/51) 1번 집과 N번 집의 색깔이 같으면 안 된다. 이 조건을 맞춰주기 위해 초기값(1번 집)에서 최솟값이 나오는 인덱스를 구하고, DP가 끝난 후에 최솟값이 나오는 인덱스 값(1번 집 색깔)을 제외한 색깔 중에 DP 최솟값을..

https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 저번에 공부했던 LCS알고리즘을 이해하고 있다면 똑같은 DP의 방식으로 문자열 배열 DP를 돌리면 된다. (LCS 정리 https://draw-code-boy.tistory.com/126) [AC 코드] cache2 == 문자열 메모이제이션 배열 #include #include #include #include #define MAX 1000 + 1 #..

https://www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수 www.acmicpc.net 연산자 배열을 선언 후 각 연산자를 고른 경우 총 4가지를 가지고서 백트래킹 하면 된다. #include #include #include #include #include using namespace std; int n; vector num; int oper[4] = { 0, }; int maxValue = INT_MIN; int minValue = INT..

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 범위가 8밖에 되지 않아서 백트래킹으로 나올 수 있는 수열들을 temp 배열에 담아 직관적으로 풀 수 있는 문제였다. abs() == 절댓값 함수 #include #include #include #define MAX 8 + 1 using namespace std; vector v; vector temp; int n; bool visited[MAX]; int maxValue = 0; void sol(vector&..