Codility (3) 썸네일형 리스트형 Codility CountConformingBitmasks 2진수로 표현된 A와 B, C를 준수(Comforms)할 수 있는 2진수들의 개수를 찾는 문제입니다. 여기서 준수(Comforms)할 수 있는 2진수라는 뜻은 A라는 2진수의 0에 해당하는 자리가 0 또는 1이 될 수 있는 모든 수 입니다. 말이 어려운데, 예를 하나 들어보겠습니다. 1101 라는 수가 주어졌을 때, 1101 1111 이렇게 2개가 될 수 있습니다. 2번째 자리에 있는 유일한 0의 자리에 0 또는 1이 되는 2진수가 준수(Comforms)할 수 있는 2진수가 되는 것이죠. 즉, 준수(Comforms)할 수 있는 2진수의 개수는 원본이 되는 수의 0의 개수에 따라 0 또는 1이라는 두가지 선택지가 있기 때문에 준수(Comforms)할 수 있는 2진수의 개수 = (0의 개수)² 가 됩니다. .. Codility FloodDepth 바위들 중, 가장 깊은 웅덩이의 깊이를 알아내는 문제입니다. 이 문제의 알고리즘은 바위의 가장 높은 곳을 가르키는 peak와 새로운 peak가 나오기 전까지의 가장 낮은 바위의 row값을 알아내어 그 차를 구해 가장 큰값을 구하는 알고리즘 입니다. 1. 웅덩이가 발생하는 곳을 알아내는 것(내리막이 발생하는 지점), 만약 웅덩이가 발생한다면 현재까지의 웅덩이 중 가장 낮은지 row와 비교한다. 2. 오르막이 발생한다면, 웅덩이가 발생하는 곳 이전에 있던 바위들 중의 가장 높은 바위의 길이(peak)와 오르막이 발생한 지점의 바위높이 중 낮은 바위의 높이에서 지금까지 가장낮은 바위높이인 row값을 빼줍니다. depth = min(peak, rock[index+1]) - row 3. 이때, 새로운 peak가 .. Codility RectangleBuilderGreaterArea 이 문제는 N이 100,000개 까지 나올 수 있으므로 N^2 이상의 알고리즘으로 풀면 안됩니다. 다행히 펜스의 너비가 같더라도 가로와 세로길이가 다르면, 다른 종류의 펜스로 인정하니 만들수 있는 장대의 길이를 오름차순으로 정렬하여 어떤 index부터 X의 너비이상을 만족하는지 찾으면 N*log(N) 시간에 펜스의 종류를 확인할 수 있습니다. 1. 같은 길이의 장대가 2개 이상인 장대를 list에 할당한다. 2. 장대를 하나 정하고(A) 그 장대로 X너비 이상의 펜스를 만들 수 있는 최소길이의 장대(B)를 찾는다. (이분탐색) 3. 전체 장대길이 - 최소길이의 장대(B) index한 만큼 만들 수 있는 펜스의 종류이므로 이 값을 누적시킨다. 4. A 장대가 4개 이상이면, A장대만으로 펜스를 만들 수 있.. 이전 1 다음
