팩토리얼, 지수시간에 비해 빠르지만 입력 크기가 커질수록 처리 시간이 급격히 증가하는 알고리즘 범주에 속한다.

이 복잡도는 이중 반복문이 포함된 구조에서 자주 나타나며, 작은 입력에선 문제없지만, 큰 입력에서는 비효율적인 성능을 보인다.

대표적으로 정렬 알고리즘 중 버블 정렬, 삽입 정렬, 선택 정렬이 이에 해당하며, 브루트포스 방식의 문제 해결에서도 볼 수 있다.

 

버블 정렬

오름차순 기준

 

배열의 인접한 두 원소를 검사하고 정렬한다.

bubble sort

 

길이가 n인 배열이 있다.

전체 루프 i는 첫 번째부터 마지막 요소 앞 n-1까지 진행한다.

내부 루프 j는 인접한 두 요소를 비교하고 더 큰 수인 경우 교환을 진행하여 n - 1 - i까지 진행한다.

루프마다 가장 큰 요소가 순서대로 끝에 배치된다.

 

def bubble_sort(arr):
    n = len(arr)

    # 총 n-1회 반복
    for i in range(n - 1):
        # 정렬된 요소를 제외한 범위에서 반복
        for j in range(n - 1 - i):
            # 인접한 요소 비교 후 순서가 잘못되면 교환
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

data = [5, 2, 4, 3, 1]
print("정렬 전:", data)
bubble_sort(data)
print("정렬 후:", data)

"""
정렬 전: [5, 2, 4, 3, 1]
정렬 후: [1, 2, 3, 4, 5]
"""

 

모든 요소를 반복적으로 비교 및 교환한다. 어떤 경우든 i 반복은 무조건 n-1번을 수행하게 되며 이미 정렬된 배열인 경우에도 불필요한 반복이 진행되게 된다. 이러한 점을 개선해 스왑 발생 여부를 확인하여 정렬이 된 상태인 경우 조기 종료를 시킬 수 있다.

 

def bubble_sort_optimized(arr):
    n = len(arr)

    for i in range(n - 1):
        swapped = False

        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True

        # 스왑이 한 번도 없으면 이미 정렬된 상태
        if not swapped:
            break

data = [1, 2, 3, 4, 5]
print("정렬 전:", data)
bubble_sort(data)
print("정렬 후:", data)

 

최악이나 평균의 경우에는 모든 요소를 끝까지 비교하고 교환해야 하므로 시간 복잡도는 O(n^2)이다. 그러나 이미 정렬된 배열인 최선의 경우에는 비교만 수행되고 스왑이 한 번도 발생하지 않기 때문에 조기에 종료되어, 최적화된 구현에서는 O(n)의 시간 복잡도를 가질 수 있다.

 

선택정렬

매 반복마다 가장 작은 값을 찾아 맨 앞과 교환하는 방식이다. 정렬된 부분과 미정렬 부분을 구분하고, 매 단계마다 최솟값을 선택한다. 교환 횟수는 최대 n-1회이지만 비교는 항상 일정하게 많이 발생하기 때문에 최선/최악 구분 없이 O(n^2)이다.

 

select sort

 

비교 방식이 데이터 정렬 여부와 무관하다.

 

def selection_sort(arr):
    """
    선택 정렬 함수
    현재 위치 이후의 요소 중 최솟값을 찾아 현재 위치와 교환
    """
    n = len(arr)

    for i in range(n - 1):
        min_index = i  # 현재 위치를 최솟값 인덱스로 가정

        # i 이후 요소들 중에서 최솟값 인덱스 탐색
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j

        # 현재 위치와 최솟값 위치를 교환
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]

data = [5, 2, 4, 3, 1]
print("정렬 전:", data)
selection_sort(data)
print("정렬 후:", data)

"""
정렬 전: [5, 2, 4, 3, 1]
정렬 후: [1, 2, 3, 4, 5]
"""

 

구조가 단순하고, 교환 횟수가 적기 때문에 메모리 이동 비용이 큰 환경에 적합하지만 비교 횟수가 많고 입력이 정렬되어 있어도 시간 복잡도가 항상 O(n^2)인 단점이 있어 대규모 데이터에는 부적합하다.

 

삽입 정렬

삽입 정렬은 배열의 두 번째 요소부터 시작하여, 현재 요소를 그 앞에 있는 요소들과 비교하면서 적절한 위치를 찾아 삽입하는 방식이다. 비교 과정에서는, 앞의 요소가 현재 요소보다 크면 한 칸씩 뒤로 이동시키고, 더 작은 값을 만나거나 배열의 처음까지 도달하면 그 자리에 현재 요소를 삽입한다. 이 과정을 반복하며 배열의 왼쪽 부분부터 정렬된 상태가 된다.

insert sort

 

def insertion_sort(arr):
    """
    삽입 정렬 함수
    배열의 각 요소를 순차적으로 '정렬된 부분'에 삽입하여 정렬하는 알고리즘.
    """
    n = len(arr)
    
    # 두 번째 요소부터 시작: 첫 번째 요소는 이미 '정렬된 부분'으로 가정
    for i in range(1, n):
        key = arr[i]        # 현재 정렬할 값
        j = i - 1           # key 앞의 마지막 인덱스

        # key가 정렬된 부분의 값보다 작으면, 한 칸씩 오른쪽으로 이동시켜 자리 비움
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        # 최종적으로 key를 알맞은 위치에 배치
        arr[j + 1] = key

data = [5, 2, 4, 3, 1]
print("정렬 전:", data)
insertion_sort(data)
print("정렬 후:", data)

"""
정렬 전: [5, 2, 4, 3, 1]
정렬 후: [1, 2, 3, 4, 5]
"""

 

 

정렬된 배열일 경우 비교만 하고 이동이 거의 없어 O(n)에 가까운 성능을 보인다.

구현이 간단하며, 안정 정렬이기 때문에 동일한 값을 가진 요소들의 상대적 순서가 유지된다. 추가적인 배열 없이 입력 배열 내부에서만 정렬 수행을 하기 때문에 메모리에 효율적이지만 전체가 정렬되지 않은 경우 비교, 이동이 많아져 시간 복잡도는 O(n^2)가 된다.

 

728x90
반응형

'Coding > Algorithm' 카테고리의 다른 글

O(2^n) - 지수 시간  (1) 2025.07.12
NP - TSP  (1) 2025.07.11
P, NP  (0) 2025.07.08
O(n!) - 팩토리얼 시간  (2) 2025.07.08
빅-오(Big-O) 표기법  (1) 2025.07.08

O(2^n) - 지수 시간

O(n!) 시간 복잡도처럼, 지수 시간 복잡도 또한 입력 크기가 조금만 커져도 실행 시간이 급격히 증가하는 대표적인 비효율적인 복잡도이다. 특히, 모든 가능한 경우의 수를 탐색해야 하는 문제에서 자주 나타난다.

 

부분 집합 생성

집합 [1, 2, 3]이 있을 때, 모든 부분 집합의 개수는 2^3 = 8개이다.

 

def subsets(arr):
    if not arr:
        return [[]]

    first = arr[0]
    rest_subsets = subsets(arr[1:])

    # 기존 부분집합들 + first를 포함한 새로운 부분집합들
    return rest_subsets + [[first] + subset for subset in rest_subsets]

print(subsets([1,2,3]))

"""
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
"""

 

1. 재귀를 사용해서 주어진 리스트의 모든 가능한 부분 집합을 생성한다.

재귀 호출의 종료 조건은 입력 리스트가 비어있어 더 이상 처리할 요소가 없으면 빈 리스트를 반환하여 공집합이 모든 집합의 부분집합이 되는 규칙을 반영한다.

 

2. 현재 리스트에서 첫 번째 요소를 분리하고, 나머지 요소를 처리하는 하위 문제로 분할한다.

첫 번째 요소를 제외한 나머지 리스트의 모든 부분집합을 재귀적으로 구한다.

 

3. 재귀적으로 얻은 나머지 요소들의 부분집합을 기반으로 최종 부분집합들을 조합한다.

first를 포함하지 않는 부분집합과 포함하는 부분집합 두 그룹을 반환한다.

 

 

subsets([1, 2, 3])

├── first = 1

├── rest_subsets = subsets([2, 3])

│          ├── first = 2

│          ├── rest_subsets = subsets([3])

│           │       ├── first = 3

│           │       ├── rest_subsets = subsets([]) → [[]]

│           │       └── return [[], [3]]

│           └── return [[], [3], [2], [2, 3]]

└── return [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

 

- n개 원소의 부분집합 개수 2^n개

- 각 원소마다 포함 또는 비포함 2가지 선택

- 재귀 호출 2^n번 발생

 

부분집합을 구하는 방식은 비트마스킹을 사용하여 재귀 없이 반복문과 비트 연산으로 더 효율적으로 생성할 수 있다.

 

def subsets_bitmask(arr):
    n = len(arr)
    result = []
    
    for i in range(2**n):  # 0부터 2^n-1까지
        subset = []
        for j in range(n):
            if i & (1 << j):  # j번째 비트가 1이면
                subset.append(arr[j])
        result.append(subset)
    
    return result
# 시간복잡도: O(2^n * n) — 모든 부분집합을 순회하며 최대 n개의 요소를 확인
print(subsets_bitmask([1, 2, 3]))

"""
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
"""

 

피보나치수열(비효율적 재귀)

 피보나치수열은 첫째 및 둘째 항은 1로 고정되고 그 뒤의 모든 항은 바로 앞 두 항의 합으로 이루어진 수열이다.

입력을 받아서 해당 순서에 들어오는 수를 출력하는 코드를 만들어 본다.

 

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

# 호출 예시
print(fibonacci(5)) 

"""
5
"""

 

시간 복잡도는 O(2^n)이며 재귀호출로 인한 중복 호출이 많이 발생하게 된다.

n = 5일 때, 

finbonacci(3) : 2번

finbonacci(2) : 3번

finbonacci(1) : 5번

finbonacci(0) : 3번

 

이러한 중복을 대처하기 위해 효율적인 대안으로 동적 계획법이나 메모이제이션으로 O(n)으로 개선이 가능하다.

 

조합 탐색 (DFS/백트래킹 기반)

n개의 원소 중에서 순서에 상관없이 R개를 뽑는 모든 조합을 탐색한다.

- DFS : 깊이 우선 탐색

- 백트래킹 : 모든 경우의 수를 탐색하면서 가능성이 없는 분기는 중단하고 되돌아가는 기법

 

def dfs(arr, path, start, r):
    if len(path) == r:
        print(path)
        return
    for i in range(start, len(arr)):
        dfs(arr, path + [arr[i]], i + 1, r)

dfs([1, 2, 3, 4], [], 0, 2)

"""
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
"""

 

주어진 배열(arr)에서 r개의 원소를 선택하는 모든 조합을 찾는다.

선택한 원소보다 뒤에 있는 원소들만 탐색하여 중복 선택을 방지하고 순서를 고려하지 않는 조합의 특성을 구한다.

 

조합의 수는 C(n, r)로 최대 O(2^n)이 된다. 백트래킹의 경우 조건에 따라 일부 경로는 생략 가능해서 효율은 개선되지만 최악의 경우는 여전히 O(2^n)이다.

 

동적 계획법

Top-Down

큰 문제를 작은 하위 문제로 쪼개면서 재귀적으로 호출한다.

이미 계산한 하위 문제의 결과는 메모이제이션을 통해 저장하여 중복 호출을 방지한다.

재귀 호출 중에 처음 계산되는 하위 문제만 실제 계산되고, 이후에는 저장된 값을 재사용한다.

 

def fibonacci_memo_top_down(n, memo=None):
    # memo는 계산된 값을 저장하기 위한 딕셔너리 (기본값은 None으로 시작)
    if memo is None:
        memo = {}

    if n in memo:
        return memo[n]  # 이미 계산된 값이 있으면 바로 반환 (중복 계산 방지)

    if n <= 1:
        return n  # 기저 사례: 피보나치(0) = 0, 피보나치(1) = 1

    # 아직 계산되지 않은 경우 재귀적으로 계산
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]  # 계산된 값을 반환
    
print(fibonacci_memo_top_down(10))
# 55

 

시간 복잡도 O(n), 코드가 간결하지만 메모리 사용량이 많을 수 있으며 재귀 한도가 있어 너무 큰 입력에는 스택 오버플로우 위험이 있다.

 

Bottom-Up

가장 작은 하위 문제부터 차례대로 해결하면서 결과를 쌓아 올린다.

반복문을 이용해 누적적으로 해결하여 스택 사용 없이 처리한다.

 

def fibonacci_dp_bottom_up(n):
    # 피보나치 수열의 n번째 수를 구하기 위한 동적 계획법 (Bottom-Up 방식) 구현

    if n <= 1:
        return n  # n이 0 또는 1일 경우, 그대로 반환 (기저 사례)

    dp = [0] * (n + 1)  # 0부터 n까지의 값을 저장할 DP 테이블 생성 (n+1 크기)
    dp[1] = 1  # 초기 조건 설정: 피보나치(0) = 0, 피보나치(1) = 1

    # 점화식에 따라 2부터 n까지 순차적으로 계산
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]  # 이전 두 항을 더한 값을 현재 위치에 저장

    return dp[n]  # 최종적으로 n번째 피보나치 수를 반환
    
 print(fibonacci_dp_bottom_up(10))

 

테이블을 통해 모든 값을 저장한다. 시간 복잡도 O(n)을 가지며 재귀 호출이 없어 스택 오버플로우 걱정이 없으며 공간복잡도를 O(n)에서 O(1)로 개선 가능하여 메모리 최적화가 가능하다. 하지만 DP 테이블을 모두 만들어야 하기 때문에 필요 없는 값도 계산하게 되기도 한다.

 

공간 복잡도 개선

def fibonacci_optimized(n):
    # 피보나치(0) = 0, 피보나치(1) = 1 처리
    if n <= 1:
        return n

    # 이전 두 항만 저장 (dp 테이블 전체 필요 없음)
    prev2 = 0  # 피보나치(n-2)
    prev1 = 1  # 피보나치(n-1)

    for i in range(2, n + 1):
        curr = prev1 + prev2  # 현재 피보나치 수
        prev2 = prev1         # 피보나치(n-2) ← 피보나치(n-1)
        prev1 = curr          # 피보나치(n-1) ← 현재 피보나치 수

    return prev1  # n번째 피보나치 수

 

일반적인 bottom-up 방식은 dp = [0] * (n+1)로 전체 수열을 저장하므로 공간복잡도는 O(n)이다. 하지만 피보나치수열의 다른 특징은 항을 계산할 때 오직 이전 두 항만 사용하기 때문에 dp 배열 없이 prev1, prev2 두 변수만 사용해도 충분하다. 불필요한 dp 배열을 제거하게 되면 공간 복잡도는 O(1)로 줄어들게 된다.

728x90
반응형

'Coding > Algorithm' 카테고리의 다른 글

O(n^2) - 이차 시간  (1) 2025.07.12
NP - TSP  (1) 2025.07.11
P, NP  (0) 2025.07.08
O(n!) - 팩토리얼 시간  (2) 2025.07.08
빅-오(Big-O) 표기법  (1) 2025.07.08

외판원 문제(TSP)

NP는 정답을 빠르게 검증할 수 있는 문제 집합이다. 즉, 어떤 해답이 주어졌을 때, 그것이 맞는지 다항 시간 내에 확인 가능한 문제들을 말한다. 

 

NP-complete는 NP 문제 중 가장 어려운 문제들로, NP에 속하면서 모든 NP 문제로부터 다항 시간 내에 환원이 가능한 문제이다. 

 

NP-hard는 모든 NP-complete 이상의 난이도를 포함하는 상위 개념이다. 이 집합은 NP를 포함하지 않을 수도 있으며, 검증조차 다항 시간 내에 불가능할 수 있는 문제까지 포함한다.

 

P ⊆ NP  
NP-complete ⊆ NP  
NP-complete ⊆ NP-hard  

 

TSP는 하나의 경로가 주어졌을 때, 그 경로가 총얼마의 비용을 갖는지 계산하는 데는 O(n)으로 정답을 빠르게 검증하는 게 가능하기 때문에 NP 문제에 속한다.

 

최적 경로를 찾기 위한 모든 경우를 탐색하면 (n-1)!개의 경로가 생기고, 이는 O(n!) 시간 복잡도로, 도시 수가 조금만 늘어나도 계산이 불가능한 수준으로 커지게 된다. 현재까지는 다항 시간 내에 최적해를 찾는 알고리즘은 발견되지 않았기 때문에 TSP의 최적화 문제(정답을 찾는 문제)는 NP-hard이다.

 

TSP의 최단 경로를 묻는 최적화가 문제가 아닌 "총 경로 비용이 K 이하인 경로가 존재하는가?"처럼 결정 문제로 형태를 바꾸면 예/아니오로 답할 수 있고, 다항 시간 검증/환원이 가능한 NP-complete 문제가 된다.

 

즉, 본질적으로는 NP-hard 한 최적화 문제지만, 이를 결정 문제로 변환하면 NP-complete 문제로 볼 수 있다. 실제 적용에서는 정확한 해 대신, 근사 알고리즘이나 동적 계획법을 활용해 현실적인 해를 구하는 방향으로 발전하였다.

 

Held-Karp 알고리즘

작은 규모의 문제에 대해 최적해를 찾는 효율적인 방법을 제공하는 TSP를 해결하기 위한 동적 계획법 기반의 알고리즘이다. 알고리즘의 핵심은 문제를 더 작은 하위 문제로 분할하고, 이 하위 문제들의 해를 저장하여 중복 계산을 피하는 것으로 이때 비트 마스킹을 사용하여 효율적으로 표현한다.

 

문제 풀이의 구조

하위 문제 정의

C(S, j) : 시작 도시(0)에서 출발해 집합 S(0 포함, j 포함)에 속한 도시를 한 번씩 방문, 마지막 도시가 j일 때의 최소 비용 

 

- S: 방문한 도시 집합 (도시 0은 항상 포함)

- j ∈ S, j ≠ 0

 

비트마스킹으로 상태 표현

방문한 도시의 집합 S를 정수로 표현한다

예) s =  0b1011 (0, 1, 3번 도시를 방문한 상태)

 

알고리즘 구성

기저 사례 (Base Case)

더 이상 쪼갤 수 없는 최소 단위 하위 문제이다.

 

두 도시만 방문한 경우(0에서 j로 바로 가는 비용) : C({0, j}, j) = cost(0, j) 

 

점화식 (Recurrence)

작은 하위 문제를 통해 큰 문제를 푸는 공식이다.

 

C(S, j) = min { C(S - {j}, i) + cost(i, j) } (단, i ∈ S - {j})

 

도시 j에 도착하기 직전 도시 i를 고려해, i까지 최소 비용 + i -> j 비용을 더한 값을 구한다.

 

계산 순서

S의 크기를 2 → n까지 증가시키며 모든 C(S, j) 계산한다.

각 상태는 비트마스킹으로 구현한다.

 

최종 결과

모든 도시(V) 방문 후 0으로 돌아오는 최소 경로를 구한다.

 

min { C(V, j) + cost(j, 0) } (단, j ≠ 0)

 

def tsp_dp(dist):
    n = len(dist)
    
    # dp[visited][curr]:
    # 시작 도시 0에서 출발, visited(비트마스킹) 상태의 도시 방문 && 현재 위치 curr일 때 최소 비용
    # 2^n * n -> O(n * 2^n)
    dp = [[float('inf')] * n for _ in range(1 << n)]
    dp[1][0] = 0 # Base Case : 시작 도시(0) 방문 상태

    for visited in range(1 << n): # 총 2^n개의 visited 상태
        for curr in range(n):     # 현재 위치한 도시 (j)
            if not (visited & (1 << curr)):
                continue
            for next in range(n):
                if visited & (1 << next):
                    continue
                next_visited = visited | (1 << next)
                
               	# C(S ∪ {next}, next) = min(C(S, curr) + cost(curr, next))
                dp[next_visited][next] = min(
                    dp[next_visited][next],
                    dp[visited][curr] + dist[curr][next]
                ) # O(n^2 * 2^n)
    
    # 모든 도시 방문 후, 다시 0으로 돌아오는 비용 중 최솟값
    # min(C(V, j) + cost(j, 0))  (j != 0)
    return min(dp[(1 << n) - 1][i] + dist[i][0] for i in range(1, n))

dist = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

result = tsp_dp(dist)
print(f"최소 이동 비용: {result}")

"""
최소 이동 비용: 80
"""

 

시간 복잡도는 개선되어 O(m^2 * 2^n)이 되지만 여전히 도시 수가 증가했을 때 지수적으로 증가하므로 큰 입력엔 부적합하다.

 

근사 알고리즘

도시 수가 증가하면 계산량이 급격히 증가하는 문제를 해결하기 위한 방법으로, 정확한 최적해는 아니지만 계산 가능한 시간 내에 효율적인 경로를 찾는 방법이다.

 

최소 신장 트리 (Minimum Spanning Tree, MST) 알고리즘

MST는 가중치가 있는 무방향 그래프에서 모든 정점을 연결하면서, 간선 가중치의 총합이 최소가 되는 트리를 말한다.

TSP는 출발점에서 모든 정점을 한 번씩 방문하고, 다시 출발점으로 돌아오는 사이클(순환 경로)을 찾는 문제이지만, MST는 사이클이 없는 트리이다. 하지만 이 MST를 활용하여 다음과 같은 방식으로 TSP 근사 경로를 만들 수 있다.

 

1. 완전 그래프 구성

풀고자 하는 TSP 문제의 원래 그래프가 주어지면, 모든 도시 간의 최단 거리를 간선 가중치로 하는 완전 그래프를 구성한다.

이는 특히 삼각 부등식을 만족하는 Metric TSP에서 유용하다.

 

*  Metric TSP?

- 모든 정점 쌍이 연결되어 있으며, 거리 함수가 삼각 부등식을 만족하는 TSP를 의미한다.

- distance(A, C) ≤ distance(A, B) + distance(B, C)

- 이러한 조건을 만족할 경우, 근사 알고리즘의 성능 보장이 가능하다.

 

2. MST 구성

완전 그래프에 대해 MST를 구성한다. 보통 프림(Prim) 알고리즘이 사용되며, 전체 간선 가중치의 합이 최소가 되도록 트리를 구성한다.

 

3. MST 전위 순회 (Preorder Traversal)

MST를 DFS 방식으로 전위 순회하여 방문 순서를 얻는다. 이 순서는 중복 방문이 가능하며, 이후 중복된 정점을 생략하고 한 번씩만 방문하는 경로로 정제한다. 이를 통해 해밀턴 순환 경로에 근사한 경로를 얻는다.


* 해밀턴 순환 경로

- 해밀턴 경로 : 그래프 내의 모든 정점을 정확히 한 번씩만 방문하는 경로, 시작점과 도착점이 다를 수 있다.(비순환)

- 해밀턴 순환 경로는 해밀턴 경로의 조건에서 시작점으로 다시 돌아오는 순환 경로를 추가한다.

 

4. 쇼트컷 적용 및 최종 경로 구성

방문 순서 중 이미 방문한 정점은 건너뛰고 다음 미방문 정점으로 이동하는 쇼트컷(shortcut)을 적용한다. 이를 통해 중복 없이 정점을 한 번씩만 방문하는 해밀턴 순환 경로가 완성되며, 마지막에 시작 도시로 돌아와 TSP의 근사해를 얻는다.

 

프림 (Prim) 알고리즘

최소 신장 트리를 찾을 때는 대표적으로 프림 알고리즘을 사용한다. 이 알고리즘은 그래프의 한 정점에서 시작해서, MST 바깥에 있는 정점 중 현재 MST에 있는 정점과 가장 가중치가 낮은 간선으로 연결된 정점을 하나씩 추가하면서 MST를 만들어 나가는 방식이다. 모든 정점을 연결하는 트리를 사이클 없이 만들고, 총 간선 가중치의 합이 최소가 되도록 구성한다.

 

1. 정점 중 하나를 시작 정점으로 선택하고 MST에 포함시킨다.

2. 현재 MST에 포함된 정점들과 연결된 간선들 중에서, MST 바깥에 있는 정점으로 연결되며 가중치가 가장 낮은 간선을 선택한다.

3. 선택한 간선의 반대쪽 정점을 MST에 새롭게 추가하고, 해당 간선도 MST에 포함시킨다.

4. 모든 정점이 MST에 포함될 때까지 반복한다.

 

import heapq

# 1. Prim 알고리즘으로 MST 구성
def prim_mst(graph):
    n = len(graph)
    visited = [False] * n
    mst = [[] for _ in range(n)]  # MST를 인접 리스트로 표현
    min_heap = [(0, 0)]  # (가중치, 정점)
    
    while min_heap:
        weight, u = heapq.heappop(min_heap)
        if visited[u]:
            continue
        visited[u] = True
        for v in range(n):
            if not visited[v] and u != v:
                heapq.heappush(min_heap, (graph[u][v], v))
                mst[u].append(v)
                mst[v].append(u)  # 무방향 MST
    return mst

# 2. DFS로 MST 순회하여 TSP 경로 획득
def dfs_path(tree, node, visited, path):
    visited[node] = True
    path.append(node)
    for neighbor in tree[node]:
        if not visited[neighbor]:
            dfs_path(tree, neighbor, visited, path)

# 3. 근사 TSP 실행
def tsp_mst_approx(graph):
    mst = prim_mst(graph)  # MST 생성
    path = []
    visited = [False] * len(graph)
    dfs_path(mst, 0, visited, path)  # DFS로 순회 경로 생성
    path.append(0)  # 출발 도시로 복귀
    total_cost = sum(graph[path[i]][path[i+1]] for i in range(len(path)-1))
    return total_cost, path

# 테스트용 그래프 (대칭 행렬, 삼각 부등식 만족)
graph = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

cost, path = tsp_mst_approx(graph)
print(f"근사 비용: {cost}")
print(f"근사 경로: {path}")

"""
근사 비용: 95
근사 경로: [0, 1, 2, 3, 0]
"""

 

 

이 알고리즘은 Metric TSP (삼각 부등식 만족) 조건에서만 유효하며, 항상 최적해의 2배 이내의 근사 결과를 보장하는 2-근사 알고리즘(2-approximation)이다.

 

 

최근접 이웃 (Nearest Neighbor) 알고리즘

출발점에서 시작해서 가장 가까운 도시부터 방문해 나가는 방식이다. 정점을 한 번씩만 방문하고, 모든 도시를 돌고 나면 다시 출발점으로 돌아간다. 

 

1. 시작 정점을 임의로 선택

2. 현재 정점에서 가장 가까운 미방문 정점으로 이동

3. 모든 정점을 한 번씩 방문할 때까지 반복

4. 마지막 정점에서 시작 정점으로 돌아와 순환 경로 완성

 

def tsp_nearest_neighbor(graph, start=0):
    n = len(graph)
    visited = [False] * n
    path = [start]
    total_cost = 0
    current = start
    visited[current] = True

    for _ in range(n - 1):
        nearest = None
        min_dist = float('inf')
        for i in range(n):
            if not visited[i] and graph[current][i] < min_dist:
                nearest = i
                min_dist = graph[current][i]
        visited[nearest] = True
        path.append(nearest)
        total_cost += min_dist
        current = nearest

    # 돌아오는 거리 추가
    total_cost += graph[current][start]
    path.append(start)
    return total_cost, path

# 테스트용 대칭 거리 행렬
graph = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

cost, path = tsp_nearest_neighbor(graph)
print(f"근사 비용: {cost}")
print(f"근사 경로: {path}")

"""
근사 비용: 80
근사 경로: [0, 1, 3, 2, 0]
"""

 

(한 번의 탐색마다 O(n) 거리 계산) * (n개 도시) = O(n^2)의 시간복잡도를 가진다.

 

구현이 간단하고 빠르고 직관적이지만, 초기 시작점에 따라 결과가 달라지며 지역 최적 해에 빠지기 쉽다. 최악의 경우 낮은 수준의 근사율을 가질 수 있어 최적해보다 빠른 근사해가 필요한 시스템에 활용되거나 대규모 TSP문제 등에 활용하거나 최적해를 개선하기 위한 방식들로 개선한다.

 

1. Multi-Start Nearest Neighbor

- n개의 정점을 모두 출발점으로 시도, 최적 경로 선택

- 시간복잡도 O(n^3)까지 증가하지만 품질이 향상된다.

 

2. 2-opt / 3-opt 알고리즘

- 최근접 이웃으로 얻은 경로에서 두 정점 간 경로를 교환하여 더 짧은 경로 탐색

- 지역 최적해 탈출 가능

 

3. 다른 휴리스틱과 결합

- MST 기반 알고리즘, Christofiedes 알고리즘 등과 비교 및 결합 가능

728x90
반응형

'Coding > Algorithm' 카테고리의 다른 글

O(n^2) - 이차 시간  (1) 2025.07.12
O(2^n) - 지수 시간  (1) 2025.07.12
P, NP  (0) 2025.07.08
O(n!) - 팩토리얼 시간  (2) 2025.07.08
빅-오(Big-O) 표기법  (1) 2025.07.08

Polynomial time

다항 시간

다항 시간이란 알고리즘의 실행 시간이 입력 크기 n에 대한 다항식으로 표현되는 경우를 말합니다. 이는 O(n^k ) (k는 양의 상수)와 같은 형태로 나타나는 시간 복잡도를 의미한다.

 

O(n), O(n²), O(n³ + n² + 3), O(log n), O(1) 등은 모두 다항 시간으로 분류되는데 O(log n), O(1)의 경우 엄밀히 말하면 다항식은 아니지만 다항 시간보다 훨씬 효율적이므로 넓은 의미에서 다항 시간 범주에 포함된다.

 

반면 O(2ⁿ), O(n!)과 같은 복잡도는 다항 n이 커질수록 기하급수적으로 실행시간이 폭증하여 다항 시간이 아니며, 이런 알고리즘은 대개 비실용적으로 간주한다.

 

어떤 문제에 대해 다항 시간 내에 항상 정답을 찾을 수 있는 알고리즘이 존재한다면, 그 문제는 Class P에 속한다. 

NP

비결정적 다항 시간(Nondeterministic Polynomial time)이란, 어떤 문제에 대해 정답이 주어졌을 때, 그 정답이 올바른지 다항 시간 내에 검증이 가능한 문제들을 말한다.

 

즉, 해를 찾는 과정은 어려울 수 있지만, 해가 주어졌을 때 그 해를 확인하는 것은 쉽고 빠르다.

 

예를 들어 아주 큰 숫자를 소인수분해하는 것은 시간이 오래 걸리는 어려운 문제이다. 하지만 누군가 소인수의 정답을 알려준다면, 그 답들을 곱해서 원래 숫자가 나오는지 확인하기만 하면 되며 이 곱셈 연산은 다항 시간 안에 완료할 수 있으므로 이런 문제를 NP에 속한다고 한다.

 

NP-complete

NP에 속하는 문제들 중에서 가장 어려운 문제들의 집합이다. 

- NP에 속한다 : 정답이 주어졌을 때 다항 시간 내에 검증이 가능하다.

- NP-환원성 : NP에 속하는 모든 다른 문제들을 다항 시간 내에 NP-complete 문제로 변환할 수 있다.

 

NP-환원성은 핵심적인 특징으로 이는 NP-complete 문제 중 하나라도 다항 시간 내에 해결할 수 있는 알고리즘을 찾는다면, 이론적으로 NP에 속하는 모든 문제도 다항 시간 내에 해결할 수 있게 된다는 의미를 가진다.

 

예) SAT 만족 가능성 문제, 3-CNF SAT, TSP(결정형), 그래프 색칠 문제

 

NP-hard

NP-complete보다 더 넓은 개념으로, NP의 모든 문제만큼 어렵거나 그 이상일 수 있는 문제들이다. NP-complete와 유사하게 NP에 속하는 모든 문제를 다항 시간 내에 자기 자신으로 환원할 수 있어야 하지만 반드시 NP에 속할 필요는 없다. 즉, 해가 주어져도 그 검증조차 다항 시간 안에 불가능할 수 있다. 주로 최적값 찾기 문제나 결정 불가능한 문제들이 NP-hard에 속한다.

 

예) TSP(최적 경로 길이 구하기), 체스 문제, 할터 문제(Halting Problem)

 

┌─── P (다항 시간에 풀 수 있는 문제들)

├─── NP (정답 검증이 다항 시간인 문제들)
│          │

│          └─ NP-complete (NP 중 가장 어려운 문제들)

└─── NP-hard (NP보다 어려울 수도 있는 문제들)
            │

            └─ NP-complete ⊆ NP-hard

 

 

P vs NP

밀레니엄 문제 중 하나로, P와 NP 사이의 관계는 아직도 해결되지 못한 문제이다.

 

- P : 다항 시간 내에 문제를 풀 수 있는 문제들의 집합이다.

- NP : 정답이 주어졌을 때, 그 정답이 다항 시간 내에 검증될 수 있는 문제들의 집합이다.

 

다항 시간 안에 해를 찾을 수 있는 문제라면 당연히 그 해가 맞는지도 다항 시간 안에 검증할 수 있기 때문에 P ⊆ NP는 항상 참이다. 진정한 문제는 P = NP인가 P ≠ NP인가에 대한 질문으로, 정답을 빠르게 검증할 수 있다면 답을 빠르게 구할 수도 있는가?이다.

728x90
반응형

'Coding > Algorithm' 카테고리의 다른 글

O(2^n) - 지수 시간  (1) 2025.07.12
NP - TSP  (1) 2025.07.11
O(n!) - 팩토리얼 시간  (2) 2025.07.08
빅-오(Big-O) 표기법  (1) 2025.07.08
시간 복잡도  (1) 2025.07.08

O(n!) - 팩토리얼 시간

주어진 배열의 원소들을 가능한 모든 순서로 배열하는 것을 순열 생성의 모든 경우의 수이다. 여기서 순열은 일반적인 순열인 직순열로 일직선상의 배열이다.

 

이러한 연산에서 n개 원소는 n! 개의 순열이 존재하고, 각 순열을 생성하는 데 걸리는 시간을 포함한 전체 시간 복잡도는 n! * n = O(n!)이다.

 

순열 생성

배열 [1, 2, 3]가 있을 때, 가능한 모든 순열은 다음과 같다.

 

[1, 2, 3], [1, 3, 2],

[2, 1, 3], [2, 3, 1],

[3, 1, 2], [3, 2, 1]

 

총 3! = 6가지 경우가 존재한다.

 

코드로 표현하면 다음과 같다.

def permutations(arr):
    if len(arr) <= 1:
        return [arr]
    result = []
    for i in range(len(arr)):
        # ':' 슬라이싱, :끝 : 처음부터 끝 인덱스 바로 전까지(끝 비포함), 시작: : 시작 인덱스부터 끝까지
        # => :i i인덱스를 제외한 그 앞의 집합, i+1: 다음 인덱스까지의 집합, 길이 초과하는 경우 빈 배열
        rest = arr[:i] + arr[i+1:] 
        for p in permutations(rest): # 
            result.append([arr[i]] + p) # append : 리스트 객체 맨 끝에 새로운 요소 추가
    return result

print(permutations([1, 2, 3]))

"""
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
"""


1. 하나의 인덱스를 고정한다.

2. 나머지 요소들의 순열을 재귀적으로 구한다.

3. 그 앞에 고정 요소를 붙여서 순열을 구성한다.

 

이 방식은 재귀 호출마다 n-1개의 원소로 순열을 생성하며, 전체 시간 복잡도는 O(n!)이다.

 

외판원 문제(TSP, Travelling Salesman Problem)

외판원이 n개의 도시를 모두 방문하고 출발점으로 돌아오는 최단 경로를 찾는 문제이다.

NP-hard 문제의 대표적인 예시로 자주 사용된다.

 

조건

- 각 도시는 정확히 한 번씩만 방문한다.

- 모든 도시 간의 거리가 주어진다.

 

이 문제는 다양한 해결법이 존재하지만 그중에서 브루트포스 접근법이 O(n!)의 시간 복잡도를 가진다.

 

브루트포스

4개 도시 A, B, C, D가 있을 때, 가능한 모든 경로를 확인한다.

A -> B -> C -> D -> A

A -> B -> D -> C -> A

...

 

다시 출발점으로 돌아오기 때문에 원순열로 취급할 수 있어 시작점을 A로 고정하고 모든 경로를 구한다.

나머지 n-1개 도시의 순열을 구한다. (n-1)!

4개 도시 -> (4 - 1)! = 6가지

 

import itertools

def tsp_bruteforce(distance):
    # distance : 2D 배열, distance[i][j] : 도시 i에서 j로의 거리
    n = len(distance)
    cities = list(range(1, n)) # 시작 도시(0번)를 고정한 상태에서 나머지 도시의 순열을 생성

    min_cost = float('inf')
    best_path = None

	# itertools.permutations : 순열을 생성해준다.
    # 내부적으로 최적화가 잘되어있어 메모리 효율이 좋다. 시간복잡도는 그대로 O(n!)
    for path in itertools.permutations(cities):
        current_cost = 0
        current_city =0

        for next_city in path:
            current_cost += distance[current_city][next_city]
            current_city = next_city

        current_cost += distance[current_city][0]

        if current_cost < min_cost:
            min_cost = current_cost
            best_path = [0] + list(path) + [0]

    return min_cost, best_path

distance = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

city_names = ["A", "B", "C", "D"]

cost, path = tsp_bruteforce(distance)
print(f"Min cost : {cost}")
print(f"Best path : {path}")

named_path = ' -> '.join(city_names[i] for i in path)
print(f"Best path : {named_path}")

"""
Min cost : 80
Best path : [0, 1, 3, 2, 0]
Best path : A -> B -> D -> C -> A
"""

 

순열생성

O((n-1)!), n-1개 도시의 모든 순열 생성 

 

각 경로 비용 계산

O(n), 각 순열마다 n개 도시를 거쳐가는 비용 계산

 

전체 시간복잡도

O(n * (n-1)!) = O(n!)

 

브루트포스의 가장 큰 문제점은 도시의 수가 조금만 늘어나도 실행 시간이 급격하게 증가하여 계산이 불가능해진다.

 

계산 시간 테스트 코드

도시의 개수를 추가하고 경과시간을 체크해 본다.

import time
import itertools
import random

def generate_distance_matrix(n):
    matrix = [[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(i+1, n):
            dist = random.randint(1, 99)
            matrix[i][j] = dist
            matrix[j][i] = dist
    return matrix

def tsp_bruteforce(distance):
    n = len(distance)
    cities = list(range(1, n))

    min_cost = float('inf')
    best_path = None

    for path in itertools.permutations(cities):
        current_cost = 0
        current_city = 0

        for next_city in path:
            current_cost += distance[current_city][next_city]
            current_city = next_city

        current_cost += distance[current_city][0]

        if current_cost < min_cost:
            min_cost = current_cost
            best_path = [0] + list(path) + [0]

    return min_cost, best_path

# 테스트 도시 수: 4 ~ 10
for n in range(4, 11):
    print(f"\n=== TSP for {n} cities ===")
    distance = generate_distance_matrix(n)

    start = time.perf_counter()
    cost, path = tsp_bruteforce(distance)
    end = time.perf_counter()
    elapsed = end - start

    print(f"Min cost: {cost}")
    print(f"Best path (index): {path}")
    print(f"Elapsed time: {elapsed:.6f} seconds")

"""
=== TSP for 4 cities ===
Min cost: 209
Best path (index): [0, 1, 2, 3, 0]
Elapsed time: 0.000019 seconds

=== TSP for 5 cities ===
Min cost: 167
Best path (index): [0, 2, 1, 3, 4, 0]
Elapsed time: 0.000019 seconds

=== TSP for 6 cities ===
Min cost: 159
Best path (index): [0, 3, 1, 2, 5, 4, 0]
Elapsed time: 0.000077 seconds

=== TSP for 7 cities ===
Min cost: 186
Best path (index): [0, 5, 2, 1, 4, 3, 6, 0]
Elapsed time: 0.000502 seconds

=== TSP for 8 cities ===
Min cost: 161
Best path (index): [0, 3, 1, 2, 4, 6, 7, 5, 0]
Elapsed time: 0.019747 seconds

=== TSP for 9 cities ===
Min cost: 172
Best path (index): [0, 4, 5, 8, 2, 7, 3, 1, 6, 0]
Elapsed time: 0.157354 seconds

=== TSP for 10 cities ===
Min cost: 236
Best path (index): [0, 2, 3, 6, 1, 9, 4, 5, 8, 7, 0]
Elapsed time: 1.502671 seconds
"""

 

10개까지의 테스트는 실행이 되었지만 테스트를 위해 사용한 웹 컴파일러는 15초 이상의 작업은 실패로 처리하는데 11개의 도시 테스트에서 실패로 처리되었다.

 

수치를 추정해 보면,

10개의 도시인 경우 10! = 3,628,800개의 경우의 수를 처리하는데 1.5초의 소요 시간이 걸렸다.

11개의 도시는 11! = 39,916,800개로 약 11배가 증가했으므로 추정 소요 시간은 16.5초로 예상된다.

도시 수 순열 수 예상 시간 (초)
10 3,628,800 1.5
11 39,916,800 16.5
12 479,001,600 198+ 초 (약 3.3분)
13 6,227,020,800 약 27~30분
14 87,178,291,200 5시간 이상
 
사용법은 간단하지만 한계가 명확하기 때문에 실용적이지 않아 다른 효율적인 방법으로 대체된다.
 
동적 계획법 (O(n^2 * 2^n))
정확한 해를 구할 수 있는 방법으로, 방문 상태를 비트마스크로 표현하여 중복 계산을 줄인다.
 
근사 알고리즘(다항시간)
최적 해는 아니지만, 일정한 오차 범위 내에서 빠르게 좋은 해를 보장한다.
대표적으로 MST 기반 알고리즘이 있다.
 
휴리스틱 기법
엄밀한 최적 보장은 없지만, 실제 환경에서 유용하게 사용된다. 
유전 알고리즘(GA)이나 시뮬레이티드 어닐링(SA)들이 이에 해당한다.

 

728x90
반응형

'Coding > Algorithm' 카테고리의 다른 글

O(2^n) - 지수 시간  (1) 2025.07.12
NP - TSP  (1) 2025.07.11
P, NP  (0) 2025.07.08
빅-오(Big-O) 표기법  (1) 2025.07.08
시간 복잡도  (1) 2025.07.08

빅-오(Big-O) 표기법

빅-오(Big-O) 표기법은 알고리즘이 입력 크기(n)에 따라 수행 시간이나 연산 횟수가 어떻게 증가하는지를 나타내는 수학적 표기법이다. 보통 최악의 경우(Worst Case) 기준으로 시간 복잡도를 분석하며, 다양한 알고리즘의 효율성을 비교하는 데 활용된다.

 

https://en.wikipedia.org/wiki/File:Comparison_computational_complexity.svg

 

시간 복잡도는 입력 크기에 따른 실행 시간의 증가율에 따라 여러 등급으로 나뉘며 다음은 효율이 낮은 순서부터 정리한 목록이다.

O(n!) - 팩토리얼 시간

가능한 모든 순열을 탐색하는 경우

외판원 문제(TSP), 순열 생성 등

 

O(2^n) - 지수 시간

모든 부분 조합이나 경우의 수를 탐색할 때

부분집합 생성, 피보나치(재귀), DFS/백트래킹 등

 

O(n^2) - 이차 시간

이중 루프를 사용하는 비교 기반 알고리즘

버블 정렬, 선택 정렬 등

 

O(n log n) - 선형 로그 시간

효율적인 비교 기반 정렬 알고리즘의 평균/최선 시간

병합 정렬, 힙 정렬, 퀵 정렬(평균적 경우)

 

O(n) - 선형 시간

입력 전체를 한 번 순회하는 경우

배열을 전체 탐색

 

O(log n) - 로그 시간

입력이 절반씩 줄어드는 알고리즘

이진 탐색, 힘 삽입/삭제 등

 

O(1) - 상수 시간

입력 크기와 무관하게 항상 일정한 시간

배열 인덱스 접근, 해시맵 키 조회

 

 

 

 

 

 

 

728x90
반응형

'Coding > Algorithm' 카테고리의 다른 글

O(2^n) - 지수 시간  (1) 2025.07.12
NP - TSP  (1) 2025.07.11
P, NP  (0) 2025.07.08
O(n!) - 팩토리얼 시간  (2) 2025.07.08
시간 복잡도  (1) 2025.07.08

시간 복잡도(Time Complexity)

시간 복잡도는 알고리즘이 입력 코기(n)에 따라 얼마나 많은 연산을 수행하는지를 수학적으로 표현한 것이다.

보통 알고리즘의 효율성과 실행 속도를 평가하기 위해 사용된다.

 

시간 복잡도는 주로 세 가지 표기법으로 분류된다.

 

빅-오(Big-O)

최악의 경우(Worst Case)를 나타내며, 가장 많이 사용되는 표기법이다. 알고리즘이 가장 오래 걸리는 상황에서의 연산 횟수를 설명한다.

 

빅-오메가(Big-Ω)

최선의 경우(Best Case) 를 나타내며, 가장 적게 걸리는 상황에서의 연산 횟수를 설명한다.

 

빅-세타(Big-Θ)

상한과 하한이 같을 때 사용되며, 정확한 수행 시간을 나타낸다.

 

예시

다음은 1~100 사이에서 무작위 숫자를 뽑고, 해당 숫자를 찾을 때까지 순회하는 알고리즘이다.

 

import random

randNumber = random.randrange(1, 101)

for i in range(1, 101):
    if i == randNumber:
        print(i)
        break

 

Best Case

뽑은 숫자가 1일 경우, 단 1번만에 찾는다 → Ω(1)

 

Average Case

1 일 때 1번

2 일 때 2번

...

n 일 때 n번

 

전체 평균 횟수를 계산하면 1 + 2 + ... + n으로 등차수열을 계산하면 n(n + 1) / 2, 이는 입력 크기 n이 커질수록 선형적으로 증가하므로, Average Case는 O(n)으로 표현한다.

 

Worst Case

뽑은 숫자가 100일 경우, 100번 순회 → O(n)

728x90
반응형

'Coding > Algorithm' 카테고리의 다른 글

O(2^n) - 지수 시간  (1) 2025.07.12
NP - TSP  (1) 2025.07.11
P, NP  (0) 2025.07.08
O(n!) - 팩토리얼 시간  (2) 2025.07.08
빅-오(Big-O) 표기법  (1) 2025.07.08

1번 행렬 덧셈

문제

N * M 크기의 두 행렬 A와 B가 주어졌을 때, 두 행렬을 더하는 프로그램을 작성하시오.

 

입력

첫째 줄에 행렬의 크기 N과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 차례대로 주어진다.

이어서 N개의 줄에 행렬 B의 원소 M개가 차례대로 주어진다. N과 M은 100보다 작거나 같고, 행렬의 원소는 절댓값이 100보다 작거나 같은 정수이다.

 

출력

첫째 줄부터 N개의 줄에 행렬 A와 B를 더한 행렬을 출력한다. 행렬의 각 원소는 공백으로 구분한다.

 

C++

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int n, m;
    cin >> n >> m;
    vector<vector<int>> arr_2d(n, vector<int>(m));
    
    for (int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> arr_2d[i][j];
        }
    }
    for (int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            int val = 0;
            cin >> val;
            cout << arr_2d[i][j] + val << " ";
        }
        cout << "\n";
    }
}

 

C#

using System;
using System.Collections;
using System.Collections.Generic;
class Program{
    static void Main(string[] args){
        string input = Console.ReadLine();
        string[] input_arr = input.Split();
        int n = int.Parse(input_arr[0]);
        int m = int.Parse(input_arr[1]);
        int[][] arr_2d = new int[n][];
        
        for (int i = 0; i < n; i++){
            arr_2d[i] = new int[m];
        }
        
        for (int i = 0; i < n; i++)
        {
            string[] arr_val = Console.ReadLine().Split();
            for (int j = 0; j < m; j++)
            {
                arr_2d[i][j] = int.Parse(arr_val[j]);
            }
        }
        for (int i = 0; i < n; i++)
        {
            string[] arr_val = Console.ReadLine().Split();
            for (int j = 0; j < m; j++)
            {
                arr_2d[i][j] += int.Parse(arr_val[j]);
                Console.Write(arr_2d[i][j] + " ");
            }
            Console.WriteLine();
        }
    }
}

 

Python

n, m = map(int, input().split())
arr_2d_1 = [list(map(int, input().split())) for _ in range(n)]
arr_2d_2 = [list(map(int, input().split())) for _ in range(n)]
result = [[arr_2d_1[i][j] + arr_2d_2[i][j] for j in range(m)] for i in range(n)]
for row in result:
    print(' '.join(map(str, row)))

 

Node.js

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin', 'utf8').trim().split('\n');
const [n, m] = input[0].split(' ').map(Number);
const arr1 = [];
const arr2 = [];

for (let i = 1; i <= n; i++){
    arr1.push(input[i].split(' ').map(Number));
}

for (let i = n + 1; i <= 2 * n; i++){
    arr2.push(input[i].split(' ').map(Number));
}

var result = [];
for (let i = 0; i < n; i++){
    const row = [];
    for (let j = 0; j < m; j++){
        row.push(arr1[i][j] + arr2[i][j]);
    }
    result.push(row);
}

result.forEach(row => console.log(row.join(' ')));

 

2번 최댓값

문제

<그림 1>과 같이 9×9 격자판에 쓰인 81개의 자연수 또는 0이 주어질 때, 이들 중 최댓값을 찾고 그 최댓값이 몇 행 몇 열에 위치한 수인지 구하는 프로그램을 작성하시오. 예를 들어, 다음과 같이 81개의 수가 주어지면

https://www.acmicpc.net/problem/2566

 

이들 중 최댓값은 90이고, 이 값은 5행 7열에 위치한다.

 

입력

첫째 줄부터 아홉 번째 줄까지 한 줄에 아홉 개씩 수가 주어진다. 주어지는 수는 100보다 작은 자연수 또는 0이다.

 

출력

첫째 줄에 최댓값을 출력하고, 둘째 줄에 최댓값이 위치한 행 번호와 열 번호를 빈칸을 사이에 두고 차례로 출력한다. 최댓값이 두 개 이상인 경우 그중 한 곳의 위치를 출력한다.

 

이차원 배열에 저장하고 순회하면서 가장 큰 숫자를 찾고 그 숫자와 인덱스를 출력하면 되는 문제다. 그런데 이차원 배열을 굳이 만들지 않아도 입력을 처리할 때 바로 큰 수와 인덱스를 찾을 수 있긴 하다. 처음 풀이는 의도에 맞게 풀고 그 이후는 간단한 방법을 사용해 본다.

 

C++

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int n = 9;
    vector<vector<int>> arr_2d(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr_2d[i][j];
        }
    }
    
    
    int max_val = arr_2d[0][0];
    int max_row = 0;
    int max_col = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr_2d[i][j] > max_val) {
                max_val = arr_2d[i][j];
                max_row = i;
                max_col = j;
            }
        }
    }
    cout << max_val << "\n";
    cout << max_row + 1 << " " << max_col + 1;
    
    return 0;
}

 

C#

using System;
class Program{
    static void Main(string[] args){
        int n = 9;
        int maxVal = 0;
        int row = 0;
        int col = 0;
        for (int i = 0; i < n; i++){
            string[] strArr = Console.ReadLine().Split();
            for (int j = 0; j < n; j++){
                int tmpVal = int.Parse(strArr[j]);
                if (tmpVal > maxVal){
                    maxVal = tmpVal;
                    row = i;
                    col = j;
                }
            }
        }
        Console.WriteLine($"{maxVal}");
        Console.WriteLine($"{row + 1} {col + 1}");
    }
}

 

Python

max_val = 0;
col = 0;
row = 0;
for i in range(9):
    arr = list(map(int, input().split()))
    for j in range(9):
        tmp_val = arr[j]
        if max_val < tmp_val:
            max_val = tmp_val
            row = i;
            col = j;
print(f"{max_val}\n{row + 1} {col + 1}")

 

Node.js

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin', 'utf8').trim().split('\n');
let col = 0;
let row = 0;
let max_val = 0;
for (let i = 0; i < 9; i++){
    const arr = input[i].split(' ').map(Number);
    for (let j = 0; j < 9; j++){
        if (arr[j] > max_val){
            max_val = arr[j];
            row = i;
            col = j;
        }
    }
}
console.log(`${max_val}\n${row + 1} ${col + 1}`);

 

3번 세로 읽기

문제

아직 글을 모르는 영석이가 벽에 걸린 칠판에 자석이 붙어있는 글자들을 붙이는 장난감을 가지고 놀고 있다. 이 장난감에 있는 글자들은 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’부터 ‘9’이다. 영석이는 칠판에 글자들을 수평으로 일렬로 붙여서 단어를 만든다. 다시 그 아래쪽에 글자들을 붙여서 또 다른 단어를 만든다. 이런 식으로 다섯 개의 단어를 만든다. 아래 그림 1은 영석이가 칠판에 붙여 만든 단어들의 예이다.

A A B C D D
a f z z 
0 9 1 2 1
a 8 E W g 6
P 5 h 3 k x
<그림 1>

 

한 줄의 단어는 글자들을 빈칸 없이 연속으로 나열해서 최대 15개의 글자들로 이루어진다. 또한 만들어진 다섯 개의 단어들의 글자 개수는 서로 다를 수 있다. 심심해진 영석이는 칠판에 만들어진 다섯 개의 단어를 세로로 읽으려 한다. 세로로 읽을 때, 각 단어의 첫 번째 글자들을 위에서 아래로 세로로 읽는다. 다음에 두 번째 글자들을 세로로 읽는다. 이런 식으로 왼쪽에서 오른쪽으로 한 자리씩 이동하면서 동일한 자리의 글자들을 세로로 읽어 나간다. 위의 그림 1의 다섯 번째 자리를 보면 두 번째 줄의 다섯 번째 자리의 글자는 없다. 이런 경우처럼 세로로 읽을 때 해당 자리의 글자가 없으면, 읽지 않고 그다음 글자를 계속 읽는다. 그림 1의 다섯 번째 자리를 세로로 읽으면 D1gk로 읽는다. 그림 1에서 영석이가 세로로 읽은 순서대로 글자들을 공백 없이 출력하면 다음과 같다: Aa0aPAf985Bz1EhCz2W3D1gkD6x 칠판에 붙여진 단어들이 주어질 때, 영석이가 세로로 읽은 순서대로 글자들을 출력하는 프로그램을 작성하시오.

 

입력

총 다섯 줄의 입력이 주어진다. 각 줄에는 최소 1개, 최대 15개의 글자들이 빈칸 없이 연속으로 주어진다. 주어지는 글자는 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’부터 ‘9’ 중 하나이다. 각 줄의 시작과 마지막에 빈칸은 없다.

 

출력

영석이가 세로로 읽은 순서대로 글자들을 출력한다. 이때, 글자들을 공백 없이 연속해서 출력한다.

 

C++

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
int main(){
    int max_col = 15;
    string line;
    vector<vector<char>> matrix;
    for (int i = 0; i < 5; i++){
        getline(cin, line);
        vector<char> row(line.begin(), line.end());
        matrix.push_back(row);
    }
    for (int col = 0; col < max_col; col++){
        for (int row = 0; row < matrix.size(); row++){
            if (col < matrix[row].size()){
                cout << matrix[row][col];
            }
        }
    }
    return 0;
}

 

C#

using System;
using System.Collections.Generic;
using System.Linq;
class Program{
    static void Main(string[] args){
        int max_col = 15;
        string line;
        List<List<char>> matrix = new List<List<char>>();
        
        while((line = Console.ReadLine()) != null){
            matrix.Add(line.ToList());
        }

        for (int col = 0; col < max_col; col++){
            for (int row = 0; row < matrix.Count; row++){
                if (matrix[row].Count > col){
                    Console.Write(matrix[row][col]);
                }
            }
        }
    }
}

 

Python

max_row = 5;
max_col = 15;
matrix = [list(input()) for _ in range(max_row)]
for col in range(max_col):
    for row in range(max_row):
        if col < len(matrix[row]):
            print(matrix[row][col], end="")

 

Node.js

const fs = require('fs');
const max_row = 5;
const max_col = 15;
const input = fs.readFileSync('/dev/stdin', 'utf8').trim().split('\n');
for (let col = 0; col < max_col; col++){
    for (let row = 0; row < max_row; row++){
        if (col < input[row].length) {
            process.stdout.write(input[row][col]);    
        }
    }
}

 

4번 색종이

문제

가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오.

https://www.acmicpc.net/problem/2563

 

예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다.

 

입력

첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리이다. 색종이의 수는 100 이하이며, 색종이가 도화지 밖으로 나가는 경우는 없다.

 

출력

첫째 줄에 색종이가 붙은 검은 영역의 넓이를 출력한다.

 

2차원 배열 카테고리의 마지막 문제라서 그런가 단순 값 처리가 아닌 응용이 필요한 문제이다.

100 x 100 크기의 도화지란 배열의 최대 크기를 정한 것으로 [100][100] 크기의 2차원 배열 안에서 이루어지는 작업이다.

색종이는 모두 동일한 크기로 최대 100개까지 붙인다. 색종이 크기는 모두 일정한 10 x 10이며 왼쪽 하단의 꼭짓점에 대한 좌표가 주어진다.

 

당장은 두 가지 방법이 떠오른다.

1. 도화지에서 색종이가 없는 영역 구하기

2. 전체 색종이 개수의 영역에서 겹치는 부분 제외하기

 

2차원 배열의 구조를 기준으로 생각해 본다.

100 x 100 크기에서 입력된 색종이 범위만큼 인덱스를 체크해 놓고 최종적으로 체크한 부분만 계산하면 색종이가 덮은 영역이 나온다.

C++

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int count = 0;
    int matrix[100][100] = {0};
    cin >> count;
    for (int i = 0; i < count; i++){
        int x1, y1, x2, y2 = 0;
        cin >> x1;
        cin >> y1;
        x2 = x1 + 10;
        y2 = y1 + 10;
        for (int x = x1; x < x2; x++){
            for (int y = y1; y < y2; y++){
                matrix[x][y] = -1;
            }
        }
    }
    
    int area = 0;
    for (int row = 0; row < 100; row++){
        for (int col = 0; col < 100; col++){
            if (matrix[row][col] == -1){
                area++;
            }
        }
    }
    cout << area;
    return 0;
}

 

 

중복으로 겹쳐진 부분을 체크하는 부분을 조건을 주고 확인하는 걸 추가해도 될 것 같다.

 

C#

C++로 코드를 쓰면서 방식에 문제가 없으니 좀 더 정리해서 작성해 본다.

using System;
class Program{
    static void Main(string[] args){
        int[,] matrix = new int[100, 100];
        int count = int.Parse(Console.ReadLine()!);
        
        for (int i = 0; i < count; i++){
            string? input = Console.ReadLine();
            if (string.IsNullOrEmpty(input)) return;
            string[] xy = input.Split();
            int x = int.Parse(xy[0]);
            int y = int.Parse(xy[1]);
            
            for (int dx = x; dx < x + 10; dx++){
                for (int dy = y; dy < y + 10; dy++){
                    matrix[dx, dy] = -1;
                }
            }
        }
        
        int area = 0;
        for (int row = 0; row < 100; row++){
            for (int col = 0; col < 100; col++){
                if (matrix[row, col] == -1){
                    area++;
                }
            }
        }
        Console.WriteLine(area);
    }
}

 

Python

count = int(input());
matrix = [[0] * 100 for _ in range(100)]
for _ in range(count):
    x, y = map(int, input().split())
    for dx in range(x, x + 10):
        for dy in range(y, y + 10):
            matrix[dx][dy] = 1
area = sum(row.count(1) for row in matrix)
print(area)

 

Node.js

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin', 'utf8').trim().split('\n');
const count = parseInt(input[0]);
let matrix = Array.from({length : 100 }, () => Array(100).fill(0));
for (let i = 1; i <= count; i++){
    const xy = input[i].split(" ").map(Number);
    const x = xy[0];
    const y = xy[1];
    for (let dx = x; dx < x + 10; dx++){
        for (let dy = y; dy < y + 10; dy++){
            matrix[dx][dy] = 1;
        }
    }
}
let area = 0;
for (let row = 0; row < 100; row++){
    for (let col = 0; col < 100; col++){
        if (matrix[row][col] == 1){
            area++;
        }
    }
}
console.log(area);

 

728x90
반응형

6번 크로아티아 알파벳

문제

예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다.

 

크로아티아 알파벳 변경
č c=
ć c-
dz=
đ d-
lj lj
nj nj
š s=
ž z=

 

예를 들어, ljes=njak은 크로아티아 알파벳 6개(lj, e, š, nj, a, k)로 이루어져 있다. 단어가 주어졌을 때, 몇 개의 크로아티아 알파벳으로 이루어져 있는지 출력한다. dž는 무조건 하나의 알파벳으로 쓰이고, d와 ž가 분리된 것으로 보지 않는다. lj와 nj도 마찬가지이다. 위 목록에 없는 알파벳은 한 글자씩 센다.

 

입력

첫째 줄에 최대 100글자의 단어가 주어진다. 알파벳 소문자와 '-', '='로만 이루어져 있다.

 

단어는 크로아티아 알파벳으로 이루어져 있다. 문제 설명의 표에 나와있는 알파벳은 변경된 형태로 입력된다.

 

출력

입력으로 주어진 단어가 몇 개의 크로아티아 알파벳으로 이루어져 있는지 출력한다.

 

입력되는 문자열에서 대응하는 크로아티아 문자열이 있는지 확인하여 글자 수를 구한다.

 

C++

#include <iostream>
#include <string>
using namespace std;
int main(){
    string input;
    cin >> input;
    int char_cnt = 0;
    string str_arr[8] = {"c=", "c-", "dz=", "d-", "lj", "nj", "s=", "z="};
    for (int i = 0; i < input.length(); i++){
        bool matched = false;
        for (int j = 0; j < 8; j++){
            string croatian_char = str_arr[j];
            if (input.substr(i, croatian_char.length()) == croatian_char){
                char_cnt++;
                i += croatian_char.length() - 1;
                matched = true;
                break;
            }
        }
        if (!matched){
            char_cnt++;
        }
    }
    cout << char_cnt;
    return 0;
}

 

크로아티아 문자를 배열에 저장해 두고 입력된 문자열을 순회하면서 크로아티아 문자가 포함되어 있는지 검사한다.

 

검사할 때 크로아티아 문자 배열을 순회하면서 하나씩 입력된 문자열의 인덱스를 기준으로 동일한지 검사한다.

 

C#

using System;
class Program{
    static void Main(string[] args){
        string[] str_arr = {"c=", "c-", "dz=", "d-", "lj", "nj", "s=", "z="};
        string input = Console.ReadLine();
        int char_cnt = 0;
        for (int i = 0; i < input.Length; i++){
            bool char_matched = false;
            for (int j = 0; j < str_arr.Length; j++){
                string croatian_char = str_arr[j];
                if (i + croatian_char.Length <= input.Length &&
                    input.Substring(i, croatian_char.Length) == croatian_char){
                    char_cnt++;
                    i += croatian_char.Length - 1;
                    char_matched = true;
                    break;
                }
            }
            if (!char_matched) char_cnt++;
        }
        Console.WriteLine(char_cnt);
    }
}

 

 

Python

input_str = input()
str_arr = ["c=", "c-", "dz=", "d-", "lj", "nj", "s=", "z="]
char_cnt = 0
i = 0
while i < len(input_str):
    is_char_matched = False
    for croatian_char in str_arr:
        if input_str[i:i+len(croatian_char)] == croatian_char:
            char_cnt += 1
            i += len(croatian_char)
            is_char_matched = True
            break
    if not is_char_matched:
        char_cnt += 1
        i += 1
print(char_cnt)

 

Node.js

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin','utf8').trim();
const croatian_chars = ["c=", "c-", "dz=", "d-", "lj", "nj", "s=", "z="];
let char_cnt = 0;
for (let i = 0; i < input.length; i++){
    let is_char_matched = false;
    for (let j = 0; j < croatian_chars.length; j++){
        const croatian_char = croatian_chars[j];
        if (input.slice(i, i + croatian_char.length) === croatian_char){
            char_cnt += 1;
            i += croatian_char.length - 1;
            is_char_matched = true;
            break;
        }
    }
    if (!is_char_matched){
        char_cnt += 1;
    }
}
console.log(char_cnt);

 

7번 그룹 단어 체커

문제

그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다. 

 

단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 단어의 개수 N이 들어온다. N은 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 단어가 들어온다. 단어는 알파벳 소문자로만 되어있고 중복되지 않으며, 길이는 최대 100이다.

 

출력

첫째 줄에 그룹 단어의 개수를 출력한다.

 

N개의 입력을 받아서 해당 단어가 연속되는 문자인지 확인을 해야 한다. 연속은 동일한 문자 사이에 다른 문자가 등장했을 때 연속성이 깨진다.

 

C++

#include <iostream>
#include <string>
using namespace std;
int main(){
    int n;
    cin >> n;
    
    string word;
    int word_cnt = 0;
    while(cin >> word){
        bool is_seq_word = true;
        int char_arr[26] = {0};
        char last_char = '\0';
        for (char c : word){
            if (c != last_char){
                if (char_arr[c - 'a'] != 0){
                    is_seq_word = false;
                    break;
                }
                char_arr[c - 'a'] = 1;
            }
            last_char = c;
        }
        if (is_seq_word) 
            word_cnt++;
    }
    cout << word_cnt;
    return 0;
}

 

 

 

C#

using System;
class Program{
    static void Main(string[] args){
        int n = int.Parse(Console.ReadLine());
        int word_cnt = 0;
        for (int i = 0; i < n; i++){
            char last_char = '\0';
            int[] char_arr = new int[26];
            string word = Console.ReadLine();
            bool is_seq_word = true;
            foreach (char c in word){
                if (c != last_char){
                    if (char_arr[c - 'a'] != 0){
                        is_seq_word = false;
                        break;
                    }
                    char_arr[c - 'a'] = 1;
                }
                last_char = c;
            }
            if (is_seq_word)
                word_cnt++;
        }
        Console.WriteLine(word_cnt);
    }
}

 

Python

n = int(input())
word_cnt = 0;
for i in range(n):
    word = input();
    is_seq_word = True
    last_char = '\0'
    char_arr = [0] * 26
    for c in word:
        if c != last_char:
            if char_arr[ord(c) - ord('a')] != 0:
                is_seq_word = False
                break
            char_arr[ord(c) - ord('a')] = 1
        last_char = c
    if is_seq_word:
        word_cnt += 1
print(word_cnt)

 

Node.js

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin','utf8').trim().split('\n');
const n = parseInt(input[0]);
let word_cnt = 0;
for (let i = 1; i <= n; i++){
    const char_arr = Array(26).fill(0);
    const word = input[i];
    let is_seq_word = true;
    let last_char = '\0';
    for (const c of word){
        if (c !== last_char){
            if (char_arr[c.charCodeAt(0) - 'a'.charCodeAt(0)]){
                is_seq_word = false;
                break;
            }
            char_arr[c.charCodeAt(0) - 'a'.charCodeAt(0)] = 1;
        }
        last_char = c;
    }
    if (is_seq_word){
        word_cnt++;
    }
}
console.log(word_cnt);

 

8번 너의 평점은

문제

인하대학교 컴퓨터공학과를 졸업하기 위해서는, 전공평점이 3.3 이상이거나 졸업고사를 통과해야 한다. 그런데 아뿔싸, 치훈이는 깜빡하고 졸업고사를 응시하지 않았다는 사실을 깨달았다! 

 

치훈이의 전공평점을 계산해 주는 프로그램을 작성해 보자. 

 

전공평점은 전공과목별 (학점 × 과목평점)의 합을 학점의 총합으로 나눈 값이다. 

 

인하대학교 컴퓨터공학과의 등급에 따른 과목평점은 다음 표와 같다.

 

A+ 4.5
A0 4.0
B+ 3.5
B0 3.0
C+ 2.5
C0 2.0
D+ 1.5
D0 1.0
F 0.0

 

P/F 과목의 경우 등급이 P 또는 F로 표시되는데, 등급이 P인 과목은 계산에서 제외해야 한다. 

 

과연 치훈이는 무사히 졸업할 수 있을까?

 

입력

20줄에 걸쳐 치훈이가 수강한 전공과목의 과목명, 학점, 등급이 공백으로 구분되어 주어진다.

 

출력

치훈이의 전공평점을 출력한다. 

 

정답과의 절대오차 또는 상대오차가 \(10^{-4}\) 이하이면 정답으로 인정한다.

 

제한

- 1 ≤ 과목명의 길이 ≤ 50

- 과목명은 알파벳 대소문자 또는 숫자로만 이루어져 있으며, 띄어쓰기 없이 주어진다. 입력으로 주어지는 모든 과목명은 서로 다르다.

- 학점은 1.0,2.0,3.0,4.0중 하나이다.

- 등급은 A+, A0, B+, B0, C+, C0, D+, D0, F, P 중 하나이다.

- 적어도 한 과목은 등급이 P가 아님이 보장된다.

 

20과목 정보가 이름, 점수, 등급으로 각 줄에 입력된다.

 

P가 아닌 등급일 때만 점수를 계산한다.

 

C++

#include <iostream>
#include <iomanip>
#include <string>
using namespace std;
int main(){
    float total_score = 0.0f;
    float sum_score = 0.0f;
    for (int i = 0; i < 20; i++){
        string name;
        float score;
        string grade;
        float grade_score;
        cin >> name >> score >> grade;
        if (grade == "A+"){
            grade_score = 4.5;
        }
        else if (grade == "A0"){
            grade_score = 4.0;
        }
        else if (grade == "B+"){
            grade_score = 3.5;
        }
        else if (grade == "B0"){
            grade_score = 3.0;
        }
        else if (grade == "C+"){
            grade_score = 2.5;
        }
        else if (grade == "C0"){
            grade_score = 2.0;
        }
        else if (grade == "D+"){
            grade_score = 1.5;
        }
        else if (grade == "D0"){
            grade_score = 1.0;
        }
        else if (grade == "F"){
            grade_score = 0.0;
        }
        
        if (grade != "P"){
            sum_score += score;
            total_score += score * grade_score;
        }
    }
    float result = total_score / sum_score;
    cout << fixed << setprecision(6) << result;
    return 0;
}

 

C#

using System;
class Program{
    static void Main(string[] args){
        float sum_score = 0f;
        float total_score = 0f;
        for (int i = 0; i < 20; i++){
            string str = Console.ReadLine();
            string[] str_arr = str.Split();
            string name = str_arr[0];
            float score = float.Parse(str_arr[1]);
            string grade = str_arr[2];
            float grade_score = 0f;
            if (grade == "A+"){
                grade_score = 4.5f;
            }
            else if (grade == "A0"){
                grade_score = 4.0f;
            }
            else if (grade == "B+"){
                grade_score = 3.5f;
            }
            else if (grade == "B0"){
                grade_score = 3.0f;
            }
            else if (grade == "C+"){
                grade_score = 2.5f;
            }
            else if (grade == "C0"){
                grade_score = 2.0f;
            }
            else if (grade == "D+"){
                grade_score = 1.5f;
            }
            else if (grade == "D0"){
                grade_score = 1.0f;
            }
            else if (grade == "F"){
                grade_score = 0.0f;
            }
            if (grade != "P"){
                sum_score += score;
                total_score += score * grade_score;
            }
        }
        float result = total_score / sum_score;
        Console.WriteLine(result);
    }
}

 

Python

import sys
sum_score = 0;
total_score = 0;
for i in range(20):
    name, score, grade = sys.stdin.readline().strip().split()
    score = float(score)
    grade_score = 0;
    if grade != "P":
        if grade == "A+":
            grade_score = 4.5
        elif grade == "A0":
            grade_score = 4.0
        elif grade == "B+":
            grade_score = 3.5
        elif grade == "B0":
            grade_score = 3.0
        elif grade == "C+":
            grade_score = 2.5
        elif grade == "C0":
            grade_score = 2.0
        elif grade == "D+":
            grade_score = 1.5
        elif grade == "D0":
            grade_score = 1.0
        elif grade == "F":
            grade_score = 0.0
        sum_score += score
        total_score += score * grade_score
result = total_score / sum_score
print(f"{result:.6f}")

 

Node.js

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin','utf8').trim().split('\n');
let total_score = 0.0;
let sum_score = 0.0;
for (let i = 0; i < 20; i++){
    const str = input[i].split(' ');
    const name = str[0];
    const score = parseFloat(str[1]);
    const grade = str[2];
    let grade_score = 0.0;
    if (grade === "A+")
    {
        grade_score = 4.5;
    }
    else if (grade === "A0")
    {
        grade_score = 4.0;
    }
    else if (grade === "B+")
    {
        grade_score = 3.5;
    }
    else if (grade === "B0")
    {
        grade_score = 3.0;
    }
    else if (grade === "C+")
    {
        grade_score = 2.5;
    }
    else if (grade === "C0")
    {
        grade_score = 2.0;
    }
    else if (grade === "D+")
    {
        grade_score = 1.5;
    }
    else if (grade === "D0")
    {
        grade_score = 1.0;
    }
    else if (grade === "F")
    {
        grade_score = 0.0;
    }
    if (grade != "P"){
        sum_score += score;
        total_score += score * grade_score;
    }
}
const result = total_score / sum_score;
console.log(result.toFixed(6));
728x90
반응형

1번 새싹

문제

아래 예제와 같이 새싹을 출력하시오.

 

입력

입력은 없다.

 

출력

새싹을 출력한다.

 

         ,r'"7
r`-_   ,'  ,/
 \. ". L_r'
   `~\/
      |
      |

 

예제 출력의 모양대로 출력을 한다.

 

C++

#include <iostream>
using namespace std;
int main(){
    cout << "         ,r\'\"7" << "\n";
    cout << "r`-_   ,\'  ,/" << "\n";
    cout << " \\. \". L_r\'" << "\n";
    cout << "   `~\\/" << "\n";
    cout << "      |" << "\n";
    cout << "      |" << "\n";
    return 0;
}

 

 

C#

using System;
class Program{
    static void Main(string[] args){
        Console.WriteLine("         ,r\'\"7");
        Console.WriteLine("r`-_   ,\'  ,/");
        Console.WriteLine(" \\. \". L_r\'");
        Console.WriteLine("   `~\\/");
        Console.WriteLine("      |");
        Console.WriteLine("      |");
    }
}

 

Python

print("         ,r\'\"7")
print("r`-_   ,\'  ,/")
print(" \\. \". L_r\'")
print("   `~\\/")
print("      |")
print("      |")

 

Node.js

console.log("         ,r\'\"7");
console.log("r`-_   ,\'  ,/");
console.log(" \\. \". L_r\'");
console.log("   `~\\/");
console.log("      |");
console.log("      |");

 

2번 킹, 퀸, 룩, 비숍, 나이트, 폰

문제

동혁이는 오래된 창고를 뒤지다가 낡은 체스판과 피스를 발견했다. 

 

체스판의 먼지를 털어내고 걸레로 닦으니 그럭저럭 쓸만한 체스판이 되었다. 하지만, 검은색 피스는 모두 있었으나, 흰색 피스는 개수가 올바르지 않았다. 

 

체스는 총 16개의 피스를 사용하며, 킹 1개, 퀸 1개, 룩 2개, 비숍 2개, 나이트 2개, 폰 8개로 구성되어 있다. 

 

동혁이가 발견한 흰색 피스의 개수가 주어졌을 때, 몇 개를 더하거나 빼야 올바른 세트가 되는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 동혁이가 찾은 흰색 킹, 퀸, 룩, 비숍, 나이트, 폰의 개수가 주어진다. 이 값은 0보다 크거나 같고 10보다 작거나 같은 정수이다.

 

출력

첫째 줄에 입력에서 주어진 순서대로 몇 개의 피스를 더하거나 빼야 되는지를 출력한다. 만약 수가 양수라면 동혁이는 그 개수만큼 피스를 더해야 하는 것이고, 음수라면 제거해야 하는 것이다.

 

입력된 체스말의 개수가 한 세트가 될 수 있도록 개수를 맞춘다.

 

C++

#include <iostream>
using namespace std;
int main(){
    int chess_set[] = {1, 1, 2, 2, 2, 8 };
    int need_val[6];
    int count;
    for (int i = 0; i < 6; i++){
        cin >> count;
        need_val[i] = chess_set[i] - count;
    }
    for (int i : need_val){
        cout << i << " ";
    }
    return 0;
}

 

C#

using System;
class Program{
    static void Main(string[] args){
        int[] chess_set = { 1, 1, 2, 2, 2, 8 };
        string[] input_arr = Console.ReadLine().Split();
        for (int i = 0; i < 6; i++){
            int val = int.Parse(input_arr[i]);
            int need_val = chess_set[i] - val;
            Console.Write($"{need_val} ");
        }
    }
}

 

Python

chess_set = [1, 1, 2, 2, 2, 8]
input_set = list(map(int, input().split()))
for i in range(6):
    val = chess_set[i] - input_set[i]
    print(f'{val} ', end='')

 

Node.js

const fs = require('fs');
const input_set = fs.readFileSync('/dev/stdin','utf8').split(' ').map(Number);
const chess_set = [1, 1, 2, 2, 2, 8]
for (let i = 0; i < 6; i++){
    const val = chess_set[i] - input_set[i];
    process.stdout.write(`${val} `);
}

 

3번 별 찍기 - 7

문제

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

 

입력

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

 

출력

첫째 줄부터 2 ×N-1번째 줄까지 차례대로 별을 출력한다.

 

    *
   ***
  *****
 *******
*********
 *******
  *****
   ***
    *

 

입력된 숫자와 규칙을 적용해서 별을 찍는 문제이다. 입력된 N을 사용해서 2N -1줄에 별을 찍는다.

 

각 줄에는 시행 횟수 i의 2i - 1 개의 별을 찍고 i가 N보다 클 때부터 2i - N 개의 별을 찍는다.

 

공백도 필요한데 공백은 N - i, i가 N보다 커지면 i - N 이 된다.

 

C++

#include <iostream>
#include <string>
using namespace std;
int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 1; i <= 2 * n - 1; i++){
        int space_count = n - i;
        int star_count = 2 * i - 1;
        if (i > n){
            space_count = i - n;
            star_count = 2 * (2 * n - i) - 1;
        }
        string space(space_count, ' ');
        string star(star_count, '*');
        cout << space << star << "\n";
    }
    return 0;
}

 

C#

using System;
class Program{
    static void Main(string[] args){
        int n = int.Parse(Console.ReadLine());
        int line = 2 * n;
        for (int i = 1; i < line; i++){
            int space_cnt = n - i;
            int star_cnt = 2 * i - 1;
            if (i > n){
                space_cnt = i - n;
                star_cnt = 2 * (line - i) - 1;
            }
            string space = new string(' ', space_cnt);
            string star = new string('*', star_cnt);
            Console.WriteLine($"{space}{star}");
        }
    }
}

 

Python

n = int(input())
line = 2 * n
for i in range(1, line):
    if i > n:
        space_cnt = i - n
        star_cnt = 2 * (line - i) - 1
    else:
        space_cnt = n - i
        star_cnt = 2 * i - 1
    space = ' ' * space_cnt
    star = '*' * star_cnt
    print(f"{space}{star}")

 

Node.js

const fs = require('fs');
const n = parseInt(fs.readFileSync('/dev/stdin','utf8'));
const line = 2 * n;
for (let i = 1; i < line; i++){
    let space_cnt;
    let star_cnt;
    if (i > n){
        space_cnt = i - n;
        star_cnt = 2 * (line - i) - 1;
    }
    else{
        space_cnt = n - i;
        star_cnt = 2 * i - 1;
    }
    const space = ' '.repeat(space_cnt);
    const star = '*'.repeat(star_cnt);
    console.log(`${space}${star}`);
}

 

4번 팰린드롬인지 확인하기

문제

알파벳 소문자로만 이루어진 단어가 주어진다. 이때, 이 단어가 팰린드롬인지 아닌지 확인하는 프로그램을 작성하시오. 

 

팰린드롬이란 앞으로 읽을 때와 거꾸로 읽을 때 똑같은 단어를 말한다. 

 

level, noon은 팰린드롬이고, baekjoon, online, judge는 팰린드롬이 아니다.

 

입력

첫째 줄에 단어가 주어진다. 단어의 길이는 1보다 크거나 같고, 100보다 작거나 같으며, 알파벳 소문자로만 이루어져 있다.

 

출력

첫째 줄에 팰린드롬이면 1, 아니면 0을 출력한다.

 

팰린드롬이란 기러기, 역삼역, 스위스 같은 건가 보다. 

 

입력된 문자열을 뒤집었을 때와 비교해서 동일하면 1, 아니면 0을 출력한다.

 

C++

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
    string str;
    cin >> str;
    string rev_str = str;
    reverse(str.begin(), str.end());
    int result = 0;
    if (str == rev_str)
        result = 1;
    else
        result = 0;
    cout << result;
    return 0;
}

 

reverse는 값을 반환하지 않기 때문에 rev_str에 str을 할당 후에 이 문자열을 뒤집어 준다.

 

C#

using System;
class Program{
    static void Main(string[] args){
        string str = Console.ReadLine();
        char[] rev_str_arr = str.ToCharArray();
        Array.Reverse(rev_str_arr);
        string rev_str = new string(rev_str_arr);
        int result = 0;
        if (str == rev_str)
            result = 1;
        else
            result = 0;
        Console.Write(result);
    }
}

 

Python

input_str = input()
rev_str = input_str[::-1]
result = 0
if input_str == rev_str:
    result = 1
else:
    result = 0
print(result)

 

Node.js

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin','utf8').trim();
const rev_input = input.split('').reverse().join('');
let result = 0;
if (input === rev_input)
    result = 1;
else
    result = 0;
console.log(result);

 

5번 단어 공부

문제

알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다.

 

입력

첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어진다. 주어지는 단어의 길이는 1,000,000을 넘지 않는다.

 

출력

첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다. 단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는 ?를 출력한다.

 

알파벳 개수만큼 배열을 선언하고 해당 알파벳이 나올 때 인덱스에 값을 증가시키면 될 듯하다.

 

C++

#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>
using namespace std;
int main(){
    int str_count[26] = {0};
    string str;
    cin >> str;
    transform(str.begin(), str.end(), str.begin(), ::toupper);
    for (char c : str){
        int idx = c - 'A';
        str_count[idx]++;
    }
    int* max_iter = max_element(str_count, str_count + 26);
    int max_index = distance(str_count, max_iter);
    int max_count = *max_iter;
    char max_char = max_index + 'A';
    int duplicate_count = 0;
    for (int i : str_count){
        if (i == max_count){
            duplicate_count++;
            if (duplicate_count > 1)
                break;
        }
    }
    if (duplicate_count > 1)
        cout << "?";
    else
        cout << max_char;
    return 0;
}

 

입력에 대소문자가 모두 들어오기 때문에 문자열을 소문자 또는 대문자로 통일시킨 다음 비교를 진행한다.

 

대문자로 변환시키기 위해서 algorithm의 transform과 cctype의 ::toupper를 사용한다. 소문자는 ::tolower

 

각 문자의 등장 횟수 중 가장 큰 수를 구한 다음 해당 횟수가 또 존재하는지 검사하여 ? 또는 해당 문자의 대문자를 출력한다.

 

C#

using System;
using System.Linq;
class Program{
    static void Main(string[] args){
        string str = Console.ReadLine().ToUpper();
        int[] char_count = new int[26];
        foreach(char c in str){
            char_count[c - 'A']++;
        }
        int max_count = char_count.Max();
        int max_count_index = Array.IndexOf(char_count, max_count);
        int duplicate_count = char_count.Count(x => x == max_count);
        if (duplicate_count > 1){
            Console.WriteLine("?");
        }
        else{
            Console.WriteLine((char)(max_count_index + 'A'));
        }
    }
}

 

Python

s = input().upper()
str_cnt = [0] * 26
for c in s:
    idx = ord(c) - ord('A')
    str_cnt[idx] += 1
max_cnt = max(str_cnt)
max_idx = 0
duplicate_cnt = 0
for i in range(26):
    if str_cnt[i] == max_cnt:
        duplicate_cnt += 1
        max_idx = i
        if duplicate_cnt > 1:
            break
if duplicate_cnt > 1:
    print("?")
else:
    print(chr(max_idx + ord('A')))

 

Node.js

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin', 'utf8').toUpperCase();
const str_cnt = new Array(26).fill(0);
for (const c of input){
    const i = c.charCodeAt(0) - 'A'.charCodeAt(0);
    str_cnt[i]++;
}
const max = Math.max(...str_cnt);
let max_idx = 0;
let duplicate_cnt = 0;
for (let i = 0; i < 26; i++){
    if (str_cnt[i] === max){
        duplicate_cnt++;
        max_idx = i;
        if (duplicate_cnt > 1)
            break;
    }
}
if (duplicate_cnt > 1)
    console.log("?");
else
    console.log(String.fromCharCode(max_idx + 'A'.charCodeAt(0)));

 

728x90
반응형

+ Recent posts