알고리즘 문제408 [leetcode][990] Satisfiability of Equality 문제 : https://leetcode.com/problems/satisfiability-of-equality-equations/ Union-Find로 풀었다.먼저 == 인 경우만 보고 Union-Find로 같아야 하는 알파벳들끼리 그룹으로 묶는다.다음으로 같지 않아야 하는 조건(!=)을 보고 알파벳 두 개의 그룹이 다른지 판단한다. 만약 달라야하는 알파벳 두 개가 서로 같은 그룹이라면 조건이 충돌나므로 false를 반환한다. 소스코드 : https://gist.github.com/fpdjsns/e8e25e4cd52a20322f91556fee3e7994 2019. 2. 11. [CodeJam][2017] Play the Dragon - Round1A ProblemC 문제 : https://code.google.com/codejam/contest/5304486/dashboard#s=p2&a=2 - IMPOSSIBLE내가 한 번에 knight를 죽일 수 없고 (첫 번째 턴에서 끝낼 수 없음)knight에게 2번 이하 맞으면 죽는 경우 (첫 번째 턴에서 지거나, 나는 계속 힐해야 함)-> 단, 2번 맞았을때 죽는 경우(& 첫번째 턴에 나이트 못죽임)는 첫 번째 턴에 버프나 디버프를 건다.버프를 걸었을 때 한 번 공격하면 나이트가 죽는 경우 이길 수 있다.디버프를 걸었을 때 2번 맞아도 안죽는 경우 내가 이길 수 있다. - knight 턴에서는 무조건 나를 때린다. (정해져 있는 조건)디버프를 쓰려면 무조건 초반에 몰아서 써야 이득이다. - 회복 횟수, 나이트 공격력, 디.. 2019. 2. 9. [leetcode][988] Smallest String Starting From Leaf 문제 : https://leetcode.com/problems/smallest-string-starting-from-leaf/ DFS로 완전탐색해서 풀었다. 루트를 기준으로 자식 노드로 탐색하면서 문자열을 만들어간다.현재 노드의 val를 이때까지 만든 문자열 앞에 붙인다.그리고 리프 노드가 되면 이때까지 만든 문자열을 이때까지 구한 정답 문자열과 비교해서 사전순으로 앞서있다면 정답을 갱신한다. 시간복잡도는 모든 노드를 탐색해야 하므로 O(N + 정답문자열 비교 시간 * 리프노드 개수) 이다.완전이진트리라 했을 때 정답문자열 비교 시간 * 리프노드 개수는 트리의 높이는 logN이므로 정답 문자열 비교 시간은 logN이고 리프노드 개수는 N/2이므로 N*logN/2가 된다.좀 더 상세하게 따지면 몇가지 케이.. 2019. 2. 9. [CodeJam][2017] Ratatouille - Round1A ProblemB 문제 : https://code.google.com/codejam/contest/5304486/dashboard#s=p1 그리디로 풀었다.6번 case로 예를 들어보자. 3 370 80 901260 1500 700800 1440 16001700 1620 900cs 입력으로 받은 Q배열을 재료별로 오름차순 정렬한다. 700 1260 1500800 1440 1600900 1620 1700cs 이제 각 재료를 cnt 개 사용해서 만들 수 있는 패키지를 구한다.cnt는 1부터 시작한다.각 재료의 그램 수는 처음 입력에서 본 것과 같이 각각 70, 80, 90 이다. 먼저 각 재료들 하나로 만들 수 있는 패키지(Q)는 없다.하나인 경우 -> [63~77, 72~88, 81~99]. 만들 수 있는 패키지가 있을 때.. 2019. 2. 8. [CodeJam][2017] Alphabet Cake - Round1A ProblemA 문제 : https://code.google.com/codejam/contest/5304486/dashboard#s=p0 A ? ?? ? ?? ? Ccs 위와 같은 배열이 인풋으로 주어졌다고 하자. A A A? ? ?? ? Ccs먼저 행을 왼쪽 부터 탐색하면서 이전에 나온 알파벳으로 채운다. A A A? ? ?C C Ccs이후 행을 오른쪽부터 탐색하면서 이전에 나온 알파벳으로 채운다. A A AA A AC C Ccs그 다음 열도 행과 마찬가지로 위에서 아래로 이전 알파벳으로 채우고 이후 아래에서 위로 탐색하면서 이전 알파벳으로 배열을 채운다. 시간복잡도는 배열의 크기가 된다. 소스코드 : https://gist.github.com/fpdjsns/9bbfe5adaf339558cd0d077ee2c2f248 2019. 2. 7. [Leetcode][981] Time Based Key-Value Store 문제 : https://leetcode.com/problems/time-based-key-value-store/ timestamp를 key, value를 value로 하는 map을 하나만들고 이를 value 값으로 가지고 key값을 key로 가지는 unordered_map(정렬될 필요 없으므로)을 만든다.unordered_map m; // {key, {timestamp, value}}cs즉, 위와 같은 맵을 하나 만든다.set할 때에는 key, timestamp, value를 자료형 타입과 맞게 m에 넣어준다. get 할 때는 먼저 key값과 맞는 {timestamp, value}를 찾는다.만약 하나도 없다면 빈 스트링을 반환한다. 맞는 map이 있다면 해당 맵에서 upper_bound를 이용해 time.. 2019. 1. 31. 이전 1 ··· 58 59 60 61 62 63 64 ··· 68 다음
