전체 글

아스키코드(ASCII Code) - 컴퓨터의 문자 처리 원리

컴퓨터가 이해하는 언어는 0과 1(1bit)이다. 2진수로 데이터를 처리한다. 컴퓨터는 전기신호를 받아들이므로 전기의 OFF, ON 두 가지 상태(0과 1)로 모든 걸 표현하기 때문이다. 0과 1의 두 가지 상태를 나타내는 단위를 bit라고 한다. 그러나 1bit만으로는 표현할 수 있는 게 0, 1 단 두 개뿐이니, 더 큰 수를 표현하기 위해 8개의 bit를 묶어서 1byte를 사용한다. 컴퓨터가 데이터를 저장하는 최소 단위가 바로 이 byte다. 1byte는 8개의 bit니까 2의 8제곱, 즉 0~255(256개)의 데이터를 저장할 수 있다. 중요한 것은 더 큰 수를 표현할 수 있게 되었더라도 컴퓨터가 인식하는 것은 숫자라는 점이다. 컴퓨터는 0과 1 이외에는 아무것도 인식할 수 없기 때문이다. 그렇다..

[골5] 12904 - A와 B

#include #include #include using namespace std; #pragma region 입출력 속도향상 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion int main() { FAST_IO(); string s, t; cin >> s >> t; while (t.length() != s.length()) { if (t.back() != 'A') { t.pop_back(); reverse(t.begin(), t.end()); } else t.pop_back(); } cout

[실1] 2527 - 직사각형

#include #include using namespace std; int main() { int x1, y1, p1, q1, x2, y2, p2, q2; int xr, xl, yb, yt, xdiff, ydiff; for (int i = 0; i > x1 >> y1 >> p1 >> q1 >> x2 >> y2 >> p2 >> q2; xl = max(x1, x2); xr = min(p1, p2); yb = max(y1, y2); yt = min(q1, q2); xdiff = xr - xl; ydiff = yt - yb; if (xdiff > 0 && ydiff > 0) cout

[실1] 1629 - 곱셈

#include using namespace std; long long A, B, C; long long POW(int A, int B, int C) { if (B == 0) return 1; long long temp = POW(A, B/2, C); temp = temp * temp % C; if (B % 2 == 0) return temp; //짝수 일때 else return temp * A % C; //홀 수 일때 } int main(void) { cin >> A >> B >> C; cout

[실1] 1309 - 동물원

#include int D[100001]={1,3}; int main() { int N; std::cin>>N; for(int i=2;i

[실1] 11660 - 구간 합 구하기 5

#include #include using namespace std; #pragma region 입출력 속도향상 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion int main() { FAST_IO(); int n, m; cin >> n >> m; vector v(n + 1, vector(n + 1)); // 입력 for (int y = 1; y > v[y][x]; } // 구간합 구하기 vector d(n + 1, vector(n + 1)); for..

[골5] 9084 - 동전

#include using namespace std; #pragma region 입출력 속도향상 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion int main() { FAST_IO(); int t; cin >> t; while (t--) { int n; cin >> n; int coin[21] = { 0 }; for (int i = 1; i > coin[i]; int m; cin >> m; // n가지 동전 1 ≤ M ≤ 10000 int dp[10001] = { 0 }; dp[0] = 1; for (int i = 1; i

[골5] 12865 - 평범한 배낭

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

[C++] Dynamic Programming (동적계획법) / Top-Down (탑다운)과 Bottom-Up (바텀업) 방식

I. 다이나믹 프로그래밍 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다는 것이 핵심이다. 즉, 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이다. (우리가 평소에 문제를 풀이할 때 효율적인 방법으로 고안할 필요가 있다.) 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운-하향식, 바텀업-상향식)으로 구성된다. 매우 비효율적인 문제더라도 다이나믹으로 획기적으로 시간을 줄일 수 있다. 다이나믹 프로그래밍은 조건을 만족해야 사용할 수 있다. 최적 부분 구조 - 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제를 모아서 큰 문제를 해결 중복 부분 문제 - 동일..

탐욕 / 그리디 알고리즘 (Greedy Algorithm)

Greedy Algorithm 탐욕 알고리즘(그리디 알고리즘)은 특정 경우들 중 하나를 선택할 때, 그 순간에 가장 최적의 경우를 선택하는 알고리즘이다. 목적지까지 최단 경로로 가야 하는 상황을 예로 들어보자. 목적지를 향해 가던 중, 갈림길을 만났다. 그리디 알고리즘에서는, 다음과 같은 갈림길들 중 현재 상황에서만 최적인 경우를 선택한다. 따라서 위 그림에 그리디 알고리즘을 적용한다면, 직진을 하게 될 것이다. 하지만 만약 직진으로 간 다음 경유지에서 목적지까지의 거리가 100km이고, 다른 두 갈림길의 경유지에서 거리는 10km라면 어떻게 될까? 그리디 알고리즘을 통해 최적의 경우를 선택했지만, 결과적으로는 직진을 선택했기 때문에 목적지까지 최단경로로 갈 수 없게 된다. 이와 같이 그리디 알고리즘은 ..