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 방식으로 모든 부분 문자열에 대...

..9/17 18:00 쯤에 카카오톡이 와서 이메일을 확인해봤다. 작년에 보았을 때는 2.5솔 정도 했었는데, 이번에는 4솔로 마무리하게 되었다. (1, 2, 3, 4 풀고, 5번 푸는 도중에 테스트 종료) 내가 느낀 문제별로 필요한 지식 및 아이디어는 다음과 같다. 1번 문제 - 문자열 처리 (+ 정규식) -> 문제에서 시키는 대로 차례대로 조건에 맞게 문자열을 필터링하였다. 2번 문제 - 적절한 자료구조 사용 능력 (완전탐색 / 해시) -> map을 사용하여 해당 값이 들어온 횟수를 세고, 큰 순서대로 담았다.     데이터의 개수가 많지 않기 때문에, 빈틈없이 잘 처리하는게 중요한 것 같았다. 3번 문제 - 적절한 자료구조 사용 능력 + 이분 탐색 응용 (트라이?) -> (1) 다차원 배열(마지막 차원은 동적 배열)을 사용하여 데이터를 담아 정렬한 뒤,     (2) lower_bound를 사용하여 조건에 맞는 데이터들을 가져왔다.     예를 들어서, "java, backend, junior, pizza, 100" 라는 데이터를     h[1][2][1][1].push_back(100); ~ h[0][0][0][0].push_back(100); 까지 저장했고,      "python, frontend, senior, pizza, 200" 라는 데이터는     h[2][1][2][1].push_back(200); ~ h[0][0][0][0].push_back(200); 까지 저장했다.     문제에 조건에 따라, "언어(3종류), 직무(2종류), 경력(2종류), 음식(2종류), 점수" 의      각 항목마다 정해진 개수가 있었는데,      이때, "- and - and - and - and 100" 이라는 형태로 쿼리가 들어올 수 있으므로  ...

decltype은 알고자 하는 변수 식의 타입으로 치환하는 역할을 한다. 예를 들어서 int a = 10; decltype(a) b = 3; b의 타입은 a의 타입인 int로 된다. 이로써, 정확하게 타입 그대로를 전달할 수 있게 된다. 또, 타입의 결과를 알 수 없을 때도 사용한다. template <typename T, typename U> void add(T t, U u, decltype(t + u) *result) {     *result = t + u; } (1) double t, double u => double * result (2) double t, int u => double * result (3) int t, int u => int * result

예를 들어서, while (arrSum[end] - arrSum[start - 1] < s) end++; 라는 코드가 있다고 하자. 반복문 안에서 end를 증가시키기 때문에, 배열의 범위를 벗어나지 않는 선에서 검사해야 한다. 인덱스에 대한 처리를 while 내부에 쓰거나, while의 조건문에 쓰는 방법 등이 있지만 아래처럼 범위를 검사하는 부분을 가장 먼저 쓰면 좋다. while (end < n && arrSum[end] - arrSum[start - 1] < s) end++; 이렇게 하면, if 문의 뒷 부분(arrSum[end] - arrSum[start - 1] < s)을 검사하기 이전에 앞 부분(end < n)을 검사하고 빠져나오게 된다. 왜냐하면, and 조건은 if (true && true) 인접한 두 조건을 모두 만족시켜야 하기 때문에 앞에서 하나라도 거짓인 명제를 만나면, 뒤를 볼 필요없이 빠져나오게 되기 때문이다.

//예외를 반환하지 않는다. int func1(int a, int b, int c) noexcept {     ... } //예외를 반환할 수 있다. int func2(int a, int b, int c) noexcept(false) {     ... } 예외처리에 관해서 한정자 noexcept를 작성하면 얻는 이점은 다음과 같다. (1) 예외 처리 여부를 바로 알 수 있다. (2) Strong exception guarantee (강한 예외 보증)     copy semantics가 아닌 move semantics로 처리한다. (3) Performance improvement (성능 향상)     해당 함수가 예외처리를 무조건적으로 하지 않는다고 가정하므로     예외를 반환할 수 있는 상황에 대한 고려를 하지 않는다. (여분공간X)