전체 글

벨만 포드 (Bellman-Ford) 알고리즘

벨만 포드 알고리즘은 그래프 상에서 최단경로를 찾는 알고리즘이다. 최단경로를 찾는 다른 알고리즘인 다익스트라(Dijkstra)알고리즘과 다른 점은 간선의 가중치가 음수여도 가능하다는 점이다. 다만 다익스트라보다 수행시간이 더 오래걸린다는 단점이 있다. 따라서 간선의 가중치에 음수가 없다면 다익스트라를, 음수가 있다면 벨만 포드를 사용하는게 일반적으로 좋다. 개념 다익스트라 알고리즘이 그리디 알고리즘이였다면, 벨만 포드 알고리즘의 기본 개념은 다이나믹 프로그래밍이다. 즉, 이전에 계산한 최단경로를 이용해 새로운 최단경로를 갱신하는 식으로 동작한다. 예를 들어 시작노드 s에서 v에 이르는 최단경로는 s에서 u까지의 최단경로에 u에서 v사이의 가중치(거리)를 더한 값이다. 위와 같은 그래프가 있다면, s에서 ..

[실4] 15489 - 파스칼의 삼각형

dp를 활용했다 #pragma region 입출력 속도향상 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion #include using namespace std; #define SIZE 30 int dp[SIZE + 1][SIZE + 1]; int main() { FAST_IO(); int r, c, w; cin >> r >> c >> w; dp[1][1] = 1; for (int i = 1; i

[실5] 16395 - 파스칼의 삼각형

#pragma region 입출력 속도향상 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion #include #include using namespace std; int main() { FAST_IO(); int n, k; cin >> n >> k; vector pascal(n); for (int i = 0; i < n; i++) { int val = 1; for (int k = 0; k

[C++] 파스칼의 삼각형 (Pascal's triangle)

수학에서 이항계수를 삼각형 모양의 기하학적 형태로 배열한 것 위의 삼각형을 조합으로 그리면 아래와 같은 형태가 됨 #include using namespace std; int main() { int rows; cout > rows; cout

DP(동적계획법)을 이용한 이항계수 (Binomial Coefficient)

이항계수는 다음과 같이 표현되며 다음과 같은 성질을 따른다. int binomial(int n, int k) { if (k == 0 || k == n) { return 1; } return binomial(n - 1, k) + binomial(n - 1, k - 1); } 이렇게 간단하게 구현 가능하지만, 효율적이지는 않다. 알고리즘을 재귀호출하면서 이미 했던 계산을 반복해서 수행하기 때문이다 하지만 동적프로그래밍을 이용하면 중복되는 부분을 커버하여 효율적인 알고리즘을 만들 수 있다. Divide and conquer가 top-down 방식이였다면 dynamic progr..

[C/C++] 32bit 자료형 / 64bit 자료형의 크기 정리

#include #include #include int main(void) { printf("### 1 Byte = 8 bit ###\n"); printf("int : %d byte\n",sizeof(int)); printf("unsigned int : %d byte\n",sizeof(unsigned int)); printf("long int : %d byte\n",sizeof(long int)); printf("unsigned long int : %d byte\n",sizeof(unsigned long int)); printf("long long int : %d byte\n",sizeof(long long int)); printf("float : %d byte\n",sizeof(float)); prin..

[골3] 10986 - 나머지 합 구하기

#pragma region 입출력 속도향상 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion #include #include using namespace std; int main() { FAST_IO(); int n, m; cin >> n >> m; vector v(n + 1), c(m); vector s(n + 1); long ans = 0; for (int i = 1; i > tmp; v[i] = (v[i - 1] + tmp) % m; ans += (v[i] == 0); c[v[i]]++; } for (const auto& val : c) ans += (va..

C++ 컴파일과정 [링킹, 컴파일, 라이브러리, 오브젝트]

라이브러리(library)는 다른 프로그램들과 링크되기 위하여 존재하는, 하나 이상의 서브루틴(subroutine)이나 함수(function)들의 집합 파일 말하는데 함께 링크(link)될 수 있도록 보통 컴파일된 형태인 목적코드(object code) 형태로 존재한다. 라이브러리는 코드 재사용을 위해 조직화된 오래된 기법 중의 하나이며, 많은 다른 프로그램들에서 사용할 수 있도록, 운영체계나 소프트웨어 개발 환경 제공자들에 의해 제공되는 경우가 많다. 보통은 목적코드형태를 하나의 파일로 묶어 사용한다. 라이브러리가 생긴이유 1. 코드의 재사용 2. 코드의 부품화 실현 3. 소스를 제공하지 않아 기술 유출 방지 4. 사용자의 개발시간 단축 등의 이유가 있다. 프로그램 빌드 과정 - 컴파일 과정 링킹은 프..

[골5] 1806 - 부분합

#include #include #include using namespace std; #define MAX 987654321 int main() { int n, r; cin >> n >> r; vector v(100001); for (int i = 0; i > v[i]; int s = 0, e = 0, res = MAX; int sum = v[0]; while (true) { if (sum >= r) { res = min(res, e - s + 1); sum -= v[s++]; } else { if (++e == n) break; sum += v[e]; } } cout

[실3] 3273 - 두 수의 합

#include #include #include using namespace std; int main() { int n; cin >> n; vector v(n); for (int i = 0; i > v[i]; sort(v.begin(), v.end()); int x; cin >> x; int s = 0, e = n - 1, cnt = 0; while (s < e) { int a = v[s], b = v[e]; int sum = a + b; if (sum == x) cnt++; if (sum < x) s++; else e--; } cout