J.Althea

  할로윈데이(10/31)를 맞이하여 깃헙에서도 소소한 변화가 있었다. 일명 잔디밭의 색이 바뀐 것이다. 이뻐서 기념샷을 촬영하였다.  :)

https://app.codility.com/programmers/challenges/ 이메일을 읽다가 Silver Challenge라는 문구에 관심이 생겨 참여하게 되었다. 읽어보니, 대략 알고리즘 문제를 풀면 되는 것 같았다. 그래서 '주말이고 시간도 있으니 풀어봐야지' 라고 생각하고 있다가 UTC 기준이라서 대한민국 시간으로 10/18(토) 02:00 인 걸 보고 다음 날에 풀기로 다짐했다. 문제는 1문제였고, 2시간 동안 풀면 되는 것이였는데, 1, 2, 3등의 푼 시간을 보니 쉬운 문제인 것 같았다. 다 풀고 나니 Codility에서 이런 것을 주었다. 정성이 담겨진 디자인이라 기분은 좋았다. 아래는 해당 문제에 대한 정보와 점수, 정확성, 효율성 이다. 다음에도 참여해보면 좋을 것 같다.  :)

  1번 문제 [Level 1] 3진수로 변환할 수 있는지 물어보는 문제였다. 2번 문제 [Level 2] 요구 조건에 따라 재귀 함수를 작성할 수 있는지 물어보는 문제였다. 쿼드트리를 규칙에 따라 압축하여 표현해야 한다. 비슷한 문제 : https://www.acmicpc.net/problem/1992 3번 문제 [Level 4] 트리 구조에서 세 점 사이의 거리의 최댓값 : f(a, b, c) = max(dist(a, b) + dist(b, c) + dist(c, a)) 를  만족하는 각각의 거리 중 중간값 : median(dist(a, b), dist(b, c), dist(c, a)) 을 구하는 문제였다. 일일이 구하면 시간초과가 뜰 것이므로 생각을 달리해야 한다. 트리에서 두 점 사이가 가장 멀 때(이 거리를 '트리의 지름')를 구하는 방법을 응용하여 풀었다. Idea : dfs(임의의 점, 현재까지 거리) dfs(1, 0) -> dfs(e1, 0) -> dfs(e2, 0) -> dfs(e3, 0) 비슷한 문제 : https://www.acmicpc.net/problem/1967 4번 문제 [Level 5] 문자열의 부분 문자 a와 b의 인덱스 차이가 최대가 되도록 골라서 합을 구하는 문제였다. https://programmers.co.kr/learn/courses/30/lessons/68938 시간초과를 해결할 수 있는 방법이 생각나지 않아서, 일단 할 수 있는 한 시간을 줄여보고자 노력했다. DP 개념을 응용했다. 문자열의 길이가 n이라고 하면, 부분 문자열들의 길이는 2~n이므로 먼저 메모이제이션을 이용해서 부분 문자열의 길이가 2일 때의 최댓값들을 구해놓으면, 다음 부분 문자열의 길이가 3일 때는 양 끝만 비교하면 된다. 이 과정을 부분 문자열의 길이가 n이 될 때까지 반복한다. 핵심은 부분 문자열의 모든 인덱스를 중복없이 계산하려고 했다. 이렇게 bottom-up 방식으로 모든 부분 문자열에 대...