[C/Python] 심화 2

🚀 [알고리즘 정복] 심화 2: 자료구조와 정렬의 미학 (Python & C)

안녕하세요! 오늘은 백준 심화 2 단계의 핵심 문제들을 통해 데이터를 어떻게 효율적으로 관리하고 정렬하는지에 대해 깊이 있게 다뤄보겠습니다. 특히 편리한 Python과 로우레벨의 C언어를 비교하며 핵심 원리를 파헤쳐 봅니다.

---

1. 중복 제거의 마법: 집합(Set)과 정렬

관련 문제: [25192번: 인사성 밝은 곰곰이], [26069번: 붙임성 좋은 총총이]

데이터의 중복을 제거하고 "새로운 데이터"가 몇 개인지 세는 것은 알고리즘의 기본입니다.

• Python: set() 자료구조를 활용해 O(1)의 속도로 중복을 체크합니다. m.add(name) 한 줄이면 끝이죠.
• C언어: 표준 집합 자료구조가 없기에 '정렬 후 인접 요소 비교' 전략을 사용합니다. qsort로 데이터를 모은 뒤, 바로 앞의 데이터와 다를 때만 카운트하는 방식입니다.

---

2. 통계학: 데이터의 대푯값 찾기

관련 문제: [2108번: 통계학]

산술평균, 중앙값, 최빈값, 범위를 구하는 문제입니다. 여기서 C언어와 Python의 자료형 차이를 극명하게 느낄 수 있습니다.

• 산술평균과 반올림: Python은 round()를 쓰지만, C언어에서는 정확한 반올림을 위해 floor(sum/n + 0.5) 또는 round() 함수와 함께 double 형변환이 필수입니다.

최빈값(Mode): Python은 Counter().most_common()으로 쉽게 구하지만, C언어에서는 입력 범위(-4000 ~ 4000)를 인덱스로 변환한 **카운팅 배열(count[8001])**을 직접 만들어 해결했습니다.

---

3. 정렬의 끝판왕: 다중 조건 우선순위

관련 문제: [20920번: 영단어 암기는 괴로워]

단순히 숫자 크기가 아니라 빈도 -> 길이 -> 사전순이라는 3단계 조건을 적용해야 합니다.

• Python (Lambda): sort(key=lambda x: (-count[x], -len(x), x))로 매우 직관적인 구현이 가능합니다.
• C언어 (qsort & 구조체): 단어, 빈도, 길이를 하나로 묶는 **구조체(struct)**를 정의하고, compare 함수 내에서 if문을 단계별로 배치하여 우선순위를 결정합니다.

---

4. C언어의 심장: 메모리 관리 (malloc & free)

심화 단계를 거치며 가장 중요하게 다룬 부분은 동적 할당입니다. 특히 **이중 포인터(char**)**를 다룰 때의 주의사항을 정리합니다.

💡 핵심 요약: 왜 free를 반복문으로 하나요?

temp_list 같은 이중 포인터는 '주소를 담은 상자'와 '실제 데이터가 든 방'이 따로 존재합니다. 상자만 버리면(free) 그 안의 데이터들은 메모리 미아가 되어 **메모리 누수(Memory Leak)**를 일으킵니다. 반드시 안쪽 방부터 하나씩 비워줘야 합니다!

---

🎯 학습 포인트 요약 (정보처리기사 대비)

1. 시간 복잡도: 정렬은 보통 O(NlogN)이며, 해시(Python의 set / dict)는 O(1)입니다.
2. 메모리 레이아웃: 전역 변수는 데이터 영역에, 지역 변수는 스택에, malloc은 힙 영역에 저장됩니다.
3. 데이터 타입: 큰 합계를 구할 때는 오버플로우 방지를 위해 double이나 long long을 선택해야 합니다.

---

✅ 마치며

Python은 생산성이 뛰어나고, C언어는 시스템의 원리를 이해하게 해줍니다. 두 언어를 교차하며 문제를 풀다 보니 데이터가 메모리 위에서 어떻게 움직이는지 더 명확해진 것 같습니다.