목록ALGORITHM/ALGORITHM STUDY (23)
MY MEMO
DFS는 stack BFS는 Queue를 이용하여 구현한다. DFS에서 visit가 2번 이상된 노드가 있다면 그것은 cycle이 생겼다는 의미이다. #include #include #include #include using namespace std; stack storage; vector visit; vector graph; int graph_count; void dfs() { storage.push(1); while (!storage.empty()) { int index = storage.top(); visit[index]++; if (visit[index] >= 2) return; storage.pop(); for (int j = 0; j < graph[index].size(); j++) { if(..
전구의 개수, testcase명령 0 : start_index end_index -> ON을 OFF로 OFF를 ON으로명령 1 : start_index,end_index 켜진 전구 개수 출력 #include #include #include #include using namespace std; #define ON 1 #define OFF 0 int main() { ifstream fcin; fcin.open("input.txt"); int bulb_count, testcase, order, start_index, end_index; fcin >> bulb_count >> testcase; vectorbulb(bulb_count+1, OFF); while (testcase--) { fcin >> order>..
1.십진수-이진수 변환 : string, while문, shift연산이진수 대칭 확인 : string_front,string_back,string_front.compare(string_back) #include #include #include #include #include #define CHECK_TIME_START __int64 freq, start, end; if (QueryPerformanceFrequency((_LARGE_INTEGER*)&freq)) {QueryPerformanceCounter((_LARGE_INTEGER*)&start); #define CHECK_TIME_END(a,b) QueryPerformanceCounter((_LARGE_INTEGER*)&end); a=(float)((..
#include #include #include #include #include #include "stdio.h" #include "time.h" using namespace std; //!%1한2%!345글eng이li다sh^&()@* int main() { clock_t before; double result; before = clock(); string english, korean, character,number; CString input = "!%1한2%!345글eng이li다sh^&()@*"; for (int j = 0; j = input.GetAt(j) || 127 < input.GetAt(j))) korean.push_back(..
[ 충돌(collision) ]- 두 개 이상의 키가 동일한 위치로 해싱되는 경우- 대표적인 두 가지 충돌 해결 방법: chaining과 open addressing 출처 : http://blog.naver.com/kts1801/220956548474 Linear Probing의 단점- 해시테이블에서 할당도니 공간이 연속해서 나타나는 뭉치가 있으면 이것이 점점 커지는 현상이 발생할 수 있는데, 이것을 집적화(Clustering)라고 부른다.- 클러스터링이 생기면 데이터 삽입 시 비어 있는 공간을 찾는 시간이 길어진다. 즉, 평균 탐색 시간을 증가시켜 성능을 저하시킴. 출처 : http://blog.naver.com/kts1801/220956548474 [출처] [해싱] - 충돌(Collision), 연쇄..
Heap Sort 개념 : http://priv.tistory.com/61 sort.h #pragma once #include #include using namespace std; #define LEFT_CHILD(x) (2*x + 1) #define RIGHT_CHILD(x) (2*x + 2) #define PARENT(x) ((x-1)/2) #define HEAP_FLAG_ON 1 #define HEAP_FLAG_OFF 0 #define LEFT_CHILD_FLAG_OFF 0 #define LEFT_CHILD_FLAG_ON 1 #define RIGHT_CHILD_FLAG_OFF 0 #define RIGHT_CHILD_FLAG_ON 1 #define HEAP_TREE_COUNT 200 #define N..
+) 출처 : https://blog.weirdx.io/post/3656이진 트리이진 트리(binary tree)는 한 노드가 최대 2개의 자식 노드를 가지는 트리를 말하며 첫 번째 노드는 부모(parent), 자식 노드는 왼쪽(left), 오른쪽(right)라고 불립니다.루트 이진 트리(rooted binary tree)는 모든 노드의 자식이 최대 2개인 루트를 가진 트리입니다.포화 이진 트리(full binary tree)는 모든 노드가 2개의 자식 노드를 가지며 모든 레벨이 꽉 찬 트리입니다.완전 이진 트리(complete binary tree)는 포화 이진 트리같이 모든 레벨이 꽉 찬 트리는 아니지만 모든 노드가 2개의 자식 노드를 가지는 트리입니다.+) 출처 : http://3dmpengines..
문제 출처 : https://code.google.com/codejam/contest/6254486/dashboard#s=p2+)i solve only small dataset (Cannot solve problem perfectly)ProblemA jamcoin is a string of N ≥ 2 digits with the following properties:Every digit is either 0 or 1.The first digit is 1 and the last digit is 1.If you interpret the string in any base between 2 and 10, inclusive, the resulting number is not prime.Not every strin..
ALGOSPOT RATIO : https://algospot.com/judge/problem/read/RATIO 알고리즘 책의 수치해석 부분에 있는 문제이다1%를 올리기 위한 최소로 이긴 게임의 수를 구해야한다 1. Rear와 Front를 이용하여 중간값을 구한다2.새로운 승률 - 원래 승률 >1 이면 =>조금 더 적은 경기를 이겨야 한다 따라서 Rear = Middle 새로운 승률 - 원래 승률 ==0 이면 =>더 많은 경기를 이겨야 한다 따라서 Front = Middle 3. Rear의 값이 Front보다 1더 많다면 최소로 이겨야하는 게임의 수가 도출된다4. 이 때 Front는 1%가 오르기 전의 최대 이긴 게임의 수 이고 Rear는 1%가 오른 최소 이긴 게임의 수이다 예외 ) 최대로 이길수 있는..
ALGOSPOT ROUTING : http://www.playsw.or.kr/repo/cast/105 최단 경로 알고리즘 (다익스트라 알고리즘 Dijkstra Algorithm)을 이용 최단 경로 알고리즘 개념 참고 : http://www.playsw.or.kr/repo/cast/105 visit라는 vector를 정의하여 목적지 노드로 갈 수 있는 최소의 거리를 저장한다.visit의 초기값은 무한대이므로 double의 최대인 DBL_MAX로 초기화한다. 1. 시작할 땐 noise에 있는 distance 값을 1.0으로 초기화 한다. -> 곱해야 자기 자신이 나올 수 있도록 여기서 distance는 현재까지 이동한 값이다. 이 값에 간선의 가중치를 곱하여 visit의 값과 비교한다 시작하는 index는 ..