프밍노트

달려라 홍준아!!!https://www.acmicpc.net/problem/1306 풀이방식더보기투포인터,슬라이딩 윈도우 방식으로 풀수있다.왼쪽 i-M 부터 오른쪽 i+M 을 탐색하며 큰수가 들어오면 그수의 크기와 위치 를 기억해두고위치가 i-M 시야에서 나가면 윈도우(i-M 부터 i+M 까지) 를 재탐색후 크기가 큰것을 찾아준다. 만약 다음 위치로 이동시 크기가 큰게 들어오면 다시 변경 현재 가장큰 light를 answer로 추가 #include#include using namespace std;void RuningHong() { int N, M, d, after, befor, StrongLight = 0, StrongNumber = 0; cin >> N >> M; vector way(N);..

https://www.acmicpc.net/problem/3197         위 이미지처럼 X = 얼음.   = 호수L  =  백조 하루마다 호수에 맞닿아 있는 얼음이 녹는다.백조는 며칠뒤에 서로 만날 수 있을지 구하는 문제이다.       여기 주소에서 데이터를 받아볼수있다.https://hsin.hr/2005/            문제 풀이에 사용한 알고리즘은 BFS , UnionFind  두개다  문제는 아래 두가지 라고 생각했다.1.얼음을 녹일 방법2.백조가 만날수 있는지 확인할수 있는 방법   해결방식    1.얼음의 외각을 녹일때 다음 녹을 얼음을 지정해 큐에 넣어준다.2.얼음마다 지역을 설정해둔뒤 다른지역과 합쳐질때 서로 합쳐준다.       코드 더보기 #include#include u..

해당문제는 그래프  최소 스패닝 트리로 풀 수 있는 문제다. 최소 스패닝트리는 프림과 크루스칼 알고리즘 으로 플수있다. 해당문제는  프림으로 풀었다 프림이 기본적인 알고리즘은 더 쉽다.   간단하게 말하자면  다익스트라가 누적과 다음노드로 가는 가격을 본다면 프림의 경우는 현재 갈 수 있는 간선들 중 가장 값싼 간선을 우선적으로 본다는 것이다,. 다시 문제로 돌아와 "켜져 있는"위치로만 가야 하기에 다익스트라는 다시 왔을 때 가격을 비교해야 하기에 어울리지 않을 수 있다.  코드르 보면서 설명해 보자 #include#include #include#include#include using namespace std;unordered_map>> Spninmap;unordered_map maps;//unorder..

종이 자르기 문제 위처럼 종이가 주어지면 흰색 부분과 파란 부분을 분리하여 자르되정사각형이 되도록  자르는게 목적이다. 해당 문제는 한칸씩 확인하며 정사각형을 측정한다면틀렸을때 최적이 될 정사각형을 찾아야 하기에 중복 되는 탐색이 매우 많을 것 같은 느낌이다. 이문제는 모든 사각형을 정사각형으로 자른다가 핵심이라고 생각한다. 가장 큰 종이에서 나올 수 있는 최대 정 사각형은 4개 그 안에서도 4개로 오히려 쪼개면서 계산하는 것이다. 사실 문제에서 내용을 이미지로 간단하게 설명해준다. 위 이미지 순서대로 큰거 자르고 문제 있는 부분만 자르면서 들어가는식으로 풀면된다 #include #include using namespace std;vector> arrya;int color[2] = {0,0};//재귀함수..

토마토마토마토 https://www.acmicpc.net/problem/7576          익지 않은 토마토는 근처 토마토를 익게 하는 문제  혼자 익는경우가 없을때모든 토마토가 익을때까지 최소일수 를 구하는 문제 간단하게 BFS 를 써서 푸는 문제다  골드 5인만큼 그냥 시뮬레이션 돌리면 풀린다.      #include#include#include#include using namespace std;#define XYZ tuplevector nonfire;const XYZ MoverDirection[4] = { {1,0} ,{-1,0} ,{0,-1} ,{0,1} };vector> vec;int N = 0, H = 0;///토마토 익는칸 확인 함수vector findNextTomato(vector ..

https://www.acmicpc.net/problem/15806   통학이 너무나도 하기 싫었던 영우는 결국 학교의 기숙사에 들어갔다. 통학의 고통에서 해방된 기쁨도 잠시, 학교 기숙사에서는 일정 기간마다 청소 검사를 한다는 사실을 알게 되었다. 청소 검사에서 나쁜 점수를 받으면 벌점을 받게 되고, 벌점이 많이 쌓이면 기숙사에서 퇴사 해야 한다. 영우는 어떤 경우에 벌점을 받는지 궁금하여 기숙사에서 진행하는 청소 검사 시스템에 대해 자세히 조사해 보았다. 기숙사 청소 검사 시스템은 오늘로부터 정확히 t 일이 지나고 검사를 하며, 검사 시간 단축을 위해 방의 특정 부분만 검사한다. 하지만 검사하는 특정 부분 중 한 곳이라도 더럽다면 영우는 벌점을 받게 된다. 영우가 사는 방은 N * N 정사각형 방이며..

내가 이해한 위상정렬을 간단하게 정리해 보겠다. 위상정렬은 순환하지 않는 비순환 방향 그래프 에서만 가능하다. https://ko.wikipedia.org/wiki/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC 위상정렬 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예 ko.wikipedia.org 위상정렬의 구현방법은 정말 간단한 순서로 알수있다. 1. 자신을 가리키는 간선이 없는 노드 들을 큐에 넣어준다. 2. 큐에 있는 노드를 받아준다. 3. 노드가 가리키는 간선을 지워준다. ..

처음 풀어보는 백준의 플래티넘 문제. 내가 풀었던 방식 부터 적을 생각이다. 우선 문제는 이름 그대로 최단 경로가 아닌 거의 최단 경로를 찾는다. 그래프에서 최단경로들의 간선을 제외한 그다음에 나오는 최단경로를 찾는 문제 우선 생각했던 방법은 다익스트라로 간선들을 지우면서 나간뒤 다익스트라를 한번더 돌릴예정이였다. 그렇게 테스트 하였지만 결과는 8% 실패 실패 이유는 다익스트라로 간선을 지울경우 간선이 하나만 지워지는 문제가 생긴다. 위 의경우 최단경로는 두개로 1 2 4 5 와 1 3 4 5가 있다. 거의 최단경로는 저두개를 제외한 1 ->5인 이여야 하지만 경로를 먼저 지워주게 될경우 4->5가 공유되지않으면서 거의최단경로는 6이 나오게된다. 정상적인경우 위처럼 최단경로들을 제외하여 4->5로가는 길..