시간 복잡도 비교 문제

AList = [1, 2, 3], BSet = {1, 2, 3}일 때 다음 질문에 답하시오:

1. 값 4를 찾을 때, 리스트와 집합 중 어느 쪽의 최악 시간 복잡도가 더 큰가?
2. 값 4를 삽입할 때, 리스트와 집합 중 어느 쪽의 최악 시간 복잡도가 더 큰가?

답변:

1. 검색 연산의 경우, 리스트와 집합 모두 O(n)의 시간 복잡도를 가진다.
2. 삽입 연산의 경우, 리스트는 O(n), 집합은 평균적으로 O(1)의 시간 복잡도를 가지므로 리스트가 더 높은 복잡도를 갖는다. 집합은 해시 테이블 기반으로 구현되어 대부분의 연산이 상수 시간에 수행된다.

이진 탐색 함수 구현

def binary_search(data_list, target_value):
    start_index = 0
    end_index = len(data_list) - 1
    
    while start_index <= end_index:
        middle_index = (start_index + end_index) // 2
        
        if data_list[middle_index] < target_value:
            start_index = middle_index + 1
        elif data_list[middle_index] > target_value:
            end_index = middle_index - 1
        else:
            print(f"위치:{middle_index}, 값:{data_list[middle_index]}")
            return True
    
    return False

# 실행 예시
if __name__ == '__main__':
    test_list = [1, 3, 4, 5, 6, 7, 8]
    binary_search(test_list, 8)

싱글톤 패턴 구현 방법

파이썬에서 싱글톤 패턴을 구현하는 방법은 다양하다. 모듈 자체가 싱글톤 특성을 가지며, 여기서는 __new__ 메소드를 활용한 방식을 보여준다.

class Document:
    def __new__(cls, document_name):
        if not hasattr(cls, "_instance"):
            cls._instance = super().__new__(cls)
            print('새 인스턴스 생성')
        return cls._instance

    def __init__(self, document_name):
        print('초기화 진행')
        super().__init__()
        self.document_name = document_name

# 테스트
if __name__ == '__main__':
    doc1 = Document('웹 개발 문서')
    doc2 = Document('모바일 문서')
    print(id(doc1))
    print(id(doc2))
    print(doc1.document_name)
    print(doc2.document_name)

피보나치 수열 생성

피보나치 수열은 세 번째 항부터 각 항이 앞 두 항의 합인 수열이다.

def generate_fibonacci(count):
    prev_num, curr_num = 0, 1
    sequence = [prev_num, curr_num]
    
    for _ in range(count):
        prev_num, curr_num = curr_num, prev_num + curr_num
        sequence.append(curr_num)
    
    return sequence

# 실행 예시
if __name__ == '__main__':
    print(generate_fibonacci(10))

중복 요소 찾기

class DuplicateFinder:
    def find_duplicates(self, number_list):
        if not number_list or len(number_list) <= 1:
            return False
            
        seen_numbers = set()
        duplicates = {}
        
        for position, value in enumerate(number_list):
            if value not in seen_numbers:
                seen_numbers.add(value)
            else:
                duplicates[position] = value
                
        return duplicates

# 테스트
if __name__ == '__main__':
    finder = DuplicateFinder()
    result = finder.find_duplicates([1, 2, -3, 4, 4, 95, 95, 5, 2, 2, -3, 7, 7, 5])
    print(result)

단일 요소 찾기

def find_unique_element(input_list):
    xor_result = 0
    
    for element in input_list:
        xor_result ^= element
    
    if xor_result == 0:
        print("모든 요소가 짝을 이룸")
    else:
        print("단일 요소:", xor_result)

# 테스트
if __name__ == '__main__':
    test_data = [1, 2, 3, 4, 5, 6, 2, 3, 4, 5, 6]
    find_unique_element(test_data)

버블 정렬 구현

def bubble_sort_algorithm(array):
    length = len(array)
    
    for i in range(length - 1):
        for j in range(length - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]

# 테스트
if __name__ == '__main__':
    sample_array = [1, 2, 3, 4, 5, 55, 6, 3, 4, 5, 6]
    bubble_sort_algorithm(sample_array)
    print(sample_array)

퀵 정렬 구현

def quick_sort_algorithm(array, start, end):
    if start >= end:
        return
    
    pivot_value = array[start]
    left_pointer = start
    right_pointer = end
    
    while left_pointer < right_pointer:
        while left_pointer < right_pointer and array[right_pointer] >= pivot_value:
            right_pointer -= 1
        array[left_pointer] = array[right_pointer]
        
        while left_pointer < right_pointer and array[left_pointer] < pivot_value:
            left_pointer += 1
        array[right_pointer] = array[left_pointer]
    
    array[left_pointer] = pivot_value
    quick_sort_algorithm(array, start, left_pointer - 1)
    quick_sort_algorithm(array, left_pointer + 1, end)

# 테스트
if __name__ == '__main__':
    test_array = [1, 2, 3, 4, 5, 55, 6, 3, 4, 5, 6]
    quick_sort_algorithm(test_array, 0, len(test_array) - 1)
    print(test_array)

위상 정렬 구현

방향성 비순환 그래프(DAG)에 대한 위상 정렬을 구현한다.

from typing import Dict, List

def topological_sort_algorithm(graph: Dict[str, str]) -> List[str]:
    # 각 노드의 진입 차수 초기화
    in_degree = {node: 0 for node in graph}
    
    # 진입 차수 계산
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1
    
    # 진입 차수가 0인 노드 큐
    zero_indegree_queue = [node for node in graph if in_degree[node] == 0]
    sorted_nodes = []
    
    while zero_indegree_queue:
        current_node = zero_indegree_queue.pop()
        sorted_nodes.append(current_node)
        
        for adjacent_node in graph[current_node]:
            in_degree[adjacent_node] -= 1
            if in_degree[adjacent_node] == 0:
                zero_indegree_queue.append(adjacent_node)
    
    return sorted_nodes

# 테스트
if __name__ == '__main__':
    graph_structure = {
        'a': 'bf',
        'b': 'cdf',
        'c': 'd',
        'd': 'ef',
        'e': 'f',
        'f': ''
    }
    
    result = topological_sort_algorithm(graph_structure)
    print(result)

이진수 연산 구현

def add_binary_numbers(first_binary: str, second_binary: str) -> str:
    decimal_sum = int(first_binary, 2) + int(second_binary, 2)
    return bin(decimal_sum)[2:]

# 테스트
if __name__ == '__main__':
    binary1 = input("첫 번째 이진수 입력:\n")
    binary2 = input("두 번째 이진수 입력:\n")
    print(add_binary_numbers(binary1, binary2))