알고리즘을 위한 간략 정리 (30) 썸네일형 리스트형 [C++] 우선순위 큐(PRIORITY_QUEUE) & 페어(PAIR) 사용법 개요우선순위 큐는 컨테이너 안의 자료들을 내림차순 혹은 오름차순으로 정렬해주는 자료형이다. 그런데 pair와 같이 자료가 두 개 이상이 되면 어떻게 될까?? 간략하게 알아보도록 하자. 1. 기본 사용법(내림차순)첫 번째 인자를 기준으로 내림차순으로 정렬된다.첫 번째 인자가 같다면 두 번째 인자를 기준으로 내림차순 정렬된다.#include #include #include using namespace std;int main(void) { ios_base::sync_with_stdio(false); cin.tie(nullptr); priority_queue> pq; pq.push({1, 1}); pq.push({1, 2}); pq.push({2, 3}); pq.push.. [C++] memset 함수(메모리 초기화) 함수 이해C언어와 C++에서 쓰이는 memset 함수는 메모리의 내용(값)을 원하는 크기만큼 특정 값으로 세팅할 수 있는 함수 입니다. 주로 0으로 배열의 값들을 초기화할 때 자주 사용하는 함수입니다. 함수 원형void* memset(void* ptr, int value, size_t num); 1. 반환값: 정상적인 값이 들어온다면 첫 번째 인자로 들어온 ptr 포인터를 반환하지만,실패한다면 NULL을 반환합니다. 2. 첫 번째 인자(void* ptr): 바꾸고자 하는 메모리의 시작 주소가 들어가는 자리입니다.즉, 그 주소를 가리키고 있는 포인터가 위치하는 자리입니다. 흔히 사용하는 방법으로 배열을 초기화한다면 배열의 이름(배열의 시작 주소)이 들어갑니다.Ex)int Rank[500];memse.. [C++] 매개변수 탐색 매개변수 탐색? - 이분 탐색(Binary search)와 상당히 유사한 알고리즘 - Nimrod Megido에 의해 발명되었으며, 최적화 문제를 "결정 문제"로 풀 수 있는 알고리즘 - 시간 복잡도(Time complexity): O(log N) 최적화 문제: 어떠한 함수값을 최적화 시키는 변수를 찾는 문제 결정 문제: 예-아니오의 형태로 답안이 나오는 문제 알고리즘 동작 방식 1. 특정 변수 값(mid)을 토대로 조건을 만족하는지 안하는지 탐색한다. ※ 이때, 구현은 이분 탐색으로 구현한다. 2. 이 탐색 과정에서 우리는 두 가지를 알 수 있다. - 조건을 만족하는 가? -> 결정문제 - 나머지 범위가 조건을 만족하는 가? -> 이분 탐색 3. 조건을 만족하는 범위를 계속 좁혀가며(start와 end.. [C++] 소수 판정(에라토스테네스의 체) 숫자들 중 소수인 것들을 어떻게 구분할 수 있을까? 0. 충분히 큰 수를 최댓값으로 설정한다. 1. int형 배열을 하나 만든 뒤, 각 값들을 각 인덱스로 초기화한다. 2. 소수인 2부터 시작해서 배수들을 모두 0으로 초기화한다. ※이때, 소수들은 초기화해선 안되므로 bool형 변수를 활용한다. 3. 배열에 0이 아닌 숫자들이 들어있는 숫자들은 모두 소수이다! #include #define MAX 1000000 using namespace std; int num[MAX]; int main(){ for(int i = 2; i [C++] int를 string으로 변환하는 방법 std::to_string()으로 int를 string으로 변환 std::to_string()은 C++ 11에서 추가된 함수입니다. 인자로 전달된 int형 변수를 string 변수로 변환시켜줍니다. #include #include using namespace std; int main(){ int num = 12345; string s = to_string(num); cout [C++] 벨만-포드 알고리즘 핵심 요약 한 정점에서 다른 모든 정점으로 가는데 걸리는 최소비용을 구하는데 사용하는 알고리즘 음의 가중치가 있을 때 사용 → 음의 사이클을 찾음 동작 원리 모든 간선들을 탐색하면서, 간선이 잇는 출발정점이 '한번이라도 계산 된 정점' 이라면 해당 간선이 잇는 정점의 거리를 비교해서 업데이트 한다. ⇒ 방향성이 있기 때문! 1번 과정을 반복한다. (N-1번) 음의 사이클을 찾는 방법 N-1번 반복 후, 1번 더 반복한다. → "정상적인 그래프라면, 즉, 음의 사이클이 발생하지 않는 그래프라면, N - 1번을 탐색한 이후에, 또 한번의 탐색을 더 하더라도 절대로! 최소비용이 변하는 정점이 발생하지 않는다" [C++] 다익스트라(Dijkstra) 핵심 요약 최단 경로 탐색 알고리즘. 방문한 노드들과 연결된 간선 중 최소 비용인 간선을 선택하는 알고리즘. 단, 가중치가 양수일때만 적용할 수 있다. 동작 원리 '비용' 이라는 말을 많이 사용하게 될 텐데, 이 값은 1차원 배열 Dist[] 라는 배열에 저장되어 있다고 생각하자. 초기 Dist배열의 모든 값은 무한대(INF)로 초기화 되어 있다. 시작 노드와 직접적으로 연결된 모든 정점들의 거리를 비교해서 업데이트 시켜주고, 시작 노드를 방문한 노드로 체크한다. 방문한 정점들과 연결되어 있는 정점들 중, 비용이 가장 적게 드는 정점을 선택하고, 해당 정점을 방문한 정점으로 체크해준다. 2번 과정에 의해서 갱신될 수 있는 정점들의 거리를 갱신시켜준다. 3 ~ 4번 과정을 반복한다. 구현 1. 비용을 저장.. [C++] 수학 함수 제곱(pow) 함수 원형 double pow(double base, double n) // base가 되는 숫자의 n 제곱 새로운 수학 함수를 사용할 때마다 차근차근 정리할 예정입니다. 이전 1 2 3 4 다음
