CodingTest

[코테 1주차] 파이참 환경 세팅, 시간·공간 복잡도 & 프로그래머스 입문 문제 풀이

2025년 12월 28일 · 8분 읽기

1. 1주차 개요

이번 주차에서는 코딩테스트 준비의 첫 단계로, 파이썬 개발 환경에 익숙해지고 알고리즘의 기본 개념을 이해하는 데 집중했다.

강의를 통해 개념을 정리하고, 프로그래머스 문제 풀이는 강의 진도와 상관없이 매일 최소 5문제 이상 꾸준히 진행하는 방식으로 시작했다.

2. 1주차 목표

파이썬 개발 환경에 익숙해지기
시간 복잡도 / 공간 복잡도의 개념을 코드로 이해하기
알고리즘 문제 풀이 흐름에 익숙해지기
프로그래머스 입문 문제 풀이 루틴 만들기

3. 강의 내용 정리

3-1. 알고리즘과 친해지기 ① : 최댓값 찾기

문제 설명 숫자로 이루어진 배열이 주어졌을 때, 가장 큰 수를 반환하시오.

[3, 5, 6, 1, 2, 4]

풀이 1️⃣ 모든 원소를 서로 비교하는 방법

def find_max_num(array):
    for number in array:
        is_max_num = True
        for compare_number in array:
            if number < compare_number:
                is_max_num = False
        if is_max_num:
            return number

아이디어

하나의 숫자를 기준으로 모든 숫자와 비교
끝까지 더 큰 값이 없으면 최대값

특징

이중 반복문 사용
직관적이지만 비효율적

풀이 2️⃣ 기준 변수를 하나 두고 비교하는 방법 (권장)

def find_max_num(array):
    max_number = array[0]
    for number in array:
        if number > max_number:
            max_number = number
    return max_number

아이디어

현재까지의 최대값을 저장
더 큰 값이 나오면 갱신

특징

단일 반복문
실무와 코딩테스트에서 가장 많이 쓰이는 방식

3-2. 알고리즘과 친해지기 ② : 최빈값 찾기

문제 설명 문자열이 주어졌을 때 가장 많이 등장한 알파벳을 반환하시오. (최빈값이 여러 개면 알파벳 순으로 가장 앞선 문자 반환)

"hello my name is dingcodingco"

풀이 아이디어

알파벳은 총 26개 → 길이 26짜리 배열 사용
각 알파벳의 등장 횟수를 저장

def find_max_occurred_alphabet(string):
    alphabet_occurrence = [0] * 26

    for char in string:
        if not char.isalpha():
            continue
        index = ord(char) - ord('a')
        alphabet_occurrence[index] += 1

    max_count = 0
    max_index = 0
    for i in range(26):
        if alphabet_occurrence[i] > max_count:
            max_count = alphabet_occurrence[i]
            max_index = i

    return chr(max_index + ord('a'))

3-3. 시간 복잡도(Time Complexity)

입력값의 크기에 따라 연산 횟수가 얼마나 늘어나는가를 나타내는 개념이다.

최댓값 찾기 시간 복잡도 비교

풀이 1 (이중 반복문)

연산량: 2N² + N
시간 복잡도: O(N²)

풀이 2 (단일 반복문)

연산량: 2N + 1
시간 복잡도: O(N)

✅ 입력값 N이 커질수록 성능 차이는 극명해진다.

3-4. 공간 복잡도(Space Complexity)

입력값 크기에 따라 추가로 사용하는 메모리 공간의 크기

알파벳 배열(26칸) + 변수 몇 개 → 모두 상수 공간
두 풀이 모두 공간 복잡도는 O(1)

👉 공간 복잡도가 같다면 시간 복잡도로 성능을 판단한다.

3-5. 점근 표기법(Asymptotic Notation)

알고리즘 성능을 수학적으로 표현하는 방법이다.

Big-O (O) : 최악의 경우
Big-Ω (Ω) : 최선의 경우

예제: 배열에서 특정 요소 찾기

def is_number_exist(number, array):
    for element in array:
        if number == element:
            return True
    return False

최선의 경우: 첫 번째 원소 → Ω(1)
최악의 경우: 끝까지 탐색 → O(N)

👉 코딩테스트에서는 항상 Big-O 기준으로 판단한다.

4. 프로그래머스 문제 풀이 중 정리한 핵심 개념

4-1. 형변환 (Type Casting) + 나눗셈 + 올림 개념

형변환이란 데이터의 타입을 다른 타입으로 바꾸는 것을 말한다.

int(3.7)    # 3
float(3)    # 3.0
str(123)    # "123"

알고리즘 문제에서는 특히 float → int 형변환이 자주 등장한다.

// 연산자 주의점

//는 정수 나눗셈(몫 연산)이지만, 피연산자 중 하나라도 실수이면 결과는 float가 된다.

7 // 2     # 3
7.8 // 1   # 7.0

answer = 7.8
return answer // 1   # ❌ float 반환

코딩테스트에서는 값뿐만 아니라 반환 타입까지 정확히 비교하기 때문에, 정수 반환 문제에서 실수 타입은 오답이 될 수 있다.

권장 방식

return int(answer)

👉 정수 반환 문제에서는 int()로 명시적인 형변환을 하는 것이 가장 안전하다.

4-1-1. 올림 (Ceiling) 개념

1) 올림이란?

나눗셈 결과가 정수가 아닐 때, 값을 무조건 큰 정수 쪽으로 올리는 것을 말한다.

1.1 → 2
2.0 → 2
2.3 → 3

2) 알고리즘 문제에서 올림이 필요한 이유

알고리즘 문제에서는 다음과 같은 상황이 자주 등장한다.

사람 수 / 한 번에 처리 가능한 수
조각 수 / 묶음 크기
용량 / 단위 크기

👉 조금이라도 남으면 하나 더 필요

예)

8명을 7명씩 나누기 → 2판 필요
10개를 3개씩 담기 → 4봉지 필요

3) // 만 사용하면 안 되는 이유

8 // 7   # 1 ❌

//는 항상 내림이기 때문에 남는 값이 있어도 버려진다.

4) 올림을 만드는 방법

① 조건문 사용

if n % slice == 0:
    answer = n // slice
else:
    answer = n // slice + 1

② 정수 나눗셈 공식 사용 ⭐

answer = (n + slice - 1) // slice

또는 동일한 의미

answer = ((n - 1) // slice) + 1

👉 정수 연산만 사용하면서 올림 효과를 만든다.

③ math.ceil 사용

import math
answer = math.ceil(n / slice)

⚠️ /는 실수 연산이므로 코딩테스트에서는 정수 공식 방식이 더 안전하다.

5) (n - 1) // slice + 1 이 되는 이유

뒤의 +1은 무조건 하나 더 추가
딱 나누어떨어지는 경우에는 +1이 과해진다
그래서 앞에서 1을 미리 빼서 상쇄

n = 7
slice = 7

(7 - 1) // 7 + 1
# = 6 // 7 + 1
# = 0 + 1
# = 1

6) 자주 하는 실수

int(n / slice)     # ❌ 올림 안 됨
7.8 // 1           # ❌ 7.0 (float)

7) 핵심 요약

//는 내림
남으면 하나 더 필요 → 올림
가장 안전한 공식

(n + slice - 1) // slice

정수 반환 문제에서는 반환 타입 반드시 확인

4-2. 조건문 (if / elif / else)

기본 구조

if 조건1:
    실행문
elif 조건2:
    실행문
else:
    실행문

조건은 위에서부터 순서대로 검사
가장 먼저 True가 된 블록만 실행

if와 elif의 차이

# 잘못된 예
if x > 0:
    print("양수")
if x > 10:
    print("10보다 큼")

if를 여러 개 사용하면 모든 조건을 각각 검사
의도하지 않은 중복 실행 가능

# 권장 방식
if x > 10:
    print("10보다 큼")
elif x > 0:
    print("양수")

👉 서로 배타적인 조건은 반드시 elif 사용

else 사용 시 주의점

if score >= 60:
    return "합격"
else:
    return "불합격"

else는 모든 조건이 False일 때 실행
조건이 명확할 때만 사용하는 것이 좋다

# 더 깔끔한 방식
if score >= 60:
    return "합격"
return "불합격"

알고리즘 문제에서 자주 쓰이는 조건 패턴

# 범위 조건
if 0 <= x <= 100:
    pass

# 조기 종료 (early return)
if n == 0:
    return 0

👉 불필요한 연산을 줄여 가독성과 성능 모두 개선

조건문 + 형변환 실수 예시

answer = 7.8
if answer > 7:
    return answer   # ❌ float 반환

# 수정
if answer > 7:
    return int(answer)

👉 조건문 안에서도 반환 타입을 항상 의식해야 한다.

4-3. range() 함수 개념

range()는 연속된 정수 값을 만들어 주는 함수로, 주로 for 반복문에서 사용한다.

1) 기본 형태

range(끝)

0부터 시작
끝 - 1까지 생성

range(5)  # 0, 1, 2, 3, 4

2) 시작값과 끝값 지정

range(시작, 끝)

range(2, 6)  # 2, 3, 4, 5

3) 증가값(간격) 지정

range(시작, 끝, 증가값)

range(2, 11, 2)  # 2, 4, 6, 8, 10

4) range()의 특징

끝 값은 포함되지 않음
정수만 사용 가능
메모리를 거의 사용하지 않음

5) 반복문 사용 예

for i in range(1, 6):
    print(i)

4-4. GCD (Greatest Common Divisor, 최대공약수)

1) 정의

두 정수가 공통으로 나누어 떨어지는 수 중 가장 큰 수

2) 예시

GCD(8, 12) = 4
GCD(10, 25) = 5

3) 사용 이유

분수를 기약분수로 만들기 위해
두 수를 가장 단순한 비율로 표현하기 위해

4) 파이썬에서 사용

import math
math.gcd(a, b)

5) 분수 문제 활용 흐름

분자, 분모 계산
gcd(분자, 분모) 구하기
각각 나누기 → 기약분수 완성

4-5. 리스트(List)와 append() 활용

1) 리스트란?

numbers = [1, 2, 3]

여러 값을 순서대로 저장
알고리즘 문제의 배열 = 리스트

2) append()

answer = []
answer.append(2)
answer.append(4)
# [2, 4]

3) 배열 문제 기본 패턴

def solution(numbers):
    answer = []
    for n in numbers:
        answer.append(n * 2)
    return answer

4) 자주 하는 실수

❌ 정수로 초기화

answer = 0

✅ 리스트로 초기화

answer = []

❌ 값 덮어쓰기

answer = n * 2

✅ 누적

answer.append(n * 2)

4-6. 리스트 컴프리헨션

1) 개념

[표현식 for 항목 in 반복가능객체]

2) 기본 예시

numbers = [1, 2, 3]
[num * 2 for num in numbers]

3) 조건 포함

[num * 2 for num in numbers if num % 2 == 0]

4) 사용하면 좋은 경우

단순 반복 + 가공
바로 리스트 반환

⚠️ 복잡하면 for + append()가 더 가독성 좋음

4-7. 정렬 (Sorting)

1) 개념

오름차순 / 내림차순
중앙값, 최댓값/최솟값 문제에서 필수

2) 정렬 방법

sorted(array)      # 새 리스트
array.sort()       # 원본 변경

3) 내림차순

sorted(array, reverse=True)

4) 중앙값 주의점

sorted(array)[len(array)//2]

4-8. 최빈값 풀이에 사용된 문법

1) set() — 중복 제거

set(array)

2) enumerate()

for i, v in enumerate(['a', 'b', 'c']):
    print(i, v)

3) while

while len(array) != 0:
    pass

4) len()

len(array)

5) remove()

array.remove(value)

⚠️ 반복 중 리스트 수정은 실전에서 권장되지 않음

4-9. 조건식에서 숫자를 바로 사용하는 개념 (Truthiness)

1) False로 취급되는 값

0, 0.0
''
[], {}, ()
None

2) %와 조건식

if x % 2:      # 홀수
if x % 2 == 0: # 짝수

3) 리스트 컴프리헨션 활용

[x for x in range(n + 1) if x % 2]

4) 짝수만 고르기

[x for x in range(0, n + 1, 2)]

5) 자주 하는 오해

❌ if x % 2 → 짝수?

✅ 실제 의미 → 홀수 검사

5. 1주차 핵심 정리

시간 복잡도는 입력값 증가에 따른 연산 증가율을 본다
상수는 무시하고 차수(N, N²) 만 비교한다
공간 복잡도가 같다면 시간 복잡도가 더 중요하다
코딩테스트에서는 Big-O 기준으로 사고한다
정수 반환 문제에서는 형변환을 명확히 처리한다

GitHub 계정으로 댓글을 남길 수 있어요.