[코딩테스트 합격자 되기 - 1주차] 알고리즘의 효율 분석, 코딩테스트 필수문법

03. 알고리즘의 효율 분석

시간복잡도

시간 복잡도(time complexity)란, 알고리즘의 성능을 나타내는 지표로 입력 크기에 대한 연산 횟수의 상한을 의미한다. 

"내가 구현한 알고리즘 성능이 제한 시간내 결과값을 낼수 있는지"를 위해 필요하다.

 

알고리즘 수행 시간을 측정하는 방법

시간 복잡도를 측정하는 법

입력 크기에 따른 연산 횟수의 추이를 활용해서 성능을 가늠하게끔 시간 복잡도를 표현하는 방법을 점근적 표기법이라고 합니다

가장 많이 사용하는 점근적 표기법은 상한선을 활용하는 방법입니다. 그리고 이 표기법을 빅오 표기법(big-O notation)이라고 합니다. 빅오 표기법은 어렵지 않습니다. 어떤 프로그램의 연산 횟수가 f(x)라고 할 때 함수의 최고차항을 남기고 차수를 지워 O(...)와 같이 표기하면 됩니다. 

 

빅오 표기법을 쉽게 쓸 때는 왜 최고차항만 남기고 차수를 지울까?

그래프를 보면 데이터가 커질수록 세 그래프의 차이는 확연히 벌어집니다. x값이 무한하게 커지면 그 격차는 더 심해지겠죠. x3에 비해 x와 x2는 무시할 수 있을 정도로 작을 겁니다.

로그함수는 다항함수보다 느리게 증가하고, 지수함수는 다항함수보다 빠르게 증가합니다. 

 

시간 복잡도를 코딩 테스트에 활용하는 방법

코딩 테스트 문제에는 제한 시간이 있으므로 문제를 분석한 후에 빅오 표기법을 활용해서 해당 알고리즘을 적용했을 때 제한 시간 내에 출력값이 나올 수 있을지 확인해볼 수 있다.

코딩 테스트의 문제는 출제자가 의도한 로직을 구현했다면 대부분의 코드를 정답 처리할 수 있도록 채점 시간을 충분히 여유있게 지정한다.

따라서 연산 횟수는 1,000~3,000만 정도로 고려해서 시간 복잡도를 생각하면 된다.

예를 들어 제한 시간이 1초인 문제는 연산 횟수가 3,000만이 넘는 알고리즘은 사용하면 안 된다. 

제한 시간이 1초인 문제에 각 시간 복잡도별로 허용할 수 있는 최대 연산 횟수는 다음과 같이 생각하면 된다.

N은 입력값. 입력값으로 시간 복잡도를 고민 가능하다.

초당 연산 횟수는 1000만~3000만이라고 생각하면 된다.

 

정리

• 입력 크기에 따른 연산 횟수의 추이를 활용해서 시간 복잡도를 표현하는 방법을 점근적 표기법이라고 합니다.
• 빅오 표기법은 점근적 표기법 중 상한선을 활용하는 방법을 표기하는 방법이고, 가장 많이 사용됩니다.
• 시간 복잡도를 빅오 표기법으로 나타내려면 데이터 개수 N에 대해 연산 횟수를 일반화한 후 최고차항을 남기고 차수를 제거하면 됩니다.

문제

 

위 수식을 만족하는 C*g(x)는? 실제 특정 시점부터 넘는지 확인할 수 있는 그래프도 제시하라.

 

---

1. 각 f(x)에 대해 적절한 C 값을 추정한다.

2. 추정한 C 값으로 C*g(x)를 계산한다.

3. 원래 f(x) 함수와 새로 계산된 C*g(x)를 비교한다.

 

1. f(x)=3x^2+5x+6, O(x^2), C≈14
2. f(x)=x+log(x), O(x), C≈1
3. f(x)=2^x+10x^5+5x+2, O(2^x), C≈10010.76
4. f(x)=5x^2−6x, O(x^2), C≈4.4

시간 복잡도 : O(N)

 

시간 복잡도 : O(N)

 

시간 복잡도 : O(N!)

factorial = n(n+1)/2

---

04. 코딩테스트 필수 문법

04-1. 빌트인 데이터 타입

빌트인 데이터 타입built-in data type은 언어 자체에서 제공하는 데이터 타입과 컬렉션 데이터 타입이 있습니다. 기본 데이터 타입으로는 정수형int, 부동소수형float, 문자열 타입이 있고 컬렉션 데이터 타입으로는 리스트, 튜플, 셋, 딕셔너리 등

 

정수형

# 정수형 변수 선언
a = 13
b = 4 

# 정수형 산술 연산
print(a + b)  # 더하기 / 17
print(a - b)  # 빼기 / 9
print(a * b)  # 곱하기 / 52
print(a / b)  # 나누기 (소수점 포함) / 3.25
print(a // b)   # 나누기 (소수점 제외) / 3
print(a % b)    # 모듈러 연산 (나머지) / 1
print(-a)   # 부호를 바꿈 / -13
print(abs(-a))  # 절대값 / 13
print(a**b) # a의 b승 / 28561

# 정수형 비교 연산
print(a & b)    # AND / 4
print(a | b)    # OR / 13
print(a ^ b)    # XOR / 9
print(~a)   # NOT / -14
print(a << 2)   # 왼쪽 시프트 (a에 2^2를 곱한 것과 동일)  / 52
print(a >> 1)   # 오른쪽 시프트 (a를 2^1로 나눈 것과 동일) / 6

# 정수형 논리 연산
print(a and b)  # 논리 연산 AND / 4
print(a or b)   # 논리 연산 OR / 13
print(not a)    # 논리 연산 NOT / False

 

부동소수형 (소수)

# 부동소수형 사칙 연산
print(2.5 + 3.7)    # 더하기 / 6.2
print(7.9 - 4.2)    # 빼기 / 3.7
print(1.5 * 4.8)    # 곱하기 / 7.199999999999999
print(10.0 / 3.2)   # 나누기 / 3.125 

# 부동소수형 정수형 나누기, 모듈러, 제곱 연산
print(10.0 // 3.2)  # 정수형 나누기 / 3.0
print(10.0 % 3.2)   # 모듈러  / 0.39999999999999947
print(2.0 ** 3.2)   # 제곱 연산 / 9.18958683997628 

# 보둥소수형 논리 연산
x = 0.5
y = 1.2
z = 2.0
print(x > y and y < z)  # AND 연산 / False
print(x < y or y < z)   # OR 연산 / True
print(not (x > y))  # NOT 연산 / True

 

엡실론 포함 연산에 주의 하라

파이썬은 부동소수형 데이터를 이진법으로 표현하기 때문에 표현 과정에서 오차가 발생하는 것. 이를 엡실론epsilon이라고 한다. 이 내용을 언급한 이유는 코딩 테스트에서 부동소수형 데이터를 다룰 일이 생겼을 때 이 엡실론을 항상 생각하라는 이유에서이다. 

(0.1을 3번 더한 a의 값에 0.3을 빼면 0이 아닙니다.)

많은 사람이 실수하니 꼭 체크!

import sys

# 엡실론 출력
print(sys.float_info.epsilon)  # 2.220446049250313e-16
# 부동소수점 수의 오차 검사
a = 0.1 + 0.1 + 0.1
b = 0.3
print(a - b)  # 5.551115123125783e-17
if abs(a - b) < sys.float_info.epsilon:
  print("a와 b는 같은 값입니다.")  # 이 코드가 출력됨
else:
  print("a와 b는 다른 값입니다.")

 

 

04-2. 컬렉션 데이터 타입

대표적으로 리스트list, 튜플tuple, 딕셔너리 dictionary, 셋 set, 문자열string 등이 있습니다. 그리고 이 컬렉션들은 데이터의 수정 가능 여부에 따라 변경할 수 있는 객체mutable object와 변경할 수 없는 객체immutable object 이렇게 2가지로 구분합니다. 

 

뮤터블 객체

객체 생성 후 객체 수정이 가능하다. 대표적으로 리스트, 딕셔너리, 셋이 있다.

 

이뮤터블 객체

객체 생성 후 객체 수정이 불가능하다. 대표적으로 정수, 부동소수점, 문자열, 튜플이 있다.

a = 4   # ➊ a = 4
b = a   # ➋ a = 4, b = 4 / b는 a가 아닌 a가 참조한 4를 참조
b += 2  # ➌ b = 6 / 기존에 참조한 객체를 수정하지 않음, 새 객체 6을 참조
print(a, b)  # 4 6

 

a가 4라는 객체를 참조합니다.
a가 참조한 4라는 이뮤터블 객체를 b도 똑같이 참조합니다.
b는 6이라는 객체를 참조합니다. 주목할 점은 4는 이뮤터블 객체이므로 수정할 수 없습니다. 따라서 객체 6을 새로 생성하고 그 객체를 참조합니다.

 

리스트

뮤터블 객체이고. []로 원소를 감싸는 형태로 사용

"데이터의 순서(시퀀스)가 있는 변경 가능한 컬렉션" 자료형 입니다. 데이터의 순서가 있다는 것은 배열처럼 인덱스를 활용해서 접근할 수 있다는 것을 의미하며, 반복문에서 리스트를 순회할 때 정확시 추가된 순서대로 순회할 수 있습니다. 인덱싱-슬라이싱을 할 수 있다.

# 리스트 선언

# 빈 리스트 생성
empty_list = [] 
print(empty_list)  # 출력 결과: []

# 리스트 선언
my_list = [1, 2, 3, 4, 5]
my_list2 = [1, 3, 5] + [7, 9]
my_list3 = list(my_list)
print(my_list)      # [1, 2, 3, 4, 5]
print(my_list2)     # [1, 3, 5, 7, 9]
print(my_list3)     # [1, 2, 3, 4, 5]

# 반복을 사용하여 동일한 값을 가진 리스트 생성
repeated_list = [0] * 5
print(repeated_list)  # 출력 결과: [0, 0, 0, 0, 0]

# 리스트 생성 함수 (list()) 사용
# 여기서는 문자열을 리스트로 변환합니다.
string_to_list = list("hello")
print(string_to_list)  # 출력 결과: ['h', 'e', 'l', 'l', 'o']

# 리스트 언패킹을 사용한 복합 리스트 생성
first_part = [1, 2]
second_part = [3, 4]
combined_list = [*first_part, *second_part]
print(combined_list)  # 출력 결과: [1, 2, 3, 4]

# 리스트 원소에 접근

# 리스트 인덱싱 
my_list = [1, 2, 4]

# 첫 번째 원소에 접근 (인덱스 0)
first_element = my_list[0]
print(first_element)  # 출력 결과: 1

# 세 번째 원소에 접근 (인덱스 2)
third_element = my_list[2]
print(third_element)  # 출력 결과: 4

# 마지막 원소에 접근
# 인덱스 '-1'을 사용하여 리스트의 마지막 원소에 접근합니다.
# 파이썬에서 음수 인덱스는 리스트의 끝에서 시작하는 것을 의미합니다.
# 따라서, '-1'은 리스트의 마지막 원소를 가리킵니다.
last_element = my_list[-1]
print(last_element)  # 출력 결과: 4

# 슬라이싱을 사용하여 부분 리스트 접근
# 슬라이싱은 리스트의 일부분을 선택할 때 사용합니다.
# my_list[1:3]는 인덱스 1부터 시작하여 인덱스 3 전까지의 원소를 포함하는 새로운 리스트를 생성합니다.
# 즉, 인덱스 1, 2의 원소인 2, 4가 포함됩니다.
sub_list = my_list[1:3]
print(sub_list)  # 출력 결과: [2, 4]

# 값 추가
my_list.append(6) # ➊
print(my_list)    # [1, 2, 4, 6]

# 인덱싱으로 값 삭제
del my_list[2]    # ❷ del은 인덱스 위치에 있는 원소를 지우는 키워드입니다.
print(my_list)    # ➌ [1, 2, 6]

# 리스트 슬라이싱
my_list = [1, 2, 3, 4, 5]
print(my_list[0:2])    # ➊ [1, 2]
print(my_list[1:])     # ➋ [2, 3, 4, 5]
print(my_list[3:4])    # ➌ [4]
print(my_list[-4:-2])  # ➍ [2, 3]

# 리스트 원소 수정

# 리스트 생성
my_list = [1, 2, 3, 4, 5]

# 인덱스 2의 원소를 수정 (리스트는 0부터 시작하므로, 이는 세 번째 원소입니다)
my_list[2] = 10

# 수정된 리스트 출력
print(my_list)  # 출력 결과: [1, 2, 10, 4, 5]

유의할 점

리스트는 배열과 유사합니다.(실제 내부는 동적배열처럼 구현되어있습니다.) 따라서 현재기준 맨 뒤에 원소를 추가하거나, 맨 뒤의 원소를 삭제하는 연산은 시간복잡도 O(1)로 처리가 가능합니다.
아래를 보면, 맨 뒤에 원소 삽입/삭제 시 이전의 원소들은 이동할 필요가 없는것을 알 수 있습니다. 따라서 맨뒤에 원소를 삽입/삭제하는 연산은 효율적으로 보입니다.

하지만 맨 앞의 원소를삭제 하는 경우는 조심해야 합니다. 아래와 같이 맨 뒤에 원소를 삭제하는 경우를 생각해 봅시다.

이 경우에는 원소 2~5를 전부 앞으로 이동시켜야 합니다. 이전의 원소의 갯수가 N개인 경우 (N-1)개의 원소가 이동할 수 있는 것이지요 굉장히 비효율적입니다. 그림으로 나타내면 아래와 같습니다. 위에서 설명한 "리스트가 제공하는 메서드"에서 pop(0)가 이외같은 방식으로 연산이 됩니다. 시간복잡도가 O(N)이 되고 굉장히 비효율적

 

이 경우에는, deque(덱)을 활용하면 좋습니다. 리스트는 맨 뒤에서만 원소를 추가하는 구조였다면, deque은 양쪽에서 원소를 추가할 수 있습니다. 따라서 맨 앞의 원소를 추가할때도 O(1)의 성능을 보장합니다. deque에서 제공하는 메서드는 아래 예시코드를 참조해주세요

#############################################################
# | cafe       | http://cafe.naver.com/dremdelover          |
# | Q&A        | https://open.kakao.com/o/gX0WnTCf          |
# | business   | ultrasuperrok@gmail.com                    |
#############################################################

from collections import deque

# 데크 객체 생성
deq = deque()

# append(item): 데크의 오른쪽 끝에 item을 추가합니다.
# 반환값: 없음
# 시간 복잡도: O(1)
deq.append(1)  # 현재 데크: deque([1])
print(deq)  # 출력: deque([1])

# appendleft(item): 데크의 왼쪽 끝에 item을 추가합니다.
# 반환값: 없음
# 시간 복잡도: O(1)
deq.appendleft(0)  # 현재 데크: deque([0, 1])
print(deq)  # 출력: deque([0, 1])

# popleft(): 데크의 왼쪽 끝 요소를 제거하고 그 요소를 반환합니다.
# 반환값: 제거된 요소
# 시간 복잡도: O(1)
deq.popleft()  # 현재 데크: deque([1])
print(deq)  # 출력: deque([1])

# deq[K]: 데크의 K번째 요소를 반환합니다.
# 반환값: K번째 요소
# 시간 복잡도: O(1)
print(deq[0])  # 출력: 1

 

딕셔너리

딕셔너리dictionary는 뮤터블 객체이며, 키key와 값value 쌍을 저장하는 해시 테이블로 구현되어 있습니다. 이름 그대로 키를 사용하여 값을 검색하는 자료형이다.

# 딕셔너리 초기화
my_dict = { }

# 딕셔너리 값 삽입
my_dict["apple"] = 1
my_dict["banana"] = 2
my_dict["orange"] = 3

# 딕셔너리 값 출력
print(my_dict)  # {'apple': 1, 'banana': 2, 'orange': 3} 

# 딕셔너리 검색
key = "apple"
if key in my_dict:
  value = my_dict[key]
  print(f"{key}: {value}")  # apple: 1
else:
  print(f"{key}는 딕셔너리에 존재하지 않습니다.") 

# 딕셔너리 수정
my_dict["banana"] = 4
print(my_dict)  # {'apple': 1, 'banana': 4, 'orange': 3} 

# 딕셔너리 삭제 (키 없을 경우 에러 발생하므로 예외 처리 해주어야 함)
del my_dict["orange"]
print(my_dict)  # {'apple': 1, 'banana': 4} 

# ➊ 딕셔너리 생성
my_dict = {"apple": 1, "banana": 2, "cherry": 3}

# ➋ my_dict에 없는 key로 설정
key = "kiwi"

# ➌ 키가 딕셔너리에 있는지 확인
if key in my_dict:
    # ➍ 키가 딕셔너리에 있으면 해당 값 출력
    print(f"값: {my_dict[key]}")
else:
    # ➎ 키가 딕셔너리에 없으면 에러 메시지 출력
    print(f"'{key}' 키가 딕셔너리에 없습니다.")

 

 

튜플

이뮤터블 객체이고, 리스트 딕셔너리와 달리 한 번 생성하면 삽입하거나 삭제할 수 없다.

# 튜플 초기화
my_tuple = (1, 2, 3) 

# 튜플 인덱싱
print(my_tuple[0])  # 1
print(my_tuple[1])  # 2
print(my_tuple[2])  # 3

# 튜플 슬라이싱
print(my_tuple[1:])   # (2, 3)
print(my_tuple[:2])   # (1, 2)
print(my_tuple[1:2])  # (2,)

 

튜플은 삽입, 삭제는 되지 않지만 인덱싱, 슬라이싱은 할 수 있습니다. 문법 자체는 리스트와 같습니다.

 

문자열

문자열은 문자들을 집합의 형태로 구성한 이뮤터블 객체입니다.

# 문자열 초기화
string = "Hello, World!"   # 큰따옴표 사용
string2 = 'Hello, World!'  # 작은따옴표 사용 

# 문자열 추가, 삭제
string = "He"   # ➊
string += "llo"     # ➋
print(string)   # "Hello" 

# 문자열 수정
string = "Hello"  
string = string.replace("l", "")    # "l"을 모두 삭제
print(string)   # Heo

 

 

04-3. 함수

# 함수 정의
def function_name(param1, param2, param3, ..., paramN):
  # 함수의 실행 코드
  # ...
  # ...
  return result # 반환값 

# 함수 호출
def add(num1, num2):  
  result = num1 + num2 
  return result 
# 함수 호출하여 결과 출력
ret = add(5, 10)
print(ret)  # 15

def 에 의해 정의하고, 매개 변수가 있는 경우 func(a,b)와 함께 인수 전달

람다식

# 람다식 정의
lambda x, y : x + y   # x와 y를 받아서 더한 값을 반환하는 람다식 

# 사용1. 변수로 참조
add = lambda x, y: x + y 
print(add(5, 4)) # 9 

# 사용2. 인수로 람다식 넘기기
num = [1, 2, 3, 4, 5]  # ➊ 리스트 선언
squares = list(map(lambda x: x**2, num))  # ➋ 람다식 넘기기
print(squares)  # [1, 4, 9, 16, 25]

 

➊ 정수형 리스트를 하나 선언하고 ➋ map( ) 함수에 람다식을 넘깁니다. 이렇게 하면 map( ) 함수는 2번째 인수로 넘어온 리스트에 1번째 인수로 받은 람다식을 적용하여 num의 원소를 각각 제곱한 새 리스트를 반환합니다.

 

04-4. 코딩 테스트 코드 구현 노하우

조기 반환

조기 반환 early return은 코드 실행 과정이 함수 끝까지 도달하기 전에 반환하는 기법입니다.

def total_price(quantity, price):
  total = quantity * price  # ➊
  if total > 100:   # ➋ total이 100보다 크면
    return total * 0.9      # ➌ 조기 반환
  return total

print(total_price(4, 50))

 

보호 구문

보호 구문guard clauses은 본격적인 로직을 진행하기 전 예외 처리 코드를 추가하는 기법입니다. 예를 들어 조건문을 이용하여 초기에 입력값이 유효한지 검사하고 그렇지 않으면 바로 함수를 종료하는 보호 구문을 쓸 수 있습니다.

def calculate_average(numbers):
  if numbers is None:  # ➊ 값이 없으면 종료(예외)
    return None

  if not isinstance(numbers, list):  # ➋ numbers가 리스트가 아니면 종료(예외)
    return None

  if len(numbers) == 0:  # ➌ numbers의 길이가 0이면 종료(예외)
    return None

  total = sum(numbers)  # ➍
  average = total / len(numbers)
  return average

 

합성 함수

합성 함수composite method는 2개 이상의 함수를 활용하여 함수를 추가로 만드는 기법입니다. 보통 합성 함수는 람다식을 활용합니다.

def add_three(x):  # ➊
  return x + 3

def square(x):  # ➋
  return x * x

composed_function = lambda x: square(add_three(x))  # ➌
print(composed_function(3))  # ➍ (3 + 3)^2 = 36

두 함수를 마치 하나의 함수처럼 활용하는 것을 볼 수 있습니다. 이렇게 코드를 구현하면 작은 기능을 분리해서 코드를 작성할 수 있으므로 관리자는 코드를 쉽게 관리할 수 있고, 함수를 사용하는 사용자는 코드를 쉽게 사용할 수 있습니다.

 

정리

• 파이썬의 빌트인 데이터 타입은 기본 타입(정수형, 부동소수형, 문자열)과 컬렉션 타입(리스트, 딕셔너리, 튜플, 셋)이 있습니다.
• 파이썬의 데이터 타입은 이뮤터블(값을 변경할 수 없음) 타입과 뮤터블(값을 변경할 수 있음) 타입으로 나눌 수 있습니다. 이뮤터블 타입은 기본 타입, 문자열, 튜플이 있고 뮤터블 타입은 리스트, 딕셔너리, 셋이 있습니다.
• 함수는 프로그램의 기본 구성 요소로 파이썬에서는 예약어로 def로 정의할 수 있습니다.
• 람다식은 간결한 함수 표현 방법입니다. 한 번만 사용하거나 인자로 함수를 넘겨야 할 경우 유용합니다.
• 조기 반환, 보호 구문, 합성 함수 등의 기법을 활용하면 코드의 가독성과 효율성을 높일 수 있습니다.

 

문제

# 리스트 예시코드와 시간 복잡도

#############################################################
# | cafe       | http://cafe.naver.com/dremdelover          |
# | Q&A        | https://open.kakao.com/o/gX0WnTCf          |
# | business   | ultrasuperrok@gmail.com                    |
#############################################################

lst = [1, 2, 3, 4]

# append(item): 리스트의 끝에 item을 추가합니다. 반환값은 없습니다.
# 시간 복잡도: O(1) (상수 시간)
lst.append(5)
print(lst)  # 출력: [1, 2, 3, 4, 5]

# insert(idx, item): idx 위치에 item을 추가합니다. 반환값은 없습니다.
# 시간 복잡도: O(n) (n: 리스트의 길이)
lst.insert(2, 6)
print(lst)  # 출력: [1, 2, 6, 3, 4, 5]

# pop(): 리스트의 마지막 요소를 제거하고 반환합니다.
# 시간 복잡도: O(1) (상수 시간)
print(lst.pop())  # 출력: 5
print(lst)  # 출력: [1, 2, 6, 3, 4]

# pop(0): 리스트의 첫 번째 요소를 제거하고 반환합니다.
# 시간 복잡도: O(n) (n: 리스트의 길이)
print(lst.pop(0))  # 출력: 1
print(lst)  # 출력: [2, 6, 3, 4]

# remove(item): 리스트에서 item을 찾아 제거합니다. 반환값은 없습니다.
# 시간 복잡도: O(n) (n: 리스트의 길이)
lst.remove(6)
print(lst)  # 출력: [2, 3, 4]

# extend(s): 리스트에 s의 모든 요소를 추가합니다. 반환값은 없습니다.
# 시간 복잡도: O(k) (k: 추가하는 리스트 s의 길이)
lst.extend([7, 8])
print(lst)  # 출력: [2, 3, 4, 7, 8]

# lst[K]: 리스트의 K 위치의 요소에 접근합니다.
# 시간 복잡도: O(1) (상수 시간)
print(lst[2])  # 출력: 4

# lst1 + lst2: 두 리스트를 결합하여 새 리스트를 생성하고 반환합니다.
# 시간 복잡도: O(n+m) (n: lst1의 길이, m: lst2의 길이)
print([1, 2, 3] + [4, 5, 6])  # 출력: [1, 2, 3, 4, 5, 6]

# list(set): 집합을 리스트로 변환하여 중복을 제거합니다. 순서는 보장되지 않습니다.
# 시간 복잡도: O(n) (n: 리스트/집합의 길이)
print(list(set([1, 2, 2, 3, 3, 4])))  # 출력 : [1,2,3,4]

# item in lst: 리스트에 item이 있는지 확인합니다.
# 시간 복잡도: O(n) (n: 리스트의 길이)
print(3 in lst)  # 출력: True

 

 

# 딕셔너리 예시코드와 시간 복잡도

#############################################################
# | cafe       | http://cafe.naver.com/dremdelover          |
# | Q&A        | https://open.kakao.com/o/gX0WnTCf          |
# | business   | ultrasuperrok@gmail.com                    |
#############################################################

# dic.get(key)
# 딕셔너리 dic에서 주어진 key에 해당하는 값을 반환합니다. 
# key가 딕셔너리에 없으면 None을 반환합니다.
# 시간 복잡도: O(1)
dic = {'a': 1, 'b': 2, 'c': 3}
value = dic.get('a')
print(value)  # 출력값: 1
value = dic.get('d')
print(value)  # 출력값: None

# dic[key]
# 딕셔너리 dic에서 주어진 key에 해당하는 값을 반환합니다. 
# key가 딕셔너리에 없으면 KeyError를 발생시킵니다.
# 시간 복잡도: O(1)
try:
    value = dic['b']
    print(value)  # 출력값: 2
    value = dic['d']
    print(value)  # 출력값: (이 줄은 실행되지 않습니다; KeyError 발생)
except KeyError as e:
    print(e)  # 출력값: 'd'

# dic.pop(key)
# 딕셔너리 dic에서 주어진 key에 해당하는 항목을 제거하고 그 값을 반환합니다. 
# key가 딕셔너리에 없으면 KeyError를 발생시킵니다.
# 시간 복잡도: O(1)
try:
    value = dic.pop('c')
    print(value)  # 출력값: 3
    value = dic.pop('d')
    print(value)  # 출력값: (이 줄은 실행되지 않습니다; KeyError 발생)
except KeyError as e:
    print(e)  # 출력값: 'd'

# key in dic
# 주어진 key가 딕셔너리 dic에 있는지를 검사합니다. 
# 시간 복잡도: O(1)
key_presence = 'a' in dic
print(key_presence)  # 출력값: True
key_presence = 'd' in dic
print(key_presence)  # 출력값: False

 

# 집합 예시 코드와 시간 복잡도

#############################################################
# | cafe       | http://cafe.naver.com/dremdelover          |
# | Q&A        | https://open.kakao.com/o/gX0WnTCf          |
# | business   | ultrasuperrok@gmail.com                    |
#############################################################

# 집합 s 생성
s = set()

# s.add(item): 집합 s에 요소 item을 추가합니다.
# 반환값: 없음
# 시간 복잡도: O(1)
s.add(1)  # 현재 집합: {1}
print(s)  # 출력: {1}

# s.remove(item): 집합 s에서 요소 item을 제거합니다. item이 s에 없을 경우 KeyError를 발생시킵니다.
# 반환값: 없음
# 시간 복잡도: O(1)
s.remove(1)  # 현재 집합: {}
print(s)  # 출력: set()

# s.discard(item): 집합 s에서 요소 item을 제거합니다. item이 s에 없어도 에러가 발생하지 않습니다.
# 반환값: 없음
# 시간 복잡도: O(1)
s.discard(1)  # 현재 집합: {} (아무 변화 없음)
print(s)  # 출력: set()

# 집합 s와 s2 생성 및 초기화
s = {1, 2, 3}
s2 = {3, 4, 5}

# s.union(s2): 집합 s와 s2의 합집합을 반환합니다.
# 반환값: 합집합
# 시간 복잡도: O(len(s) + len(s2))
print(s.union(s2))  # 출력: {1, 2, 3, 4, 5}

# s.intersection(s2): 집합 s와 s2의 교집합을 반환합니다.
# 반환값: 교집합
# 시간 복잡도: O(min(len(s), len(s2)))
print(s.intersection(s2))  # 출력: {3}

# s.difference(s2): 집합 s에서 s2의 요소를 제거한 차집합을 반환합니다.
# 반환값: 차집합
# 시간 복잡도: O(len(s))
print(s.difference(s2))  # 출력: {1, 2}

# set(list): 리스트를 집합으로 변환합니다.
# 반환값: 집합
# 시간 복잡도: O(len(list))
print(set([6, 7, 8]))  # 출력: {8,6,7}, {6,7,8} 등 으로 나타남, 집합은 순서를 보장하지 않으므로 순서 달라질수 있음

# item in s: 집합 s에 item이 포함되어 있는지 확인합니다.
# 반환값: bool (True 또는 False)
# 시간 복잡도: O(1)
print(1 in s)  # 출력: True

 

 

# 문자열 예시코드와 시간 복잡도

#############################################################
# | cafe       | http://cafe.naver.com/dremdelover          |
# | Q&A        | https://open.kakao.com/o/gX0WnTCf          |
# | business   | ultrasuperrok@gmail.com                    |
#############################################################

# str1 + str2: 두 문자열 str1과 str2를 연결합니다.
# 반환값: 새로운 문자열
# 시간 복잡도: O(n + m), n과 m은 각각 str1과 str2의 길이입니다.
str1 = "Hello"
str2 = " World"
result = str1 + str2
print(result)  # 출력: "Hello World"

# delimiter.join(list_of_strings): delimiter 문자열을 사용하여 list_of_strings의 모든 문자열을 연결합니다.
# 반환값: 새로운 문자열
# 시간 복잡도: O(n), n은 list_of_strings의 모든 문자열 길이의 합입니다.
delimiter = " | "
list_of_strings = ["apple", "banana", "cherry"]
result = delimiter.join(list_of_strings)
print(result)  # 출력: "apple | banana | cherry"

# str.replace(old, new): 문자열 str에서 old 부분 문자열을 new 부분 문자열로 교체합니다.
# 반환값: 새로운 문자열
# 시간 복잡도: O(n), n은 str의 길이입니다.
str3 = "Hello, World!"
result = str3.replace("World", "Python")
print(result)  # 출력: "Hello, Python!"

# str.split(sep): 문자열 str을 sep 문자열을 기준으로 나눕니다.
# 반환값: 문자열 리스트
# 시간 복잡도: O(n), n은 str의 길이입니다.
str4 = "apple,banana,cherry"
result = str4.split(",")
print(result)  # 출력: ['apple', 'banana', 'cherry']

# str.startswith(prefix): 문자열 str이 prefix로 시작하는지 확인합니다.
# 반환값: bool (True 또는 False)
# 시간 복잡도: O(k), k는 prefix의 길이입니다.
str5 = "Hello, World!"
result = str5.startswith("Hello")
print(result)  # 출력: True

# str.endswith(suffix): 문자열 str이 suffix로 끝나는지 확인합니다.
# 반환값: bool (True 또는 False)
# 시간 복잡도: O(k), k는 suffix의 길이입니다.
result = str5.endswith("World!")
print(result)  # 출력: True

 

list comprehension을 활용해서 1~100까지 수 중 3과 9의 공배수만 리스트에 담기도록 구현하라.

[x for x in range(1,101) if x % 9 == 0]

 

 

 

 

출처: 코딩 테스트 합격자 되기 - 1주차 (저자 박경록)

 

https://wikidocs.net/222559

03 알고리즘의 효율 분석

https://github.com/dremdeveloper/codingtest_python/tree/main

GitHub - dremdeveloper/codingtest_python: 코딩테스트 합격자 되기(파이썬)

https://www.youtube.com/watch?v=wtBUKpXPN4Q