알고리즘 문제/CodeJam34 [Codejam][2020][QR] 4. ESAb ATAd 문제 : https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/0000000000209a9e B 개의 비트 배열이 있다. 사용자는 1과 B 사이의 비트 위치를 질문하고 해당 위치의 비트를 응답받는다. 이 기계는 1, 11, 21 ... 등 일의 자리가 1인 쿼리 횟수 번째에는 양자 변동을 일으킨다. 즉, 1, 11, 21 .. 번째 질문에는 응답하기 전 양자 변동이 일어난 후 변동의 결과를 기준으로 응답한다. 양자 변동은 1/4의 확률로 아래 4가지 중 하나가 발생한다. 1. 모든 0은 1로, 1은 0으로 변환. 2. 배열의 위치가 반전된다. ex) 1번째 비트는 마지막 비트와 교체. 2번째 비트는 마지막에서 2번째 비트와 교체.. 2020. 4. 19. [Codejam][2020][QR] 3. Parenting Partnering Returns 문제 : https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/000000000020bdf9 각 활동의 시작, 종료 시간이 주어지면 Jamie, Cameron이 활동을 나눠서 한다고 하자. 활동 중 다른 활동을 중복으로 수행은 불가능하다. (한 번에 하나의 활동만 가능) 두 사람이 모든 활동을 나눠가질 수 없을 때는 IMPOSSIBLE을 출력하자. 가능하다면 각 활동을 수행하는 사람의 이니셜 배열을 구하자. greedy의 대표 문제. 각 활동들의 시작 시간을 기준으로 오름차순 정렬한다. 정렬하면 활동들의 순서가 뒤섞이므로 배열에 인덱스를 추가하고 정렬한다. Jamie, Cameron 를 순서대로 활동 중인지 체크한다. 이를 위해.. 2020. 4. 18. [Codejam][2020][QR] 2. Nesting Depth 문제 : https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/0000000000209a9f 숫자 문자열이 주어질 때, 이를 엄격하게 괄호로 묶어서 반환하라. 이 때, 괄호의 개수는 최소로 하고 숫자는 일의 자리로 판단하라 (ex. 10 은 1과 0으로 인식되지 10으로 인식되진 않는다.) 엄격하게 괄호로 묶는 방법은 숫자만큼 해당 문자를 괄호로 감싸면 된다. example) 0000 -> 0000 101 -> (1)0(1) 111000 -> (111)000 1 -> (1) 1324 -> (1((3)2((4)))) 문자열을 탐색하면서 이전 숫자와 현재 탐색중인 숫자의 차이를 구한다. 1. 이전 숫자가 현재 숫자보자 작다면, (열.. 2020. 4. 18. [Codejam][2020][QR] 1. Vestigium 문제 : https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/000000000020993c Vestigium은 라틴어로 trace를 의미한다. 정사각형 행렬(let, arr)의 trace는 arr[i][i](왼쪽 위에서 오른쪽 아래까지의 요소들) 의 합이다. 정사각형 행렬이 주어질 때, trace의 값과 중복되는 요소가 있는 행, 열의 수를 각각 구해라. 예를 들어, 2 1 3 1 3 2 1 2 3 행렬이 주어지면 trace 값은 2 + 3 + 3 = 8. 중복되는 요소가 있는 행의 수는 0. 중복되는 요소가 있는 열의 수는 1열, 3열이 있으므로 2를 출력한다. trace값은 i = [0, N)을 탐색하면서 arr[i][i].. 2020. 4. 18. [Kickstart][2019][Round A] 1. Training 문제 : https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050e01/00000000000698d6 N명의 학생이 있고 이 중 P명의 학생을 선택하려고 한다. 각 학생들은 등급이 있는데 선택하는 학생들의 등급은 모두 같아야한다. 학생에게 1:1 코칭 1시간을 해주면 등급이 1증가한다. 최소의 시간으로 학생들의 등급을 높여 P명의 학생을 선택할 때, 코칭하는데 드는 시간의 최소값은 얼마인가. P명의 학생을 선택할 때, 이를 팀으로 이루기 위해 코칭하는데 드는 최소 시간은 얼마일까. P명의 학생들 중 가장 높은 등급을 학생들이 모두 가지게 된다면 팀을 이룰 수 있게된다. 즉, (가장 높은 등급 * P) - P명의 등급의 합이 코칭하는데.. 2020. 3. 27. [Kickstart][2020][Round A] 4. Bundling 문제 : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d3ff3 Pip는 N개의 문자열을 가지고 있다. 문자열들은 모두 대문자로만 이루어진다. Pip는 이 문자열들을 그룹화 시키려고 한다. 이 때, 각 그룹은 정확히 K개의 문자열들로 이루어진다. 각 그룹의 점수는 그룹에 속한 문자열들의 공통 prefix 길이다. 만들 수 있는 그룹들의 점수의 합의 최대값은 얼마인가. 문자열 배열, 공통된 Prefix.. 트라이를 써야될 것 같은 느낌이 든다. 일단 N개의 문자열들로 Trie를 만든다. 그룹들의 최대값을 만드려면 어떻게 해야하는지 먼저 고민해보자. 최대값을 만드려면 prefix가 커야한다. 즉, 트.. 2020. 3. 26. 이전 1 2 3 4 5 6 다음