목록2016/10 (43)
:: ADVANCE ::
BAEKJOON ONLINE JUDGE 1475 방 번호 https://www.acmicpc.net/problem/1475 1234567891011121314151617181920212223242526272829#include int num[10]; int main(){ int number; int cnt; int i; scanf("%d", &number); while (number) { num[number % 10]++; number /= 10; } cnt = (num[9] + num[6] + 1) / 2; for (i = 0; i cnt) cnt = num[i]; } } printf("%d\n", cnt); return 0;}Colored by Color Scriptercs
BAEKJOON ONLINE JUDGE 3055 탈출 https://www.acmicpc.net/problem/3055 동시 이동 시 비버가 이동한 곳에 물이 잠기므로 비버는 물이 이동할 곳으로 갈 수 없다.따라서 물이 먼저 이동한 후에 비버가 이동해야 한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115#include #inclu..
[MST] 크루스칼 알고리즘 Kruskal Algorithm최소 스패닝 트리 구하는 알고리즘 중 하나다른 알고리즘으로는 Prim (프림) 알고리즘이 있다 최소 스패닝 트리는사이클을 형성하지 않고 가장 적은 가중치로 이루어진 트리이다 크루스칼은 간선을 기준으로 트리를 형성해 나가는 알고리즘이다.자세한 설명은 [참고] 이 곳이 설명이 자세하고 그림이 있어 이해하기 좋다 크루스칼은 dfs 또는 Union-find을 이용하여 구현할 수 있다 코드를 간단하게 하고 싶어서 Union-find을 이용하여 구현해 보았다. 간선을 오름차순으로 정렬하여야 하는데 입력받을 때 priority_queue에 넣어서 따로 정렬을 해주지 않았다.만약 C로 구현할 필요가 있다면 구조체를 선언하고, 정렬알고리즘을 따로 구현하기만 하면..
bit 중 1의 개수를 세어 저장해두는 함수 12345678void countbit(int n){ int bc[1
BAEKJOON ONLINE JUDGE 2412 암벽 등반 https://www.acmicpc.net/problem/2412 이진탐색 문제집에서 본 문제지만bfs로도 풀리는 문제탐색 시간을 줄이기 위해 x, y를 오름차순 정렬자신의 x와 왼쪽으로 2보다 작은 지점들만 검사, +2 보다 작은 지점들만 검사하여 시간을 줄임-> y도 x에 따라서 정렬을 한 후에 이진탐색으로 위치를 찾아서 거기까지만 탐색하게 하면 시간을 더 줄일 수 있을 듯 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include #include #include #i..
BAEKJOON ONLINE JUDGE 1613 역사 https://www.acmicpc.net/problem/1613 1. dfs모든 -1 중에서 새롭게 만들 수 있는 -1을 모두 탐색 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include using namespace std; struct Number { int num, idx;}; int n;Number num[100001]; bool cmp(const Number &first, const Number &second){ return first.num
BAEKJOON ONLINE JUDGE 7469 K번째 숫자 https://www.acmicpc.net/problem/7469 O(n*m) 이하로 풀어야 하는 문제처음에 quick select로 문제를 풀려 하였으나O(m*n + a)라서 시간초과 O(n*m) -> 입력을 index와 값을 같이 저장한 후 값을 기준으로 정렬 정렬한 값을 다 돌면서 index가 주어진 범위안에 있는 수 중 k 번째를 찾아서 출력 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include using namespace std; struct Number { int num, idx;}; int n;Number ..
BAEKJOON ONLINE JUDGE 2842 집배원 한상덕 https://www.acmicpc.net/problem/2842 처음 접하는 이진탐색... 이라고 해야하나일단 처음 풀이는 이진 탐색 문제집에서 열어본 문제기 때문에 이진탐색이라는 점을 염두해 두고 풀이를 접근해 보았다. 또한 이전에 풀었던 '배열에서 이동' 문제가 생각나서 이와 비슷한 문제라고 생각을 하였다.but, '배열에서 이동'처럼 문제를 접근하기에는 고도 값이 매우 크기 때문에 time limit이 날 수 밖에 없다. 1. 다익스트라 일단 이진탐색으로 고도의 최소값을 정해놓고, 그 중 P에서 K로 가는 경로의 최대값을 파악했다.될 수 있는 최소 고도의 최대값을 이진탐색으로 찾고, 0부터 최소 고도의 최대값까지 다익스트라를 돌리면서 ..
BAEKJOON ONLINE JUDGE 2792 보석 상자 https://www.acmicpc.net/problem/2792 보석을 받지 못하는 학생도 있다 -> 보석은 꼭 배분해야 한다. 라고 해석최대값을 지정해 놓고 그 이하의 개수로 분배를 할 때 받는 학생의 수를 세서분배를 위해 필요한 학생의 수가 존재하는 학생의 수보다 많으면 -> 보석을 전부 분배할 수 없다 -> 최대값을 늘린다.분배를 위해 필요한 학생의 수가 존재하는 학생의 수보다 작으면 -> 보석을 전부 분배할 수 있다 -> 최대값을 줄일 수 있다.=> 이분탐색 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include int n..
BAEKJOON ONLINE JUDGE 3649 로봇 프로젝트 https://www.acmicpc.net/problem/3649 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include #include using namespace std; int len;int n;int lego[1000001]; int bsearch(int num){ int s = 0, e = n - 1; int m; while (s