Do you believe in you?

소수: 2보다 크고 자기 자신 외에 약수를 가지지 않는 수 1. 자연수 N이 소수인지 판별하는 법 : 2보다 크거나 같고, 루트N보다 작거나 같은 자연수로 나누어 떨어지지 않는지 확인하기. : 시간복잡도 루트N * 왜 루트 N 까지? 자연수 N이 소수가 아니라면 N = a X b로 나타낼 수 있습니다.(a와 b는 자연수이고 N의 약수 조합) 이 때, a > b라면 두 수의 위치를 바꿔가며 항상 a 2) { return false; } for (int i = 2; i*i> n; bool result = prime(n); cout

*Binary Search Tree(이진 탐색 트리) : 이진 탐색이 동작할 수 있도록 고안된 자료구조. : 모든 key값은 유일하고, 값의 크기는 '왼쪽자식 노드 < 부모 노드 < 오르쪽 자식 노드' 순을 가짐. *이진 트리의 예 값의 크기를 왼쪽자식 노드 < 부모 노드 < 오르쪽 자식 노드 순으로 갖고 있기 때문에 위 트리는 이진트리이다. *이진 탐색 트리 방법 30을 찾는다고 가정해보자. 1) 루트노드인 20부터 탐색한다. 2) 30은 20보다 큰 수이므로 오른쪽 서브트리를 탐색한다. 3) 23보다 30이 큰 수이므로 23의 오른쪽 서브트리를 탐색한다. 4) 30 찾음 ! : 기존엔 모든 노드를 탐색해야했다면, 이진 트리이기에 탐색을 반으로 줄여가며 탐색할 수 있다. O(log₂N) but, 자식노..

1. Graph(그래프) 자료구조 *용어정리 G = (V, E) (정점 Node, Vertex / 간선 Edge) - 경로(시작점과 도착점이 다를 경우), 사이클(시작점과 도착점이 같을 경우) cf) 단순경로/단순 사이클: 같은 정점을 두 번 이상 방문하지 않는 경로/사이클 - 방향이 있는 그래프/방향이 없는 그래프 - 가중치: 간선의 비용. - 차수(Degree): 정점과 연결된 간선의 개수 cf) 방향 그래프의 경우, In-degree, Out-degree로 나누어서 차수를 계산한다. *그래프를 저장하는 법 ; 어떤 정점 x와 연결된 간선을 찾기 위해 어떻게 효율적으로 저장할지. 1) 인접 행렬 방법 A[i][j] = 1, A[i][j] = 0. > nodeNum; vector *graph = new..

코딩을 할 때, 메모리를 효율적으로 사용하기 위해 동적할당을 사용하곤 합니다. 원하는 만큼 메모리를 할당하고 사용이 끝나면 메모리를 해제해서 메모리를 관리하는 것이지요. 참고로 정적변수들은 stack 메모리에 생성되고 동적변수들은 heap 메모리에 생성됩니다. stack영역은 컴파일 동안 메모리가 결정되고 CPU에 의해 관리되어 함수 호출이 완료되면 사라집니다. 선입선출구조로. heap영역은 런타임 동안 메모리가 결정되고 프로그래머가 요구한 만큼 OS가 빈공간을 찾아서 할당해줍니다. 선입선출 구조가 아니고 유동적으로 할당/해제되므로 꼭 해제가 필요합니다. (메모리가 조각조각 배분되어 메모리 누수가 발생할 수 있음) 1. 1차원 배열 동적할당 int* arr = new int[5]; //크기가 5인 일차원..

C++은 해시테이블을 unordered_map 이라는 STL로 구현할 수 있다. unordered_map 클래스 다양한 길이의 요소 시퀀스를 제어하는 C++ 표준 라이브러리 컨테이너 클래스 에 대한 API `unordered_map` 참조입니다. docs.microsoft.com * 시간복잡도 해쉬테이블은 key 값으로 탐색하기 때문에 탐색 시간복잡도는 O(1) 밖에 걸리지 않는다. 또한, 정렬할 필요가 없으므로 데이터 추가, 삭제 시에도 그 성능이 꾸준히 보장된다. * map vs unordered_map map 은 정렬이 된다. 레드블랙트리기반이므로 탐색, 삽입, 삭제에 O(longN)의 시간복잡도가 걸린다. unordered_map 은 정렬이 안된다. 해시테이블 기반이므로 탐색, 삽입, 삭제에 평균..

* Heap(힙) : 최대값/최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 형태의 자료구조 (완전 이진 트리: 마지막 레벨을 제외한 모든 레벨의 node가 완전히 채워져 있고, 마지막 레벨의 node들은 가능한 한 왼쪽부터 채워져 있는 구조) : 삽입/삭제/최대값 찾기/최소값 찾기에 걸리는 시간복잡도 O(logN) : root가 최대 값을 갖는 최대 힙(Max Heap)과 root가 최소 값을 갖는 최소 힙(Min Heap)이 있음 : 값이 '왼쪽 자식 < 부모 < 오른쪽 자식' 순으로 크기가 큰 이진 탐색 트리(Binary Search Tree)와 달리 '자식 < 부모' 형태의 값 크기만 유지됨. : Heap 자료구조를 응용한 대표적인 예) Priority q..

정적할당으로 만들어진 변수는 DATA영역에 저장되는데, 동적할당으로 만들어진 변수는 HEAP영역에 저장된다. DATA 영역에 할당된 변수의 메모리 크기는 sizeof 연산자로 크기를 불러 올 수 있지만, HEAP 영역에 할당된 변수의 메모리 크기는 sizeof 연산자로 불러올 수 없다. _msize 연산자로 불러와야 한다. _msize Learn more about: _msize docs.microsoft.com * 정적할당으로 만든 배열의 크기 구하기 int arr[5]; int arr_size = sizeof(arr) / sizeof(int); * 동적할당으로 만든 배열의 크기 구하기 #include #include // _msize() 사용을 위해 malloc.h 헤더 추가! using namesp..

[본론으로 들어가기 전에...] 기존의 map은 요소가 자동으로 오름차순으로 정렬되는 이진 탐색 트리(BST) 기반이었다. 그래서 정렬이 필요하지 않은 경우에도 자동으로 정렬되어 불필요한 오버헤드가 있었다. 즉, 오버헤드를 감수하면서 map을 사용하던지, 비표준 라이브러리인 hash_map을 사용해야 했다. 그런데, C++11 부터 이런 불편함을 해소해줄 unordered_map 이 등장했다. map과 달리 이진 탐색 트리가 아니라 '해시 테이블'로 구현되어 있는 자료구조로. unorderd_map은 정렬이 자동으로 되지 않고, 요소 검색/삽입/삭제 연산이 O(1) 시간 안에 가능하다. 그래서 우리가 공부해야할 자료구조는 unordered_map 이다 ! [unordered_map(hash_map)의 특..

문자열 문제에서 유용하게 쓸 정규표현식을 공부해보자. (http://sweeper.egloos.com/2999049 사이트를 참고해서 적었습니다.) · 헤더파일: · 관련 함수: 1) regex_match: 정규식이 전체 대상 문자열과 일치하는지 여부를 반환(bool) 2) regex_search: 문자열이 정규식과 매치되는 sub string을 포함하고 있는지 여부를 반환(bool) 3) regex_replace: 정규식 표현식을 replace 문자열로 교체한다. 교체된 전체 문자열을 반환한다.(string) 4) swap: 두 basic_regex 또는 match_results 개체를 교환 합니다.(string) · 상세 설명 1) std::regex_match 는 전체 문자열이 특정 규칙(패턴)을 ..

2차원 행열을 2차원 벡터를 활용해서 표현해보고, 그 값을 초기화해보자. vector visited_map(4, vector(3, false)); 뜻은 2차원 행열과 같은 역할을 하는 4 X 3 짜리 2차원 벡터를 생성과 동시에 false로 초기화한다는 말이다. 그럼 아래와 같은 데이터 공간이 만들어지게찌~ false false false false false false false false false false false false 참고로 1차원 벡터의 생성과 초기화는 다음 구문으로 표현할 수 있다. vector v(4,0); 뜻은 4열짜리 벡터를 만들고 0으로 초기화 해준다는 말~ 0 0 0 0 #2차원 벡터 동적할당 및 해제 방법! #include int main(){ //동적할당 생성 vector..