노는 게 제일 좋아

이것은 그냥 생각했을 때.. 단순한 문제지만 시간을 단축하려면 조금 더 머리가 필요한 문제였다. 중요한 문제라고 생각한다. 우선순위 큐라면 이 문제가 가장 대표적이라고 생각한다. 나는 시간초과나서 실패했다. 그리고 다시 답을 찾게되었다. https://www.acmicpc.net/problem/1826 #시간 초과 풀이 #include using namespace std; //해당 위치의 값이 0이 아니면 주유소의 위치이며 값은 기름의 양임 int stations[1000001]; //이렇게 하면.. 시간 초과남, 답은 나올지 모르겠으나 풀이는 아님 int N; int ans = 123456789; int l,p; //도착위치, 초기 기름양 void func(int pos, int cnt, int fue..

이 친구는 메모리제한이 빡세다. 그래서.. 새로운 방법을 생각해내야 했다. N이 1500번이라 1500*1500은 충분한데.. 공간이 부족하다..? https://www.acmicpc.net/problem/2075 힙 사이즈를 N으로 고정시켜서 1500 * 1500의 계산을 함에도 메모리가 부족하지 않게 했다. 이 생각을 한 번에 생각할 수는 없었고.. 그냥.. N번째 큰수라함은.. 가장 큰 수 5개 중 가장 작은 값이라 생각할 수도 있고 그냥 모든 수 중에서 5개라고 생각할 수도 있다. 위에 생각이 문제 푸는데 더 도움이 되었다. #맞은 풀이 #include using namespace std; priority_queue pq; //최소힙 int main(){ ios::sync_with_stdio(fa..

두개의 큐를 쓰면 되지 않을까??? 생각이었지만 예외처리가 꽤나 까다로웠다. https://www.acmicpc.net/problem/7662 여러가지 방법이 있겠지만 나는 쉬운 방법으로 풀었다. MultiSet 자체가 무엇을 위해 만들어졌냐고 하면..? Set이라는 것이 집합이라 중복을 허용하지 않지만.. 이 친구는 key의 중복을 허용해서 유용하게 이 문제에 쓰였다. 중복이 허용되는 Set이라고 보면 된다. 자동정렬 + key,value 형태라고 보면 된다. #맞는 풀이 #include using namespace std; int tc; int main(){ cin>>tc; while(tc--){ int k; cin >> k; //1. ordered된 multi_set으로 중복도 포함된 set을 만들..

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

우선 Queue라는 또 다른 자료구조 형태가 있다. 참 많지,, 자료구조형태가?? 자료마다 용도가 다르니 다르게 저장하고 다르게 꺼낼 수 밖에 ㅠㅠㅠ 근데 큐면 큐지 무슨 우선순위 큐가 있는거지...? 라고 생각할 수 있지 뭐랄까.. 비행기 탈때도 VIP들은 다른 입구로 들어가잖아?? 그런 것과 같이 조금 차등을 둔다고하는거지 그니까 뭐 순위를 줘가지고 우선순위가 가장 높은 사람을 먼저 태우는 것처럼 자료도 우선순위가 높은 것을 출력한다 뭐 이런 비슷한 느낌을 가지면 될거야. 우선순위 큐가 이용되는 분야는 시뮬레이션, 네트워크 트래픽 제어, OS의 작업 스케쥴링 이런 곳? 아무튼 우선순위 큐는 스택으로도, 큐로도 구현할 수 있는데 그보다 제일 효율적인 구조는 heap이라는 구조인데 나중에 더 자세히 살펴..