기억을 위한 기록들

그래프 내의 모든 간선들의 가중치 정보를 사전에 파악하고 이 정보를 토대로 최소 신장 트리를 구축해나가는 것이 특징입니다. 작동 순서 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 <..

UPROPERTY는 멤버 변수 앞에 기술 되며, UPROPERTY내에 프로퍼티 지정자를 나열함으로, 해당 프로퍼티가 엔진과 에디터의 다양한 부분과 상호작용 할 수 있습니다. 빌드 시 UHD(Unreal Header Tool)이 해당 매크로를 감지하고 리플렉션 유형에 추가함. 이렇게 언리얼 리플렉션 시슽메에 추가된 UPROPERTY는 가비지 콜렉션(GC)에 의해 생명주기가 관리되며, 리플렉션을 통해 이 멤버 변수의 이름, 유형 등을 런타임 중에 확인할 수 있게 됩니다. 반대로, UPROPERTY()매크로가 있지 않는 멤버 변수는 언리얼 리플렉션에 노출되지 않으며, 리플렉션 시스템이 제공하는 GC, 런타임 정보 확인등을 사용할수 없게 된다. 언리얼 리플렉션에 관하여 www.unrealengine.com/ko..

www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net #include #include using namespace std; int target1; int target2; int cnt; vector info[100]; bool checkArr[100]; bool bIsSuc = false; int resultCnt = 9999; void D(int _n) { if (_n == target2) { bIsSuc = true; if (cnt < resul..

www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net #include #include using namespace std; int n; vector info[100001]; bool checkArr[100001]; int result[100001]; void D(int _n) { for (int i = 0; i < static_cast(info[_n].size()); i++) { int target = info[_n][i]; if (checkArr[target] == false) { checkArr[target] = true;..

www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net #include #include #include #include using namespace std; int main() { int n; int dp[46][2]; cin >> n; memset(dp, 0, sizeof(dp)); dp[0][0] = 0; dp[0][1] = 0; dp[1][0] = 0; dp[1][1] = 1; dp[2][0] = 1; dp[2][1] = 1; dp[3][0] = 1; dp[3][..

www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net #include #include #include using namespace std; int main() { int n; long long dp[91][2] = { {0, 0} //0 ,{0, 1} //1 ,{1, 0} //2 }; cin >> n; for (int i = 3; i

www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net #include #include #include using namespace std; int main() { long long n; cin >> n; long long dp[91]; dp[0] = 0; dp[1] = 1; dp[2] = 1; dp[3] = 2; for (int i = 4; i

acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net #include #include #include using namespace std; int main() { int n = 0; cin >> n; vector info[500]; int dp[500][500]; int input; for (int i = 0; i > input; info[i].push_back(input); } } dp[0][0] = info[0][0]; int result = dp[..

1. malloc은 라이브러리 제공함수로 함수 콜을 요청한다. new는 C++언어에서 제공하는 기본 키워드로, 별도의 라이브러리 추가 없이 바로 사용가능 2. malloc은 사이즈를 매개변수로 받고, 리턴타입이 void* 형 이므로 캐스트 연산자의 도움을 받아야한다. new는 할당할 타입을 지정하면, 알아서 할당할 타입의 포인터로 넘어온다. 그래서 할당할 타입의 포인터 변수로 받아오면 된다. 3. malloc은 메모리를 동적으로 할당하는 것만이 목적이라 초기값 지정 불가능. new는 할당과 동시에 초기화 가능 4. new키워드는 생성자를 자동으로 호출. 생성자는 객체를 자동으로 초기화 해주는 함수로, malloc과 new의 가장 큰 차이점이다. * new가 좋아보이긴하지만 malloc의 경우 reallo..