728x90 반응형 알고리즘4 [알고리즘 공부] 3. N-Queens 문제 안녕하세요 오늘은 N-Queens 문제에 대해 알아보겠습니다. N-Queens 문제란?N x N 체스판에서 N 개의 퀸을 서로 공격하지 못하게 배치하는 방법에 관한 문제입니다. # 이 함수는 N-Queens 문제를 해결하고 가능한 모든 배치를 반환합니다. # 내부에 두 개의 중첩 함수(is_safe와 solve)를 사용하여 재귀적으로 문제를 해결합니다.def solve_n_queens(n): # is_safe 함수는 현재 위치에 퀸을 놓는 것이 안전한지를 확인합니다. # 현재 위치 (row, col)에서 이전 행들을 검사하여 다음 세 가지 조건을 만족하는지 확인합니다 def is_safe(board, row, col): for i in range(row): .. 2024. 6. 4. [알고리즘 공부] * 시간복잡도란? 안녕하세요 오늘은 알고리즘에서 시간복잡도가 무엇인지 왜 중요한지에 대해 알아보겠습니다. 시간 복잡도(Time Complexity)는 알고리즘의 성능을 분석할 때 사용하는 개념으로, 입력 크기(input size)에 따라 알고리즘이 실행되는 데 걸리는 시간을 수학적으로 표현한 것입니다. 시간 복잡도는 주로 Big-O 표기법(Big-O Notation)을 사용하여 나타냅니다. Big-O 표기법은 알고리즘의 최악의 실행 시간을 나타내며, 알고리즘이 얼마나 효율적인지 평가하는 데 사용됩니다. 주요 시간 복잡도 유형 O(1) - 상수 시간(Constant Time):입력 크기에 상관없이 항상 일정한 시간이 걸리는 경우입니다.예: 배열의 특정 인덱스에 접근하는 경우. O(log n) - 로그 시간(Logarithm.. 2024. 5. 30. [알고리즘 공부] 2. 분할 정복 알고리즘 안녕하세요 오늘은 분할 정복 (divide and conquer) 알고리즘에 대하여 알아보겠습니다. 분할 정복(divide and conquer)은 문제를 더 작은 부분 문제로 분할하고 각 부분 문제를 재귀적으로 해결한 다음,그 결과를 조합하여 전체 문제의 해답을 얻는 알고리즘 설계 패러다임입니다. 정렬, 수학, 그래프 알고리즘 등에 사용되며 오늘은 병합 정렬과 거듭제곱 예시를 통해 알아보겠습니다. 1. 병합 정렬 알고리즘 (Merge Sort) 병합 정렬은 분할 정복(divide and conquer) 전략을 사용하는 안정적인 정렬 알고리즘입니다.이 알고리즘은 배열을 반으로 나눈 후, 각 부분을 재귀적으로 정렬하고,두 정렬된 부분을 합병하여 최종 정렬된 배열을 만듭니다. def merge_sort.. 2024. 5. 30. [알고리즘 공부] 1. 배열 최대 연속 부분합 (Kadane's Algorithm) 안녕하세요 오늘부터 알고리즘에 대해 공부하는 시간을 가져 보겠습니다. 문제는 다음과 같습니다. 주어진 정수 배열에서 연속된 부분 배열 중 가장 큰 합을 구하는 문제를 해결하세요. def max_subarray_sum(nums): # 초기화 # 최대 합계 변수 음의 무한대로 초기화 max_sum = float('-inf') # 현재 합계 변수 0으로 초기화 current_sum = 0 # 목록에 대한 반복 for num in nums: current_sum = max(num, current_sum + num) max_sum = max(max_sum, current_sum) return max_sum # 테스트 nums.. 2024. 5. 29. 이전 1 다음 728x90 반응형
