알고리즘 썸네일형 리스트형 15661번 15661번 - 링크와 스타트 '스타트와 링크' 문제랑 흡사하게 만든 다른 문제이다. 기존문제랑 다르게 이 문제는 팀을 절반으로 나누지않아도 된다. 그냥 1명이상 팀이 유 지되면 된다는 조건이 있기 때문에 약간 다르다. 나는 그냥 완전탐색을 통해, 1번팀으로 뽑는다/ 뽑지 않는다 이런방식으로 완전탐색을 진행하였다. 왜냐하면 N제한이 20이기 때문에 시간복 잡도가 O(2^20) 으로 충분히 실행이 가능하다고 생각했기 때문이다. 하지만 이런 방식은 중복되는 값들을 다시 한번 계산하게 되므로 좀 더 시간 복잡도를 줄여서 풀 수 있을 것 같다. ( 빨리 푸신 분들은 DP로 접근한 듯 하다) 중복된다는 것은 i번 사람을 1번 팀으로 뽑고, 전부다 2번 팀으로 뽑는 경우와 i번 사람을 2번 팀으로 뽑고, 나머지를 .. 더보기 4991번 4991번 - 로봇 청소기 문제에서 쓰레기의 값이 10개 이하이고, 맵에서 vertex 의 최대 갯수가 400개가 된다는 것을 파악하였다. 따라서 플로이드 워셜 알고리즘은 시간 복잡도가 O(N^3) 이고 , 400^3 은 6천만정도 되기 때문에 가능하다고 생각하고 문제를 풀었다. 하지만 이 문제는 독특하게도 테스트케 이스가 while문을 통해서 한꺼번에 여러개가 실행되므로 최대 6천만을 여러번 돌리다보면 시간초과가 발생하게 된다. 따라서 이제는 각 쓰레 기마다 BFS를 이용해서 로봇,쓰레기들의 최소거리의 모든 쌍을 구해야 했다. 따라서 dirt 라는 벡터에 로봇의 위치와 쓰레기들의 위치를 모두 저장해주었다. 그 다음 for문을 이용해서 모든 쓰레기들에서 BFS를 돌리고, 다른 쓰레기들과의 거리를 D라는 .. 더보기 15662번 15662번 - 톱니바퀴(2) 톱니바퀴 1과 똑같은 문제, 예전에 풀었던 문제 다시 풀어보는 느낌으로 풀어보았다. 비교해보니 마지막 정답을 구하는 부분과, N의 크기가 달라졌다. 재귀에서 일단 현재 톱니바퀴를 회전시킨다. (단, 회전시키기 전의 3시와 9시 값을 미리 저장한다.) 그 다음으로는 진행 방향의 톱니의 특정 위치의 값과 비교한다. 이때 합이 1이면 S극 과 N극으로 구성된 것이므로 회전시킨다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include#.. 더보기 15486번 15486번 - 퇴사(2) 기존의 퇴사 문제와 같다. 하지만 N제한이 커졌기 때문에 기존 문제처럼 완전탐색으로 해결할 수 없다. (시간복잡도가 최대 N^2 이 되기 때문에) 그리고 int 형 변수를 사용할지 long long 을 사용할지 확인해보면 P의 최대값이 1000이고, N의 1500000 이므로, 최대값은 15억으로 int 형 변수로 충분히 해결할 수 있다. 최종적으로 DP를 이용해서 문제를 해결할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940#include#includeusing namespace std;#define MAX 1500001int N;int P[MAX];int T[MAX];int D[MAX.. 더보기 15658번 15658번 - 연산자 끼워넣기(2) 기존에 있던 연산자 끼워넣기 문제와 똑같다. 다만 최대값과 최소값을 모두 구해야 한다는 차이점이 있다. N의 범위가 최대 11이기 때문에, 시간복잡도는 최대 4^11 로 완전탐색으로 충분히 구현할 수 있게 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#includeusing namespace std;int N;int num[12];int op[4];int MAX = -2000000000;int MIN = 2000000000;void go(int k,int sum){ if (k == N) { if (sum > MAX) MAX = s.. 더보기 4534. 트리 흑백 색칠 4534. 트리 흑백 색칠 모든 경우를 탐색하는 것은 시간이 너무 오래 걸린다, 하지만 생각해보면 트리 순회처럼 재귀적으로 문제를 해결 할 수 있어 보였다. 그리고 최적 부분 구조라는 판단이 섰기 때문에, DP를 이용하여 문제를 풀어나갔다. 점화식은 'D[node][color] 로 node 에서 color 를 가질 때, 가질 수 있는 최대의 색칠 방법의 수' 라고 정의하였다. 이러한 점화식에 입각해서 생각해본다면, D[node][흰색] = D[next][검은색] + D[next][흰색] D[node][검은색]=D[next][흰색] 이 된다. ###문제를 겪으면서 빠졌던 문제점### 처음에 계속 문제에서 빠뜨렸던 부분은, 한 노드에서 자식 노드가 2개 이상일 때에는, 자식 노드들의 최대 색칠 방법의 수를 .. 더보기 4583. 세븐 카드 섞기 게임 4583. 세븐 카드 섞기 게임 문제 자체가 쉬워보였지만, K값이 10^12 이기 때문에 시간을 단축하는게 아주 중요한 문제라고 생각했다. 그래서 어떤 규칙이 있을까 생각해보다가, 단순하게 따로 수학적인 규칙이나 증명이 있을 수 없을 것 같다고 생각을 했다. 그렇다면 문제의 조건에서 풀기 위해서는 반드시 맨 처음의 값이 카드를 섞으면서 다시 중복해서 나와야한다고 생각했다. 그래야지 그때를 기준으로 K값을 나머지 연산으로 줄여 풀 수 있기 때문이었다. 그래서 while 문을 통해서 맨 첫번째 0123456 이 아닌, 그 다음 0123456 이 존재하는지 여부를 확인하고 그 때의 값을 m2에 저장하였다. 그리고 while 문을 빠져나오면 K를 m2 로 나눈 나머지 값으로 변경시켜준다. 그리고 위의 while.. 더보기 5432. 쇠막대기 자르기 5432. 쇠막대기 자르기 이 문제는 스택을 이용하여 문제를 풀 수 있었다. 주어진 문자를 하나씩 순서대로 스택에 담아가면서, ) 이게 나오면 스택에서 팝을 시켜준다. 이때 스택에 남아있는 원소들의 갯수가 잘려진 쇠 막대기들의 갯수가 된다. 하지만 고려해야할 예외사항이 있다. ( ) 나왔을 경우와 ) ) 나왔을 경우는 다른 케이스이기 때문이다. ( ) 나온 경우에는 위의 방식대로 지금까지 모든 막대가 레이저에 의해서 잘리는 경우이므로 스택의 사이즈만큼 정답에 더해준다. ) ) 나온 경우에는 레이저에 의해 잘리는게 아닌, 막대기의 길이가 끝나서 생기는 것이므로 길이가 끝나는 막대 1개를 정답에 더해준다. 123456789101112131415161718192021222324252627282930313233.. 더보기 이전 1 2 3 4 5 ··· 46 다음