야생가오리

https://www.acmicpc.net/problem/1043 거짓말쟁이가 되기시러각 파티의 참여자를 서로 연결하고, 타고타고 올라갔을때 진실을 아는 사람을 만나는지 안 만나는지를 확인해야 한다. 연결하고 찾는데는 유니온파인드를 사용한다.보자마자 이거다 하고 생각이 안 났다.. 사실 지금도 잘은 모르겠다 첨엔 걍 단순히 진실을 아는 사람이 파티에 섞여있는가를 따지는 문제인가 싶었는데, 같은 사람이 다른 파티에 참여해 다른 사실을 듣는 것 역시 안 된다는 조건 때문에 유니온파인드를 사용해줘야 했다. 우선 유니온파인드 구현은 언제나와 같다.vectorparent;int findParent(int node) { if (parent[node]  입력으로 진실을 아는 사람들이 주어진다. 이 사람들을 kn..

https://www.acmicpc.net/problem/1260 클래스 3 승급 필수문제가 하나 남았길래... 근데 이걸 안 풀었길래... ㅋㅋ3 에센셜에 그래프 탐색문제가 참 많은듯?? DFS는 이제 잘 쓴다void dfs(int idx, vector&ans_dfs){ visited_dfs[idx] = true; ans_dfs.push_back(idx); for(int i=1;i BFS큐!! 를 쓴다는 것을 꼭 기억할 것시작정점을 큐에 넣고, 그걸 빼면서 그 자식이 되는 정점들을 반복문으로 큐에 넣고... 반복void bfs(vector&ans_bfs){ queue q; q.push(v); visited_bfs[v] = true; while(!q.empty()){..

https://www.acmicpc.net/problem/10026 그래프에서 구역을 찾는 문제 = DFS. 이제 바로바로 튀어나온다적록색약인 사람과 아닌 사람의 차이는 R과 G를 똑같이 처리하냐 아니냐밖에 없으므로, 그냥 보드를 따로따로 만들고 함수도 (귀찮아서) 따로따로 만들어 각자 실행해줬다.visited 배열도 두 개 만들어도 될 테지만 이건 그냥 memset(visited, 0, sizeof(visited)) 로 초기화해서 재사용 반복문으로 상하좌우를 탐색.순환호출의 조건은 다음 좌표가 보드 안에 있을 것, 그리고 같은 색깔 즉 같은 char값을 가질 것이다. (visited가 방문되지 않았음은 당연하고)void dfs(int x, int y){ char color = board[x][y]..

https://www.acmicpc.net/problem/7662 시간제한 6초여서 어떻게 문제 시간제한이 6초? 했는데 6번의 시도 6번의 시간초과로 얕본 업보를 받음문제자체는 단순하다... 수를 입력받고 명령에 따라 최댓값이나 최솟값을 삭제하기. 1트로는 그냥 깡 배열에 저장하고 최대냐 최소냐 입력받는 것에 따라 매번 sort를 통해 재정렬 후 삭제했다. 당연하지만 시간초과다. 쓰면서도 안 될 것 같았다그럼 제목에도 나와있듯 우선순위 큐를 쓰긴 써야 할 것 같은데, top이 최소냐 최대냐는 최소히프냐 최대히프냐에 따라 달라지므로 우선순위 큐 두 개가 필요하다.두개를 만들어서 저장해서 쓴다고는 치자. 문제는 두 큐를 동기화시키는 것이다. 최솟값 빼래서 최소히프에서 뺐는데 최대히프에서는 안 빼면 나중에 ..

https://www.acmicpc.net/problem/11399 최소 시간(전체)이 되도록 순서를 정하라는데전체 기다리는 시간이 줄어들려면 그냥 빨리끝나는 사람부터 뽑으면 된다.매 상황마다 가장 빨리 끝날 수 있는 사람을 뽑아나가면 그게 곧 최소시간이 된다.= 그리디를 써라#include #include #include using namespace std;int main(){ int n; cin >> n; vector arr(n); for(int i=0;i> arr[i]; } sort(arr.begin(), arr.end()); int answer = 0; for(int i=0;i

https://www.acmicpc.net/problem/11279 최소힙 문제에서 우선순위 조건만 바꾸면 됨..날먹솔브드 클래스 필수문제에 둘다 있는걸 어케~#include #include #include using namespace std;priority_queue, less> pq;int solution(int x){ int answer; if(x==0){ if(pq.empty()) answer = 0; else { answer = pq.top(); pq.pop(); } } else { pq.push(x); } return answer;}int main(){ ios_..

https://www.acmicpc.net/problem/1927 걍 우선순위 큐 쓰는 문제...이왜 실2?씨쁠쁠은 짱이다 #include #include #include using namespace std;priority_queue, greater> pq;int solution(int x){ int answer; if(x==0){ if(pq.empty()) answer = 0; else { answer = pq.top(); pq.pop(); } } else { pq.push(x); } return answer;}int main(){ ios_base::sync_with_s..

https://www.acmicpc.net/problem/1541 +와 -로만 이루어진 식에서 순서를 적절히 하여 최솟값을 찾으라는 문제값이 작아지려면 빼기를 많이 해주면 될 것이다.. 식 자체의 순서를 섞을 수는 없으므로, 마이너스가 등장했다면 그다음 마이너스가 나오기 전까지 모든 값을 더해준 뒤 빼주면, 가장 큰 값을 빼주는 것이 되므로 곧 최솟값이 될 것이다.마이너스가 나왔는지 여부를 체크하며 적절히 구현해주면 해결된다. 전체 코드#include #include using namespace std;int solution(string str){ int answer=0; string tmp = ""; //피연산자 임시로 저장할 스트링 bool flag = false; //마이너스가 등장..

https://www.acmicpc.net/problem/1931 그리디매 단계에서 최적의 방법을 선택하는 알고리즘. 탐욕법이라고도 한다항상 최적해를 찾을 수는 없다. 사용 조건은-시간/공간적 제약으로 최적해를 구하지 못해 근사해를 구해야 하는 문제-그리디를 사용해도 항상 최적해를 구할 수 있는 문제여야 한다.두번째 경우로는1) 탐욕 선택 속성: 탐욕적으로 선택하더라도 문제의 최적해가 보장될 때2) 최적 부분 구조: 부분문제의 최적해가 전체 문제의 최적해로 확장될 수 있을 때가 있다. 이 문제는 그리디를 사용할 수 있는 문제다.가장 빨리 끝나는 회의를 선택하면 다른 회의에 사용할 수 있는 시간이 많아지고,매번 가장 빨리 끝나는 회의를 선택한다면 남은 회의 시간에 대해 똑같이 가장 빨리 끝나는 회의를 선택..

https://www.acmicpc.net/problem/1074 일정한 규칙에 따라 정사각형의 칸을 방문한다.사각형 크기에 관계없이 언제나 Z 형태로 순서가 정해진다.좌표계의 2 - 1 - 3 - 4사분면 순서로 방문한다고도 볼 수 있다. (근데 구현할 때는 헷갈리니까 걍 1 2 3 4 순서라고 했다)결국 주어진 점이 각 2^n-1 사각형들로 나누어진 보드에서 몇사분면에 속해있느냐를 구하는 문제이다.단 한번만 구하는 게 아니라 가장 작은 사각형이 될때까지 찾아야 하므로 n부터 역순으로 반복문을 돌아주면 될 것이다. 몇번 사분면인지 구하는 함수그냥 정의 그대로 만들었다.typedef pair ci;int square(int n, int y, int x) { //주어진 좌표가 몇번 사분면에 있는지 i..