2주차 - 알고리즘

카테고리

프로그래밍/소프트웨어 개발

서브카테고리

데이터 분석

대상자

소프트웨어 개발자, 특히 알고리즘과 자료구조를 학습 중인 중급자

핵심 요약

• 링크드 리스트 병합: mergeTwoLists() 함수를 통해 정렬된 두 링크드 리스트를 새로운 정렬 리스트로 병합 (C++ 구현)
• 링크드 리스트 역순: reverseList() 함수로 헤드 포인터를 기반으로 리스트를 역순 (dummy node 활용)
• 사이클 탐지: hasCycle() 함수를 통해 두 포인터로 사이클 존재 여부 확인 (Floyd's Cycle Detection Algorithm)
• 최대 서브어레이 합계: maxSubArray() 함수로 Kadane's Algorithm 적용, O(n) 시간 복잡도로 최대 합계 계산

섹션별 세부 요약

1. 정렬된 링크드 리스트 병합

• ListNode 구조체로 노드 정의 (val, next)
• mergeTwoLists() 함수:

- dummyHead 생성 후 current 포인터로 새 리스트 순회

- list1과 list2 중 작은 값 선택 및 연결

- 한 리스트가 끝나면 나머지 연결

• 예제: list1 = [1,3,5], list2 = [2,4,6] → [1,2,3,4,5,6]

2. 링크드 리스트 역순

• reverseList() 함수:

- dummy 노드 생성 후 current 포인터로 원본 리스트 순회

- current->next를 dummy->next에 삽입 (헤드부터 역순 연결)

• 예제: 1 → 2 → 3 → 4 → 4 → 3 → 2 → 1

3. 사이클 탐지

• hasCycle() 함수:

- slowPointer와 fastPointer로 이동 (slow: 1단계, fast: 2단계)

- 포인터가 만나면 사이클 존재 (slow == fast)

• 예제: 1 → 2 → 3 → 4 → 2 → 사이클 존재 여부: true

4. 최대 서브어레이 합계

• maxSubArray() 함수:

- currentMax와 globalMax 변수로 최대 합계 계산

- currentMax가 음수면 0으로 리셋 (Kadane's Algorithm)

• 예제: [-2,1,-3,4,-1,2,1,-5,4] → 최대 합계: 6 (4, -1, 2, 1)

결론

• 알고리즘 실습 팁: mergeTwoLists()와 reverseList()는 dummy node 활용이 핵심, hasCycle()은 두 포인터로 시간 복잡도 O(n) 유지, maxSubArray()는 Kadane's Algorithm 적용 시 O(n) 계산 가능.
• 실무 적용: 자료구조 문제 해결 시, 메모리 효율성과 시간 복잡도를 고려한 알고리즘 선택이 중요.