[Python] 기초 알고리즘 문제 풀이

[Python] 기초 알고리즘 문제 풀이

초보자를 위한 기본적인 알고리즘 문제와 해결 방법을 Python 코드로 살펴보자.

 

순차 탐색

기본 순차 탐색

def sequential_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # 찾은 위치 반환
    return -1  # 못 찾은 경우

# 사용 예시
numbers = [4, 2, 7, 1, 9, 3]
result = sequential_search(numbers, 7)
print(f"위치: {result}")  # 위치: 2

 

문자열에서 문자 찾기

def find_all_positions(text, char):
    positions = []
    for i in range(len(text)):
        if text[i] == char:
            positions.append(i)
    return positions

# 사용 예시
text = "hello world"
positions = find_all_positions(text, 'l')
print(f"l의 위치들: {positions}")  # [2, 3, 9]

 

정렬하기

버블 정렬

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

# 사용 예시
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = bubble_sort(numbers.copy())
print(f"정렬된 결과: {sorted_numbers}")

 

선택 정렬

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# 사용 예시
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = selection_sort(numbers.copy())
print(f"정렬된 결과: {sorted_numbers}")

 

 

최대/최소 찾기

 

기본 최대/최소 찾기

def find_min_max(arr):
    if not arr:  # 빈 리스트 체크
        return None, None

    current_min = current_max = arr[0]
    for num in arr[1:]:
        if num < current_min:
            current_min = num
        if num > current_max:
            current_max = num

    return current_min, current_max

# 사용 예시
numbers = [4, 2, 7, 1, 9, 3]
min_val, max_val = find_min_max(numbers)
print(f"최소값: {min_val}, 최대값: {max_val}")

 

인덱스와 함께 찾기

def find_min_max_indices(arr):
    if not arr:
        return None, None

    min_idx = max_idx = 0
    for i in range(1, len(arr)):
        if arr[i] < arr[min_idx]:
            min_idx = i
        if arr[i] > arr[max_idx]:
            max_idx = i

    return min_idx, max_idx

# 사용 예시
numbers = [4, 2, 7, 1, 9, 3]
min_idx, max_idx = find_min_max_indices(numbers)
print(f"최소값 위치: {min_idx}, 최대값 위치: {max_idx}")

 

빈도수 계산

 

딕셔너리를 이용한 빈도수 계산

def count_frequency(arr):
    frequency = {}
    for item in arr:
        frequency[item] = frequency.get(item, 0) + 1
    return frequency

# 사용 예시
items = ['a', 'b', 'a', 'c', 'b', 'a']
freq = count_frequency(items)
print(f"빈도수: {freq}")  # {'a': 3, 'b': 2, 'c': 1}

 

가장 많이 등장하는 요소 찾기

def find_most_frequent(arr):
    if not arr:
        return None

    frequency = count_frequency(arr)
    max_freq = max(frequency.values())
    most_frequent = [k for k, v in frequency.items() if v == max_freq]

    return most_frequent

# 사용 예시
numbers = [1, 2, 3, 2, 4, 2, 3]
most_freq = find_most_frequent(numbers)
print(f"가장 많이 등장하는 숫자: {most_freq}")

 

실전 문제 예시

 

중복 제거하기

def remove_duplicates(arr):
    return list(dict.fromkeys(arr))

# 사용 예시
numbers = [1, 2, 2, 3, 4, 3, 5]
unique_numbers = remove_duplicates(numbers)
print(f"중복 제거 결과: {unique_numbers}")

 

두 리스트의 공통 요소 찾기

def find_common_elements(list1, list2):
    return list(set(list1) & set(list2))

# 사용 예시
list1 = [1, 2, 3, 4, 5]
list2 = [4, 5, 6, 7, 8]
common = find_common_elements(list1, list2)
print(f"공통 요소: {common}")