본문 바로가기

분류 전체보기

 (308)
[알고리즘] 다익스트라 알고리즘 지금까지는 그래프의 노드간 이동 비용이 동일하다고 가정하에 진행했다. 하지만 가중치라는 값이 있어서 노드간 이동비용이 다를 수 있다. 이렇게 가중치가 있는 경우에는 처음에는 C에서 D까지 가는 비용이 9인데 E를 거치면 6이 된다. 탐색 중에 더 짧은 경로를 발견할 수 있기 때문에 이럴 때마다 경로를 다시 설정해야 한다. 그래서 다익스트라는 두가지 행동을 반복해서 최단경로를 찾는다. 1. 방문하지 않은 노드 중에 비용이 가장 적은 노드를 선택한다. 2. 해당 노드에서 특정한 노드로 가는 것을 고려해서 최소 비용을 갱신한다. verticles.resize(6); adjacent = vector(6,vector(6,-1)); adjacent[0][1] = 15; adjacent[0][3] = 35; adja..
[알고리즘] BFS(너비 우선 탐색) BFS는 시작 지점을 기준으로 거리(몇번을 거쳐야 하는지)가 짧은 순으로 탐색한다. BFS는 큐를 이용해 구현할 수 있다. void BFS(int here) { queue q; q.push(here); discovered[here] = true; while(q.empty() == false) { here = q.front(); q.pop(); for(int there : adjacent[here]) //큐에 현재 정점과 인접한 정점 중 발견되지 않은 정점을 큐에 예약 { if(discovered[there]) continue; q.push(there); discovered[there] = true; } } } visited가 아니라 discovered를 사용하는 이유는 방문한 정점만 저장하는 것이 아니라..
[알고리즘] DFS(깊이 우선 탐색) DFS는 길이 있으면 무조건 길 따라 더 들어가보는 노빠꾸 상남자다. 가보지 않는 길을 가는 상남자기 때문에 정점과 연결되어 있는 정점의 방문 여부를 체크한다. void DFS(int here) { visited[here] = true; for(int i=0; i < adjacent[here].size(); i++) //정점과 연결된 정점들 순회 { int there = adjacent[here][i]; if(visited[there]==false) DFS(there); //방문하지 않은 정점에 대하여 재귀 } 이렇게 하면 간선이 연결되지 않은 정점은 아예 탐색이 안될 수 있기 때문에 모든 정점에 대해 DFS를 해줘야 한다. void DFSAll(int here) { visited = vector(6,f..
[알고리즘] 그래프 표현 방법 그래프를 표현하는 것은 정점과 연결된 정점을 표현하는 것이다. 1. 연결된 정점의 숫자만 표시 vector adjacent; adjacent[0] = {1,2}; adjacent[1] = {2}; adajcent[2] = {0,1}; 메모리 낭비가 적다는 장점이 있지만, 해당 정점이 몇번 정점과 연결되어 있는지 찾으려면 오래걸림(std::find..) 2. 연결된 정점은 true, 아니면 false로 표시 vector adjacent(3,vector(3,false)); //기본값 false로 설정 adjacent[0][1] = true; adjacent[0][2] = true; adjacent[1][2] = true; adjacent[2][0] = true; adjacent[2][1] = true; 메모..
[알고리즘] Big-O 표기법 알고리즘의 효율 측정 방법이다. 1. 수행되는 연산의 개수를 대략적으로 판단 int sum = 0; // 1 int sum = 0; for(int i=0;i
[C++] 람다 람다는 함수 객체를 빠르게 만드는 문법이다. 람다는 [](매개변수){함수 본체} 의 형식으로 이루어져있다. 반환타입이 없는데 auto와 같이 자동으로 반환타입을 추론한다. [](매개변수)->반환타입{함수본체}의 형식으로 반환타입을 정할 수도 있다. auto LambObj = [=](Item& item){return Item.id==itemId}; //클로져 위와 같이 람다로 만든 객체를 클로져라고 한다. 그런데 본체 부분에서 itemId는 어디서 불러오는 것일까? 함수 객체에서는 변수를 만들어 저장하지만 람다에서는 다른 곳에 있는 변수를 가져와 저장할 수 있다. 가져오는 방식에 따라 복사면 []괄호안에 =, 참조면 &을 쓴다. 이것을 캡쳐 모드라고 한다. 그래서 위 예제에서 복사를 사용하면 람다 생성 시..
[C++] 오른값 참조(rvalue reference) int a = 3; 에서 a는 왼값(lvalue), 3은 오른값(rvalue)이다. 왼값이란 단일 식을 넘어 계속 지속되는 개체이고 오른값이란 왼값이 아닌 나머지이다. (임시 값, 열거형, 람다, i++ 등) 다음은 참조 방법에 대해 알아보자. void Copy_RValueRef(Player&& player){} 오른값 참조를 사용할 때는 &을 연속해서 두개 붙인다. 그러면 rvalue을 참조할 것이며 rvalue는 우리 마음대로 수정이 가능하고 lvalue처럼 지속되지도 않는다. 그래서 위 코드에서 매개변수로 받은 rvalue player을 nullptr로 설정할 수 있다. 이런 특성 때문에 복사가 아니라 이동이 가능해진다. void operator=(Player&& player) { //깊은 복사 /..
[C++] 사용하지 않는 함수 삭제하기 Modern C++이전에는 암시적으로 실행되는 클래스의 복사 생성자 등을 막기 위해 private을 사용했다. class A { private: operator= (const A& a); //대입 연산자 private으로 막기 friend class B; } class B { public: void CopyA(const A& a) { A a1; a1 = a; } } 위 코드에서 A 클래스의 대입 연산자를 private 선언하고 구현부를 선언하지 않음으로써 막았다. 그래서 오류가 나야 정상이지만 B 클래스를 friend class로 선언하니 오류가 발생하지 않는 문제가 발생한다. public: operator= (const A& a) = delete; delete를 이용하면 컴파일 전에 바로 오류가 발생한..

티스토리툴바