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

파이썬 코딩테스트 강좌, 평균 구하기

코딩 테스트를 준비하는 많은 개발자들에게 평균 구하기 문제는 단순하면서도 중요한 기초 문제로 자리 잡고 있습니다.
이 문제는 데이터 집합에서 평균을 계산하는 과정에서 프로그래밍의 기초적인 개념을 다질 수 있는 좋은 기회입니다.

문제 설명

주어진 정수 리스트에서 평균을 구하시오.
리스트는 1 이상 100 이하의 정수로 이루어져 있으며, 리스트의 길이는 1 이상 1000 이하입니다.
평균은 소수점 이하 첫째 자리까지 반올림하여 출력해야 합니다.

입력

첫 번째 줄에 정수 n (1 ≤ n ≤ 1000)이 주어집니다. n은 리스트의 길이입니다.
두 번째 줄에는 n개의 정수가 주어집니다. 각 정수는 1 이상 100 이하입니다.

출력

리스트의 평균을 소수점 이하 첫째 자리까지 반올림하여 출력합니다.

예제

입력:
5
10 20 30 40 50
출력:
30.0

문제 풀이 과정

1. 문제 분석

이 문제를 해결하기 위해서는 다음과 같은 단계를 따르면 됩니다:

리스트에서 정수를 입력 받는다.
리스트의 총 합을 계산한다.
리스트의 길이(n)로 총 합을 나누어 평균을 계산한다.
계산한 평균을 소수점 이하 첫째 자리까지 반올림한다.

2. 알고리즘 설계

위의 단계를 바탕으로 알고리즘을 설계해보겠습니다.
1. 사용자로부터 n을 입력 받습니다.
2. n개의 정수를 입력 받아 리스트에 저장합니다.
3. 리스트의 합을 구합니다.
4. 합을 n으로 나누어 평균을 계산합니다.
5. 평균을 내림차순으로 출력합니다.

3. 파이썬 코드 구현

이제 위의 알고리즘을 파이썬 코드로 구현해 보겠습니다.
코드는 다음과 같습니다:


def calculate_average():
    # 사용자로부터 길이를 입력 받음
    n = int(input("리스트의 길이를 입력하세요: "))
    # 리스트 생성
    numbers = list(map(int, input("정수를 입력하세요 (공백으로 구분): ").split()))
    
    # 유효성 검사
    if len(numbers) != n:
        print("입력한 숫자의 개수가 리스트의 길이와 일치하지 않습니다.")
        return
    
    # 평균 계산
    total = sum(numbers)
    average = total / n
    
    # 소수점 이하 첫번째 자리까지 반올림
    average_rounded = round(average, 1)
    
    # 결과 출력
    print(f"리스트의 평균: {average_rounded}")

# 함수 호출
calculate_average()

4. 코드 설명

1. 입력 받기: `n`을 입력 받고, 이후 `n`개의 정수를 입력 받아 리스트 `numbers`에 저장합니다.

2. 유효성 검사: 입력된 숫자의 개수가 `n`과 일치하는지 확인합니다.
일치하지 않으면 오류 메시지를 출력하고 함수를 종료합니다.

3. 합계와 평균 계산: 리스트의 합계를 구하고, 평균을 계산합니다.

4. 반올림: `round()` 함수를 사용하여 평균을 소수점 이하 첫째 자리까지 반올림합니다.

5. 출력: 마지막으로 계산된 평균을 출력합니다.

5. 예외 처리 및 추가 고려사항

– 입력 값이 조건을 만족하지 않을 경우 예외를 처리할 수 있어야 합니다.
예를 들어, 리스트의 길이와 입력된 숫자 개수가 다를 경우 오류 메시지를 출력하도록 설계되었습니다.

– 또한, `input()` 함수는 문자열로 입력을 받기 때문에, 이를 정수로 변환할 필요가 있습니다.
여기서는 `map(int, …)` 함수를 사용하여 리스트의 모든 요소를 정수형으로 변환하는 방법을 사용했습니다.

6. 추가 문제: 평균 계산 함수 개선하기

위의 문제를 해결한 후, 몇 가지 개선사항을 추가할 수 있습니다.
예를 들어, 함수가 입력을 받을 때 사용자에게 안내 메시지를 줄 수 있도록 개선할 수 있습니다.
사용자에 맞는 피드백을 주면 레벨 높은 사용자 경험을 제공하게 됩니다.

결론

이번 포스팅에서는 리스트에서 평균을 구하는 문제를 다루었습니다.
이와 같은 기초 문제를 통해 파이썬 기본 문법 및 데이터 처리 방법에 대해 이해할 수 있었습니다.
앞으로 더 복잡한 문제를 다루기 전에 이러한 기본적인 문제 해결 능력을 기르는 것은 필수적입니다.
파이썬을 통해 알고리즘과 데이터 처리 능력을 한 단계씩 발전시켜 나가시길 바랍니다.

감사합니다!

파이썬 코딩테스트 강좌, 특정 거리의 도시 찾기

작성자: 조광형

작성일: 2024년 11월 26일

문제 정의

주어진 도시와 거리 정보를 바탕으로, 특정 거리 K에 정확히 도달할 수 있는 도시 목록을 구하는 문제입니다.
각 도시는 번호로 표현되며, 두 도시 간의 거리 정보는 양방향 도로로 연결된 형태로 주어집니다.
목표는 K만큼 떨어진 도시를 찾는 것입니다.

예를 들어, N개의 도시가 있고, M개의 도로가 있으며, 출발 도시가 주어질 때 K만큼 떨어진 도시를 출력합니다.

입력

N: 도시의 개수 (1 ≤ N ≤ 300,000)
M: 도로의 개수 (1 ≤ M ≤ 1,000,000)
K: 거리 정보 (0 ≤ K ≤ 300,000)
X: 출발 도시 번호 (1 ≤ X ≤ N)
도로 정보: A, B (A에서 B로 가는 도로)

출력

특정 거리 K에 있는 도시의 번호를 오름차순으로 출력하고, 그러한 도시가 없으면 -1을 출력합니다.

예제

설명: 도시 1에서 시작할 때, 거리 2에 있는 도시 4가 유일합니다.

알고리즘 접근 방법

이 문제는 그래프 탐색 알고리즘을 활용하여 해결할 수 있습니다.
도시들을 노드로, 도로를 간선으로 표현한 그래프를 구성합니다.
BFS(너비 우선 탐색) 알고리즘을 이용하여 시작 도시 X에서부터 거리 K에 도달하는 도시를 찾는 방식으로 접근합니다.
BFS는 최단 경로를 찾는 데 유용하며, 대규모 그래프에서도 효율적으로 동작하기 때문에 이 문제에 적합합니다.

문제 해결 과정

1. 그래프 생성

먼저, 도로 정보로부터 그래프를 생성합니다.
리스트를 이용하여 그래프를 표현하고, 각 도시를 키로 사용하여 연결된 도시를 값으로 가지는 딕셔너리를 사용합니다.

2. BFS 구현

BFS를 구현하기 위해 큐를 사용합니다.
시작 도시를 큐에 추가하고, 방문한 도시를 기록합니다.
각 도시에 대해 방문할 거리 K인 도시를 탐색합니다.

3. 출력 처리

BFS 탐색 후, K거리 도시에 해당하는 도시 번호를 정렬하여 출력하거나, 도시가 없는 경우 -1을 출력합니다.

Python 코드

                
                from collections import deque

                def find_cities_with_distance(n, m, k, x, roads):
                    # 그래프 생성
                    graph = [[] for _ in range(n + 1)]
                    for a, b in roads:
                        graph[a].append(b)
                    
                    # BFS 초기화
                    distance = [-1] * (n + 1)
                    distance[x] = 0
                    queue = deque([x])
                    
                    while queue:
                        city = queue.popleft()
                        for neighbor in graph[city]:
                            if distance[neighbor] == -1:  # 방문하지 않은 도시
                                distance[neighbor] = distance[city] + 1
                                queue.append(neighbor)
                    
                    # 결과 생성
                    result = [i for i in range(1, n + 1) if distance[i] == k]
                    return result if result else [-1]
                
                # Test case
                n = 4
                m = 4
                k = 2
                x = 1
                roads = [(1, 2), (1, 3), (2, 3), (2, 4)]
                print(find_cities_with_distance(n, m, k, x, roads))

이 코드는 BFS를 사용하여 특정 거리 K에 도달할 수 있는 도시를 찾습니다. 그래프는 인접 리스트로 표현되며 간선 정보를 바탕으로 노드 간의 연결 관계를 정의합니다.

결론

“특정 거리의 도시 찾기” 문제는 그래프 탐색 알고리즘, 특히 BFS를 통해 효율적으로 해결할 수 있는 문제입니다.
이 문제를 통해 BFS의 기본 원리, 그래프를 구성하는 방법, 그리고 최단 거리 탐색에 대한 이해를 높일 수 있습니다.
기초부터 시작하여, 더 복잡한 그래프 문제로 나아갈 수 있는 디딤돌이 될 것입니다.

파이썬 코딩테스트 강좌, 트리의 지름 구하기

트리는 컴퓨터 과학에서 매우 중요한 자료구조 중 하나입니다. 특히 트리는 계층적 관계를 나타내는 데 유용하며, 다양한 알고리즘 문제에서 사용됩니다. 이번 강좌에서는 트리의 지름을 구하는 문제를 다룰 것입니다.
지름이란 트리에서 두 노드 사이의 가장 긴 경로를 의미합니다. 이 문제는 DFS(깊이 우선 탐색) 또는 BFS(너비 우선 탐색) 알고리즘을 통해 해결할 수 있습니다.

문제 설명

주어진 비어있지 않은 트리의 각 노드는 정수로 표시됩니다. 트리에서 두 노드 사이의 가장 긴 경로의 길이를 구하는 문제를 해결하세요.
입력으로는 트리의 노드 수 N과 N-1개의 간선 정보가 주어집니다. 간선 정보는 두 노드를 연결하는 형태로 제공됩니다.
구체적으로, 다음과 같은 형식의 입력이 주어질 것입니다:

    N
    a1 b1
    a2 b2
    ...
    a(N-1) b(N-1)

여기서 a와 b는 각각 연결된 두 노드를 나타냅니다.

입력 예시

출력 예시

이 경우 트리의 지름은 노드 4와 노드 5 사이로, 경로는 4 → 2 → 1 → 3 또는 4 → 2 → 5로 구성됩니다.
따라서 출력은 3입니다.

문제 풀이

트리의 지름을 구하기 위해서는 DFS 또는 BFS 알고리즘을 사용할 수 있습니다.
일반적인 접근 방법은 다음과 같습니다.

첫 번째 단계로, 임의의 노드에서 DFS를 실행해서 가장 먼 노드를 찾습니다.
이 노드를 X라고 합시다.
두 번째 단계로, 노드 X에서 다시 DFS를 실행하여 가장 먼 노드인 Y를 찾습니다.
X와 Y 사이의 경로가 트리의 지름이 됩니다.

이 과정을 통해 시간 복잡도는 O(N)이 되며, 재귀적으로 DFS를 호출하는 방식으로 구현됩니다.

파이썬 코드 구현

이제 위의 로직을 바탕으로 파이썬에서 트리의 지름을 구하는 코드를 구현해 보겠습니다.
아랫부분에 제공하는 코드와 함께 각 단계의 세부 과정을 점검해 보세요.

from collections import defaultdict

def dfs(graph, node, visited):
    visited.add(node)
    max_distance = 0
    farthest_node = node

    for neighbor in graph[node]:
        if neighbor not in visited:
            distance, next_node = dfs(graph, neighbor, visited)
            distance += 1
            
            if distance > max_distance:
                max_distance = distance
                farthest_node = next_node

    return max_distance, farthest_node

def tree_diameter(edges, n):
    graph = defaultdict(list)
    
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)

    # Step 1: start DFS from an arbitrary node (1)
    visited = set()
    _, farthest_node = dfs(graph, 1, visited)

    # Step 2: start DFS from the farthest node found
    visited.clear()
    diameter, _ = dfs(graph, farthest_node, visited)

    return diameter

# Input reading part
n = int(input())
edges = [tuple(map(int, input().split())) for _ in range(n-1)]
print(tree_diameter(edges, n))

코드 설명

위의 코드는 다음과 같은 방식으로 구성되어 있습니다:

collections.defaultdict를 사용하여 그래프를 인접 리스트 형태로 만듭니다.
이 때 노드끼리의 연결관계를 나타냅니다.
dfs 함수는 깊이 우선 탐색을 수행하며, 각 노드까지의 거리를 계산합니다.
가장 먼 노드와 거리를 반환합니다.
tree_diameter 함수는 전체적인 과정을 조정하고 두 번의 DFS 호출로 지름을 계산합니다.
마지막 부분에서 사용자로부터 입력을 받고, tree_diameter 함수를 호출하여 결과를 출력합니다.

성능 분석

제시된 알고리즘은 O(N)의 시간 복잡도를 갖고 있습니다.
이는 트리의 모든 노드를 DFS로 한 번씩 방문하기 때문에 가능합니다.
따라서 매우 큰 트리에서도 효율적으로 지름을 계산할 수 있습니다.

결론

이번 강좌에서는 트리의 지름에 대해 살펴보았습니다.
DFS를 이용한 접근법으로 효율적으로 문제를 해결할 수 있었습니다.
트리는 다양한 문제에서 활용되기 때문에 이번 강좌의 내용을 잘 익혀두면 좋습니다.
추가적인 질문이나 연습문제가 필요하다면 댓글로 남겨주세요.

파이썬 코딩테스트 강좌, 트리의 부모 찾기

안녕하세요! 이번 포스트에서는 트리 구조의 데이터를 다루는 알고리즘 문제를 풀어보겠습니다. 우리는 “트리의 부모 찾기”라는 문제를 통해 트리를 이해하고, 이를 통해 파이썬 프로그래밍 능력을 향상시킬 수 있을 것입니다. 트리 구조는 컴퓨터 과학에서 아주 중요한 개념 중 하나이며, 이는 데이터베이스, 파일 시스템, 웹사이트의 구조 등 다양한 곳에 응용되고 있습니다.

문제 설명

문제: 주어진 정점의 부모 노드를 찾는 함수를 작성하세요. 트리는 노드와 엣지로 구성된 비선형 자료구조로, 각 노드는 0개 이상의 자식 노드를 가질 수 있습니다. 입력으로는 노드의 수와 각 노드의 부모 노드 정보가 주어집니다. 우리는 특정 노드의 부모 노드를 반환하는 함수를 작성해야 합니다.

입력 형식:
– 첫 번째 줄에 노드의 수 N (1 ≤ N ≤ 100,000)이 주어집니다.
– 그 다음 N-1 줄에 각 줄마다 두 개의 정수 A, B가 주어지며, 이는 A가 B의 부모임을 의미합니다.

출력 형식: 특정 노드의 부모 노드 번호를 출력합니다.

문제 해결 방안

이 문제를 해결하기 위해서는 먼저 주어진 정보를 바탕으로 트리 구조를 형성할 수 있어야 합니다. 다음 과정을 따라 문제를 해결하겠습니다.

1단계: 데이터 구조 선택

트리를 구현하기 위해 딕셔너리를 사용합니다. 각 노드의 번호를 키로 하고, 해당 노드의 부모 노드를 값으로 가지는 구조를 선택하겠습니다. 그러면 주어진 관계를 효율적으로 저장하고 빠르게 부모 노드를 찾을 수 있습니다.

2단계: 입력 데이터 처리

입력 데이터를 읽어서 트리 구조를 생성합니다. 노드의 수를 입력받고, N-1 줄에 걸쳐 부모-자식 관계를 추가합니다. 이를 통해 전체 트리를 구성할 수 있습니다.

3단계: 부모 노드 찾기

특정 노드의 부모 노드를 찾기 위해, 앞서 만든 딕셔너리에서 해당 노드의 부모를 바로 조회하면 됩니다. 이는 상수 시간 (`O(1)`)에 가능합니다.

4단계: 함수 작성

위에서 논의한 내용을 바탕으로 파이썬 함수를 작성해 보겠습니다. 다음은 문제 해결을 위한 코드입니다:


def find_parent(n, edges, query_node):
    # 부모 노드 정보를 담는 딕셔너리
    parent = {}
    
    # 입력으로 주어진 관계를 기반으로 딕셔너리 생성
    for a, b in edges:
        parent[b] = a
        
    # 특정 노드의 부모 노드를 요청받았을 때 반환
    return parent.get(query_node, None)

# 예시 입력
n = 7  # 노드 수
edges = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7)]  # 부모-자식 관계
query_node = 4  # 부모를 찾고자 하는 노드

# 부모 노드 찾기
print(find_parent(n, edges, query_node))

전체 코드


def find_parent(n, edges, query_node):
    parent = {}
    
    # 관계를 딕셔너리로 저장
    for a, b in edges:
        parent[b] = a
    
    return parent.get(query_node, None)

if __name__ == "__main__":
    n = int(input("노드 수를 입력하세요: "))
    edges = []
    for _ in range(n - 1):
        a, b = map(int, input("부모와 자식 관계를 입력하세요 (예: 'A B'): ").split())
        edges.append((a, b))
    
    query_node = int(input("부모를 찾고자 하는 노드 번호를 입력하세요: "))
    result = find_parent(n, edges, query_node)
    
    if result is not None:
        print(f"노드 {query_node}의 부모 노드는 {result}입니다.")
    else:
        print(f"노드 {query_node}의 부모 노드를 찾을 수 없습니다.")

문제 해결 과정 분석

위 코드는 다음과 같은 구조로 문제를 해결합니다:

딕셔너리를 사용하여 부모 노드 정보를 효율적으로 저장합니다.
주어진 관계를 통해 트리 구조를 형성합니다.
특정 노드에 대해 부모 노드를 빠르게 조회할 수 있습니다.

복잡도 분석

– 시간 복잡도: `O(N)` \- 노드 수(N)에 비례하여 부모 노드 관계를 저장합니다.
– 공간 복잡도: `O(N)` \- 노드 정보를 저장하기 위해 딕셔너리를 사용합니다.

결론

이번 포스트에서는 “트리의 부모 찾기”라는 문제를 통해 트리 구조와 관련된 기본적인 알고리즘을 배웠습니다. 트리는 효율적인 데이터 탐색 및 데이터 저장 방식으로 요즘 데이터 과학과 소프트웨어 개발에서 많이 사용되는 자료형입니다. 이 문제를 통해 트리를 이해하는 데 훌륭한 기초가 되었으리라 생각합니다. 다음 포스트에서는 더 복잡한 트리 문제를 다루어 보겠습니다. 감사합니다!

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

이 글에서는 트리 데이터 구조의 개념과 해당 구조를 기반으로 한 알고리즘 문제를 다루고, 이를 해결하는 과정을 상세히 설명하겠습니다.

트리란?

트리는 비선형 데이터 구조의 일종으로, 계층적인 관계를 표현하는 데 사용됩니다. 트리는 다음과 같은 특징을 가집니다:

트리는 노드의 집합으로 구성됩니다.
하나의 루트 노드가 있으며, 나머지 노드는 이 루트 노드를 기준으로 하위 트리를 형성합니다.
각 노드는 0개 이상의 자식 노드를 가질 수 있습니다.
트리는 사이클이 없습니다.

어떤 종류의 트리들이 있을까요?

트리는 그 구조와 규칙에 따라 여러 종류로 나눌 수 있습니다. 다음은 몇 가지 주요 트리의 종류입니다:

이진 트리: 각 노드가 최대 2개의 자식 노드를 가지는 트리입니다.
완전 이진 트리: 모든 레벨이 최대 노드 수를 가진 트리입니다.
균형 이진 트리: 높이 차이가 최소화된 이진 트리입니다.
이진 탐색 트리(BST): 왼쪽 서브트리의 모든 값은 부모보다 작고, 오른쪽 서브트리의 모든 값은 부모보다 큰 트리입니다.
AVL 트리: 균형 잡힌 이진 탐색 트리의 일종입니다.

알고리즘 문제: 이진 트리의 최대 깊이

다음 문제를 해결해보겠습니다.

문제: 이진 트리가 주어질 때, 이 트리의 최대 깊이를 구하는 함수를 작성하시오. 트리의 깊이는 루트 노드에서 가장 깊은 리프 노드까지의 경로에 있는 노드의 수입니다.

예를 들어, 주어진 트리가 다음과 같을 때:

이 트리의 최대 깊이는 3입니다.

문제 해결 접근법

이 문제를 해결하기 위해, 우리는 트리의 노드를 탐색하고 각 노드의 깊이를 계산할 수 있습니다. 깊이를 계산하는 방법으로는 여러 가지가 있지만, 깊이 우선 탐색(DFS)을 사용하면 간단하게 해결할 수 있습니다. 재귀적 접근법을 이용하면 코드가 간결해집니다.

파이썬 코드 구현

아래는 주어진 문제를 해결하기 위한 파이썬 코드입니다:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxDepth(root):
    if not root:
        return 0
    else:
        left_depth = maxDepth(root.left)
        right_depth = maxDepth(root.right)
        return max(left_depth, right_depth) + 1

위의 코드는 이진 트리의 루트 노드를 인자로 받아서 최대 깊이를 반환합니다. 재귀 함수를 사용하여 현재 노드가 비어있지 않은 경우, 왼쪽과 오른쪽 서브트리의 최대 깊이를 계산하고, 더 큰 깊이에 1을 더하여 반환합니다.

코드 실행 예시

아래는 트리를 생성하고, 최대 깊이를 계산하는 예시입니다:

root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

print(maxDepth(root))  # 출력 결과: 3

위 코드를 실행하면, 주어진 이진 트리의 최대 깊이는 3이라는 결과를 얻습니다.

심화 학습: 트리의 다른 탐색 방법

트리 탐색에는 DFS 외에도 너비 우선 탐색(BFS) 방법이 있습니다. BFS는 큐를 사용하여 레벨 순서대로 노드를 탐색하는 방식입니다. 아래는 BFS를 사용하여 최대 깊이를 계산하는 방법입니다.

from collections import deque

def maxDepthBFS(root):
    if not root:
        return 0
    queue = deque([root])
    depth = 0
    while queue:
        depth += 1
        level_size = len(queue)
        for _ in range(level_size):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return depth

BFS 접근법을 사용하게 되면, 각 레벨을 반복하면서 노드를 탐색하므로 전체 깊이를 효율적으로 계산할 수 있습니다.

트리 문제 풀이의 중요성

코딩 테스트에서 트리 문제는 자주 출제됩니다. 트리는 복잡한 데이터 구조이므로, 이에 대한 이해가 없으면 어려운 문제를 해결하기 어렵습니다. 트리 문제를 통해 재귀, BFS, DFS, 백트래킹 등 다양한 알고리즘 문제 해결 전략을 익힐 수 있습니다. 따라서, 기업의 코딩 테스트에 대비하기 위해 트리 문제를 충분히 연습하는 것이 중요합니다.

결론

이번 글에서는 이진 트리의 개념과 최대 깊이를 구하는 알고리즘 문제를 통해 깊이 우선 탐색 및 너비 우선 탐색의 두 가지 접근 방식을 살펴보았습니다. 트리 문제는 알고리즘 문제의 기본이며, 실제 코딩 테스트에서도 자주 출제되는 중요한 주제입니다. 따라서, 이와 관련된 다양한 문제를 풀어보며 경험을 쌓는 것이 중요합니다.

트리와 관련된 문제를 풀어보면서 다양한 경험을 쌓고, 알고리즘 이해도를 높이는 계기가 되길 바랍니다. 앞으로도 다양한 자료 구조와 알고리즘에 대해 깊이 있게 공부해보세요.