728x90 Algorithm (C++ based)70 백준 No.1504 [특정한 최단 경로] Baekjoon Online Judge No.1504 [특정한 최단 경로] Problem 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 .. 2021. 2. 9. Dijkstra (다익스트라) Dijkstra What is Dijkstra? 그래프의 한 노드에서 다른 노드로 갈 때 드는 가중치들의 합의 최소값을 구하는 알고리즘이다. 이 '가중치'를 문제가 요구하는 바에 따라 거리, 비용 등의 형태로 문제에 다양하게 적용시킬 수 있을 것 같다. Explanation A정점부터 탐색을 시작해봤다. 실제 코드에서 알고리즘을 사용할 땐 처음에 시작하고자 하는 정점을 정해주면 된다. 좌측의 표에서 빨간색은 확정된 최소 비용을 나타낸다. A에서 A로 갈 때에는 당연히 비용이 0이므로 확정이다. 숫자 앞에 A를 붙인 이유는 직전에 A에서 왔다는 의미이다. B, C, D E 열에 차례대로 비용을 적어준다. F열은 A에서 F로 가는 간선이 없으므로 inf 라고 하자. 저렇게 나열해준 뒤 확정이 된 빨간색 칸을.. 2021. 2. 8. 백준 No.11066 [파일 합치기] Baekjoon Online Judge No.11066 [파일 합치기] Problem 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 #incl.. 2021. 2. 7. 백준 No.12865 [평범한 배낭] Baekjoon Online Judge No.12865 [평범한 배낭] Problem 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include #include #define weight first #define value second using nam.. 2021. 2. 6. 백준 No.10942 [팰린드롬?] Baekjoon Online Judge No.10942 [팰린드롬?] Problem 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 #include #include using namespace.. 2021. 2. 5. Palindrome (팰린드롬) Palindrome Definition 앞에서부터 읽으나 뒤에서부터 읽으나 동일한 단어 혹은 구를 의미한다. Example 팰린드롬 "madam" "오디오" "안경안보여" 1234321 44 팰린드롬이 아닌것 123432 2021. 2. 5. BOJ No.2798 [블랙잭] Baekjoon Online Judge No.2798 [블랙잭] Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include #include using namespace std; int N, M; vector cards; int main() { cin >> N >> M; cards.resize(N); for (int i = 0; i > cards[i]; int answer = 0; for (int i = 0; i 2021. 2. 5. 백준 No.11049 [행렬 곱셈 순서] Baekjoon Online Judge No.11049 [행렬 곱셈 순서] Problem 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 7.. 2021. 2. 4. Monge array (Monge matrix) Monge array (Monge matrix) Definition 아래와 같은 조건을 갖는 m-by-n matrix 이다. 의 조건에 대해서 를 만족하는 matrix 를 Monge array 혹은 Monge matrix 라고 한다. Example 위 사진을 보면 Monge array 의 정의를 직관적으로 볼 수 있다. 표시해둔 보라색, 연두색 점들로 예를 들어보자. 이 점들의 i, j, k, l 은 다음과 같다. i = 2 j = 3 k = 4 l = 5 A[2, 3] + A[4, 5] 2021. 2. 3. 백준 No.1912 [연속합] Baekjoon Online Judge No.1912 [연속합] Problem 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include #include using namespace std; int N; vector nums; void input() { cin >> ::N; nums.assign(N, 0); for (int i = .. 2021. 2. 2. Programmers [가장 큰 정사각형 찾기] Programmers [가장 큰 정사각형 찾기] Problem 코딩테스트 연습 - 가장 큰 정사각형 찾기 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include using namespace std; int solution(vector board) { int width = board[0].size(); int height = board.size(); int answer = 0; for (int i = 0; i 2021. 2. 1. power 함수 구현 (분할 정복 이용) // Devide and Conquer algorithm 을 통한 power 함수의 구현. What is power function? Code 1 2 3 4 5 6 7 8 9 10 typedef unsigned long long ull; ull power(int num, int jisu) { if (!jisu) return 1; // num^0 = 1 이므로 if (jisu % 2) return (power(num, jisu - 1) * num) % p; ull half = power(num, jisu / 2) % p; return (half * half) % p; } Colored by Color Scripter cs Additional explanation 사실, 혹은 헤더파일에 있는 pow(a, n.. 2021. 1. 29. Pascal's triangle (파스칼의 삼각형) // Pascal's triangle What is Pascal's triangle? 좌측의 수식과 같은 이항계수의 값을 구할 때 사용할 수 있다. 하지만 아래 설명을 보면 알 수 있듯 점화식을 활용한 Dynamic Programming의 알고리즘을 사용하는 형태로, n의 값이 상당히 커진다면 사용하기 곤란한 알고리즘이다. n의 값이 상당히 커졌을 경우에는 Lucas Theorem (뤼카의 정리) 를 사용하면 된다. Explanation 위 파스칼의 삼각형을 나타낸 피라미드 모양의 그림에 연두색 값들은, 위에 있는 두 블록의 값의 합과 같다. 또한 양 변들은 nC0, nCn 이 되므로 값이 1이 된다. 이는 이항계수의 성질로서 증명이 된다. Dynamic Programming으로 C[n][k] 와 같은 .. 2021. 1. 28. Lucas's theorem (뤼카의 정리) // Lucas's theorem What is Lucas's theorem? 를 구하는 과정에서 n의 값이 상당히 클 경우 사용하면 유용한 정리이다. n의 값이 적당하다면, n!, ( n-k )!, k! 의 값을 각각 구하여 연산하면 되지만, n의 값이 10억만 되더라도 unsigned long lnog에 조차 담을 수 없게 된다. 이때 뤼카의 정리를 이용할 수 있다. Theorem 먼저, n과 k를 p진법의 전개식으로 나타내보자. 이때, 다음의 합동식이 성립한다. Example 따라서 아래와 같이 나타낼 수 있다. 따라서 답은 0이 된다. Proof // 아직 작성중인 글 입니다.. 2021. 1. 27. 백준 No.2603 [색종이 만들기] // Baekjoon Online Judge No.2630 [색종이 만들기] Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 #include #include #define DEVIDING_STANDARD 2 using namespace std; int N; vector paper; // 1 is blue, 0 is white int blue = 0; int white = 0; void DC(int len, int x, int .. 2021. 1. 24. 이전 1 2 3 4 5 다음 728x90
