Devcommon

Codility

https://codility.com/programmers/lessons/

Iterations

프로그램 내에서 반복되는 부분. 보통 for나 while.

For

1
2
3
4
5
6
7
8
for some_variable in range_of_values:
    loop_body
for i in range(0, 100) :
    print i
for i in range(100) :
    print i

While

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
while some_condition:
    loop_body
result = 0
while n > 0:
    n = n // 10
    result += 1
a = 0
b = 1
while a <= n:
    print a
    c = a + b
    a = b
    b = c

Collection을 사용한 반복

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
days = ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday', 'Sunday']
for day in days:
    print day
days = set(['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday', 'Sunday'])
for day in days:
    print day
// set을 사용할 경우 출력 순서가 set에서 지정한 순서대로 나오지는 않는다.
'''
    Monday
    Tuesday
    Friday
    Wednesday
    Thursday
    Sunday
    Saturday
'''
// key-value 구조로 사용할 수도 있다.
days = {'mon': 'Monday', 'tue': 'Tuesday', 'wed': 'Wednesday', 'thu': 'Thursday', 'fri': 'Friday', 'sat': 'Saturday', 'sun': 'Sunday'}
for day in days:
    print day, 'stand for', days[day]
'''
wed stands for Wednesday
sun stands for Sunday
fri stands for Friday
tue stands for Turesday
mon stands for Monday
thu stands for Thursday
sat stands for Saturday
'''

문제

BinaryGap

python
1차: 45점 (이 때는 잘 몰라서 링크 안 남겨둠)
2차: 100점 - https://codility.com/demo/results/training8TW2WC-EH5/

Arrays

하나의 공간에 여러 아이템을 저장할 수 있는 자료구조.

Creation

1
2
3
shopping = ['bread', 'butter', 'cheese']
shopping = []         # empty list
shopping = [0] * 365  # value가 0인 365개의 array

Accesing and Modifying

1
2
3
4
5
shopping[1]
temperatures[42] = 25
shopping += ['eggs'] # 이런 식으로 array에 추가 가능.

Iterating

1
2
3
4
5
6
7
def negative(temperatures):
    N = len(temperatures)
    days = 0
    for i in xrange(N):
        if temperatures[i] < 0:
            days += 1
    return days

위의 코드를 아래처럼 간단히 할 수 있다.

1
2
3
4
5
6
def negative(temperatures):
    days = 0
    for t in temperatures:
        if t < 0:
            days += 1
    return days

Basic array operations

1
2
3
4
5
6
7
len([1, 2, 3]) == 3
['Hello'] * 3 == ['Hello', 'Hello', 'Hello']
[1, 2, 3] + [4, 5, 6] == [1, 2, 3, 4, 5, 6]
'butter' in ['bread', 'butter', 'cheese'] == True

연습하기

1
2
3
4
5
6
7
8
def reverse(A):
    N = len(A)
    for i in xrange(N // 2):
        k = N - i - 1
        A[i], A[k] = A[k], A[i]
    return A
A.reverse() # python native

문제

CyclicRotation

python
1차: 37점 (이 때는 잘 몰라서 링크 안 남겨둠)
2차: 100점 - https://codility.com/demo/results/training35CKZE-B4V/

OddOccurrencesInArray

python: 100점 - https://codility.com/demo/results/trainingR3ZUNQ-JXX/

Time Complexity

BIG O Complexity에 따로 정리.

### TapeEquilibrium

python: 100점 - https://codility.com/demo/results/trainingWJH42B-PFB/

### FrogJmp

python: 100점 - https://codility.com/demo/results/training8A2TYQ-AAP/

### PermMissingElem

python: 100점 - https://codility.com/demo/results/trainingZDKEVT-JMK/

# Counting Elements

O(n + m) 복잡도의 counting 알고리즘.

배열 A에 들어있는 각 integer값이 몇 번이나 나오는지 count 배열에 카운팅한다.

A = [1, 2, 3, 1, 3, 5] 라면, count = [0, 2, 1, 2, 0, 1] 이 된다.

1
2
3
4
5
6
def counting(A, m):
    n = len(A)
    count = [0] * (m + 1)
    for k in xrange(n):
        count[A[k]] += 1
    return count

다음과 같은 문제가 있다.

A, B 두 개의 배열과 integer m이 주어지고, 각 원소 n은 0 <= n <= m 의 크기를 갖는다.

배열 A, B 에서 각각 하나의 원소를 swap하여 배열 A, B 각각의 합이 같은지 확인하고 아니면 다른 원소를 swap해보는 동작을 구현한다고 하자.

가장 간단한 방법은 모든 쌍을 swap하여 계속 비교하는 것이다. 이 경우 O(n^3)의 복잡도를 갖는다.

이보다 조금 나은 방법으로 처음에 전체의 합을 구한 뒤 swap 시 전체 합이 어떻게 변할지에 대해 체크하는 방법(아래 코드, O(n^2))이 있다. (실제로 swap이 발생하진 않는다.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def slow_solution(A, B, m):
    n = len(A)
    sum_a = sum(A)
    sum_b = sum(B)
    for i in xrange(n):
        for j in xrange(n):
            change = B[j] - A[i]
            sum_a += change
            sum_b -= change
            if sum_a == sum_b:
                return True
            sum_a -= change
            sum_b += change
    return False

위의 방법보다 더 좋은 방법은 배열 A 원소의 수를 세고 배열 A와 B 요소들의 합의 차 d를 계산하는 방법이다.

두 배열의 합의 차이인 d는 우리가 배열 A에서 어떤 값을 swap해야 하는지 알려준다. 왜냐하면 하나의 값을 swap할 때 두 개의 합이 동일해지기 때문이다.

배열을 카운팅 한 후 이 값을 구하는 동작은 상수 시간 내에 가능하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
def fast_solution(A, B, m):
    n = len(A)
    sum_a = sum(A)
    sum_b = sum(B)
    d = sum_b - sum_a
    if d % 2 == 1:
        return False
    d //= 2
    count = counting(A, m)
    for i in xrange(n):
        if 0 <= B[i] - d and B[i] - d <= m and count[B[i] - d] > 0:
            return True
    return False

PermCheck

python
1차: 30점 - https://codility.com/demo/results/trainingHBR2ZE-W52/
2차: 70점 - https://codility.com/demo/results/trainingDW7FCK-495/

아직 paneless 문제인데 여기부터 벌써 한계가 찾아오다니… ㅠㅠ

MissingInteger

python
1차: 22점 - https://codility.com/demo/results/training2P6BG5-N6S/

FrogRiverOne

python
1차: 54점 - https://codility.com/demo/results/training3K6KVK-6NB/
2차: 100점 - https://codility.com/demo/results/trainingU2PU2U-K5K/

MaxCounters

Share