기억을 위한 기록들

www.acmicpc.net/problem/13565 13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net #include using namespace std; int map[1001][1001]; int chk[1001][1001]; int N, M; int dir[4][2] = { {-1,0} ,{0,1} ,{1,0} ,{0,-1} }; bool bIsFind; void D(int _x, int _y) { if (_x == N-1) { bIsFind = true; return;..

위 코드는 빌드하면 아무런 문제도 없다고 나온다. 이대로 F5 디버그를 눌러봐도 문제는 없어서 정상적으로 실행된다. 하지만 해당 코드는 힙에 메모리를 할당(new)해주고 해제(delete)를 해주지 않아 메모리 누수가 발생되는 코드이다. 이런 누수를 체크해주는 라이브러리가 있다. 라이브러리 _CrtDumpMemoryLeaks(); 그래서 해당 함수를 추가하고 디버그를 찍어보면, 중간에 Detected memory leaks! 라는 "메모리 누출 감지됨!" 이라는 말이 보인다. 그 밑에 그 말외엔 직관적인 힌트를 얻기 힘든데, #if _DEBUG #define new new(_NORMAL_BLOCK,__FILE__,__LINE__) #define malloc(s) _malloc_dbg(s,_NORMAL_B..

www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net #include #include using namespace std; int main() { int n; cin >> n; if (n

www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net #include #include using namespace std; int main() { int N; cin >> N; int arr[100000]; for (int i = 0; i > arr[i]; } sort(arr, arr + N, greater()); //내림차순 정렬 long long result = 0; for (int i = 0; i < N; i++) { ..

www.acmicpc.net/problem/2828 2828번: 사과 담기 게임 상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M> screenSize; cin >> basketSize; cin >> appleNum; int arr[20]; memset(arr, -1, sizeof(arr)); int n; //사과 떨어지는 위치 순서 저장 for (int i = 0; i > n; arr[i] = n; } //처음 바구니의 자치하는 정도 int left = 1; int right = basketSize; int moveCost = 0; for (int i = 0; i..

언리얼 스마트 포인터 라이브러리(Unreal Smart Pointer Library) 는 메모리 할당과 추적의 부담을 해소해주도록 설계된 C++11 스마트 포인터들의 커스텀 구현입니다. 이 구현에는 업계 표준인 쉐어드 포인터(Shared Pointers), 위크 포인터(Weak Pointers) 그리고 유니크 포인터(Unique Pointers) 가 포함되어 있습니다. 또한, null이 불가능한(non-nullable) 쉐어드 포인터와 같은 역할을 하는 쉐어드 레퍼런스(Shared References) 도 추가되었습니다. 단, 언리얼 오브젝트는 게임 코드에 더 최적화된 별도의 메모리 추적 시스템을 사용하기 때문에 이러한 클래스들은 ‘UObject' 시스템과 사용할 수 없습니다. -언리얼 엔진 공식 문서 ..

기존 그래프는 정점의 집합과 간선의 집합으로 이루어진 자료구조이다. 여기서 새로운 속성인 간선간의 가중치(Weight)를 부여해주게 된다. 최소 신장트리에서 신장트리(Spanning Tree)에서 Spanning는 여러 가지 뜻을 갖고 있지만, 떨어져 있는 둘 사이를 다리 등으로 연결한다는 뜻으로 사용. 즉, 신장 트리는 그래프의 모든 정점을 연결하는 트리이다. 신장트리는 한편으로 그래프의 하위 개념이기도 합니다. 그래프는 사이클을 형성하는 간선만 제고하면 트리로 됩니다. 최소 신장트리란 결국 최소 가중치 신장트리라고도 불립니다. 각 간선이 갖고 있는 가중치의 합이 최소가 되는 신장 트리가 바로 최소 신장 트리인것이다. 보통 "최소한의 비용으로 모든 도시를 연결하는 도로를 건설할 방법을 찾아라"라는 문제..

다익스트라 알고리즘은 프림 알고리즘 과 동작방식이 비슷하다. 다만 프림알고리즘은 단순히 간선의 길이를 이용해 어떤 간선을 먼저 연결할지 결정하는데 반해, 다익스트라 알고리즘은 '경로의 길이'를 감안해서 간선을 연결한다. 다익스트라의 최단 경로 탐색 알고리즘은 사이클이 없는 방향성 그래프에 한해서만 사용 가능. 동작 방식 1. 각 정점 위에 시작점으로부터 자신에게 이르는 경로의 길이를 저장할 곳을 준비하고 모든 정점 위에 있는 경로의 길이를 무한대로 초기화한다. 2. 시작 정점의 경로 길이를 0으로 초기화 하고(시작에서 시작까지는 0이므로), 최단 경로에 추가한다. 3. 최단 경로에 새로 추가된 정점의 인접 정점들에 대해 경로 길이를 갱신하고 이들을 최단 경로에 추가. 만약 추가하려는 인접 정점이 이미 최..

그래프 내의 모든 간선들의 가중치 정보를 사전에 파악하고 이 정보를 토대로 최소 신장 트리를 구축해나가는 것이 특징입니다. 작동 순서 1. 그래프 내의 몯느 간선을 가중치의 오름차순으로 목록을 만듭니다. 2. 1번에서 만든 간선의 목록을 차례대로 순회하면서 간선을 최소 신장 트리에 추가합니다. 단, 이때 추가 된 간선으로 인해 최소 신장 트리 내에 사이클이 형성되면 안됩니다. 해결해야 할 문제 최소 신장 트리에 생기는 사이클을 어떻게 효율적으로 감지 할 것인가? 대안 각 정점들을 각각의 집합 안에 입력하고, 간선으로 연결되어 있는 정점들에 대해서는 합집합을 수행. 이때 간선으로 연결할 두 정점이 같은 집합에 속해 있다면 이 연결은 사이클을 이루게 됨. 예제 사이클 탐지의 문제를 해결 했으니 예제를 통해 ..

최소 신장 트리를 만들어 내는 과정 1. 그래프와 최소 신장 트리를 준비. 이때의 최소 신장트리는 노드가 하나도 없는 상태 2. 그래프에서 임의의 정점을 시작 정점으로 선택하여 최소 신장 트리의 루트 노드로 삽입한다. 3. 삽입되어 있는 정점들과 모든 인접 정점 사이에 있는 간선의 가중치를 조사. 간선 중 가장 가중치가 작은 것을 골라 이 간선에 연결되어 있는 인접 정점을 최소 신장트리에 삽입. 단, 새로 삽입되는 정점은 최소 신장트리에 삽입되어 있는 기존의 노드들과 사이클을 형성 하면 안됨. 4. 3의 과정을 반복하다가 최소 신장 트리가 그래프의 모든 정점을 연결하게 되면 알고리즘 종료 예제 위와 같은 그래프가 있다. 여기서 임의의 정점 B를 시작으로 루트로 정해보자. 그 주위에 정점 A F C 로 가..

0. 기본 우선순위는 less (내림차순 높은값이 루트값) #include #include #include using namespace std; int main() { //priority_queue //아무것도 입력하지 않으면 기본 정렬은 less priority_queue pq; pq.push(4); //원소 추가 push pq.push(20); pq.push(3); pq.push(9); pq.push(1); pq.pop();//원소 제거 // 가장 높은 수인 20 제거 됨 cout

www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net #include #include #include using namespace std; int main(){ int n; cin >> n; int arr[100001]; int dp[100001]; int input; for (int i = 0; i > input; arr[i] = input; dp[i] = input; } int result = dp[0]; for (int i = 1; i <..