13주차 · 실용 알고리즘과 데이터 활용

1. 카운팅·정렬·탐색 3가지 패턴을 EE 맥락(센서 로그, 측정값, 임계값)에서 사용한다
2. dict로 빈도를 세는 카운팅 패턴을 작성한다
3. sorted(..., key=함수)로 측정 레코드를 원하는 기준으로 정렬한다
4. for 루프와 break로 조건을 만족하는 첫 번째 항목을 효율적으로 탐색한다
5. 알고리즘 결과를 의사결정 문장으로 요약한다
6. O(n)과 O(n²) 차이를 루프 횟수로 직관적으로 설명한다

공학에서 “알고리즘”이라고 하면 복잡한 수학을 떠올리기 쉽지만, 실제 현장 데이터 처리의 대부분은 “이 데이터로 무엇을 결정하려는가”라는 질문에서 출발합니다. 그리고 그 질문은 거의 항상 다음 셋 중 하나로 정리됩니다. 무엇이 얼마나 자주 일어났는지, 무엇이 가장 중요한지, 어디서 처음 문제가 생겼는지입니다. 이 세 질문에 각각 카운팅·정렬·탐색으로 답합니다.

그래서 새로운 문제를 만나면 코드를 먼저 쓰지 말고, 문제 문장을 질문으로 바꾼 뒤 어느 패턴에 속하는지부터 분류하세요. 패턴이 정해지면 자료구조와 루프 구조가 거의 자동으로 따라옵니다.

counts = {}
for x in items:
    counts[x] = counts.get(x, 0) + 1

def sort_key(item):
    return item["value"]   # 정렬 기준을 함수로 명시한다

ordered = sorted(items, key=sort_key)

found = None
for x in items:
    if x > threshold:
        found = x
        break   # 첫 번째 매치에서 즉시 종료

1. 문제를 먼저 카운팅 / 정렬 / 탐색 중 하나로 분류한다
2. 카운팅·조회가 많으면 dict를 쓴다
3. 첫 번째 항목만 필요하면 break로 조기 종료한다
4. 결과를 의사결정 문장 한 줄로 요약한다

세 패턴은 이미 배운 문법을 새로운 의도로 다시 쓰는 것입니다. 아래 4가지 도구의 “왜 쓰는가”를 먼저 익혀 두면 코드가 훨씬 쉽게 읽힙니다.

시간복잡도는 데이터가 커질 때 작업량이 어떤 속도로 늘어나는지를 나타냅니다. 정확한 초 단위 시간보다 증가 추세를 봅니다. 측정값이 24개일 때는 어떤 방법을 써도 충분히 빠르지만, 24만 개가 되면 이 추세 차이가 실제 실행 시간 차이로 드러납니다.

• O(n): 루프 한 겹 → 데이터 2배면 반복 횟수도 약 2배 (예: 리스트를 한 번 훑기)
• O(n²): 루프 두 겹 → 데이터 2배면 반복 횟수는 약 4배 (예: 모든 쌍을 비교)

위 그림에서 두 곡선은 작은 n에서는 큰 차이가 없지만, n이 커질수록 O(n²)가 급격히 위로 치솟습니다. 같은 데이터를 두 겹 루프로 비교하는 방식은 데이터가 조금만 커져도 빠르게 느려진다는 뜻입니다. 그래서 “같은 키를 또 찾으려고 리스트를 매번 다시 훑는” 코드는 O(n²)가 되기 쉽고, 이때 dict로 한 번에 조회하면 O(n)으로 줄일 수 있습니다.

실행 시간이 아니라 반복 횟수를 세어 보면 O(n)과 O(n²) 차이를 더 쉽게 볼 수 있습니다. 아래 예제에서 n을 10에서 100으로 바꾸면, 한 겹 루프는 10배 늘지만 두 겹 루프는 100배 늘어납니다.

카운팅은 긴 리스트를 짧은 빈도표로 압축하는 작업입니다. 수백 줄의 상태 로그를 그대로 읽는 대신, “각 상태가 몇 번 나왔는가”라는 한 장의 요약표로 바꾸면 시스템 상태를 한눈에 파악할 수 있습니다. 이때 표의 키는 상태 이름이고 값은 누적 횟수이므로, 자료구조는 자연스럽게 dict가 됩니다.

핵심은 counts.get(x, 0) + 1 한 줄입니다. get(x, 0)은 “키 x가 이미 있으면 그 값을, 없으면 0을 돌려줘”라는 뜻입니다. 그래서 처음 보는 상태는 0에서 시작해 1이 되고, 이미 본 상태는 기존 값에 1을 더합니다. 만약 dict 대신 list로 “이 상태가 전에 나온 적 있나?”를 매번 다시 훑으면 루프 안에 또 루프가 생겨 O(n²)가 됩니다. 반면 dict 조회는 평균 O(1)이라 전체가 O(n)으로 끝납니다. 카운팅에 dict를 쓰는 이유가 여기 있습니다.

위 그림처럼 입력 리스트를 왼쪽에서 오른쪽으로 한 번만 훑으면서, 같은 키를 만날 때마다 오른쪽 빈도표의 막대를 1칸씩 키웁니다. 마지막에 sum(counts.values())가 원본 길이와 같은지 확인하면, 빠뜨리거나 중복으로 센 항목이 없는지 검증할 수 있습니다.

• counts.get(status, 0): 딕셔너리에 키가 없으면 0을 기본값으로 반환합니다
• max(counts, key=get_count): counts 딕셔너리의 키 중에서 get_count를 적용했을 때 가장 큰 값을 찾습니다. 여기서 key는 “무엇을 기준으로 비교할 것인가”를 알려주는 함수입니다
• counts.values(): 딕셔너리에서 값만 꺼냅니다. 예를 들어 sum(counts.values())는 세어 놓은 전체 횟수가 원본 로그 길이와 같은지 검증할 때 유용합니다
• 결과는 단순한 숫자가 아니라 의사결정 문장으로 마무리합니다

카운팅 결과를 보고할 때는 가장 많이 나온 상태부터 보여 주는 경우가 많습니다. 딕셔너리의 items()는 ("OK", 4)처럼 키와 값이 한 쌍인 tuple들을 만들어 줍니다. 이때 item[0]은 상태 이름, item[1]은 횟수입니다.

둘 다 내림차순 정렬에 사용할 수 있습니다. reverse=True는 “정렬 결과 전체를 뒤집는다”는 뜻이고, -item[1]은 “횟수에 마이너스를 붙여 큰 값이 앞에 오도록 기준을 바꾼다”는 뜻입니다. 초급 단계에서는 둘 중 하나만 일관되게 쓰면 충분하지만, 여러 기준을 섞어 정렬할 때는 return (-count, name)처럼 기준 함수를 쓰는 방식이 읽기 쉽습니다.

정렬은 “어떤 기준으로 우선순위를 매길 것인가”를 코드로 표현하는 과정입니다. **“각 레코드에 점수표를 붙인 뒤 그 점수로 줄을 세운다”**고 생각하면 쉽습니다. 이 “점수표를 붙이는 규칙”이 key 함수입니다. 정렬 알고리즘 자체는 신경 쓰지 않아도 되고, 우리가 정하는 것은 비교 기준 하나뿐입니다.

sorted(..., key=함수)에서 key에는 함수 객체를 넘깁니다. lambda도 사용할 수 있지만, 이 수업에서는 가독성을 위해 **이름 있는 함수(def)**를 먼저 권장합니다. 정렬 기준을 함수로 분리하면, 기준이 바뀌어도 정렬 코드는 그대로 두고 key 함수만 고치면 됩니다.

위 그림에서 key 함수는 각 채널에 (-snr, id)라는 비교용 점수를 매깁니다. snr에 마이너스를 붙였으므로 SNR이 큰 채널이 앞으로 옵니다(내림차순). SNR이 같은 CH3·CH4는 2차 기준인 채널 ID 오름차순으로 순서가 정해집니다. 이렇게 튜플로 여러 기준을 한 번에 넘기면 “1차 기준이 같을 때 어떻게 처리할지(tie-break)“까지 명확하게 표현됩니다. 또한 Python의 sorted는 안정 정렬이라, 동점 항목의 원래 등장 순서가 그대로 보존됩니다.

sorted(items, key=f)는 각 원소에 함수 f를 적용한 결과를 기준으로 정렬합니다. 함수 이름만 넘기고 괄호는 붙이지 않습니다.

def sort_key(record):
    return record["snr"]          # 함수를 정의하고

ordered = sorted(records, key=sort_key)   # 이름만 넘긴다 (sort_key() 가 아님)

• -ch["snr"]를 쓰는 이유: sorted는 기본 오름차순이므로 내림차순으로 정렬하려면 부호를 반전합니다
• CH3와 CH4는 SNR이 같으므로 두 번째 기준인 채널 ID 오름차순으로 결정됩니다
• 정렬 결과의 첫 번째 원소가 최우선 채널입니다

탐색은 “조건을 만족하는 항목을 찾는” 패턴입니다. 여기서 배우는 방식은 앞에서부터 하나씩 확인하는 **선형 탐색(linear search)**으로, 데이터가 정렬되어 있지 않아도 항상 동작하는 가장 기본적인 방법입니다. **“앞에서부터 하나씩 확인하다가 원하는 것을 찾는 순간 멈춘다”**는 그림을 떠올리면 됩니다.

핵심은 두 가지입니다. 첫째, 첫 번째 매치만 필요하면 break로 루프를 즉시 종료해 불필요한 반복을 줄입니다. 가장 좋을 때는 첫 항목에서 끝나고, 가장 나쁠 때는 끝까지 가며, 평균적으로는 절반쯤 확인합니다. 둘째, found = None으로 시작해 두면 루프가 끝난 뒤 “찾았다 / 못 찾았다”를 명확히 구분할 수 있습니다. 탐색에서는 “못 찾음”도 똑같이 중요한 결과이기 때문입니다.

위 그림에서 임계값 5.0 V를 넘는 첫 값(5.2 V)을 만나면 break가 실행되어 뒤쪽 값은 확인하지 않습니다. 6개 중 4개만 보고 멈춘 것이 조기 종료의 효과입니다.

• break는 첫 번째 매치를 찾은 즉시 루프를 종료합니다 — 이후 데이터를 불필요하게 확인하지 않습니다
• loop_count를 출력하면 조기 종료 효과를 직접 확인할 수 있습니다
• first_over is not None 조건으로 탐색 실패 케이스를 안전하게 처리합니다

탐색에서는 “찾았다”만큼 “못 찾았다”도 중요한 결과입니다. 처음에 found = None으로 시작하면, 루프가 끝난 뒤에도 None인지 확인해서 실패 케이스를 안전하게 처리할 수 있습니다.

실제 문제는 한 패턴만 쓰고 끝나지 않는 경우가 많습니다. 아래 예시는 같은 채널 로그에서 상태를 세고, 전력 기준으로 정렬하고, 기준보다 강한 첫 채널을 찾습니다.

1. status_counts는 dict 카운팅 패턴입니다.
2. ordered는 정렬 결과이므로 원본 channel_log와 순서가 다릅니다.
3. 첫 번째 후보만 필요하므로 탐색 루프에서 break를 사용합니다.
4. 마지막 assert는 상태 카운트가 원본 데이터 개수와 맞는지 확인합니다.

1. 이론: 문제를 “카운팅 / 정렬 / 탐색” 중 하나로 분류한다.
2. 이론: 자료구조를 선택하고 루프 겹 수를 예상한다.
3. 코드: 가장 짧은 정답 루프부터 작성한다.
4. 코드: 중간 결과(counts, ordered)를 출력해 검증한다.
5. 해석: 결과를 근거로 다음 행동 문장을 한 줄 작성한다.

• 문제를 카운팅/정렬/탐색 중 하나로 먼저 분류했는가?
• 딕셔너리 카운팅에서 없는 key를 안전하게 처리했는가?
• 정렬 방향이 문제 의도와 맞는가?
• 첫 번째 결과만 필요할 때 break를 사용했는가?
• 숫자 결과 뒤에 해석 문장을 붙였는가?