99클럽 코테 스터디 1일차 TIL : 복잡도 및 파이썬 기본 문법

 

복잡도

• 복잡도 : 알고리즘의 성능을 나타내는 척도이다
  • 시간 복잡도 : 특정한 크기의 입력에 대해 알고리즘의 수행 시간 분석
  • 공간 복잡도 : 특정한 크기의 입력에 대해 알고리즘의 메모리 사용량 분석

—> 동일한 기능을 수행하는 알고리즘이 있다면, 복잡도가 낮을수록 좋은 알고리즘이다

• 빅오 표기법 : 가장 빠르게 증가하는 항만을 고려하는 표기법

—> 빅오 표기법에서는 차수가 가장 큰 항만 남기므로 O(N^3)으로 표현된다. 앞의 계수는 무시한다

—> N이 엄청 큰 수라고 생각을 해보면 된다

 

 

 💡 요구사항에 따라 적절한 알고리즘 설계하기

• 문제에세 가장 먼저 확인해야 하는 내용은 시간제한(수행시간 요구사항) 이다
• 시간제한이 1초인 문제인 경우, 일반적인 기준은 다음과 같다 
  • N의 범위 500 - O(N^3)인 알고리즘 설계시 가능
  • N의 범위 2000 - O(N^2)인 알고리즘 설계시 가능
  • N의 범위 100,000 - O(NlogN)인 알고리즘 설계시 가능
  • N의 범위 10,000,000 - O(N)인 알고리즘 설계시 가능

 

• 수행시간 측정 소스코드 예제

다음과 같은 코드를 통해 소스코드의 수행시간을 측정할 수있다 

import time
start_time = time.time() # 시간 측정 시작

##소스코드

end_time = time.time()  # 시간 측정 종료
print(end_time - start_time)  # 수행 시간 출력

 

 

자료형

• 파이썬의 자료형으로는 정수형, 실수형, 복소수형, 문자열, 리스트, 튜플, 사전 등이 있다
• 지수 표현 방식 : 1e9 는 1X10^9 이다 —> 실수형이다
• 개발 과정에서 표현상의 오류로 실수 값을 제대로 비교하지 못해서 원하는 결과를 얻지 못할 수 있다 . 이럴때는 **round()**함수를 이용한다.
  • 예를들어 123.456을 소수 셋째 자리에서 반올림하려면 round(123.456, 2) 라고 작성한다 —> 소수 둘째 자리까지 만든다는 의미
• / : 나누기 연산자
• % : 나머지 연산자
• // : 몫 연산자
• ** : 거듭제곱 연산자

 

리스트

• 리스트 : 여러개의 데이터를 연속적으로 담아 처리하기 위해 사용하는 자료형
  • 배열의 기능 및 연결 리스트와 유사한 기능을 지원한다
  • 리스트 대신 배열 혹은 테이블이라고 부르기도 한다
• 리스트 초기화 : a= [1, 2, 3] —> 인덱싱을 통해 값에 접근
• 슬라이싱 : 리스트에서 연속적인 위치를 갖는 원소들을 가져올 때 쓰인다
  • b = a[1 : 4] —> 1인덱스 부터 3인덱스까지 가져온다
  • b= a[ : : -1 ] —> 리스트 뒤집기
    • ex)
    def solution(n):    return list(map(int,str(n)))[::-1]
  • 리스트 컴프리헨션 : 리스트를 반복문과 조건문을 통해 초기화 하는 것
    • a = [ i for i in range(10)] —> 0부터 9까지
    • a = [i * i for i in range(1,10)] —> 1부터 9까지 제곱 수를 리스트에 넣는다
    • a = [ [0] * m for _ in range(n)] —> 2차원 리스트 초기화하기

💡 파이썬에서는 반복을 수행하되 반복을 위한 변수의 값을 무시하고자 할 때 언더바(_)를 자주 사용한다

 

 

 

 

리스트 관련 기타 메서드

함수명	사용법	설명	시간 복잡도
append()	변수명.append()	리스트에 원소를 하나 삽입	O(1)
sort()	변수명.sort()	오름차순 정렬	O(NlogM)
reverse()	변수명.reverse()	리스트의 원소의 순서를 모두 뒤집는다	O(N)
insert()	insert(삽입할 위치 인덱스, 삽입할 값)	특정한 인덱스 위치에 원소를 삽입한다	O(N)
count()	변수명.count(특정 값)	리스트에서 특정한 값을 가지는 데이터의 개수를 셀 때 사용한다	O(N)
remove()	변수명.remove( 특정 값)	특정한 값을 갖는 원소를 제거하는데, 값을 가진 원소가 여러개면 하나만 제것한다	O(N)

 

 

 

문자열 자료형

• “” , ‘’ 를 이용하여 문자열 변수를 초기화한다
• 덧셈을 이용하면 연결된다 , 양의 정수와 곱하는 경우 문자열이 그 값만큼 여러번 더해진다
• 문자열도 인덱싱과 슬라이싱을 이용할 수 있으나 문자열을 바꿀 수 는없다

 

 

튜플 자료형

• 한 번 선언된 값을 변경할 수 없다
• 튜플은 () 소괄호를 이용한다
• 튜플을 사용하면 좋은 경우
  • 서로다른 성질의 데이터를 묶어서 관리해야 할 때
    • 최단 경로 알고리즘에서는 ( 비용, 노드번호) 의 형태로 튜플 자료형을 자주 사용한다
  • 데이터의 나열을 해싱의 키 값으로 사용해야 할 때
    • 튜플은 변경이 불가능하므로 리스트와 다르게 키 값으로 사용될 수 있다
  • 리스트보다 메모리를 효율적으로 사용해야 할 때

 

 

사전 자료형

• 키와 값의 쌍을 데이터로 가지는 자료형이다
• 변경 불가능한 자료형을 키로 사용할 수 있다
• 사전 자료형은 해시테이블을 이용하므로 데이터의 조회 및 수정에 있어서 O(1)의 시간에 처리할 수 있다
• 키 데이터만 뽑아서 리스트로 이용할 때 : keys()
• 값 데이터만 뽑아서 리스트로 이용할 때 : values()

—> 함수를 통해 반환된 키 값들은 키 객체로서 반환되므로 안에 있는 값만 필요한 경우에는 다음과 같이 list 안에 넣어주어야 한다

 

 

---

---

 

 

< 항해 99 코딩테스트 준비 1일차 문제 >

프로그래머스 - 자연수 뒤집어 배열 만들기

https://school.programmers.co.kr/learn/courses/30/lessons/12932

프로그래머스

 

 

• 문제 

 

 

• 내가 쓴 코드

def solution(n):
    r=list(map(int,str(n)))
    a=[0]*len(r)

    for i in range(len(r)):
        a[i] = r[-i-1]
    return a

 

 

• 디벨롭 한 코드 

 

def solution(n):
 
    return list(map(int,str(n)))[::-1]

 

 

• 회고 및 알게된 부분

range 함수를 통해서 새 리스트를 만드는 코드를 작성했다.

그 후 다른 풀이를 보고 간단하게 슬라이싱을  통해 리스트를 뒤집을 수 있다는 점을 복기하게 되었고 이를 활용한 코드로 디벨로 하였다 

 

b= a[ : : -1 ] —> 리스트 뒤집기