[부트캠프 3일차] 시간복잡도와 DataFrame 전처리 정리

wb_sunny 오늘 일상 공유

오늘은 원래 실습 시간이었는데, 그걸 모르고 미션 과제를 아르바이트하면서 이미 다 풀어버렸다. 그래서 오전엔 프로그래머스 문제를 다시 붙잡고 직접 고도화하면서 시간을 보냈고, 이후 시간부터는 DataFrame 마스터하기 인강을 들었다. 오늘 푼 코테 내용이랑 공부한 내용을 공유하려고 한다.

edit_note 오늘 코테 문제

문제	가장 큰 정사각형 돗자리 찾기
플랫폼	프로그래머스
핵심 요구사항	공원 자리 배치도에서 지민이가 깔 수 있는 가장 큰 정사각형 돗자리의 한 변 길이를 구하기

python

def solution(mats, park):
    answer = -1
    
    rows = len(park)
    cols = len(park[0])
    
    dp = [[0] * cols for _ in range(rows)]
    
    for i in range(rows):
        for j in range(cols):
            if park[i][j] != "-1":
                dp[i][j] = 0
            else:
                
                up = dp[i-1][j] if i > 0 else 0
                left = dp[i][j-1] if j > 0 else 0
                up_left = dp[i-1][j-1] if(i > 0) and (j > 0) else 0
                
                dp[i][j] = min(up, left, up_left) + 1
            
            if dp[i][j] in mats:
                answer = max(answer, dp[i][j])
     
    return answer

풀이 접근법

핵심 아이디어는 이거예요: 정사각형이 되는지 매번 안쪽을 다 뒤져보면 느리다. 그래서 "바로 위 칸, 바로 왼쪽 칸, 왼쪽 위 대각선 칸"이 이미 계산해놓은 결과를 그대로 가져다 쓰는 방식으로 푼다.

1

dp 배열 만들기

dp[i][j]는 "이 칸을 오른쪽 아래 끝으로 잡았을 때, 만들 수 있는 가장 큰 정사각형의 한 변 길이"를 저장하는 곳이다. 일단 전부 0으로 채워둔다.

python

rows = len(park)
cols = len(park[0])
dp = [[0] * cols for _ in range(rows)]

2

사람이 있는 칸이면 그냥 0

park[i][j]가 문자열인 거 주의해야 한다. 빈칸은 "-1", 사람 있으면 알파벳이다. 사람이 앉아있으면 그 칸은 정사각형에 못 들어가니까 무조건 0으로 끝.

python

if park[i][j] != "-1":
    dp[i][j] = 0

3

빈칸이면 위/왼쪽/왼쪽위 중에 제일 작은 값 + 1

빈칸이면 위쪽 칸/왼쪽 칸/왼쪽 위 대각선 칸의 dp값 중에서 가장 작은 걸 골라서 +1을 해준다. 그 이유는, 어떤 칸은 3자리 정사각형을 깔 수 있고 어떤 칸은 1자리 정사각형밖에 못 깔 수 있는 상황이면, 결국 셋 중에 가장 작은 쪽에 맞춰서만 정사각형을 만들 수 있기 때문이다. 그리고 지금 이 칸도 빈칸이라서 깔 수 있는 자리니까, 거기에 +1을 더해주는 것이다.

python

up = dp[i-1][j] if i > 0 else 0
left = dp[i][j-1] if j > 0 else 0
up_left = dp[i-1][j-1] if(i > 0) and (j > 0) else 0
dp[i][j] = min(up, left, up_left) + 1

4

dp값이 mats에 있는 크기면 answer 갱신

이 칸에서 나온 dp값이 지민이가 실제로 가지고 있는 돗자리 크기(mats) 중 하나와 일치하면, 그 크기를 깔 수 있다는 뜻이니까 answer를 그 값으로 갱신한다. 지금까지 나온 것 중 제일 큰 값을 유지해야 하니까 max(answer, dp[i][j])로 비교하면서 갱신한다.

python

if dp[i][j] in mats:
    answer = max(answer, dp[i][j])

이렇게 하면 격자를 한 번만 순회하면서, dp값을 계산하는 동시에 mats에 있는 것 중 가장 큰 걸 바로바로 확인할 수 있다. 만약 끝까지 한 번도 조건을 만족 못 하면 처음 설정한 answer = -1이 그대로 반환된다.

시간 복잡도

이걸 정리해두려는 이유는, 코테를 보다 보면 답은 맞았는데 시간복잡도를 맞추거나 줄여야 하는 상황이 종종 생기기 때문이다. 그냥 정답만 통과시키는 문제 풀이에서 한 단계 더 나아가서, "이 코드가 왜 느린지"를 스스로 설명할 수 있을 정도로 시간복잡도를 제대로 이해하고 싶어서 오늘 계산 과정을 정리해본다.

시간복잡도가 뭐냐면 — 입력 크기가 커질수록 코드 실행 시간이 얼마나 늘어나는지를 나타내는 지표다. 정확한 초 단위 시간이 아니라, "입력이 2배가 되면 시간이 어떻게 변하는가"를 보는 것이고, 이를 표현할 때 Big-O 표기법(O(...))을 쓴다.

1

O(1) — 상수 시간

입력 크기랑 상관없이 항상 똑같은 시간이 걸리는 경우다.

python

def get_first(arr):
    return arr[0]

배열이 10개짜리든 1000개짜리든, 첫 번째 원소 꺼내는 데 걸리는 시간은 똑같다. 그래서 O(1).

2

O(n) — 선형 시간

입력 크기에 정비례해서 시간이 늘어나는 경우다.

python

def find_max(arr):
    max_val = arr[0]
    for x in arr:
        if x > max_val:
            max_val = x
    return max_val

배열 길이가 n이면 반복문이 n번 도니까 O(n). 배열이 2배로 커지면 시간도 대략 2배로 늘어난다.

3

O(n²) — 이중 반복문

반복문 안에 반복문이 또 있으면 곱해진다.

python

def has_duplicate(arr):
    for i in range(len(arr)):
        for j in range(len(arr)):
            if i != j and arr[i] == arr[j]:
                return True
    return False

바깥 루프 n번, 안쪽 루프도 매번 n번 도니까 n × n = O(n²). 배열이 2배 커지면 시간은 4배로 늘어난다. 이게 왜 무서우냐면, 입력이 커질수록 격차가 기하급수적으로 벌어지기 때문이다.

4

O(log n) — 로그 시간 (참고용)

이진 탐색처럼, 매번 절반씩 버리면서 찾는 경우다. n이 아무리 커져도 절반씩 줄어드니까 시간이 아주 천천히 늘어난다. 오늘 짠 DP엔 안 나오지만 참고로 알아두면 좋다.

이제 오늘 짠 DP 코드에 적용해보기

python

dp = [[0] * cols for _ in range(rows)]

for i in range(rows):
    for j in range(cols):
        if park[i][j] != "-1":
            dp[i][j] = 0
        else:
            up = dp[i-1][j] if i > 0 else 0
            left = dp[i][j-1] if j > 0 else 0
            up_left = dp[i-1][j-1] if(i > 0) and (j > 0) else 0
            dp[i][j] = min(up, left, up_left) + 1
        
        if dp[i][j] in mats:
            answer = max(answer, dp[i][j])

여기서 시간복잡도를 계산하는 순서는 이렇다.

먼저 dp 초기화 부분. [[0] * cols for _ in range(rows)]는 rows × cols개의 칸을 하나씩 채우는 거니까 O(rows × cols)다.

그다음 이중 for문. for i in range(rows)가 rows번, 그 안에 for j in range(cols)가 cols번 도니까 곱하면 O(rows × cols).

안쪽에서 하는 일들을 보면, up, left, up_left 구하는 건 배열 인덱스 접근이라 전부 O(1). min()도 값 3개 비교하는 거라 O(1).

문제는 if dp[i][j] in mats: 이 줄이다. in 연산자는 리스트 안에 그 값이 있는지 하나씩 다 훑어보면서 확인한다. mats의 길이를 k라고 하면, 이 한 줄이 최악의 경우 O(k)가 걸린다.

이게 rows × cols번 반복되는 루프 안에 들어있으니까, 전체적으로는 O(rows × cols × k)가 되는 것이다.

여기서 든 생각

✓이렇게 시간복잡도를 하나씩 뜯어보니까, if dp[i][j] in mats:처럼 이중 for문 안에서 k만큼 곱해지는 구조가 좀 비효율적이라는 생각이 들었다. 어차피 우리가 필요한 건 "dp에서 나올 수 있는 가장 큰 정사각형 크기"이고, 그 값이 mats 중 어떤 것과 정확히 일치하는지는 dp를 다 채운 후에 한 번만 확인해도 되는 문제였다.

✓그래서 이중 for문 안에서는 mats 체크 없이 max_size 변수 하나만 두고 dp값이 나올 때마다 max()로 최댓값만 갱신하면 되고, for문 두 개가 다 끝난 다음에 mats를 큰 순서로 정렬해서 max_size 이하인 것 중 가장 큰 걸 찾아 반환하는 방식이 시간복잡도상 k를 덜 곱하게 되니까 더 빠르다고 판단했다.

참고로 만약 if dp[i][j] in mats: 대신, max_size = max(max_size, dp[i][j])처럼 mats 검사 없이 최댓값만 저장하는 방식으로 바꾸면, 그 줄은 O(1)이 되니까 전체 복잡도가 O(n²)로 줄어든다. k가 붙고 안 붙고의 차이가 여기서 갈리는 것이다.

결론적으로 아래 방식으로 푸는 게 좋겠다고 생각했다

python

def solution(mats, park):
    dp = [[0] * cols for _ in range(rows)]
    max_size = 0
    
    for i in range(rows):
        for j in range(cols):
            if park[i][j] != "-1":
                dp[i][j] = 0
            else:
                up = dp[i-1][j] if i > 0 else 0
                left = dp[i][j-1] if j > 0 else 0
                up_left = dp[i-1][j-1] if(i > 0) and (j > 0) else 0
                dp[i][j] = min(up, left, up_left) + 1
            
            max_size = max(max_size, dp[i][j])  # 여기서는 mats 검사 안 함
    
    for size in sorted(mats, reverse=True):
        if size <= max_size:
            return size
    return -1

이렇게 바꾸면 이중 for문 안의 연산이 전부 O(1)이 되니까 O(rows × cols)로 끝나고, mats 처리는 루프 밖에서 O(k log k)(정렬) + O(k)(순회)만 추가로 붙는다. 두 항을 더해도 rows × cols가 k보다 훨씬 크기 때문에 전체 시간복잡도는 O(n²)로 수렴한다. 원래 O(n² × k)였던 것과 비교하면, "이중 루프 안에 있던 k배수 연산을 루프 밖으로 빼냈다"는 게 최적화의 핵심이었다.

menu_book 오늘 공부한 내용

학습 주제	DataFrame 기본기, 데이터 다듬기 (결측치·중복값·이상치·문자열 가공·스케일링)
참고 자료	코드잇 스프린트 AI 엔지니어 부트캠프 강의자료 (Colab)

DataFrame 기본기

Colab 세션이 끊기면 파일이 날아가기 때문에, Google Drive를 마운트해서 csv를 불러오는 방식으로 작업했다.

python

from google.colab import drive
drive.mount('/content/drive')

loan_df = pd.read_csv('/content/drive/MyDrive/codeit/ai_14/pre_course/dataframe/loan.csv')

loan_df.head()      # 상위 5개 row (tail은 마지막)
loan_df.shape       # row, col 개수
loan_df.dtypes      # 컬럼별 데이터 타입
loan_df.info()      # Non-Null Count로 결측값 확인 가능
loan_df.describe(include='all')

괄호가 있는 건 DataFrame에 동작하는 함수, 괄호가 없는 건 DataFrame의 정보를 담고 있는 변수라는 구분이 헷갈리지 않게 도움이 됐다.

메서드	기능
sort_values(by='컬럼')	기본 오름차순 정렬, 결측값은 맨 밑. ascending=False로 내림차순
set_index('컬럼') / reset_index()	특정 컬럼을 인덱스로 지정 / 인덱스 초기화
rename(columns={...})	특정 컬럼명만 재설정
astype('float')	특정 컬럼 타입 변경
unique() / value_counts()	고유값 목록 / 값별 개수 (normalize=True면 비율)
drop('row') / drop(columns='컬럼')	row 삭제(axis=0) / 컬럼 삭제(axis=1)
to_csv('경로')	데이터 내보내기. to_excel이면 엑셀로 저장

조건 필터링 시 논리 연산자 우선순위는 not > and > or 순서라는 점도 다시 짚었다.

결측치(Missing Value) 다루기

isna()로 결측 여부를 True/False로 확인하고, isna().sum()으로 컬럼별 개수를 파악한다. isna().any(axis=1)은 row 단위로 결측값이 하나라도 있으면 True를 반환하는 불린 시리즈를 준다.

python

airbnb_df[airbnb_df.isna().any(axis=1)]  # 결측값이 있는 row만 추출

airbnb_df.dropna()  # 결측값이 있는 row 전부 삭제

rating_mean = airbnb_df['rating'].mean()
airbnb_df['rating'].fillna(rating_mean)  # 평균값으로 대체

처리 방향	기준
결측값 삭제	개수가 적어 삭제해도 영향이 작을 때, 혹은 컬럼/row 대부분이 결측값일 때
다른 값으로 채우기	연속형 숫자는 평균·중간값, 범주형 데이터는 최빈값을 주로 사용

중복값(Duplicate) 다루기

duplicated()는 기본적으로 keep='first'로 동작해서, 같은 id가 여러 번 나오면 처음 등장한 행은 제외하고 그 이후 등장하는 행만 True로 표시한다. 그래서 duplicated(subset='id')만 걸어보면 짝이 안 맞아 보이는 행이 나오는데, 이는 첫 등장 행이 화면 밖(더 위쪽 인덱스)에 있기 때문이다.

python

airbnb_df.duplicated().sum()  # 중복된 row 개수

airbnb_df[airbnb_df.duplicated(subset='id')]              # keep='first' 기본값
airbnb_df[airbnb_df.duplicated(subset='id', keep='last')] # 마지막 행만 제외
airbnb_df[airbnb_df.duplicated(subset='id', keep=False)]  # 전부 표시, 아무것도 안 뺌

airbnb_df.drop_duplicates(subset='id')  # keep='first'면 첫 번째만 남기고 삭제

옵션	제외되는 행	결과
keep='first' (기본값)	각 그룹의 첫 번째	나머지 전부 True
keep='last'	각 그룹의 마지막	나머지 전부 True
keep=False	없음	중복 그룹 전체가 True

first/last는 "그룹 크기 - 1개"만 보여주고, False는 그룹 전체를 보여준다는 차이를 명확히 이해했다.

이상치(Outlier) 찾기 — IQR

python

q1 = airbnb_df['price'].quantile(0.25)
q3 = airbnb_df['price'].quantile(0.75)

iqr = q3 - q1
lower_limit = q1 - 1.5 * iqr
upper_limit = q3 + 1.5 * iqr

condition1 = airbnb_df['price'] >= lower_limit
condition2 = airbnb_df['price'] <= upper_limit

airbnb_df[condition1 & condition2]  # 이상점 제외

처리 방법은 세 가지: 아무것도 하지 않기 / 정상범위 경계값에 맞추기(clip) / 이상점 자체를 삭제하기.

문자 데이터 가공하기

python

airbnb_df['state'].str.lower()          # 전부 소문자로 (upper는 대문자)
airbnb_df['state'].str.capitalize()     # 앞글자만 대문자로

airbnb_df['location'].str.split(", ").str[0]  # ", "로 나누고 첫번째 값 가져오기

airbnb_df['neighborhood'] = airbnb_df['location'].str.split(", ").str[0]
airbnb_df['city'] = airbnb_df['location'].str.split(", ").str[1]
airbnb_df = airbnb_df.drop(columns='location')

airbnb_df['city'].str.strip()  # 앞뒤 공백 제거
airbnb_df['city'] = airbnb_df['city'].str.replace('.', '', regex=False)  # 특정 문자열 제거

스케일링 · 정규화

스케일링은 숫자 데이터의 단위나 범위를 일정하게 맞추는 것. 정규화는 모든 데이터를 0과 1 사이 값으로 바꾸는 것이다.

python

# 파생 변수 - waist_hip_ratio
patient_df['waist_hip_ratio'] = round(patient_df['waist'] / patient_df['hip'], 2)

# 정규화 (min-max)
patient_df['height'] = (patient_df['height'] - patient_df['height'].min()) / \
    (patient_df['height'].max() - patient_df['height'].min())

patient_df['height'].describe()

round()로 반올림 자릿수를 지정하는 부분과, 정규화 이후 값이 실제로 0~1 범위 안에 들어오는지 describe()로 확인하는 습관도 같이 챙겼다.

표준화 (Standardization)

각 값이 평균에 비해 얼마나 크거나 작은지 나타내는 것. 데이터의 평균을 0, 분산을 1로 변경한다. 각 데이터가 평균에서 얼마나 떨어져 있는지 비교할 때 쓴다.

python

patient_df['height'] = (patient_df['height'] - patient_df['height'].mean()) / \
                        patient_df['height'].std()

patient_df['height'].describe()
# 과학적 표기법으로 표기돼서 복잡해 보이는데,
# 평균값이 -9e-16처럼 나오는 건 10의 -16제곱이 곱해져 있다는 뜻이라
# 사실상 평균이 거의 0이고 표준편차가 1이 되는 것이다

표준편차는 각 값에서 평균을 빼고 제곱한 걸 다 더해서 개수로 나눈 뒤 루트를 씌운 값이라는 것도 다시 짚었다.

데이터 구간화 (Binning)

연속적인 숫자 데이터를 여러 개의 구간으로 분류하는 것.

python

pd.cut(patient_df['age'], bins=[20, 30, 40, 50, 60, 70], right=False)
# 구간을 나눠서 알려줌. 괄호는 포함 안 하는 거고 50대는 포함하는 구간
# 20세는 구간이 적용 안 돼서 결측값으로 남는데, right=False를 주면
# 왼쪽 값을 포함하고 오른쪽은 포함하지 않는 구간으로 바뀐다

pd.cut(patient_df['age'], bins=[20, 30, 40, 50, 60, 70], right=False,
       labels=['20s', '30s', '40s', '50s', '60s'])  # 구간 값을 보기 좋게 라벨링

apply()와 람다 함수로 데이터 가공하기

cut()이 구간화 전용 함수라면, apply()는 원하는 함수를 값 하나하나에 적용해주는 만능 함수다. 람다는 def 없이 한 줄로 쓰는 익명 함수라, 간단한 로직은 굳이 함수를 따로 정의하지 않고 바로 넣을 수 있다.

python

# apply()로 함수 적용 (괄호 없이 함수 이름만 넘김)
df['column2'].apply(np.sqrt)

# BMI 계산 후 람다로 비만 여부 분류
patient_df['bmi'] = round(patient_df['weight'] / patient_df['height']**2, 1)
patient_df['bmi'].apply(lambda x: 'Y' if x > 30 else 'N')

cut()은 구간화에 최적화된 코드라 간결하고, apply() + 람다는 원하는 조건을 자유롭게 넣을 수 있다는 차이를 이해했다. 상황에 맞게 골라 쓰면 될 것 같다.

psychology 오늘 들었던 생각

처음엔 코딩 문제를 풀기만 하면 되겠지라는 생각을 많이 했다. 그래도 시간 여유가 있을 때 시간복잡도를 한번 뜯어보고 싶었는데, 오늘 오전에 시간이 나서 직접 뜯어봤다. 그러니 불필요한 요인들이 눈에 들어왔고, 이걸 실제로 최적화해보니 뿌듯했다. 오늘은 얻어가는 게 있는 하루라고 느껴졌다. 앞으로도 시간복잡도를 생각하면서 문제를 풀어야겠다.

checklist 내일 할 일

• 부트캠프 4일차 수업 참석
• 프로그래머스 문제 한 개 풀기