728x90 반응형 알고리즘3 [알고리즘 공부] 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. [알고리즘 공부] 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 반응형
