이숭간 공부기록

https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_double_slice_sum/ MaxDoubleSliceSum coding task - Learn to Code - Codility Find the maximal sum of any double slice. app.codility.com 문제풀이 : 어려웠던 문제다. 다른풀이를 참고해서 풀었다. 핵심은 Y를 기준으로 왼쪽의합과 오른쪽의 합을 구해서 이것의 최대를 구하는것이다. N이 십만이므로 O(N)시간에 풀어야한다. 여기서 왼쪽합의 시작은 인덱스 0부터 하고, 오른쪽합의 시작은 인덱스 n-1 즉 맨 양쪽끝으로 잡는데 이렇게하면 배열길이가 8이라고할때 (0,4,7)보다 (2..

https://app.codility.com/programmers/lessons/8-leader/dominator/ Dominator coding task - Learn to Code - Codility Find an index of an array such that its value occurs at more than half of indices in the array. app.codility.com 문제번역 : 리스트의 길이의 절반이상을 차지하는 원소가 있다면, 그 원소가 등장하는 아무 인덱스를 리턴하는것 문제풀이 : 리스트의 절반이상을 차지하는 원소가 있다면, 즉 dominator가 존재한다면 정렬했을때 무조건 중심에 위치하게 될것임 다만, 중심에 있는 원소가 dominator의 후보가 되는것이지 ..

https://app.codility.com/programmers/lessons/4-counting_elements/max_counters/ MaxCounters coding task - Learn to Code - Codility Calculate the values of counters after applying all alternating operations: increase counter by 1; set value of all counters to current maximum. app.codility.com 문제풀이 : 이문제는 시간초과가 빡세다 구현은 엄청 쉬운데 그냥 일반적이게 구현하면 시간초과가 나는데 해결하기위한 아이디어는 max counter가 마지막으로 일어나는 시점을 통해 해결해야한..

https://app.codility.com/programmers/lessons/4-counting_elements/frog_river_one/ FrogRiverOne coding task - Learn to Code - Codility Find the earliest time when a frog can jump to the other side of a river. app.codility.com 문제번역 : 개구리가 한편에서 반대로 건너가기위해서는 나뭇잎을 밟아가야함 🐸 나뭇잎이 1초에 하나씩 떨어지는데 전체가(경로전체) 나뭇잎으로 덮이는 가장 빠른 시점을 리턴하는것 문제풀이 : 방문처리 배열을 두고 방문처리가 모두 되는 첫 시점 (cnt활용)을 리턴하도록한다. # X를 순회하면서 해당위치에 나뭇잎이 ..

https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/ TapeEquilibrium coding task - Learn to Code - Codility Minimize the value |(A[0] + ... + A[P-1]) - (A[P] + ... + A[N-1])|. app.codility.com 문제번역 : N개의 정수로 구성된 비어 있지 않은 배열 A가 제공됩니다. 어레이 A는 테이프의 숫자를 나타냅니다. 0 < P < N과 같은 정수 P는 이 테이프를 비어 있지 않은 두 부분으로 나눕니다. A[0], A[1], ..., A[P − 1] 및 A[P], A[ P + 1], ..., A[N − 1]. 두 부분..