알고리즘 문제/CodeJam34 [Kickstart][2019]2. Mural 문제 : https://codingcompetitions.withgoogle.com/kickstart/round/0000000000051060/0000000000058b89 부분합으로 풀었다.벽은 가장자리부터 파괴되고 벽의 총 N개라고 했을 때 최대 (N+1)/2 개의 벽을 칠할 수 있다.즉, 문제를 간단하게 보면 연속되는 (N+1)/2개의 벽을 선택할 때 구할 수 있는 최대 값을 구하는 문제이다.부분합 배열을 sum, (N+1)/2를 cnt라고 했을 때, sum[i] - sum[i-cnt]가 (N+1)/2개의 벽을 선택했을 때의 가치이고. i 범위가 [cnt, N] 일 때 구한 가치 중 최대 값이 정답이 된다.시간 복잡도는 O(N). 소스코드 : https://gist.github.com/fpdjsns.. 2019. 2. 25. [Kickstart][2019]1. Number Guessing 문제 : https://codingcompetitions.withgoogle.com/kickstart/round/0000000000051060/00000000000588f4 이진탐색으로 풀었다.정답이 될 수 있는 범위의 가장 최소, 최대 값을 가지고 그 중간 값이 정답이 될 수 있는지 확인한다.정답이 될 수 있는 경우 종료하고, 중간 값보다 정답이 작다고 한다면 범위는 최소 ~ 중간 값 -1이 되므로 최대 값을 중간 값 -1 로 갱신한다.중간 값보다 정답이 크다고 한다면 범위는 중간 값 + 1 ~ 최대가 되므로 최소 값을 중간 값 + 1 로 갱신한다.이를 정답을 구할 때까지 혹은 N번 반복한다. 소스코드 : https://gist.github.com/fpdjsns/c129fea086f319e7340126.. 2019. 2. 25. [CodeJam][2017][Round 1B] A. Steed 2: Cruise Control 문제 : https://code.google.com/codejam/contest/8294486/dashboard N개의 말 정보를 탐색하면서 도착지까지 가는데 드는 시간 중 최대 시간을 구한다.말이 도착지까지 가는데 드는 시간 = (D - K) / S정답은 D / 구한 최대 시간 이다. 자료형은 double로 해야 조건에 맞는다. 시간복잡도는 O(N). 소스코드 : https://gist.github.com/fpdjsns/bba7e68cc46d3f7e77500d0caecaa74c 2019. 2. 17. [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. [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. 이전 1 2 3 4 5 6 다음
