hyunjin

씹어먹는 c++1.2 namesapce namespace가 정의된 파일을 먼저 #include 한 다음 namespace로 선언한 후 사용. 1. header1이라는 이름 공간이 header1이라는 헤더 파일에 존재 #include "header1.h" using namespace header1; int main(){ foo(); } 2. iostream 파일 안에 header1이라는 이름 공간이 존재하는 경우 #include using namespace header1; int main(){ foo(); } 주의 using namespace std; 와 같이 어떤 이름 공간 사용하겠다 선언하는 것 권장X 이름 겹치는 함수 만들면 오류 발생. usgine namespace std; 대신 std:: 직접 앞..

깊이 우선 탐색 (Depth - First Search) 개념 DFS(깊이 우선탐색) : 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색 현재 정점에서 다음 분기로 넘어가기 전에 해당 분기를 완변하기 탐색 노드를 깊게 탐색 DFS 장점 1. 현재 경로상의 노드들만 기억하면 되므로, 저장 공간 수요 비교적 적음 2. 목표 노드가 깊은 단계에 있는 경우 해를 빨리 구할 수 있음 3. 구현이 BFS보다 간단 DFS 단점 1. 단순 검색 속도는 BFS 보다 느림 2. 사전에 임의의 깊이를 지정 후 탐색하고, 목표 노드를 발견하지 못할 경우 다음 경로 탐색하도록 하는 것이 좋음 3. 깊이 우선 탐색은 해를 구하면 탐색이 종료되므로 , 구한 해가 최단 경로가 된다는 보장이 없음. (목표에 이르는 경로가 다수인 ..

너비 우선 탐색 (Breadth - First Search) 개념 BFS(너비우선탐색) : 현재 정점에서 연결된 가까운 점들 부터 탐색 가까운 정점 먼저 방문 후 멀리 떨어져 있는 정점 나중에 방문 노드를 넓게(wide) 탐색 주로 두 노드 사이 최단 경로 혹은 임의의 경로 찾고 싶을 때 사용 응용하면 미로찾기 같은 알고리즘도 구현 가능 BFS 장점 1. 노드 수 적고 깊이 얕은 경우 빠름 2. 단순 검색 속도가 DFS 보다 빠름 3. 너비 우선 탐색하기 때문에 답이 되는 경로가 여러 개인 경우라도 최단 경로임을 보장 4. 최단 경로가 존재한다면 어느 한 경로가 무한히 깊어져도 반드시 최단 경로 찾을 수 있음 BFS 단점 1. 재귀 호출의 DFS 와 달리 큐에 다음에 탐색할 정점들을 저장해야해 저장 공간..

유클리드 호제법이란? 두 수의 최대 공약수를 구하는 알고리즘의 하나. 2개 자연수 a, b ( a > b )에 대해 a를 b로 나눈 나머지를 r이라 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 또 다시 b , r 에 대해 b를 r로 나눈 나머지 r' 을 가지고 위의 과정을 반복해 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대 공약수. ( a , b ) = ( b , r (=a%b) ) = ( r , r' ) ( 1071 , 1029 ) = ( 1029 , 42 ) = ( 42 , 21 ) = ( 21 , 0 ) = 21 21은 1071과 1029의 최대 공약수 GCD 관련 법칙 GCD( u , v ) = GCD( u - v, v ) if u < v GCD( u, v ) = GCD(..

char string char -> string #include char ch[20] = "hello world"; string str1(ch); string str2 = ch; 1. string 생성자 이용해 생성 할 때 인자로 넘겨서 생성 2. char 배열 이름을 사용해서 대입 연사자 이용해 대입 string - > char //string -> char string str = "HELLO WORLD"; cout char* (동적 할당) string str = "hello world"; char *ch2 = new char[ str.size() + 1 ]; copy(str.begin(),str.end(),ch2); strcpy(ch2 , str.c_str()); // copy or str..

숫자, 알파벳 모두 확인하는 isalnum도 있음 1. isalpha 알파벳 판별 함수 헤더 파일 c++ 함수 원형 int isalpha (int c); char는 int나 EOF로 cast됨. 반환 대문자 A-Z(int 65~90) 는 1 반환 소문자 a-z(int 97~122) 는 2 반환 아니면 0 반환 cout 0이 나옴 - isdigit(str[1]) => '1' => 0이 아닌 수가 나옴 - isdigit(str[2]) => '2' => 0이 아닌 수가 나옴 - isdigit(str[3]) => '3' => 0이 아닌 수가 나옴 - isdigit(str[4]) => '4' => 0이 아닌 수가 나옴 - isdigit(str[5]) => '5' => 0이 아닌 수가 나옴 - isdigit(str..

데이터 정렬 이유 : 탐색을 위해서 (정렬이 탐색보다 시간이 덜 걸린다 했나?..) 1. 삽입 정렬(Insertion Sort) 두 번째 원소부터 맨 마지막 원소까지 각 원소가 왼쪽에 있는 모든 원소 보다 크거나 같을 때 까지 왼쪽으로 이동 현재 위치보다 아래쪽 순회하며 알맞은 위치에 넣는 정렬 //insertion sort #include using namespace std; template void insertSort( Vector* v, const int l, const int r){ for(int i = l+1 ; i left && v[j] < v[j-1] ; j--){ swap(v[j-1],v[j]); } } } 이미 정렬되어 있는 자료 구조에선..

1. Dynamic Programming(동적 계획법) 이란? 큰 문제를 작은 문제로 나누어 푸는 문제 1.1 Divide&Conquer(분할정복) 과 다른 점은? 거의 비슷하지만 결정적 차이가 있다. 작은 문제가 중복이 일어나나는 아닌지 분할 정복 큰 문제를 해결하기 어려워 단순히 작은 문제로 나누어 푸는 방법 작은 문제에서 반복이 일어나는 부분이 없다 DP 작은 부분 문제들이 반복되는 것(답이 바뀌지 않는다.)을 이용해 풀어나는 것 1.2 Dynamic Programming 방법 모든 작은 문제들은 한 번만 풀어야함. 정답을 구한 작은 문제들을 어딘가에 메모해놓고 다시 그보다 큰 문제 풀어나갈 때 똑같은 작은 문제가 나타나면 앞에서 메모한 작은 문제의 결과값 이용 1.3 Dynamic Programm..