• 알고리즘이 문제를 해결하는 데 걸리는 시간과 사용하는 메모리 양을 수치적으로 나타낸 것
• 입력 크기 N이 커질수록 성능이 어떻게 변하는지를 분석
• 주로 두 가지를 평가:
  • 시간 복잡도 (Time Complexity)
  • 공간 복잡도 (Space Complexity)

시간 복잡도 (Time Complexity)

정의

• 입력 크기 N에 따라 알고리즘이 수행하는 연산 횟수를 수학적으로 표현
• 반복문, 재귀 호출 등을 기준으로 분석
• 일반적으로 최악의 경우(Worst-case) 기준으로 분석

Big-O 표기법이란?

• 가장 영향력이 큰 항만 남기고, 나머지는 생략하는 방식
• 입력이 커질수록 전체 실행 시간에 가장 영향을 주는 항을 남겨 단순화

ex) O(3N² + 2N + 5) → O(N²)

주요 시간 복잡도 정리

시간 복잡도 예시 코드

# O(1)
def print_first(arr):
    print(arr[0])

# O(N)
def print_all(arr):
    for x in arr:
        print(x)

# O(N²)
def print_pairs(arr):
    for i in arr:
        for j in arr:
            print(i, j)

# O(log N) – 이진 탐색
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

공간 복잡도 (Space Complexity)

• 알고리즘이 추가로 사용하는 메모리 공간을 분석
• 입력값은 제외하고, 변수, 배열, 재귀 호출 등으로 사용되는 메모리만 고려

입력 크기에 따른 복잡도 한계

파이썬 내장 함수 시간 복잡도

실전 팁 요약

• 중첩 반복문 줄이기
• 정렬 후 이진 탐색 적용
• set, dict 활용으로 탐색 속도 개선
• 입력이 많을 경우 sys.stdin.readline()으로 입력 처리 최적화

핵심 요약

반복문의 개념

• 동일한 코드를 여러 번 실행할 때 사용.
• 파이썬에서는 for, while 두 가지 문법이 기본.
• 조건이 True인 동안 계속 반복 수행.

for 문 기본 구조

for 변수 in 반복가능한_객체:
    실행할_코드

for i in range(5):
    print(i)  # 0부터 4까지 출력

while 문 기본 구조

while 조건:
    실행할_코드

i = 0
while i < 5:
    print(i)
    i += 1

중첩 반복문

• 반복문 안에 또 다른 반복문을 사용하는 형태
• 완전탐색(브루트포스) 문제에서 자주 활용됨

for i in range(3):
    for j in range(2):
        print(i, j)

반복문의 시간 복잡도

재귀 함수 (Recursion)

재귀 함수의 개념

• 함수가 자기 자신을 다시 호출하는 방식.
• 복잡한 문제를 작게 나누어 처리할 수 있음.
• 반드시 종료 조건(Base Case)이 필요함.

기본 구조

def func():
    if 종료조건:
        return 결과
    else:
        return func()

팩토리얼 예시

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

재귀 함수의 동작 원리

• 함수가 스택에 쌓이며 호출되고, 종료 조건을 만나면 거꾸로 결과를 반환하며 정리된다.
• 메모리 구조상 스택(stack) 을 사용하며, 깊이가 너무 깊어지면 RecursionError 발생 가능.

반복문 vs 재귀 함수 비교

예제 : 1부터 N까지 합 구하기

for문

def sum_loop(n):
    total = 0
    for i in range(1, n+1):
        total += i
    return total

재귀함수

def sum_rec(n):
    if n == 0:
        return 0
    return n + sum_rec(n - 1)

피보나치 수열 (재귀)

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

• 중복 호출이 많아 성능이 비효율적.
• 향후 동적 프로그래밍(DP) 또는 메모이제이션으로 개선 가능.

핵심 요약

• 반복문은 조건을 만족하는 동안 반복 실행되는 구조.
• 재귀 함수는 동일한 문제를 더 작은 문제로 쪼개 자기 자신을 호출하여 해결.
• 재귀는 구현이 간단해질 수 있으나, 메모리와 성능에 주의가 필요.
• 알고리즘 문제 풀이 시 반복과 재귀 중 적절한 방식 선택이 중요하다.

재귀는 DFS, 백트래킹, 분할정복, 트리 탐색과 같은 고급 알고리즘에서 재귀 함수는 필수 도구로 사용된다.

• 문자(char)의 연속으로 이루어진 자료, 데이터.
• 파이썬에서는 문자열(str)이 불변(immutable) 객체이므로, 수정 시 새로운 문자열을 생성.
• C 언어에서는 char 배열을 사용하거나 char *를 동적 할당해 사용. (널 문자 \0 로 끝을 표시)

s = "hello"
print(s[1])  # 출력: 'e'

문자열의 특징

1. 인덱스 접근
   • s[i]로 개별 문자에 접근 가능 (파이썬: 상수 시간, C: 배열 인덱스 접근)
2. 불변성(파이썬)
   • 문자열을 직접 수정(s[2] = 'X') 불가 → 새로운 문자열을 만들어야 함.
3. 크기(길이)
   • 파이썬: len(s)로 길이를 쉽게 구함 (O(1)처럼 보이지만 내부 구현에 따라 O(1) 또는 O(n) 가능성).
   • C: strlen(str) 함수로 길이 계산 (실제로 한 문자씩 순회하므로 O(n)).
4. 문자열 연산 비용
   • 문자열 연결시, 새로 공간을 할당하고 복사 → 길이에 비례한 시간 소요.

요약

문자열에서 주로 하는 작업

1. 탐색

   • 특정 문자가 문자열 안에 존재하는지 찾기.
   • 선형 탐색으로 O(N)
   • 파이썬 내장: s.find('a'), 'a' in s 등 (내부적으로도 선형 탐색)

2. 슬라이싱 (파이썬)

   • s[start:end] 형태로 부분 문자열을 구함.
   • 실제로는 새 문자열을 생성 (복사가 발생) → O(N)

     s = "hello"
     print(s[1:4])  # 'ell'
     print(s[:2])   # 'he'
     print(s[2:])   # 'llo'

3. 변환/조작

   • s.replace(old, new): 부분 문자열을 다른 문자열로 교체 (새로운 문자열 리턴)
   • s.split(delim): 구분자로 나누어 리스트 형태로 반환
   • s.strip(): 공백이나 특정 문자 제거

4. 문자열 뒤집기

   • 파이썬: s[::-1] (슬라이싱 응용)
   • 직접 구현 시, O(N)의 시간에 두 인덱스를 바꿔가며 스왑.

인덱스 접근

s = "hello"
print(s[0])  # 'h'
print(s[-1]) # 'o' (뒤에서 첫 번째 문자)

직접 구현 예시 (파이썬, 내장함수 최소화)

문자열 뒤집기

def reverse_string(st):
    reversed_str = ""
    for i in range(len(st)-1, -1, -1):
        reversed_str += st[i]
    return reversed_str
s = "Hello"
print(reverse_string(s))
# 'olleH'

문자열 선형 탐색

def find_char(st, ch):
    """st에서 문자 ch를 찾으면 인덱스 반환, 없으면 -1"""
    for i in range(len(st)):
        if st[i] == ch:
            return i
    return -1
print(find_char("Hello", 'l'))  # 2 (처음 찾은 'l')
print(find_char("Hello", 'z'))  # -1 (존재하지 않음)

부분 문자열(substring) 확인

def is_substring(main_str, sub_str):
    """main_str에 sub_str이 포함되어 있는지 확인"""
    M = len(main_str)
    S = len(sub_str)
    for i in range(M - S + 1):
        match = True
        for j in range(S):
            if main_str[i+j] != sub_str[j]:
                match = False
                break
        if match:
            return True
    return False
print(is_substring("Hello World", "World"))  # True
print(is_substring("Hello World", "Bye"))    # False

문자열 관련 파이썬 내장 함수 정리

split() 함수

text = "apple,banana,grape"
result = text.split(',')   # ✅ 내장함수
print(result)              # ['apple', 'banana', 'grape']

• 기본 동작: split(separator)
• separator로 문자열을 나눠서 리스트 형태로 반환
• 생략하면 공백 기준으로 나눔 → text.split()
• C언어에서는 문자열 순회하며 구분자를 기준으로 직접 나눠야 함

strip() 함수

s = "  hello  "
print(s.strip())   # 'hello'
print(s.lstrip())  # 'hello  '
print(s.rstrip())  # '  hello'

• 문자열 앞뒤의 공백 문자(또는 지정 문자)를 제거
• 내부적으로 문자 하나하나 비교해서 제거
• C언어에서는 수동으로 인덱스 조정하면서 공백 건너뛰어야 함

문자열 불변(Immutable)의 의미

s = "hello"
s[0] = 'H'  # ❌ 오류! 문자열은 변경 불가
# 대신 이렇게 해야 함
s = 'H' + s[1:]  # ✅ 새로운 문자열 생성
print(s)  # 출력: 'Hello'

• 파이썬의 문자열은 값을 바꾸는 게 아니라, 새로 만드는 방식으로 동작
• 메모리 관점에서 비효율이 될 수 있음 (C에서는 직접 바꾸는 것이 가능)

정리

추가 tip

• 문자열은 배열처럼 인덱스로 처리
• 파이썬에서는 str, C언어에서는 char[]로 다룸
• 내장함수에 익숙해지되, 함수 없이도 구현하는 습관을 들이기
• C언어에서는 문자열 처리할 때 *널문자 \0로 종료를 표시함

C 언어에서의 문자열과 차이

• 널 문자(\0)*로 문자열의 끝을 표시해야 함.
• strlen(), strcpy(), strcat() 등 표준 라이브러리 함수를 사용하거나 직접 구현.
• 수정 가능(배열이므로), 단 ‘버퍼 크기 초과’에 유의해야 함.

예: char str[10] = "Hello"; 라면, 내부적으로 'H' 'e' 'l' 'l' 'o' '\0' ... 형태로 저장.

• 동일한 자료형의 요소들을 연속적인 메모리 공간에 저장하는 자료구조
• 데이터는 인덱스(index)로 구분되며, 0부터 시작
• 같은 자료형(예: 정수, 문자열 등)의 값을 순서대로 저장하는 방식
• 파이썬에서는 내부적으로 동적 배열(Dynamic Array)을 사용하는 list를 통해 구현.
• C 언어에서는 배열을 선언 시 크기가 고정되고, 한 번 정하면 수정이 불가능.

예시

• 파이썬: arr = [1, 2, 3]
• C: int arr[5] = {1,2,3,4,5};

배열의 주요 특징

1. 인덱스(Index)를 통한 직접 접근 가능
   • arr[i] 형태로 O(1)에 접근 가능 (파이썬도 내부적으로 동적 배열이지만 평균적으로 O(1)).
2. 연속된 메모리
   • 논리적으로나 물리적으로 연속적이며, 중간 삽입·삭제 시 요소의 이동이 필요해 시간 복잡도가 O(N)이 됨.
3. 탐색
   • 정렬되지 않은 배열에서는 선형 탐색이 보통, O(N).
   • 정렬된 배열이라면 이진 탐색으로 O(log N)에 검색 가능.

메모리 구조

• 배열은 인접한 메모리 번지를 차례로 할당받음.
• 예를 들어, arr[0]은 메모리 주소 1000부터 4바이트 차지, arr[1]은 1004부터 4바이트

배열의 주요 연산

1. 인덱스 접근 (Access)

   arr[i] # 평균 O(1)

2. 탐색 (Search)
   • 선형 탐색: 배열 전체를 순회하며 비교 (O(N))
   • 이진 탐색: 정렬 상태라면 중간값부터 비교 (O(log N))
3. 삽입 (Insert)
   • 중간에 삽입 시, 뒤쪽 원소들을 한 칸씩 밀어야 함 → O(N)
   • 파이썬 list의 insert() 메서드도 내부적으로 동일 원리
4. 삭제 (Delete)
   • 특정 위치에서 원소 삭제 후, 뒤쪽 원소들을 한 칸씩 땡겨야 함 → O(N)

시간 복잡도 요약(BIG O)

배열의 기본 연산

인덱스 접근

arr = [10, 20, 30] print(arr[0]) # 출력: 10

• arr[0] → 배열의 첫 번째 요소
• arr[1] → 두 번째 요소

길이 구하기(len())

print(len(arr)) # 출력: 3

값 변경

arr[1] = 50 print(arr) # 출력: [10, 50, 30]

배열 직접 구현

특정 위치값 삽입

def insert_at(arr, index, value):
    """index 위치에 value를 삽입"""
    new_arr = []
    for i in range(len(arr)):      # ✅ 내장함수 사용: len()
        if i == index:
            new_arr.append(value)  # ✅ 내장함수 사용: append()
        new_arr.append(arr[i])     # ✅ 내장함수 사용: append()
    return new_arr
arr = [10, 20, 30]
arr = insert_at(arr, 1, 15)
print(arr)  # 출력: [10, 15, 20, 30]

C언어에서는

• len() 배열 길이는 직접 변수로 관리하거나 문자열의 경우 \0 만날 때까지 순회
• append() 배열의 크기를 관리하면서 직접 인덱스 위치에 삽입해야 함

특정 위치값 삭제

def delete_at(arr, index):
    """index 위치의 요소를 삭제"""
    new_arr = []
    for i in range(len(arr)):       # ✅ 내장함수 사용: len()
        if i != index:
            new_arr.append(arr[i])  # ✅ 내장함수 사용: append()
    return new_arr
arr = [10, 15, 20, 30]
arr = delete_at(arr, 2)
print(arr)  # 출력: [10, 15, 30]

C언어에서는

• len() 직접 배열 길이를 세거나, 고정 길이로 선언
• append() 없이 i번째 값을 i-1에 복사하는 방식으로 직접 이동시켜야 함

값 검색

def find_value(arr, target):
    """target 값이 배열에 있는지 확인하고 위치 반환"""
    for i in range(len(arr)):       # ✅ 내장함수 사용: len()
        if arr[i] == target:
            return i
    return -1
arr = [10, 20, 30]
print(find_value(arr, 30))  # 출력: 2

C언어에서도 동일하게 for문으로 순회하며 구현 가능

핵심 요약

• 배열은 인덱스를 통한 빠른 접근(O(1))이 가장 큰 장점.
• 중간 삽입/삭제가 잦을 경우 연결 리스트 같은 다른 자료구조도 고려.
• 정렬, 탐색 알고리즘을 구현할 때 배열을 많이 사용함.

배열 관련 주요 파이썬 내장함수 정리

자주 쓰이는 알고리즘 문제 유형

목표:

1) 전산학 기본 지식
2) 팀워크 능력
3) 스스로 문제를 파고드는 자질

전체 일정

전체 기간: 2025.03.10 ~ 2025.07.31
주요 테마: CS 기반 이론 → 프로젝트 실습 → 실전 OS 개발 → 개인 기술 무기화

간단한 소개

저는 크래프톤 정글에서 개발 공부를 하고있는 준비생입니다. 전체적인 개발지식에 대해서 부족한 점이 많아 이 부트캠프에 참여하게 되었습니다. 앞으로 매일 크래프톤 정글에서의 TIL을 올리려고 노력해보려고 합니다. 모두들 화이팅

3/14일(금)

3/10일에 입소를 해서 바로 미니프로젝트를 만들었다. 기간은 13일 목요일까지 처음보는 2명의 팀원들과 함께했다. 아쉽고 잘 못한 것 같지만 한편으론 들어오자마자 있었던 큰 과제가 끝난 것 같아 후련했다. 그치만 이제 시작이였다. 정글은 코치가 1대1로 코칭해주지 않는다. 가이드를 제시해 줄 뿐 정글을 헤쳐나가는건 내 몫이다. 금주의 공부 키워드는 배열, 문자열, 반복문과 재귀함수등이 있었다. 필자는 오늘은 공부를 시작하는 첫날이라 정글에서 제시해준 백준 문제들을 먼저 풀어보았다. 근데 학교에서 배운건 C언어이기도 했고 최근 python은 정글 입학시험 문제에서 본 것 뿐이라 정신없이 검색하며 문제를 풀었다.. 아래는 공부한 흔적인데 사실상 정리도 깔끔하게 되어있지 않다. 노트정리를 눈에 들어오게 공부도 해야겠다. (현재 옵시디언을 눈여겨보고있는 중 이다.) 파이썬이 c언어나 자바보다 쉽다고 알려져있지만 필자는 c로 개발공부를 접해 많이 어색하다.. 더욱 공부가 필요해 보이고 내가 공부한걸 복습하기 위한 정리방법도 필요하다. 앞으로 D-139일동안 많은 것이 성장했을 것이다. 끌어당김의 법칙 처럼 말이다. 내일도 화이팅👍