목록Algorithm (187)
:: ADVANCE ::
BAEKJOON ONLINE JUDGE 1012 유기농 배추 https://www.acmicpc.net/problem/1012 labeling 문제15분 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include int width, height;int map[51][51];int label[51][51]; void init(){ int i, j; for (i = 0; i
BAEKJOON ONLINE JUDGE 한국정보올림피아드 시.도 지역본선 2013 7577 탐사 https://www.acmicpc.net/problem/7577 모르겠다. 이건 다시 해석해야 할 숙제 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include int l, n;int state[41][41]; int main(){ int i, j, k; int s, e, cnt; scanf("%d %d", &l, &n); // 플로이드 초기화 for (i = 0; i
BAEKJOON ONLINE JUDGE 1939 중량제한 https://www.acmicpc.net/problem/1939 입력되는 제한 중량 최대값 사이정답찾아가는 이분 탐색 + bfs 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879#include #include #include using namespace std; int n, m;int start, dest;vector graph[100001];int visit[100001];queue que; void init() { for (in..
BAEKJOON ONLINE JUDGE 1981 배열에서 이동 https://www.acmicpc.net/problem/1981 아 어렵다... 다이나믹도 해보고 dfs도 해보고 dfs 완탐은 time limit 나고. 뭐 time limit 날거라는 거는 예상했지만... 결국 해답 소스 보고함ㅠ 1. 이진 탐색으로 최대-최소 차이를 찾아나간다. 이진 탐색의 지표는 이진 탐색으로 정한 최대-최소 차이 내로 (1, 1)에서 (n, n)으로 갈 수 있느냐 (1, 1) -> (n, n) 갈 수 있느냐는 bfs로 탐색 2. bfs 최대-최소를 살펴보면서 가려면 지나온 경로들의 최대, 최소를 가지고 있어야 한다 but, 이렇게 접근하다가 다이나믹도, 완탐도 틀렸다ㅠ.ㅜ => map을 가장 작은 값에서 가장 작은 ..
BAEKJOON ONLINE JUDGE 한국정보올림피아드 2000 2636 치즈 https://www.acmicpc.net/problem/2636 공기와의 접촉면 -> 한 시간 후 녹아 없어짐 -> 공기로 됨구멍 -> 공기처럼 치즈를 녹이진 않음. but 공기와 만나면 공기가 됨 1. input 받고, 구멍과 공기를 구분 -> labeling2_1. 공기와 닿은 면적 공기로 만들기 -> 반복문2_2. 공기와 구멍이 만나면 구멍도 공기로 만들기 -> dfs 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475..
BAEKJOON ONLINE JUDGE 한국정보올림피아드 시.도 지역본선 2012 2512 예산 https://www.acmicpc.net/problem/2512 정답 찾아가는 이진 탐색 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include int n;int cost[10000];int limit;int sum[10001];int max; void solve(){ int s = 0, e = max, m; int cal, num; int i; while (s limit) e = m - 1; else s = m + 1; } printf("%d\n", e);} int main(){ int i; sca..
BAEKJOON ONLINE JUDGE 1162 도로포장 https://www.acmicpc.net/problem/1162 다익스트라 + DP평소 다익스트라는 그냥 그래프의 개수만큼 정점을 탐색하는데,이 visit 정점 배열을 DP 배열로 놓고, DP[도시 개수][포장 가능 도로의 수]로 놓고 풀면 된다.다익스트라 구현 시 반복문 안에는 다른 도시로 영역을 넓힐 때 포장가능 할 때 포장하는 경우와 포장을 하지 않는 경우 둘 다 queue에 넣어주어 구현하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727..
BAEKJOON ONLINE JUDGE 1365 꼬인 전깃줄 https://www.acmicpc.net/problem/1365 LIS 문제최장 증가 부분 수열의 개수만큼이 잘 연결된 것이고, 나머지를 잘라주면 최소가 된다.잘은 모르겠지만 직접 예제를 만들어보고 알게됨.. 12345678910111213141516171819202122232425262728293031323334353637383940414243#include int n;int size = 1;int lisArr[100000]; void lis(int num){ int s = 0, e = size, middle; if (lisArr[size - 1]
dovelet LIS http://183.106.15.130/30stair/LIS/LIS.php?pname=LIS C - 이진탐색 구현 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include int n;int num[500000];int parent[500000];int lisArr[500000];int size; void lis(int idx){ int s, e, middle; if (num[lisArr[size - 1]]
Algospot Longest Increasing Sequence https://algospot.com/judge/problem/read/LIS 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include int n;int lisarr[500], input[500];int size; void init(){ int i; for (i = 0; i