2026-1-Algorithm-assignments: 알고리즘 과제 3주차 구현 및 테스트

이번 커밋에서는 3주차 알고리즘 과제에 해당하는 4개의 파이썬 파일에 대한 구현과 테스트 코드를 추가했습니다. 각 파일은 분할 정복 기법을 활용하여 특정 문제를 해결하도록 설계되었습니다.

요약

이번 커밋은 2.1.location_problem.py, 2.2.mergesort_problem.py, baekjoon_17829_problem.py, leetcode_215_problem.py 파일에 대한 코드를 작성하고 테스트를 진행했습니다. 각 파일은 분할 정복 패러다임을 적용하여 배열에서 특정 값의 위치를 찾거나, 배열을 정렬하거나, 2차원 배열에 222-풀링을 적용하는 등의 문제를 해결합니다.

배경 및 목적

3주차 과제는 분할 정복 기법의 이해와 적용을 목표로 합니다. 각 문제는 분할 정복의 기본 원리를 바탕으로 재귀적으로 문제를 해결하며, 효율적인 알고리즘 설계를 학습하는 데 목적이 있습니다.

• 2.1.location_problem.py: 정렬된 배열에서 특정 값의 위치를 O(lg n) 시간 복잡도로 찾는 방법을 학습합니다.
• 2.2.mergesort_problem.py: 병합 정렬 알고리즘을 구현하여 O(n lg n) 시간 복잡도로 배열을 정렬하는 방법을 익힙니다.
• baekjoon_17829_problem.py: 2차원 배열에 222-풀링을 재귀적으로 적용하여 최종 값을 도출하는 문제를 해결합니다.
• leetcode_215_problem.py: LeetCode 문제 해결을 통해 분할 정복을 활용한 K번째로 큰 원소 찾기를 구현합니다.

구현 내용

총 413 라인의 코드가 추가되었습니다.

변경된 파일 목록

• Week03_problem/2.1.location_problem.py
• Week03_problem/2.2.mergesort_problem.py
• Week03_problem/baekjoon_17829_problem.py
• Week03_problem/leetcode_215_problem.py

2.1.location_problem.py

이 파일은 정렬된 배열 S에서 값 x의 위치를 찾는 location 함수를 구현합니다. 분할 정복을 사용하여 탐색 범위를 절반씩 줄여나가며, x를 찾지 못하면 -1을 반환합니다. 테스트 케이스를 통해 다양한 상황에서 함수가 올바르게 동작하는지 확인했습니다.

2.2.mergesort_problem.py

병합 정렬 알고리즘을 구현한 파일입니다. mergesort 함수는 배열을 재귀적으로 분할하고, merge 함수를 사용하여 정렬된 부분 배열들을 병합합니다. merge 함수는 두 개의 정렬된 배열을 받아 하나의 정렬된 배열로 만드는 역할을 합니다. 다양한 테스트 케이스를 통해 병합 정렬의 정확성을 검증했습니다.

baekjoon_17829_problem.py

백준 17829번 문제를 해결하는 pooling 함수를 클래스 Solution 내부에 구현했습니다. 이 함수는 2차원 배열을 2x2 블록으로 나누고, 각 블록에서 두 번째로 큰 값을 선택하는 과정을 재귀적으로 반복합니다. 최종적으로 1x1 크기가 될 때까지 이 과정을 수행하여 값을 반환합니다. 다양한 크기의 행렬에 대한 테스트 케이스를 추가하여 검증했습니다.

leetcode_215_problem.py

LeetCode 215번 문제인 "K번째으로 큰 원소 찾기"를 해결하는 findKthLargest 함수를 구현했습니다. 내부적으로 mergeSort 함수를 사용하여 배열을 정렬한 후, 정렬된 배열의 마지막에서 k번째 인덱스에 해당하는 값을 반환합니다. 다양한 예제 입력에 대한 테스트를 통해 정확성을 확인했습니다.

배운 점 및 개선점

이번 과제를 통해 분할 정복 기법의 기본 원리를 명확히 이해하고, 재귀 호출을 통해 문제를 효율적으로 해결하는 방법을 배웠습니다. 각 문제에서 요구하는 특정 조건에 맞춰 분할 정복 전략을 적용하는 연습을 했습니다.

앞으로 개선할 점으로는 테스트 코드의 커버리지를 더욱 높이는 것을 고려할 수 있습니다. 또한, 각 알고리즘의 시간 복잡도 및 공간 복잡도 분석을 더욱 심층적으로 수행하여 최적화 방안을 모색할 필요가 있습니다.

다음 단계로는 다른 분할 정복 관련 문제들을 풀어보면서 이 기법에 대한 숙련도를 더욱 높여나갈 계획입니다.