노는 게 제일 좋아

다익스트라의 개념이 조금 더 나아간 것이다. 최단거리로 갱신했을 때는 해당 경로가 정해진다는 것을 기록하면 되는 문제다. https://www.acmicpc.net/problem/11779 #맞는 풀이 #include #include #include #include #include #include #define MAX 1002 #define INF 987654321 using namespace std; int st, ed; int N, M; int dist[MAX]; vector adj[MAX]; int path[MAX]; void dijkstra() { dist[st] = 0; priority_queue heap; heap.push({ dist[st], st }); while (!heap.empty()..

다익스트라 알고리즘 또 까먹었다. 오늘은 3문제 정도 풀어봐야겠다. https://www.acmicpc.net/problem/1916 #맞는 풀이 #include #include #include #include #include #define MAX 1001 // 1000개 정도면 인접행렬 만들만하다. #define INF 987654321 //적당히 큰 숫자여야한다. using namespace std; int N; //도시 수 int M; //버스 수 int st, ed; //시작노드, 목표노드 vector adj[MAX]; //벡터를 넣는 배열 {거리, 노드} int dist[MAX]; //최소거리 테이블 void dijkstra(){ dist[st] = 0; //전역으로 시작노드를 받음. prior..

우선 이 알고리즘을 쓰기 위해서는 몇가지 조건이 필요하다. 1. 각 간선에 대한 가중치가 음수여선 안된다. -> 양수여야만 한다. 2. 단일 시작점에 대한 최단 경로이다. -> 해당 시작점에 대해서만 최단경로고 다른 vertex는 다시 돌려야 한다. 3. 프림의 MST 알고리즘과 유사한 형태다. -> 프림 알고리즘은 경계로부터의 최소 거리를 정점의 거리 값으로 설정 -> 다익스트라에서는 시작 정점으로부터 각 정점까지의 전체거리 사용 -> 다익스트라에서는 목적 정점만 파악하면 종료 아무튼 조금 다르다. 우선 기본적으로 해야 할 것들을 알아보자 1. 모든 정점에 대해서 거리 값을 무한대로 초기화한다 -> 계산하지 않았음을 의미한다. 2. 시작정점 자기자신과의 거리는 0이므로 0으로 설정한다. 3. 모든 거리..

CPU 스케줄링에서도 엄청 많이 나오는데.. 우리는 동적으로 사람이 들어오진 않으니까 starving에 대한 걱정은 말고 풀어보자. 저런 알고리즘을 적용하는 이유는 평균 대기시간을 줄이기 위해서다. 앞사람이 길수록 뒷사람이 오래기다리는 것과 같은 이치다. ??? 무슨상관이냐고..? 대기는 각각 한다. 즉, 기다리는 사람의 수만큼 한다. 일이 끝난 사람은 대기를 하지 않는다. 그렇다면...? 일을 빨리 끝내서 기다리는 사람을 줄여야 한다. 그것을 위한 알고리즘이 바로 Shortest job first algorithm 이다. 구현해보자 사실 구현할 것은.. 실제로 대기시간이 줄어들었느냐? 확인만하면 된다. 즉, 대기시간만 알아내면 끝이다...ㅎㅎ 당연히 입력으로는 작업시간이 주어져야 한다. #include..

퀵정렬도 분할 정복을 이용한 정렬로 병합정렬에서 조금 더 조건이 추가된 정렬이라고 보면 된다. 또한 병합정렬이 대량의 데이터를 대상으로 한다면 퀵정렬은 빠른 시간을 위한 정렬이다. 그렇다면 무엇이 다르냐? 피벗이 있다는 것이다. 주어진 배열을 부분 배열로 나누고 각 부분 배열을 정렬하여 합치는 것과 같다. ??? 엥 그럼 피벗은 어디다 쓰는거야??? 피벗은 주어진 부분 배열을 나누는데 쓰이고 부분 배열을 정리하는데 쓰인다. 구현해보자 #include #include //분할하는 작업 template auto partition(typename std::vector::iterator begin, typename std::vector::iterator end) { //3개의 반복자를 사용한다. //1. 피벗,..

병합 정렬이란 잘 알려진 정렬 알고리즘 중 하나다. 분할 정복이라는 간단한 아이디어이다. 많은 원소를 가지고 있더라도 작은 크기로 쪼개서 각각을 정렬한 다음 정렬된 부분집합을 정렬상태를 유지하면서 합치는 방식이다. 코드로 구현해보자 #include #include //벡터를 임의의 원소가 들어가도 괜찮게 템플릿 선언후 //벡터 2개의 참조변수를 이용한다. template std::vector merge(std::vector &arr1, std::vector& arr2) { std::vector merged; auto iter1 = arr1.begin(); auto iter2 = arr2.begin(); //차례대로 원소를 비교해나간다. -> 2개의 벡터를 받아서 가장 첫번째 원소부터 비교한다. //결국 ..

사실 그래프의 연결 상태를 표현할 때 우리는 배열로 많이 하곤 한다. 하지만 행렬을 이용했을 때 가장 큰 문제점은 노드의 개수의 제곱에 비례하는 메모리를 사용하기 때문이다. 노드의 개수 범위가 만약 100000이라면 십만의 제곱은... 우선 0이 10개다. 10억이다. int로 저장했다면 10억 * 4byte = 40억 byte 다. 그러면.. 약 3기가 바이트.. 그래서 우리는 굳이 연결되지 않은 부분까지 저장하기는 그래서 인접리스트로 저장하기로 했다. 그렇게 되면 실제로 연결된 부분만 저장할 수 있다. 즉, vector을 원소로 하는 vector 또는 array를 만들어 해당 인덱스랑 연결된 노드들의 정보를 넣는 것이다. 실제로 이는 문제풀이할 때 노드의 수로 초과하는 것을 막아주기 때문에 유용하다고..

BST를 구현해보고 기본적인 함수들을 구현해보자 BST는 이진 탐색 트리로 루트노드보다 작은 값은 항상 왼쪽에 큰 값은 항상 오른쪽에 존재하는 트리다. #include //노드에 대한 정의 이진 트리이기 때문에 자식은 2개가 최대임 struct node { int data; node* left; node* right; } struct bst { node* root = nullptr; //초기 값은 널 node* find(int value) { return find_implement(root, value); } private: node* find_implement(node* current, int value) { //현재노드가 NULL이라면 if(!current) { std::cout data == val..

배열에서 중요한 것은 배열의 크기와 해당 배열의 접근 방법이다. 때문에 생성자에서 배열의 크기와 해당 배열을 가리키는 포인터를 항상 알고 있어야 한다. 이를 염두한 채 구현해보자 #include #include //필요한 헤더파일 포함시키고 //동적 배열 클래스를 만들어보자 (임의의 타입을 위해 템플릿 선언) template class dynamic_array { T* data; // 해당 배열을 가리키는 포인터 (동적할당 받음) size_t n; // 배열 사이즈 public: //배열의 크기를 인수로 받는 생성자. dynamic_array(int n) { this->n = n; // 이 함수를 call한 객체의 n을 설정 data = new T[n]; // 해당 n만큼 배열 동적할당받음 } //복사 ..

어렵다기 보다.. 엄두를 못냈다. 사실 DP란 것을 알았으면.. N번째부터 생각해봤을텐데.. 그게 안된다. https://www.acmicpc.net/problem/9465 #맞은 풀이 #include #include #include using namespace std; int sticker[2][100002]; int dp[2][100002]; // DP int tc; int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> tc; //테스트케이스 여러개 while(tc--){ //해당 테스트케이스에 대한 입력 int length; cin >> length; //DP 초기화 for(int i = 0; i