코딩 테스트 합격자 되기 - 1주차

03 알고리즘 효율 분석

알고리즘 선택의 기준 : 시간복잡도

• 시간복잡도란?
  • 알고리즘의 성능을 나타내는 지표, 입력 크기에 대한 연산 횟수의 상한 의미 -> 낮으면 낮을수록 좋다!
  • 1차원 배열에서 예시
    • 최선 : 1회 비교
    • 최악 : 배열의 개수만큼 비교

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

• 절대 시간 측정 방법이 있지만 코테에서는 추천하지 않음!! (프로그램을 실행하는 환경에 따라 달라질 수 있음!)
• 시간 복잡도 측정 결과에 따라 최선, 보통, 최악으로 나뉨,
• 입력 크기에 따른 연산 횟수의 추이를 활용해서 시간 복잡도를 표현하는 방식을 점근적 표기법이라고 함

빅오 표기법
- 점근적 표기법 중 상한선 활용 방법
- 연산 횟수가 f(x)일 때 함수의 최고차항만 남기고 차수를 지워 O(g(x))와 같이 표기
- 그래프를 비교해볼때, 무한으로 갈 수록 타 항은 무시할 수 있을 정도로 작아지기 때문.
- 로그함수는 다항함수보다 느리게 증가하고, 지수함수는 다항함수보다 빠르게 증가한다.
- ex) x+logx -> O(x) : 그래프의 증가폭이 더 낮은 로그함수는 사라짐

문제

시간 복잡도 계산해보기

<순서>

1. 문제 정의
2. 연산 횟수 측정
3. 시간 복잡도 분석하는 순서
4. 별찍기 문제

• 문제 : 하나씩 별을 늘려간다
• f(n) = 1+2+,,,+N = n(n+1)/2
• O(N^2)

2. 박테리아 수명 문제

• 초기 박테리아 세포 개수가 N일 때 해마다 세포 개수가 이전 세포의개수의 반으로 준다면 언제 모든 박테리아가 죽을지 계산
• (1/2)^y*N <=1일 때 모든 박테리아가 죽는다. y값 찾기!!
  

  

• y>=log2N
• O(logN)의 시간 복잡도를 가진다.

03장 추가 문제

이때 다음을 만족하는 C가 있으면 f(x)의 최악의 시간 복잡도는 O(g(x))라고 쓰는 겁니다.

• 특정 x 시점 이후부터 항상 f(x)≤ C* g(x)를 만족
• C는 상수

쉽게 말해 g(x)에 상수 C를 곱했을 때 특정 시점부터 f(x)를 넘어서는지 여부를 보면 됩니다.

이 때 C*g(x) 를 찾으시오

1. 3x^2+5x+6

[ 3x^2 + 5x + 6 <= C \cdot x^2 ]

[ 3x^2 + 5x + 6 - Cx^2 <= 0 ]

[ (3 - C)x^2 + 5x + 6 <= 0 ]

부등식을 만족시키기 위해서는 ( (3 - C) )이 음수이어야 함. 그리고 이때의 ( x ) 값에 대해 부등식이 성립하게 됩니다. ( (3 - C) )이 음수가 되도록 ( C )를 설정

따라서 ( 3 - C < 0 )이므로 ( C > 3 )이어야 한다

즉 C=5, g(x)=x**2

2. x+logx

C= 2, g(x)=x

3. 2^x+10x^5+5x^2

g(x) = x**5

C= 11

4. 5x^2-6x

g(x)=x^2, C= 6

---

04 코딩 테스트 필수 문법

• 변수의 타입이 명시적이지 않고 선언하는지에 따라 달라진다.

1. 빌트인 데이터 타입
   • 언어 자체에서 제공하는 데이터 타입과 컬렉션 데이터 타입
   1. 정수형
      1. print(a == b) # 같은 값인지 비교 / False print(a != b) # 같지 않은 값인지 비교 / True print(a > b) # 왼쪽 값이 더 큰지 비교 / True print(a < b) # 왼쪽 값이 더 작은지 비교 / False print(a >= b) # 왼쪽 값이 더 크거나 같은지 비교 / True print(a <= b) # 왼쪽 값이 더 작거나 같은지 비교 / False
   2. 부동소수형 : 소수
      • 엡실론을 포함한 연산에 주의하라
        • 파이썬은 부동소수형 데이터를 이진법으로 표현하여 오차가 발생한다.(엡실론)
        • import sys

        엡실론 출력

        print(sys.float_info.epsilon) # 2.220446049250313e-16a = 0.1 + 0.1 + 0.1
        b = 0.3
        print(a - b) # 5.551115123125783e-17
        if abs(a - b) < sys.float_info.epsilon:else:
      • 결과 : 2.220446049250313e-16 \n 5.551115123125783e-17 \n a와 b는 같은 값입니다.
      • print("a와 b는 다른 값입니다.")
      • print("a와 b는 같은 값입니다.") # 이 코드가 출력됨
      • 부동소수점 수의 오차 검사
   3. print(10.0 // 3.2) # 정수형 나누기 / 3.0 print(10.0 % 3.2) # 모듈러 / 0.39999999999999947 print(2.0 \*\* 3.2) # 제곱 연산 / 9.18958683997628
2. 컬렉션 데이터 타입
   • 여러 값을 담는 데이터 타입, 리스트, 튜플, 딕셔너리,, 셋, 문자열 등
   1. mutable 객체
      • 객체 생성 후 객체 수정 가능, 리스트, 딕셔너리, 셋
      1. 리스트
         • 시퀀스(순서)가 있는 자료형
         • 인덱싱 : 특정 위치의 원소에 접근 가능
         • 슬라이싱 : 자료형의 범위를 지정해서 값들을 복사하여 가져오는 방식
           • 표기 : list_name[a:b]
           • 음수도 가능하다.
      2. 딕셔너리
         • key:value 쌍을 저장
         • key로 검색하며, key 값에 맞춰 value 값을 수정가능
         • 삭제 : del dic_name["key"]
   2. immutable 객체
      • 객체 생성 후 객체 수정 불가능
      • 정수, 부동 소수점, 문자열, 튜플
      • 객체 값을 참조하는 형식이기 때문에 새로운 값이 변경되었을 때, 새로운 값을 참조하는 형식
      1. 튜플
         • 생성 : tuple_name = (1,2,3)
         • 인덱싱과 슬라이싱
         • 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,)
      2. 문자열
         • 문자들의 집함
3. 함수
   • def라는 예약어 정의
   • 람다식
     • 함수 간략 표현, 익명 함수라고도 함.
     • 표기법 lambda x, y : x + y # x와 y를 받아서 더한 값을 반환하는 람다식
     • 사용
       1. 변수로 참조
       2. add = lambda x, y: x + y print(add(5, 4)) # 9 ```
       3. 인수로 넘기기
       4. num = [1, 2, 3, 4, 5] # ➊ 리스트 선언 squares = list(map(lambda x: x**2, num)) # ➋ 람다식 넘기기 print(squares) # [1, 4, 9, 16, 25]
4. 코딩 테스트 코드 구현 노하우
   • 습관이 되어야 하니까 코드 작성 때마다 적용!!
   1. 조기반환
      • 가독성을 높여주며 예외 깔끔!
   2. 보호구문
      • 예외처리 코드를 추가하는 기법
      • 유효한지 검사함
   3. 합성 함수
      • 2개 이상의 함수를 활용하여 함수를 추가로 만드는 기법
      • 보통 람다식을 활용

문제

1. 기본적인 컬렉션 타입의 예시코드 입니다. 아래 코드는 외울수 있을정도로 합니다. 그리고 이 예시코드에 언급된 메서
드들의 시간복잡도는 정리해주세요

리스트

메소드	시간 복잡도	설명
append(item)	O(1)	리스트의 끝에 요소를 추가
insert(idx, item)	O(n)	특정 위치에 요소를 추가
pop()	O(1)	리스트의 마지막 요소를 제거하고 반환
pop(0)	O(n)	리스트의 첫 번째 요소를 제거하고 반환
remove(item)	O(n)	리스트에서 특정 요소를 찾아 제거
extend(s)	O(k)	리스트에 다른 리스트의 모든 요소를 추가
lst[K]	O(1)	리스트의 특정 위치의 요소에 접근
lst1 + lst2	O(n + m)	두 리스트를 결합하여 새 리스트 생성
list(set)	O(n)	집합을 리스트로 변환하여 중복을 제거
item in lst	O(n)	리스트에 특정 요소가 있는지 확인

딕셔너리

• n = 딕셔너리의 크기

메소드	시간 복잡도	설명
dic.get(key)	O(1)	딕셔너리에서 주어진 키에 해당하는 값을 반환, 키가 없으면 None을 반환
dic[key]	O(1)	딕셔너리에서 주어진 키에 해당하는 값을 반환, 키가 없으면 KeyError 발생
dic.pop(key)	O(1)	딕셔너리에서 주어진 키에 해당하는 항목을 제거하고 그 값을 반환, 키가 없으면 KeyError 발생
key in dic	O(1)	주어진 키가 딕셔너리에 있는지를 검사

집합 메소드

메소드	반환값	설명	시간 복잡도
s.add(item)	없음	집합 s에 요소 item을 추가	O(1)
s.remove(item)	없음	집합 s에서 요소 item을 제거, 없으면 KeyError 발생	O(1)
s.discard(item)	없음	집합 s에서 요소 item을 제거, 없어도 에러 발생 안 함	O(1)
s.union(s2)	합집합	집합 s와 s2의 합집합 반환	O(len(s) + len(s2))
s.intersection(s2)	교집합	집합 s와 s2의 교집합 반환	O(min(len(s), len(s2)))
s.difference(s2)	차집합	집합 s에서 s2의 요소를 제거한 차집합 반환	O(len(s))
set(list)	집합	리스트를 집합으로 변환	O(len(list))
item in s	bool (True 또는 False)	집합 s에 item이 포함되어 있는지 확인	O(1)

문자열

메소드	반환값	설명	시간 복잡도
str1 + str2	문자열	두 문자열 str1과 str2를 연결	O(n + m), n과 m은 각각 str1과 str2의 길이
delimiter.join(list_of_strings)	문자열	delimiter 문자열을 사용하여 list_of_strings의 모든 문자열을 연결	O(n), n은 list_of_strings의 모든 문자열 길이의 합
str.replace(old, new)	문자열	문자열 str에서 old 부분 문자열을 new 부분 문자열로 교체	O(n), n은 str의 길이
str.split(sep)	문자열 리스트	문자열 str을 sep 문자열을 기준으로 나눔	O(n), n은 str의 길이
str.startswith(prefix)	bool (True 또는 False)	문자열 str이 prefix로 시작하는지 확인	O(k), k는 prefix의 길이
str.endswith(suffix)	bool (True 또는 False)	문자열 str이 suffix로 끝나는지 확인	O(k), k는 suffix의 길이

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

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

출처 : https://cafe.naver.com/dremdeveloper/994, https://wikidocs.net/222560