파이썬 코딩테스트 강좌 보관 - 28 중 23 번째 페이지

파이썬 코딩테스트 강좌, 깊이 우선 탐색

1. 깊이 우선 탐색(DFS) 소개

깊이 우선 탐색(Depth-First Search, DFS)은 그래프의 탐색 알고리즘 중 하나로,
주어진 노드에서 가능한 깊이까지 탐색한 후, 더 이상 탐색할 노드가 없으면 마지막으로
방문했던 노드로 되돌아가서 다른 경로를 탐색하는 방식입니다. 이 방법은 그래프의 형태에 따라
다양한 용도로 사용되며, 트리의 탐색과 연결 요소의 탐색, 경로 탐색 문제 등에 활용됩니다.

DFS의 작동 방식은 다음과 같습니다:

시작 노드를 스택에 추가한다.
스택에서 노드를 하나 꺼내 탐색한다.
탐색한 노드를 방문한 것으로 표시한다.
아직 방문하지 않은 인접 노드를 모두 스택에 추가한다.
스택이 비어있지 않은 동안 위 과정을 반복한다.

2. 문제 설명

문제: 섬의 개수 세기

주어진 2차원 배열 grid에서 ‘1’은 육지를, ‘0’은 바다를 나타냅니다.
한 섬은 상하좌우로 연결된 육지의 집합입니다.
섬의 개수를 세는 함수를 작성하세요.

            입력: 
            grid = [
                ["1","1","0","0","0"],
                ["1","1","0","0","0"],
                ["0","0","1","0","0"],
                ["0","0","0","1","1"]
            ]
            출력: 3

3. 문제 해결 과정

3.1. 문제 이해하기

문제를 해결하기 위해서는 먼저 육지가 연결된 부분(즉, 섬)을 찾아야 합니다.
각각의 섬은 DFS를 통해 찾을 수 있으며, 육지를 탐색하면서 인접한 육지도 함께 탐색하여
섬의 모든 부분을 확인할 수 있습니다.

3.2. 데이터 구조 설계하기

DFS를 구현하기 위해 스택을 사용하겠습니다.
자원을 효율적으로 관리하기 위해 2차원 배열의 모든 요소를 방문 여부를 체크할 수 있는
boolean 배열을 사용할 것입니다.

3.3. DFS 구현하기

            def dfs(grid, visited, i, j):
                # 범위를 벗어나거나 이미 방문한 경우 종료
                if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or visited[i][j] or grid[i][j] == '0':
                    return
                # 현재 위치 방문 처리
                visited[i][j] = True
                
                # 상하좌우 탐색
                dfs(grid, visited, i - 1, j)  # 위
                dfs(grid, visited, i + 1, j)  # 아래
                dfs(grid, visited, i, j - 1)  # 왼쪽
                dfs(grid, visited, i, j + 1)  # 오른쪽

3.4. 최종 함수 구현하기

            def numIslands(grid):
                if not grid:
                    return 0
                
                visited = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]
                island_count = 0
                
                # 그리드의 모든 노드 탐색
                for i in range(len(grid)):
                    for j in range(len(grid[0])):
                        if grid[i][j] == '1' and not visited[i][j]:
                            dfs(grid, visited, i, j)
                            island_count += 1  # 새로운 섬 찾음
                            
                return island_count

3.5. 코드 테스트

            grid = [
                ["1","1","0","0","0"],
                ["1","1","0","0","0"],
                ["0","0","1","0","0"],
                ["0","0","0","1","1"]
            ]

            print(numIslands(grid))  # 3이 출력되어야 합니다.

4. 문제 해결 리뷰

DFS를 활용하여 문제를 해결하였고, 시간 복잡도는 O(N * M)이며,
N은 행의 수, M은 열의 수를 나타냅니다.
모든 노드를 최대 한 번씩 방문하기 때문에 효율적인 방법이라고 할 수 있습니다.
또한, 공간 복잡도 또한 O(N * M)이 들어간다고 할 수 있습니다.
이는 visiting 리스트를 위해 추가적인 공간을 사용했기 때문입니다.

DFS는 메모리 사용량이 높을 수 있지만, 문제의 성격이나 크기에 따라 BFS보다 효과적인 경우가 많습니다.
특히, 경로 문제나 연결 구성 요소를 구별하는 문제에서 DFS의 장점을 누릴 수 있습니다.

5. 결론

이번 강좌를 통해 DFS의 기본 개념과 문제 해결 방식에 대해 알아보았습니다.
다양한 문제에서 DFS를 활용할 수 있으니, 본 강좌를 바탕으로 여러 문제를 풀어보시기 바랍니다.
감사합니다.

파이썬 코딩테스트 강좌, 나머지 합 구하기

안녕하세요, 여러분! 이번 강좌에서는 파이썬을 이용한 코딩 테스트에서 자주 출제되는 알고리즘 문제 중 하나인 ‘나머지 합 구하기’에 대해 알아보겠습니다. 이 문제는 대량의 데이터 처리 및 모듈러 연산을 이해하고 사용하는 데 도움을 주는 좋은 예시입니다.

문제 설명

여러분은 N개의 정수로 이루어진 배열 A가 주어질 때, 배열의 부분 배열의 합을 K로 나눈 나머지를 구하는 문제를 해결해야 합니다. 부분 배열의 정의는 배열의 시작 인덱스와 끝 인덱스에 의해 정의된 연속된 배열의 집합입니다.

예를 들어 배열 A가 [3, 1, 4, 1, 5]이고 K가 2라고 가정하면, 모든 부분 배열의 합을 K로 나눈 나머지를 구해야 합니다. 이 문제는 기본적인 수학과 프로그래밍 스킬을 요구하며, 다양한 접근 방법으로 해결할 수 있습니다.

입력

첫 번째 줄에 두 개의 정수 N (1 ≤ N ≤ 100,000)과 K (1 ≤ K ≤ 10,000)가 주어진다.
두 번째 줄에 N개의 정수 A[1], A[2], …, A[N] (0 ≤ A[i] ≤ 10⁹)가 주어진다.

출력

부분 배열의 합을 K로 나눈 나머지가 0인 부분 배열의 개수를 출력한다.

예제

접근 방법

이 문제를 해결하기 위해서는 다음과 같은 접근 방법을 사용할 수 있습니다.

1. 부분 배열의 정의 이해

부분 배열은 원 배열에서 연속된 원소들의 집합이므로, 주어진 배열에서 모든 가능한 부분 배열을 생성한 다음, 각 부분 배열의 합을 계산하고 K로 나눈 나머지를 확인해야 합니다.

2. 효율적인 계산 방법

부분 배열을 직접적으로 구하는 것은 최악의 경우 O(N²)의 시간 복잡도를 가지므로 비효율적입니다. 따라서, 누적합(Cumulative Sum)과 해시 맵(Hash Map)을 활용하여 이 문제를 O(N)으로 해결할 수 있습니다.

3. 누적합과 모듈러 연산 사용

누적합을 구하여 현재까지의 합을 K로 나눈 나머지를 저장합니다. 동일한 나머지 값을 가진 경우, 해당 인덱스 사이의 부분 배열의 합이 K로 나눠질 수 있다는 사실을 이용합니다.

코드 예시

    
    def count_subarrays_with_zero_modulo(n, k, arr):
        count = 0
        mod_count = [0] * k
        current_sum = 0
        
        for num in arr:
            current_sum += num
            mod = current_sum % k
            
            if mod < 0:  # Python's mod can be negative, adjust it
                mod += k
            
            # If current modulo is zero, we can count it
            if mod == 0:
                count += 1
            
            # Add the number of times this modulo has appeared before
            count += mod_count[mod]
            mod_count[mod] += 1
            
        return count

    # Example usage
    n = 5
    k = 2
    arr = [3, 1, 4, 1, 5]
    result = count_subarrays_with_zero_modulo(n, k, arr)
    print(result)  # Output: 4

결과 분석

위 코드에서 count_subarrays_with_zero_modulo 함수는 배열에 있는 부분 배열의 합이 K로 나눠진 결과가 0인 경우의 수를 세는 함수입니다. 이 과정에서 누적합을 통해 각 인덱스의 합을 계산하고, 해시 맵을 통해 같은 나머지를 가진 경우를 카운트합니다. 이렇게 함으로써, 우리는 O(N)의 시간 복잡도로 문제를 해결할 수 있습니다.

마무리

이번 강좌를 통해 나머지 합 문제에 대한 접근 방법을 이해하고, 효율적인 코딩 기법을 배웠습니다. 이러한 기법은 대규모 데이터 처리가 필요한 다양한 상황에서 활용할 수 있으며, 여러분의 알고리즘 문제 해결 능력을 크게 향상시킬 것입니다.

추가적으로 이와 유사한 문제에 대한 풀이를 시도해보며 경험을 쌓아보시기 바랍니다. 다음 강좌에서는 또 다른 흥미로운 주제를 가지고 찾아뵙겠습니다. 감사합니다!

파이썬 코딩테스트 강좌, 기하 알아보기

안녕하세요! 오늘은 파이썬 코딩테스트에서 자주 출제되는 기하 문제를 해결하는 방법에 대해 알아보겠습니다. 기하 문제는 주로 도형의 넓이, 둘레, 교차 여부, 거리 계산 등을 포함하며, 알고리즘 문제 풀이 시 중요한 부분입니다. 본 강좌에서는 기본적인 기하학 개념을 바탕으로 자주 출제되는 문제를 설명하고, 이를 성공적으로 풀기 위한 접근 방법을 단계별로 살펴보겠습니다.

문제: 두 선분의 교차 여부 판단하기

두 선분이 주어졌을 때, 이 두 선분이 교차하는지 여부를 판단하는 문제입니다.

문제 정의

주어진 두 선분 AB와 CD의 교차 여부를 판단하시오. 각 선분은 다음과 같이 두 점으로 정의됩니다:

선분 AB: 점 A(x1, y1), 점 B(x2, y2)
선분 CD: 점 C(x3, y3), 점 D(x4, y4)

입력 형식

4개의 정수 x1, y1, x2, y2, x3, y3, x4, y4가 주어집니다.

출력 형식

선분이 교차하면 “YES”, 그렇지 않으면 “NO”를 출력합니다.

문제 접근 방법

두 선분이 교차하는지 판단하기 위해서는 기하학적인 개념인 ‘선분의 방향’을 사용해야 합니다. 두 선분의 각 점에 대하여 방향을 구하고, 이를 통해 교차 여부를 확인할 수 있습니다.

1. 방향 계산

선분 AB와 CD에 대해 방향을 계산하기 위해서는 다음의 공식을 사용합니다:

def direction(px, py, qx, qy, rx, ry):
    return (qx - px) * (ry - py) - (qy - py) * (rx - px)

이 함수는 점 P, Q, R에 대해 방향을 계산하여 양수, 음수, 0을 반환합니다.

2. 선분 교차 판단

선분 AB와 CD의 끝점이 서로 다른 방향을 가질 때 교차한다고 판단할 수 있습니다. 즉, 다음의 조건을 만족해야 합니다:

방향(A, B, C)과 방향(A, B, D)의 곱은 0보다 크고, 방향(C, D, A)과 방향(C, D, B)의 곱도 0보다 큽니다.

이러한 조건을 연결하여 전체 로직을 하나의 함수로 통합할 수 있습니다.

3. 코드 구현

이제까지 설명한 내용을 바탕으로 전체 코드를 구현해 보겠습니다.

def ccw(px, py, qx, qy, rx, ry):
    return (qx - px) * (ry - py) - (qy - py) * (rx - px) > 0

def is_intersect(x1, y1, x2, y2, x3, y3, x4, y4):
    d1 = ccw(x1, y1, x2, y2, x3, y3)
    d2 = ccw(x1, y1, x2, y2, x4, y4)
    d3 = ccw(x3, y3, x4, y4, x1, y1)
    d4 = ccw(x3, y3, x4, y4, x2, y2)

    if d1 != d2 and d3 != d4:
        return "YES"

    return "NO"

# 예제 입력
x1, y1, x2, y2 = map(int, input().split())
x3, y3, x4, y4 = map(int, input().split())

print(is_intersect(x1, y1, x2, y2, x3, y3, x4, y4))

결론

이번 강좌에서는 두 선분이 교차하는지 여부를 판단하는 알고리즘을 구현해 보았습니다. 기하 문제는 기초적인 수학 이론을 기반으로 하며, 알고리즘에 대한 이해가 필요합니다. 다양한 예제를 통해 연습하시면 기하 문제에 대한 자신감을 가질 수 있을 것입니다. 앞으로 더 많은 알고리즘 문제를 접해보고, 이를 통해 코딩 실력을 더욱 향상시키시길 바랍니다.

감사합니다!

파이썬 코딩테스트 강좌, 기수 정렬

안녕하세요! 오늘은 파이썬에서 기수 정렬(Radix Sort) 알고리즘에 대해 알아보겠습니다. 기수 정렬은 공간 복잡도와 시간 복잡도가 매우 유리한 정렬 알고리즘 중 하나로, 특히 정수나 문자열과 같은 형태의 데이터를 정렬할 때 유용합니다. 이 강좌에서는 기수 정렬의 원리, 구현 방법, 그리고 실제 문제를 통해 기수 정렬을 사용하는 방법을 자세히 설명하겠습니다.

기수 정렬이란?

기수 정렬은 주어진 숫자의 각 자리수(십의 자리, 백의 자리 등)를 고려하여 정렬하는 방법입니다. 기수 정렬은 다음과 같은 단계로 진행됩니다:

가장 낮은 자리수부터 시작하여 각 자리수를 기준으로 분배합니다.
분배된 수들을 다시 모아서 정렬된 리스트를 만듭니다.
다음 자리수로 이동하여 과정을 반복합니다.

기수 정렬은 일반적으로 두 가지 방식으로 구현됩니다: LSD(Least Significant Digit) 방식과 MSD(Most Significant Digit) 방식. 이 강좌에서는 LSD 방식, 즉 가장 작은 자리수부터 시작하는 기수 정렬에 초점을 맞출 것입니다.

기수 정렬의 시간 복잡도

기수 정렬의 시간 복잡도는 O(nk)입니다. 여기서 n은 정렬할 숫자의 개수, k는 가장 큰 수의 자리수입니다. 기수 정렬은 안정 정렬로 분류되며, 이는 같은 값을 가진 요소의 상대적인 순서가 변하지 않음을 의미합니다.

문제: 기수 정렬을 이용한 정렬

이제 기수 정렬을 적용하여 주어진 정수를 정렬하는 문제를 풀어보겠습니다. 문제는 다음과 같습니다:

문제 설명

정수의 배열이 주어질 때, 기수 정렬을 사용하여 이 배열을 오름차순으로 정렬하는 프로그램을 작성하세요.

입력

정수의 배열: [170, 45, 75, 90, 802, 24, 2, 66]

출력

오름차순으로 정렬된 배열을 출력하세요.

문제 풀이 과정

이제 위의 문제를 해결하기 위해 기수 정렬을 구현해보겠습니다. 먼저, 아래와 같이 각 자리수를 기준으로 정렬하는 보조 함수인 counting_sort를 작성하겠습니다. 이 함수는 주어진 자리수를 기준으로 배열을 정렬합니다.

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n  # 정렬된 배열을 저장할 리스트
    count = [0] * 10  # 0~9까지의 숫자를 세기 위한 리스트

    # 현재 자리수에 따라 각 숫자의 개수를 센다
    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1

    # 누적합을 통해 각 숫자의 위치를 찾는다
    for i in range(1, 10):
        count[i] += count[i - 1]

    # 정렬된 배열을 생성
    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1

    # 정렬된 결과를 원본 배열에 반영
    for i in range(n):
        arr[i] = output[i]

위의 코드에서 counting_sort 함수는 입력 배열에서 각 숫자의 현재 자리수를 검사하여 해당 자리수에 맞는 숫자의 개수를 카운트하고, 누적 합을 통해 정렬된 결과를 생성합니다. 이제 기수 정렬을 구현하는 메인 함수를 작성하겠습니다.

def radix_sort(arr):
    # 배열에서 가장 큰 수를 찾아 자리수를 결정
    max_num = max(arr)

    # 가장 작은 자리수부터 시작하여 정렬
    exp = 1
    while max_num // exp > 0:
        counting_sort(arr, exp)
        exp *= 10

이제 기수 정렬의 전체 구현을 살펴보겠습니다.

def radix_sort(arr):
    max_num = max(arr)  # 최대값을 찾는다
    exp = 1  # 자리수의 승수 초기화
    while max_num // exp > 0:  # 최대값의 자리수 만큼 반복
        counting_sort(arr, exp)  # 현재 자리수에 대해 counting_sort 호출
        exp *= 10  # 다음 자리수로 이동

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n  # 정렬된 배열을 저장할 리스트
    count = [0] * 10  # 0~9까지의 숫자를 세기 위한 리스트

    # 현재 자리수에 따라 각 숫자의 개수를 센다
    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1

    # 누적합을 통해 각 숫자의 위치를 찾는다
    for i in range(1, 10):
        count[i] += count[i - 1]

    # 정렬된 배열을 생성
    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1

    # 정렬된 결과를 원본 배열에 반영
    for i in range(n):
        arr[i] = output[i]

# 테스트 코드
arr = [170, 45, 75, 90, 802, 24, 2, 66]
print("정렬 전 배열:", arr)
radix_sort(arr)
print("정렬 후 배열:", arr)

테스트 결과

위의 코드를 실행하면 다음과 같은 결과가 나타납니다:

정렬 전 배열: [170, 45, 75, 90, 802, 24, 2, 66]
정렬 후 배열: [2, 24, 45, 66, 75, 90, 170, 802]

정렬 전의 배열과 정렬 후의 배열을 비교하면, 기수 정렬이 잘 작동한 것을 알 수 있습니다.

기수 정렬의 장점과 단점

장점

특정한 조건의 데이터(정수, 문자열 등)에 대해 매우 빠른 성능을 발휘합니다.
안정 정렬이기 때문에 같은 값을 가진 요소들의 순서가 보존됩니다.
특정 자리수에 관심이 있는 경우 효율적으로 정렬이 가능합니다.

단점

메모리를 추가로 소비하며, 원본 배열과 동일한 크기의 배열이 필요합니다.
정수나 문자열이 아닌 다른 데이터 타입에는 적합하지 않습니다.
데이터의 범위가 매우 큰 경우 시간 복잡도가 증가할 수 있습니다.

마무리

이번 강좌에서는 기수 정렬에 대해 자세히 알아보았고, 이를 통해 배열을 정렬하는 문제를 해결했습니다. 기수 정렬은 특정한 상황에서 매우 유용한 정렬 알고리즘이므로, 알고리즘 시험에서는 자주 등장할 수 있습니다. 따라서, 기수 정렬의 원리와 실제 구현 방법을 명확히 이해하는 것이 중요합니다. 다음 시간에는 또 다른 유용한 정렬 알고리즘이나 데이터 구조에 대해 알아보도록 하겠습니다. 읽어주셔서 감사합니다!

파이썬 코딩테스트 강좌, 그리디 알고리즘

문제 설명

오늘 다룰 문제는 동전 거스름돈 문제입니다. 이 문제는 우리가 현실에서 자주 접하는 다양한 동전을 이용해 특정 금액을 만들 때, 가장 적은 수의 동전을 사용하는 방법을 찾는 것입니다.

문제 정의

다음과 같은 조건을 만족하는 함수 min_coins(coins, amount)를 작성하시오:

coins: 사용 가능한 동전의 목록 (예: [1, 5, 10, 25])
amount: 만들고자 하는 금액

이 함수는 주어진 금액을 만들기 위해 필요한 최소 동전의 수를 반환해야 합니다. 동전을 사용할 수 없는 경우에는 -1을 반환합니다.

문제 이해하기

문제를 좀 더 깊이 있게 이해하기 위해 몇 가지 예제를 살펴보겠습니다.

예제 1:
입력: coins = [1, 5, 10, 25], amount = 63
출력: 6
설명: 25 + 25 + 10 + 1 + 1 + 1 = 63

예제 2:
입력: coins = [2, 4], amount = 5
출력: -1
설명: 5를 만들 수 있는 방법이 없음.

접근 방법

이 문제를 해결하기 위해 그리디 알고리즘을 사용하겠습니다. 그리디 알고리즘은 현재 상황에서 가장 최적인 선택을 하는 방식으로 동작합니다. 따라서, 우리는 가장 큰 동전부터 차례대로 사용하여 목표 금액을 만드는 방법을 모색하려 합니다.

해당 알고리즘의 구체적인 단계는 다음과 같습니다:

사용 가능한 동전들을 내림차순으로 정렬합니다.
현재 금액을 동전과 비교하여 가능한 한 많은 동전을 사용합니다.
남은 금액이 0이 될 때까지 이 과정을 반복합니다.
남은 금액이 0이 되었을 경우 동전의 개수를 반환하고, 그렇지 않을 경우 -1을 반환합니다.

코드 구현

그럼 이 접근 방법을 바탕으로 코드를 작성해보겠습니다:


def min_coins(coins, amount):
    # 동전을 내림차순으로 정렬
    coins.sort(reverse=True)
    
    count = 0  # 사용한 동전의 수
    
    for coin in coins:
        # 현재 동전이 amount보다 큰 경우 무시
        while amount >= coin:
            amount -= coin  # 동전의 가치를 amount에서 빼기
            count += 1  # 동전 개수 증가
            
    # 최종적으로 amount가 0인지 확인
    return count if amount == 0 else -1

테스트

이제 작성한 함수를 테스트해보겠습니다.


# 테스트 케이스
print(min_coins([1, 5, 10, 25], 63))  # 6
print(min_coins([2, 4], 5))             # -1
print(min_coins([5, 2, 1], 11))         # 3 (5 + 5 + 1)

결론

이러한 방식으로 그리디 알고리즘을 사용하여 동전 거스름돈 문제를 해결할 수 있었습니다. 이 문제를 통해 그리디 알고리즘의 기초적인 접근 방식을 익히고, 코딩 테스트에서 흔히 나오는 문제 유형을 공부했습니다.

앞으로 더 많은 문제를 연습하며 그리디 알고리즘에 대한 이해를 깊이게 쌓아가길 바랍니다. 위의 문제와 같이, 데이터를 어떻게 정렬하고, 반복문을 활용하여 해결책을 찾아나가는지에 대한 연습이 필요합니다. 그리디 알고리즘은 다양한 문제 해결에 유용한 도구가 될 수 있습니다.

감사합니다!