전체 글

[골2] 1766 - 문제집

#include #include #include #include #pragma region 빠른 입출력 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion using namespace std; vector degree; vector graph; priority_queue pq; int main() { FAST_IO(); int n, m; cin >> n >> m; graph.assign(100001, vector()); degree.assign(n + 1, 0); for (int i = 0; i > a >> b; g..

[골3] 2252 - 줄 세우기

#include #include #include #include #pragma region 빠른 입출력 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion using namespace std; vector degree; vector graph; queue q; int main() { FAST_IO(); int n, m; cin >> n >> m; graph.assign(100001, vector()); degree.assign(n + 1, 0); for (int i = 0; i > a >> b; graph[a].pu..

[C] 복합 대입 / 증감 연산자

복합 대입 연산자와 증감 연산자는 연산식을 간단하게 표현할 수 있는 특별한 연산자다. #include int main () { int a = 3, b = 2; printf ( "%d %d \n", ++a, b–); a + 1; b -= 1; printf ( "%d %d \n", a, b); } 4행에서 정수형 변수 a와 b를 선언하고, 각각 3과 2로 초기화한다. 5행에서 a의 값을 1만큼 증가시키는 연산자 ‘++’에 의해 a의 값이 4가 된다. 그러나 b의 값을 1만큼 감소시키는 연산자’–‘는 다음 번 b의 값을 이용할 때까지 연산을 보류시킨다. 6행에서 ‘a+=1’은 a값을 1만큼 증가시키는 ‘a=a+1’을 줄인 표현이며, ‘b-=1’도 b 값을 1만큼 감소시키는 ‘b=b-1’을 줄인 표현이다. 따라..

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) / 장단점, 구현 및 시간복잡도

DFS의 장/단점 장점 현 경로상의 노드들만 기억하면 되므로 저장공간 수요가 비교적 적다. 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 단점 해가 없는 경로가 깊을 경우 탐색시간이 오래 걸릴 수 있다. 얻어진 해가 최단 경로가 된다는 보장이 없다. 깊이가 무한히 깊어지면 스택오버플로우가 날 위험이 있다. (깊이 제한을 두는 방법으로 해결가능) DFS의 구현 그래프를 인접 행렬(adjacency matrix)로 구현했는지, 인접 리스트(adjacency list)로 구현했는 지에 따라 구현방법이 달라진다. 인접 행렬로 구현했을 경우 [시간복잡도] DFS 하나당 N번의 loop를 돌게 되므로 O(n)의 시간복잡도를 가진다. 그런데 N개의 정점을 모두 방문 해야하므로 n*O(n)이므로 O(n..

[골5] 1717 - 집합의 표현

#include #include #include #pragma region 빠른 입출력 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion using namespace std; int graph[1000001]; int GetParent(int x) { if (graph[x] == x) return x; else return graph[x] = GetParent(graph[x]); } void Union(int a, int b) { a = GetParent(a), b = GetParent(b); graph[a] = b; } void Find(int a, int b..

[C++] Buffer Overflow (버퍼 오버플로우) 예시

String Buffer Overflow 20byte의 buf를 할당하고 std::cin 함수를 통해 문자열을 입력받는다. 하지만 여기서도 입력한 문자열의 길이를 검사하는 부분이 없어서 20byte 이상의 문자열을 입력한다면 버퍼오버플로우가 발생할 수 있다. #include using namespace std; int main() { char buf[20]; cin >> buf; // string 제외 입력에 따라 자동 할당됨. } Container Overflow f 함수 부분이다. vector v를 src 매개변수로 받는다. std::vector dest(5) 7행에서 기본값(0)으로 초기화 된 5개의 원소를 가지는 vector dest를 생성한다. std::copy(src.begin(), src.e..

[C] 버퍼 오버플로 (buffer overflow)

프로그램이 데이터를 버퍼(buffer)에 저장할 때, 버퍼가 가득 차 넘치게 되어 프로그래머가 지정한 부분 바깥에 덮어 씌워버리는 취약점, 버그, 이를 이용한 공격 방법을 말한다. 넘쳐난 데이터는 원래 데이터를 밀어내거나 이상한 곳에 저장하는 것이 아니라 덮어 씌우는 것이다. 덮어 씌워진 메모리에는 다른 데이터가 이미 포함되어 있을 수 있고, 이 때문에 메모리 접근 오류, 프로그램 종료, 시스템 보안 취약점 등이 발생할 수 있다. 버퍼 오버플로는 보통 데이터를 저장하는 과정에서 그 데이터를 저장할 메모리 위치가 유효한지를 검사하지 않아 발생한다. 이러한 경우 데이터가 담긴 위치 근처에 있는 값이 손상되고 그 손상이 프로그램 실행에 영향을 미칠 수도 있다. 특히, 악의적인 공격으로 인해 프로그램에 취약점이..

[C++] 디버그 모드에서 변수의 메모리 차지 공간

int64의 크기는 8바이트이고 로컬변수 선언시 스택 메모리에 8바이트씩 차지하게 된다. 8바이트 크기의 변수 3개를 선언 후 메모리 주소를 확인해보자. int64 n1 = 1; int64 n2 = 2; int64 n3 = 3; cout

[C/C++] 메모리 오류에 대하여

1. C/C++에서 메모리 오류의 종류 일단 메모리 공간에 따라 크게 Heap Memory 에러와 Stack (local variables) Memory 에러가 있다. Heap 메모리 영역에서 발생가능한 에러는 이미 해제된 메모리 다시 해제 할때 할당된적도 없는 메모리 해제 할라고 할때 이미 해제된 메모리 영역에 뭔가 데이터를 쓰려고 할때 할당된 적이 없는 메모리에 뭔가 데이터를 쓰려고 할때 메모리 할당 에러 동적으로 할당된 메모리 배열에서 초과된 index의 위치를 읽거나 쓰려고 할때 1,2 번과 3,4번을 묶어서 볼 수 있는데 해제시에 발생하는 문제 vs 데이터 입력시 발생하는 문제로 볼 수 있다. 스택 메모리 영역에서 발생가능한 에러들로는 정적 배열에서 초과된 index의 위치를 읽거나 쓰려고 할때..

[골5] 27172 - 수 나누기 게임

#include #include #include #pragma region 빠른 입출력 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion using namespace std; #define MAX 1000001 int main() { FAST_IO(); int n; cin >> n; vector v(n); int scores[MAX]{ 0 }, cards[MAX]{ 0 }; for (int i = 0; i > v[i]; cards[v[i]] = 1; } // 에라토스테네스의 체 응용 for (int i = 0; i < n; i++)..