codility에서는 엣지 케이스를 토대로 스스로 테스트 케이스를 구성해야 한다. 🥲
Codility Lessons를 풀어보자! 🌱
| Lesson | Question | Difficulty | Memo | Check |
|---|---|---|---|---|
| 04 | MaxCounters | Medium |
어떤 연산으로 인해 complexity가 높아질 수 있을지 판단할 수 있어야 한다. | ✅ |
| 04 | MissingInteger | Medium |
complexity를 줄이기 위해 어떻게 해야할지 고민을 더 해야한다. | ✅ |
| 05 | PassingCars | Easy |
Lesson 이름이 주어지지 않았다면 O(N) 아이디어를 떠올리는 데에 시간이 걸렸을 것 같다. |
|
| 05 | CountDiv | Medium |
prefix "sum"에 매몰될 필요가 없다. | |
| 05 | GenomicRangeQuery | Medium |
이중 for 문을 어떻게 줄일 수 있을 것인지를 생각해보자. 이때, prefix sum의 원리를 적용해볼 수 있겠다는 생각을 할 수 있어야 한다. 링크를 참고하여 해결했다. | ✅ |
| 05 | MinAvgTwoSlice | Medium |
알아야만 풀 수 있는 문제이다. 그냥 수학 문제라고 생각하면 된다... O(N^2)을 최대한 최적화하려면 고정 길이로 접근해야한다는 사실에서 출발하자. 링크를 참고했다. |
✅ |
| 06 | MaxProductOfThree | Easy |
모든 케이스를 잘 나눠보자. | ✅ |
| 06 | Triangle | Easy |
Lesson 이름이 주어지지 않았다면 시간이 걸렸을 것 같다. | |
| 06 | NumberOfDiscIntersections | Medium |
링크1, 링크2를 참고했다. 어렵다... | ✅ |
| 07 | Fish | Easy |
upstream 일 때의 동작에 초점을 더 맞추어 생각해야 한다. (stack + while) |
✅ |
| 07 | StoneWall | Easy |
Manhattan Skyline 문제이며, stack을 왜, 어떻게 써야하는지 생각해야 한다. (stack + while) |
✅ |
| 08 | Dominator | Easy |
[]와 같은 edge case를 놓치지 말아야 한다. leader를 구하는 O(N) 알고리즘을 잊지 말자. |
✅ |
| 08 | EquiLeader | Easy |
equileader가 어떤 경우에 존재할 수 있는지 생각해야 한다. 링크도 참고해보자. | ✅ |
| 09 | MaxProfit | Easy |
여기저기서 자주 볼 수 있는 문제이다. Kadane's Algorithm 형태에 익숙해지자. | ✅ |
| 09 | MaxDoubleSliceSum | Medium |
구하고자 하는 값의 최솟값이 무엇일지 잘 생각해보자. 링크1, 링크2, 링크3을 참고했다. | ✅ |
| 10 | CountFactors | Easy |
while i * i < N와 if i * i == N을 나눠야 할 때를 알아야 한다. |
|
| 14 | MinMaxDivision | Medium |
나는 Binary Search에서 "~의 최솟값" 또는 "~의 최댓값"을 구하는 로직이 항상 헷갈린다... 이 부분은 번거롭더라도 더 명확하게 코드에 표현(ex. result 변수에 기록)함으로써 어느정도 해소할 수 있다. 그리고 양쪽 중 하나를 선택하는 로직을 함수로 따로 빼는 것이 디버깅 시에도 편하다. 그나저나 주어진 M은 사용하지 않았는데, M을 사용하는 풀이법도 생각해봐야 할 것 같다. |
✅ |
| 15 | AbsDistinct | Easy |
코드를 간결한 로직으로 짜는 연습이 필요하다. 그리고 중복되는 로직을 어떻게 줄일 수 있을지 고민해야 한다. sol2를 참고하자. |
✅ |
| 15 | CountDistinctSlices | Easy |
링크를 참조해서 다시 풀어보자. (첫 시도는 60% 달성) Caterpillar Method에 익숙해지자. 두 요소 중에 하나의 요소(end)에만 초점을 맞춰보고, 모든 값마다 cnt++하기보다는 구간의 길이를 더해나가면서 개수를 빠르게 세어야 한다. |
✅ |
| 15 | CountTriangles | Easy |
핵심은 정렬과 복잡도 최적화이다! (삼중 루프이지만 O(N^2)으로 끊어야 한다. O(N^3) 코드로는 63% 밖에 못 받는다.) 정렬을 하면 쓸데 없는 연산을 줄일 수 있으며, 이때 모든 단계에서 cnt++하기보다는 전체 단계에서 구간의 길이를 통해 개수를 세는 방법을 염두해둬야 한다. 읽기 자료 PDF 파일의 예제와 거의 동일하니 이해가 안 된다면 다시 참고하자. |
✅ |
| 16 | MaxNonoverlappingSegments | Easy |
백준 회의실 배정 문제와 같은 문제이다. 정렬을 할 수 있는 상황이라면 정렬을 통해 얻을 수 있는 것이 무엇인지 생각하자. | |
| 16 | TieRopes | Easy |
"adjacent ropes"끼리만 묶일 수 있으므로 정렬을 할 수 없다. 이런 경우일수록 단순하게 접근해보자. | ✅ |