맛있는감귤

개요그래프/트리 탐색 알고리즘. 게임에서 많이 사용되는 최단거리 길찾기 알고리즘이다.다익스트라 확장판. BFS의 가지치기 알고리즘이라 생각하면 된다. 핵심 개념 1. 최소가 되는 지점을 우선 탐색 (우선 순위 큐)2. 휴리스틱 추정값 사용3. Open List / Closed List를 이용하여 노드 관리 다른 알고리즘과 차이점BFS (Breadth First Search) : 완전 탐색 알고리즘. 우선순위없이 모든 노드를 탐색한다. 다익스트라 : 일반적인 최단거리 알고리즘. 한 노드를 기준으로 모든 노드의 최단 경로를 찾기 때문에 시간 비용이 많이 든다.플로이드 : 모든 노드의 최단 경로를 찾는 알고리즘. 일반적인 시간 복잡도 O(N^3). 개념 설명1. 휴리스틱 추정값 f(x) = h(x) + g(x..

문제 : https://www.acmicpc.net/problem/2188기초적인 이분 매칭 문제이다.백준 알고리즘의 이분 매칭문제는 앵간하면 다 아래의 프레임을 벗어나지 않고 해결 가능하다.vector v = 소가 가고 싶어하는 축사, A[] = 소, B[] = 축사를 나타낸다.소가 갈 수 있는 축사를 하나 선택하면 그 축사에 또 다른 소가 들어갈 수 있는지 확인하고 또 다른 소가 갈 수 있는 축사를 조사하는 것을 반복해서 만족하는 값이 가장 큰 것이 문제의 해답이 된다.12345678910111213141516171819202122232425262728293031323334353637383940414243#include #include using namespace std; int N,M,ans=0;i..

문제 : https://www.acmicpc.net/problem/2169출처Olympiad > 한국정보올림피아드 > KOI 2002 > 고등부 1번 N, M의 최대가 1000이므로 완전탐색으로는 무리가 있을 수 있다.또한 좌, 우, 아래의 이동을 잘 해결해주어야한다.나는 재귀로 해결쓰. DP[][][0]은 아래 [1]은 우측, [2]는 좌측을 나타낸다.제일 처음 1,1에서 출발하여 N,M까지 갈 수 있는 모든 경로를 간다.그리고 리턴을 하면서 기준 노드의 좌,우,하에서 리턴되는 값들을 비교해서 큰 값만 저장하게 되면 마지막 1,1에 남는 값이 최대값이 된다. 12345678910111213141516171819202122232425262728#include #define INF -9876543210lo..

문제 : https://www.acmicpc.net/problem/1173문제가 요구하는 답은 운동하는 시간을 최소로 해야하기 때문에우선순위는 운동 > 휴식 이 된다.현재 혈압이 최소로 떨어졌을 때 운동이 불가하면 프로그램을 끝낸다.123456789101112131415161718192021#include int main(){ int N,m,M,R,T,X,ans=0; scanf("%d%d%d%d%d",&N,&m,&M,&T,&R); X=m; for(int i=0;i

문제 : https://www.acmicpc.net/problem/1063이동하라는대로 이동시키고 1. 킹 이동2. 킹이 맵을 벗어남?3. 안 벗어나면 돌맹이와 겹침?4. 겹쳐서 돌맹이 이동시키는데 맵 벗어남?5. 벗어나면 킹 원위치반복하면 된다. 알파벳+숫자가 열행이기 때문에 순서 주의 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113#incl..

문제 : https://www.acmicpc.net/problem/1120앞이나 뒤나 추가되는 문자는 내가 정하는 거니 무시해도 된다.문제의 조건은 A의 길이 >a>>b; for(int i=0;i

문제 : https://www.acmicpc.net/problem/15264와 7로 만 이루어진 숫자를 구하면 된다.이런 DP문제도 있는데 경우의 수가 아닌 N이하의 가장 큰 수만 구하면 되기 때문에 완전탐색으로 해결 가능1의 자리수 4, 7에서 부터 하나씩 4와 7을 붙여 나가도록 하자.1 : 4, 72 : 44, 47, 74, 77 3 ....이런 식으로 .123456789101112131415161718192021222324252627282930include #include using namespace std;int main(){ int N,ans=0; queue q; scanf("%d",&N); if(4

문제 : https://www.acmicpc.net/problem/1953BFS를 이런식으로도 활용할 수 있구나 했던 문제한명만 싫어하는 경우는 없기 때문에 A가 B를 싫어한다면 둘이 서로 다른 팀에만 배정하면 된다.블루 화이트 상관없이 아무데나 넣어버리자.flag를 순서대로 이용하여 섞이지 않도록 함.1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include #include #include using namespace std; int N;bool visited[102];vector v[102];queue q;priority_queu..

문제 : https://www.acmicpc.net/problem/3197출처Olympiad > Croatian Highschool Competitions in Informatics > 2005 > National Competition #2 - Seniors 2번 2573 빙산, 3055 탈출 문제의 하드버전문제 해결 순서1. 백조의 만남 가능 여부2. 해빙. 테두리만 녹이기3. 만날 때까지 반복해결 방법은 3055 탈출문제와 유사하지만 R, C 값이 1500이기 때문에 백조 만남 가능 여부 탐색시 TLE가 발생할 수도 있다. (이거 때문에 개고생) 문제 해결 방안제일 처음 백조 이동 후 만날 수 없다면 방문 한 곳은 다시 방문할 필요없다.만날 수 있냐 없냐만 확인하면 가능하기 때문에 백조의 위치를 변경..

문제 : https://www.acmicpc.net/problem/5567출처Olympiad > 일본정보올림피아드 예선 > JOI 2010 예선 3번 상근이 - 친구(1) - 친구의 친구(2) 상근이로부터 깊이가 2인 노드까지만 탐색한다. 12345678910111213141516171819202122232425262728293031323334353637#include #include #include using namespace std;int N,M,ans=0,cnt=0;vector v[502];bool visited[502];queue q; int main(){ scanf("%d%d",&N,&M); while(M--){ int a,b; scanf("%d%d",&a,&b); v[a].push_back(b..