노는 게 제일 좋아

어려웠다. 우선순위 큐를 이렇게 이용한다는 것이 나에겐 조금 어려웠다. 시간을 보아하니 절대로 Brute Force, 전수조사는 아니었다. 힌트를 보고나서야 풀 수 있었다. https://www.acmicpc.net/problem/1655 #맞는 풀이 #include #include using namespace std; int N; priority_queue minH; priority_queue maxH; int main(){ cin.tie(0); ios::sync_with_stdio(0); cin >> N; for(int i = 1; i> x; //min에 넣을지 max에 넣을지?? //한쪽에만 몰아넣으면 안된다. //그렇게 하면 중간값을 바로 알 수 없어서 둘의 사이즈를 항상 차이가 1만큼만 나게 해..

운영체제를 배웠다면.. 조금이라도 알 수 있지만 시험이 끝나면 까먹는 우리에게 다시 익힐 시간이 필요하다. 다시 알아보자 ** 데이터 영역에는 전역 변수, static variable들이 저장된다. 숫자나 문자열 값인 리터럴도 저장된다. **리터럴이란 소스 코드의 고정된 값을 말한다. 즉, int i = 1; 에서 1을 말한다. -생존 주기, Life Cycle은 프로그램의 시작부터 끝까지 가지고 있다. text영역은 code segment라고도 불리는데 프로그램 코드가 저장되고 절대 변경되지 않는 구역이다. 우선 스택과 힙이 하는 역할에 대해서 알아보자. 스택에는 함수호출, Function Call에서 메모리 할당이 일어난다. 함수 호출에 쓰이는 지역변수, 매개변수가 저장되고 함수호출에 대한 활성 레코..

그래프에 대해서 많이 배웠는데 이제 진짜로 적용하려면 가중치 그래프라는 것을 배워야한다. 영어로는 위에 제목에 써놨다. 가중치 그래프라는 것은 간선에 비용이나 가중치가 추가된 그래프를 말하는데 이는 정점 사이의 연결상태뿐만 아니라 연결에 필요한 비용까지 함께 표현할 수 있다. 여기서 비용이란 꼭 돈이아니라 무엇이든 될 수 있는거다. 정말 돈이 될 수도, 아니면 간선의 길이가 될 수도 있는 것이다. 이렇게 도로를 표현하는 그래프에서는 도로의 길이를 표현하면 좋겠지?? 뭐 이렇게 지도로도 쓰일 수 있고, 사실 네트워크같은 곳에 많이 쓰인다고 한다. 예를 들어 지도에서 최단거리를 가고싶다..? 그렇다면 목적지까지 경로에서 가중치의 합이 가장 적은 경로가 가장 최단거리가 되겠지?? 우선 그렇다면 가중치 그래프를..

이번에는 힙의 기본연산을 알아볼 시간인데요. 우선 트리를 만들 때 했던 것처럼 노드를 정의해야겠죠? 어차피 배열이니까 데이터를 넣는데 이제 우선순위 큐를 만들려고 하는 것이니까 우선순위도 포함되어있어야 하는데...? 어떻게 할 것인지 코드로 보면서 알아보자 우선 정수의 데이터를 다룬다고 치고 알아보도록 하자 저기 전처리기 #define은 우선순위를 정하는 것이다. 저거 없으면 그냥 트리랑 다를바가 없다. 다른 식으로도 우선순위 큐 만들기도 하던데,, 저부분은 더 공부해야할 부분인건 확실하다. ★★★★★ 까먹지 마라고 별도 붙혀놓음 아무튼 저렇게 하도록 하고,,? 배열로 만들거니까 배열선언은 쉬우니까 넘어가고? 기본연산중 하나인 삽입연산으로 ㄱㄱㄱ 우선 알고리즘부터 알아보자면 삽입은 힙의 가장 마지막 부분..

오늘은 우선순위 큐 구현방법 중에서 가장 효율적이라는 힙에 대해서 공부하도록 합시다 힙은 영어로 heap인데 뜻이 쌓다, 더미 이런 뜻을 가지고 있고, 완전이진트리를 기반으로 합니다. 완전이진트리에 대해 복습하자면 얘는 마지막 레벨 빼고는 모두 포화인 트리라고 말했죠?? 아무튼 힙에는 2가지 종류가 있는데 최대힙이랑 최소힙이 있지 max heap, min heap 영어로 이렇게 쓴다고 하더라 ??? 최대, 최소하니까 뭔가 크기를 가지고 있나보구나 생각이 들지? 아 그럼 그 크기가 우선순위가 되어야 힙으로 우선순위 큐를 구현할 것 같다... 라는 생각이 들면 굿 Max Heap이란 ○부모 노드의 키값이 자식 노드의 키값보다 크거나 같은 완전 이진 트리 key(부모노드) ≥key(자식노드) Min Heap이..