포스트

Python 코딩테스트 연습문제 21~30

파이썬 코딩테스트 준비를 하며 공부한 내용을 기록하고 복습합니다.

게시
Preview Image
By 태주아빠
읽는 시간 30분
Python 코딩테스트 연습문제 21~30

코딩테스트 참고자료

파이썬 코딩테스트

문제21

USACO 2018 January Contest, Bronze Problem 2. Lifeguards

인명구조원을 하나씩 제거한 모든 시간표를 구해 커버 되는 최대 시간을 찾는다.

  • 커버되는 시간대의 개수를 세면 된다
    • 중간에 시간이 끊겨도 해당 시간대는 포함됨
  • 모든 시간표의 조합을 생성해 내는 것이 핵심 (이후 최대값 출력)
    • 완전(전체) 탐색 알고리즘

내가 제출한 코드

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
35
36
37
38

lines = [
    '3','5 9','1 4','3 7'
]
from functools import partial
input = partial(lambda x: next(x), iter(lines))

def read_data():
    n = int(input())
    data = []
    for i in range(n):
        data.append( list(map(int, input().split())) )
    return data

data = read_data()
# print(sorted(data, key=lambda v: (v[0], v[1])))

def calc_covered_time(data):
    times = set()
    for i,j in sorted(data, key=lambda v: (v[0], v[1])):
        times.update(range(i,j))
    return len(times)

def max_covered_time(data):
    max_time = 0
    for i in range(len(data)):
        sliced = data[:i] + data[i+1:]
        covered_time = calc_covered_time(sliced)
        print(sliced, '==>', covered_time)
        if covered_time > max_time:
            max_time = covered_time
    return max_time

print( max_covered_time(data) )
## 결과
# [[1, 4], [3, 7]] ==> 6
# [[5, 9], [3, 7]] ==> 6
# [[5, 9], [1, 4]] ==> 7
# 7

문제22

USACO 2014 January Contest, Bronze Problem 1. Ski Course Design

비용함수를 구현하고 탐색범위를 제한하는 것이 핵심

내가 제출한 코드

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

lines = [
    '5',
    '20','4','1','24','21'
]
from functools import partial
input = partial(lambda x: next(x), iter(lines))

def read_data():
    n = int(input())
    data = []
    for i in range(n):
        data.append( int(input()) )
    return data

heights = read_data()
min_h, max_h = min(heights), max(heights)
ALLOWED_HEIGHT = 17
print(f'heights={heights}')

def calc_cost(heights, min_h, max_h):
    """
    주의!
    언덕의 높이가 min_h, max_h 사이에 들어가는 경우는 비용을 계산하지 않는다
    """
    cost = 0
    targets = [ x for x in heights if x < min_h or x > max_h ]
    for h in targets:
        diff = min( abs(h-min_h), abs(max_h-h) )
        cost += diff ** 2
        # print(h, diff, cost)
    return cost

def find_min_cost(heights):
    min_h, max_h = min(heights), max(heights)
    if max_h - min_h <= ALLOWED_HEIGHT:
        return 0

    # 허용치 17을 만족하기 위한 height 차이 (탐색범위)
    diff = (max_h - min_h) - ALLOWED_HEIGHT
    # 가장 많이 깍게 되는 경우를 최대치로 설정하고
    min_pair = min_h+diff, max_h-diff
    min_cost = calc_cost(heights, *min_pair)
    # min_h 를 시작으로 diff 차이만큼 구간을 옮기며 cost 계산
    for h in range(min_h, min_h+diff):
        cost = calc_cost(heights, h, h+ALLOWED_HEIGHT)
        # print(h, h+ALLOWED_HEIGHT, '==>', cost)
        if cost < min_cost:
            min_cost = cost
            min_pair = h, h+ALLOWED_HEIGHT
    return min_cost, min_pair

print( find_min_cost(heights) )
## 결과
# [20, 4, 1, 24, 21]
# (18, (4, 21))

문제23

USACO 2013 December Contest, Bronze Problem 2. Cow Baseball

나는 combinations 를 사용했는데, 책에서는 bisect 로 탐색을 수행했다

  • from itertools import combinations
    • 조합을 구한 후 정렬하고, 조합의 거리값으로 조건을 비교한다
  • from bisect import bisect_left, bisect_right
    • 배열이 정렬되어 있어야 하고, 찾는 값이 배열 내에 존재해야 한다

내가 제출한 코드

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
35
36
37
38
39
40

lines = [
    # '5','3','1','10','7','4'
    '7','16','14','23','18','1','6','11'
]
from functools import partial
input = partial(lambda x: next(x), iter(lines))

def read_data():
    n = int(input())
    data = []
    for i in range(n):
        data.append( int(input()) )
    return data

positions = read_data()
positions.sort()
print(f'positions={positions}')

from itertools import combinations
def find_xyz(positions):
    results = []
    for tp in combinations(positions,3):
        xyz = sorted(tp)
        dist_xy = xyz[1]-xyz[0]
        dist_yz = xyz[2]-xyz[1]
        if dist_xy <= dist_yz <= dist_xy*2:
            results.append(xyz)
    return results

tuples = find_xyz(positions)
print( '==>', tuples )
print( len(tuples) )

## 결과
# positions=[1, 3, 4, 7, 10]
# [[1, 3, 7], [1, 4, 7], [1, 4, 10], [4, 7, 10]]
# 4
# positions=[1, 6, 11, 14, 16, 18, 23]
# ==> [[1, 6, 11], [1, 6, 14], [1, 6, 16], [1, 11, 23], [6, 11, 16], [6, 11, 18], [6, 14, 23], [11, 14, 18], [11, 16, 23], [14, 16, 18], [14, 18, 23]]
# 11

다른 제출자 코드

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

from bisect import bisect_left, bisect_right
lines = [
    # '5','3','1','10','7','4'
    '7','16','14','23','18','1','6','11'
]
from functools import partial
input = partial(lambda x: next(x), iter(lines))

def read_data():
    n = int(input())
    data = []
    for i in range(n):
        data.append( int(input()) )
    return data

positions = read_data()
positions.sort()
print(f'positions={positions}')

n = len(positions)
total = 0
for i in range(n):
    for j in range(i+1, n):
        xy_diff = positions[j] - positions[i]
        low_pos = positions[j] + xy_diff
        high_pos = positions[j] + xy_diff*2
        left = bisect_left(positions, low_pos)
        right = bisect_right(positions, high_pos)
        if right-left > 0:
            print(f'x({positions[i]}), y({positions[j]})에 대해 거리값 {low_pos}~{high_pos} 범위에 해당하는 아이템 개수 ==> {right-left} (인덱스 {left}:{right})')
        total += right - left

print(total)

## 결과
# positions=[1, 6, 11, 14, 16, 18, 23]
# x(1), y(6)에 대해 거리값 11~16 범위에 해당하는 아이템 개수 ==> 3 (인덱스 2:5)
# x(1), y(11)에 대해 거리값 21~31 범위에 해당하는 아이템 개수 ==> 1 (인덱스 6:7)
# x(6), y(11)에 대해 거리값 16~21 범위에 해당하는 아이템 개수 ==> 2 (인덱스 4:6)
# x(6), y(14)에 대해 거리값 22~30 범위에 해당하는 아이템 개수 ==> 1 (인덱스 6:7)
# x(11), y(14)에 대해 거리값 17~20 범위에 해당하는 아이템 개수 ==> 1 (인덱스 5:6)
# x(11), y(16)에 대해 거리값 21~26 범위에 해당하는 아이템 개수 ==> 1 (인덱스 6:7)
# x(14), y(16)에 대해 거리값 18~20 범위에 해당하는 아이템 개수 ==> 1 (인덱스 5:6)
# x(14), y(18)에 대해 거리값 22~26 범위에 해당하는 아이템 개수 ==> 1 (인덱스 6:7)
# 11

# [
#   [1, 6, 11], [1, 6, 14], [1, 6, 16],
#   [1, 11, 23],
#   [6, 11, 16], [6, 11, 18],
#   [6, 14, 23],
#   [11, 14, 18],
#   [11, 16, 23],
#   [14, 16, 18],
#   [14, 18, 23]
# ]

문제24

DMOPC ‘20 Contest 2 P2 - Lousy Christmas Presents

내가 제출한 코드

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

lines = [
    '4 2','1 2 3 4','1 3','2 3'  # --> 3
    # '3 2','1 2 3','2 5','1 1'  # --> 1
    # '3 1','1 2 3','3 2'  # --> 0
]
from functools import partial
input = partial(lambda x: next(x), iter(lines))

def read_data():
    # n 스카프 길이, m 친척 숫자
    n, m = list(map(int, input().split()))
    # 스카프 색상
    scarf = list(map(int, input().split()))
    # 친척이 원하는 색상 (처음,끝)
    data = []
    for i in range(m):
        data.append( list(map(int, input().split())) )
    return n, m, scarf, data

n, m, scarf, wants = read_data(lines)
print(f'scarf_size={n}')
print(f'n_wants={m}')
print(f'scarf={scarf}')
print(f'wants={wants}')

def find_index(arr, value):
    for i, v in enumerate(arr):
        if v == value:
            yield i

def find_part(scarf, head, tail):
    longest_size = 0
    heads = [ i for i in find_index(scarf, head) ]
    for i in heads:
        tails = [ j for j in find_index(scarf, tail) if j >= i ]
        # [1:1] 도 한칸이기 때문에 +1을 해야 한다
        if tails:
            size = max(tails)-i+1
            if size > longest_size:
                print(scarf[i], scarf[max(tails)], '==>', size)
                longest_size = size
    return longest_size

longest_size = 0
for w in wants:
    size = find_part(scarf, w[0], w[1])
    longest_size = size if size > longest_size else longest_size

print(longest_size)

## 결과
# scarf_size=4
# n_wants=2
# scarf=[1, 2, 3, 4]
# wants=[[1, 3], [2, 3]]
# 1 3 ==> 3
# 2 3 ==> 2
# 3

다른 제출자 코드

1

문제25
DMOPC ‘17 Contest 4 P1 - Ribbon Colouring Fun
문제에 Subtask #N 이라는 항목으로 테스트 배점이 표시되어 있다.
 (Constraints) N,Q <= 1000 가 40점, N,Q <= 1000000 가 60점
  • 내가 제출한 코드는 TLE [>2.000s, 34.38 MB] 판정받아 40점 밖에 못받음
    • 내 코드는 set 을 이용해 겹쳐지는 부분을 제거했고
  • 반면에 책 정답은 AC [0.170s, 21.05 MB] 로 100점을 받음
    • 책 코드는 rightmost_position 으로 색칠된 영역을 유지하는 방식으로 했다
내가 제출한 코드
  
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

lines = [
    '20 4','18 19','4 16','4 14','5 12'
]
from functools import partial
input = partial(lambda x: next(x), iter(lines))

def read_data():
    n, q = list(map(int, input().split()))
    data = []
    for i in range(q):
        data.append( list(map(int, input().split())) )
    return n, data

n, strokes = read_data()
strokes.sort()  # key=lambda x: (x[0], x[1]))
print(f'N={n}, strokes={strokes}')

painted = set()
left, right = n, 0
for s in strokes:
    painted.update(range(s[0],s[1]))

print(painted)
print(n-len(painted), len(painted))

## 결과
# N=20, strokes=[[4, 14], [4, 16], [5, 12], [18, 19]]
# {4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18}
# 7 13

다른 제출자 코드
  
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

lines = [
    '20 4','18 19','4 16','4 14','5 12'
]
from functools import partial
input = partial(lambda x: next(x), iter(lines))

lst = input().split()
n, q = int(lst[0]), int(lst[1])

strokes = []
for i in range(q):
    stroke = input().split()
    strokes.append( [int(stroke[0]), int(stroke[1])])
strokes.sort()

rightmost_position = 0
blue = 0

for stroke in strokes:
    stroke_start = stroke[0]
    stroke_end = stroke[1]
    if stroke_start <= rightmost_position:
        if stroke_end > rightmost_position:
            blue += stroke_end - rightmost_position
            rightmost_position = stroke_end
    else:
        blue += stroke_end - stroke_start
        rightmost_position = stroke_end

print(n - blue, blue)

문제 26
(백준) 토마토가 모두 익을 때까지의 최소 날짜 구하기
익은 토마토를 중심으로 상하좌우의 인접 토마토가 익는데 1일이 소요된다.
 모든 토마토가 익을 때까지 며칠이 소요되는지 구하라.
 (단, 비어있는 셀은 -1로 표시되고 모두 익을 수 없는 경우에는 -1을 출력)
  • 시간 복잡도가 있는 문제라서, 결과가 맞아도 점수를 받지 못함
  • 탐색의 문제라 deque 와 bfs 탐색전략을 사용해야 올바르다
내가 제출한 코드
  
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

m, n = 6, 4
# days = 8
box = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
# days = -1 (토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다)
#box = [0, -1, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
# days = 6
#box = [1, -1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, -1, 1]


def get_adjacent(m, n, idx) -> list:
    indices = [
        None if idx < m else idx - m,       # up
        None if idx > m*(n-1) else idx + m, # down
        None if idx%m == 0 else idx - 1,    # left
        None if idx%m == m-1 else idx + 1,  # right
    ]
    # return list(filter(None, indices))
    # box 총 크기를 벗어나는 숫자(m*n)가 발생하지만 필터링으로 제외
    return list(filter(lambda x: x != None and 0 <= x < m*n, indices))


# 익지 않은 토마토 주변에 인접한 공간이 없는 상태가 발견되면
# 모두 익을 수 없는 상태로 판단하고 중단시키기
def exists_impossible(box, m, n) -> bool:
    unripen_indices = [ i for i, x in enumerate(box) if x == 0 ]
    for i in unripen_indices:
        adjacent_indices = [ x for x in get_adjacent(m, n, i) if box[x] >= 0 ]
        # print(i, adjacent_indices)
        if not adjacent_indices:
            return True
    return False


def become_ripe(box, m, n):

    def find_unripen(ripen_indices) -> list:
        unripen_indices = set()
        for i in ripen_indices:
            indices = [ x for x in get_adjacent(m, n, i) if box[x] == 0 ]
            unripen_indices.update(indices)
        return sorted(unripen_indices)

    ripen_indices = [ i for i, x in enumerate(box) if x > 0 ]
    # print('- ripen_indices:', ripen_indices)
    # 안익은 토마토 위치 찾아내기
    unripen_indices = find_unripen(ripen_indices)
    # print('- unripen_indices:', unripen_indices)
    # 익은 토마토로 상태 변경
    for i in unripen_indices:
        box[i] = 1
    return len(unripen_indices)


def main(box, m, n):
    # 초기 상태
    print(box)

    # 익을 수 없는 상태가 존재하는지 체크 (한번만 실행)
    if exists_impossible(box, m, n):
        print('-1')
        return

    days = 0
    while box.count(0) > 0:
        days += 1
        # print('unripen remains:', box.count(0))
        ripen_cnt = become_ripe(box, m, n)
        print(f'day {days}: {ripen_cnt} items became ripe')
        print(box)

    print(days)


main(box, m, n)

출력결과
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14

[1, -1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, -1, 1]
day 1: 2 items became ripe
[1, -1, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0, 0, -1, 1]
day 2: 2 items became ripe
[1, -1, 0, 0, 0, 0, 1, -1, 0, 0, 0, 1, 1, 0, 0, 0, -1, 1, 0, 0, 0, 0, -1, 1]
day 3: 4 items became ripe
[1, -1, 0, 0, 0, 1, 1, -1, 0, 0, 1, 1, 1, 1, 0, 0, -1, 1, 1, 0, 0, 0, -1, 1]
day 4: 4 items became ripe
[1, -1, 0, 0, 1, 1, 1, -1, 0, 1, 1, 1, 1, 1, 1, 0, -1, 1, 1, 1, 0, 0, -1, 1]
day 5: 4 items became ripe
[1, -1, 0, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 0, -1, 1]
day 6: 2 items became ripe
[1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1]
6

다른 제출자 코드
출처: [백준] 7576: 토마토 (파이썬 / 해설포함)
  
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

# bfs 특 queue 사용하기
# deque 모듈 안쓰면 시간복잡도 박살남(pop(0)이 시간복잡도가 O(n)이고 popleft()가 O(1)이라고 함)
from collections import deque

m, n = map(int, input().split())
# 토마토 받아서 넣기. 이차원 리스트로 만들어질거.
matrix = [list(map(int, input().split())) for _ in range(n)]
# 좌표를 넣을거니까 []를 넣자.
queue = deque([])
# 방향 리스트. [dx[0], dy[0]]은 곧 [-1, 0]이고 이는 왼쪽으로 이동하는 위치이다.
# 그려보면 이해하기 편함
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
# 정답이 담길 변수
res = 0

# queue에 처음에 받은 토마토의 위치 좌표를 append 시킨다
# n과 m을 사용하는걸 헷갈리지 말아야 함!
for i in range(n):
    for j in range(m):
        if matrix[i][j] == 1:
            queue.append([i, j])

# bfs 함수. 한번 들어가면 다 돌고 나오니까 재귀 할 필요 없음
def bfs():
    while queue:
        # 처음 토마토 좌표 x, y에 꺼내고
        x, y = queue.popleft()
        # 처음 토마토 사분면의 익힐 토마토들을 찾아본다.
        for i in range(4):
            nx, ny = dx[i] + x, dy[i] + y
            # 해당 좌표가 좌표 크기를 넘어가면 안되고, 그 좌표에 토마토가 익지 않은채로 있어야 함(0).
            if 0 <= nx < n and 0 <= ny < m and matrix[nx][ny] == 0:
                # 익히고 1을 더해주면서 횟수를 세어주기
                # 여기서 나온 제일 큰 값이 정답이 될 것임
                matrix[nx][ny] = matrix[x][y] + 1
                queue.append([nx, ny])

bfs()
for i in matrix:
    for j in i:
        # 다 찾아봤는데 토마토를 익히지 못했다면 -1 출력
        if j == 0:
            print(-1)
            exit(0)
    # 다 익혔다면 최댓값이 정답
    res = max(res, max(i))

# 처음 시작을 1로 표현했으니 1을 빼준다.
print(res - 1)

문제27
(백준) 1로 만들기
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. (동적계획법)
  • X가 3으로 나누어 떨어지면, 3으로 나눈다.
  • X가 2로 나누어 떨어지면, 2로 나눈다.
  • 1을 뺀다.
내가 제출한 코드
  
1

다른 제출자 코드 (상향식)
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

lines = [
    '10'  # --> 3
    #'2'  # --> 1
]
from functools import partial
input = partial(lambda x: next(x), iter(lines))

n = int(input())

# dp 는 연산 횟수를 카운팅
dp = [0] * (n+1)
# i 는 연산 대상인 값 (아래 +1 들은 연산 회수 증가를 뜻함)
for i in range(2, n+1):
    dp[i] = dp[i-1] + 1    # -1 연산
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2] + 1)    # //2 연산
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)    # //3 연산

print(dp[n])

문제28
코딩테스트 깊이우선탐색(DFS)
DFS의 핵심은 방문하자마자 visited를 체크하는 것이다. 인접행렬로 푼다.
  • 정점의 인덱스가 1~V 까지라서 V+1 을 사용한다 (0은 안씀)
  
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
35
36

lines = [
    # 정점(V)과 간선수(E), 정점간 연결(v-w)
    '7 8', '1 2 1 3 2 4 2 5 4 6 5 6 6 7 3 7'
]
from functools import partial
input = partial(lambda x: next(x), iter(lines))

V, E = list(map(int, input().split()))
temp = list(map(int, input().split()))

# 재귀호출로 찾을 때까지 탐색
def dfs(v):
    visited[v] = 1
    print(v, end=" ")

    for w in range(V+1):
        # 간선으로 연결되어 있고, 방문을 안했다면 dfs!
        if G[v][w] == 1 and visited[w] == 0:
            dfs(w)

#간선을 넣는 곳이다(2차원으로 바꿔주자.)
G = [ [0 for _ in range(V+1)] for _ in range(V+1) ]

# 방문을 체크해 주는 곳이다.
visited = [ 0 for _ in range(V+1) ]

# 1 2 가 들어오면 1, 2와 2, 1을 둘다 체크한다
for i in range(0, len(temp)-1):
    G[ temp[i] ][ temp[i+1] ] = 1
    G[ temp[i+1] ][ temp[i] ] = 1

# 1에서 시작하기 때문에 1을 대입하자
dfs(1)

## 결과
# 1 2 3 7 6 4 5

문제 29
이진탐색 트리 - BFS
BFS 클래스에 DFS 함수를 재귀호출, 반복호출 방식으로 구현해보았다.
  • DFS 루프 방식을 구현할 때는 스택을 사용해야 한다.
  • 초보자들이 실수하는 가장 큰것이 visited 배열을 안만드는 것이다. 반드시 만들어 주자.
  
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

# 노드 생성
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# 노드 삽입
class BST:
    def __init__(self, root):
        self.root = root

    def insert(self, value):
        # 현재 위치를 root로 설정
        self.current_node = self.root
        while True:
            if value < self.current_node.value:
                # 왼쪽 노드 처리 : 없으면 생성, 있으면 이동 후 반복
                if self.current_node.left != None:
                    self.current_node = self.current_node.left
                else:
                    self.current_node.left = Node(value)
                    break
            else:
                # 오른쪽 노드 처리 : 없으면 생성, 있으면 이동 후 반복
                if self.current_node.right != None:
                    self.current_node = self.current_node.right
                else:
                    self.current_node.right = Node(value)
                    break

    # 노드 탐색
    def search(self, value):
        # 현재 위치를 root로 설정
        self.current_node = self.root
        # 현재 위치를 계속 확인
        while self.current_node:
            # 현재 위치에서 찾으면 반환
            if self.current_node.value == value:
                return True
            # 현재 노드값이 더 크면 왼쪽으로 이동
            elif self.current_node.value > value:
                self.current_node = self.current_node.left
            # 현재 노드값이 더 작으면 오른쪽으로 이동
            else:
                self.current_node = self.current_node.right
        return False

    # 왼쪽 호출, 없으면 오른쪽 호출
    def dfs_recursive(self, value):
        def _dfs(curr):
            print(curr.value)
            if curr.value == value:
                return True
            if curr.left != None:
                return _dfs(curr.left)
            if curr.right != None:
                return _dfs(curr.right)
            return False
        # root로부터 재귀호출 탐색
        return _dfs(self.root)

    # stack 을 사용한다
    def dfs_iteration(self, value):
        # visited = 방문한 꼭지점들을 기록한 리스트
        visited = []
        # dfs는 stack, bfs는 queue개념을 이용한다.
        stack = [ self.root ]
        while stack:
            curr = stack.pop()
            if curr == None: continue
            print(curr.value)
            if curr.value == value:
                return True
            #현재 node가 방문한 적 없다 -> visited에 추가한다.
            #그리고 해당 node의 자식 node들을 stack에 추가한다.
            if curr not in visited:
                visited.append(curr)
                stack.extend([curr.right, curr.left])
        return False

root = Node(5)
bst = BST(root)
bst.insert(1)
bst.insert(2)
bst.insert(7)
bst.insert(4)
bst.insert(8)
bst.insert(10)

print( bst.dfs_iteration(4))

# print(bst.search(2))   # True
# print(bst.search(5))   # False
# print(bst.search(7))   # True
# print(bst.search(8))   # True
# print(bst.search(15))  # False

반복문 형태의 DFS 탐색
  
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

graph = {'A':['B','C'],
         'B':['A','D','E'],
         'C':['A','G','H'],
         'D':['B'],
         'E':['B','F'],
         'F':['E'],
         'G':['C'],
         'H':['C']}

def dfs_iteration(graph, start):
    # 다음 이동(파생) 위치를 유지하는 stack 과
    stack = [start]
    # 이미 지나온 경로를 유지하는 visited 가 있어야 함
    visited = []
    # 최초 위치로부터 더 이상 이동할 곳이 없을 때까지
    while stack:
        # 현재 위치를 꺼내고 (선입후출)
        # 만약 queue 를 사용하면 너비우선(BFS) 탐색이 됨
        curr = stack.pop()
        # 아직 탐색되지 않은 곳이면
        if curr not in visited:
            # 탐색 기록을 하고 (추가적으로 할 작업 있으면 여기서)
            visited.append(curr)
            # 다음 이동 경로를 추가
            stack.extend(graph[curr])
    return visited

dfs_iteration(graph,'A')
# ==> ['A', 'C', 'H', 'G', 'B', 'E', 'F', 'D']

반복문 형태의 너비 우선 탐색(BFS)
deque 는 list 처럼 queue[ idx ] 로 원소를 조회할 수 있음
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

from collections import deque

def bfs_iteration(graph, start):
    # 초기값 (생성자 이용)
    queue = deque( [start] )
    visited = []
    while queue:
        curr = queue.popleft()
        if curr not in visited:
            visited.append(curr)
            queue.extend(graph[curr])
    return visited

print( bfs_iteration(graph, 'A') )
# ==> ['A', 'B', 'C', 'D', 'E', 'G', 'H', 'F']

반복문 형태의 binary search
  
1
2
3
4
5
6
7
8
9
10
11
12

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid -1
        else:
            start = mid +1
    return None

result = binary_search(array, target, 0, n - 1)

문제 30
코딩테스트 - 정렬 알고리즘
  
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

array = [2, 3, 1, 4]

# 가장 작은 값과 SWAP (이중루프)
def selection_sort(array, reverse=False):
    for i in range(len(array)):
        min_index = i
        for j in range(i+1, len(array)):
            if array[j] < array[min_index]:
                min_index = j
                array[i], array[min_index] = array[min_index], array[i]
    return array

# pivot 값을 중심으로 나머지(tail) 값들을 작은값, 큰값으로 나누어 재귀 처리
def quick_sort(array):
    if len(array) <= 1:
        return array

    pivot = array[0] # first element as pivot
    tail = array[1:] # list accept pivot
    left_side = [x for x in tail if x <= pivot] # left side
    right_side = [x for x in tail if x > pivot] # right side
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print( selection_sort(array[:]) )
print( quick_sort(array[:]) )

  
   
끝!   읽어주셔서 감사합니다.
  Language, Python
  dmoj 코딩테스트
 이 기사는 저작권자의  CC BY 4.0  라이센스를 따릅니다.