퇴사 후 새로운 직장으로의 진입, 즉 취업은 많은 사람들에게 도전이 될 수 있습니다. 특히 IT와 소프트웨어 분야에서 취업을 원한다면 알고리즘 문제 풀이 능력이 필수적입니다. 본 강좌에서는 개발자 채용 시험에서 자주 출제되는 알고리즘 문제를 풀어보며 실력을 쌓는 방법을 소개하겠습니다.
문제 설명
문제: 두 배열의 교집합
두 개의 배열이 주어질 때, 두 배열의 교집합을 구하는 함수를 작성하세요. 교집합은 두 배열에 모두 존재하는 원소들의 집합을 의미합니다.
입력
- 정수 배열 A (길이: m, 1 ≤ m ≤ 10^5)
- 정수 배열 B (길이: n, 1 ≤ n ≤ 10^5)
출력
교집합 원소들이 담긴 배열을 오름차순으로 정렬하여 반환합니다. 교집합이 존재하지 않으면 빈 배열을 반환합니다.
예제
입력: A = [1, 2, 2, 1], B = [2, 2] 출력: [2] 입력: A = [4, 9, 5], B = [9, 4, 9, 8, 4] 출력: [4, 9]
문제 풀이 과정
문제 분석
주어진 두 배열 A와 B에서 공통적으로 존재하는 원소를 찾아내는 것이 과제입니다. 두 배열의 원소 중에서 동일한 원소들을 확인지은 후, 중복된 원소는 한 번만 포함되도록 교집합을 반환해야 합니다.
접근 방법
해당 문제를 해결하는 방법은 여러 가지가 있지만, 효율적인 방법은 해시 테이블(파이썬에서는 딕셔너리 또는 세트를 사용할 수 있음)을 사용하는 것입니다. 이 방법을 통해 두 배열을 각각 세트로 변환하여 교집합을 쉽게 구할 수 있습니다.
구현
1단계로 두 배열을 세트로 변환하고, 2단계로 세트 간의 교집합을 구합니다.
3단계로 교집합의 결과를 정렬하여 반환합니다.
def intersection(A, B):
# 1단계: 배열을 세트로 변환
set_A = set(A)
set_B = set(B)
# 2단계: 교집합 찾기
intersection_set = set_A.intersection(set_B)
# 3단계: 정렬하여 리스트로 변환
return sorted(list(intersection_set))
# 예제 실행
A = [1, 2, 2, 1]
B = [2, 2]
print(intersection(A, B)) # 출력: [2]
A = [4, 9, 5]
B = [9, 4, 9, 8, 4]
print(intersection(A, B)) # 출력: [4, 9]
복잡도 분석
시간 복잡도: O(m + n) – 두 배열을 세트로 변환하는 데 걸리는 시간, 그리고 교집합을 구하는 데 필요한 시간.
공간 복잡도: O(m + n) – 최악의 경우 두 배열 전체가 서로 다른 원소로 구성되어 있을 때 세트에 저장하기 위한 공간이 필요합니다.
마무리
이 알고리즘 문제는 코딩 테스트에서 자주 출제되며, 파이썬의 세트를 활용하여 효율적으로 해결할 수 있습니다. 알고리즘 문제를 풀 때는 문제 분석, 접근 방법, 구현 및 복잡도 분석의 단계로 나누어 체계적으로 접근하는 것이 중요합니다.
코딩 테스트 준비가 어려운 여정일 수 있지만, 꾸준히 연습하고 다양한 문제에 도전함으로써 자신감을 쌓아나갈 수 있습니다. 퇴사 준비와 함께 알고리즘 문제를 해결할 수 있는 능력을 기르시길 바랍니다.