이것이 코딩테스트다 1일차 - 파이썬 문법 : 자료형과 함수

1. 부록A
2. 2부 이론
3. 3부 문제 - 최소 3회이상

ADVICE

• 책의 문제를 푼 다음 동일 유형의 문제 온라인 저지 사이트에서 풀어보기 if 그리디 풀었으면 그리디 다풀어보기(백준)
• 책을 보는 동안에는 책에만 집중 (문제를 많이풀고 복기하는 방법)
• 복기한 내용은 기록 -> 훌륭한 요약집

• 문제해결에 대한 접근방식, 풀이방식을 기억 및 설명

파이썬 문법

자료형은 자동
무한 : INF, 최댓값이 있을 때는 예를들어 1e9(1,000,000,000)와 같이 설정
실수형의 연산에서는 정확한 값이 나오지 않을 수 있다. 메모리에 저장되는 값이 현실과 다름
보통 소숫점 다섯번째 자리에서 반올림한 값이 같으면 맞았다고 인정하기 때문에
a라는 변수가실수 이면

answer = round(a,4)
Return answer

거듭제곱 연산자

**

리스트

내부적으로 동적 배열로 구성되어 있다.

class DynamicArray:
    def __init__(self):
        self._capacity = 4  # 초기 용량
        self._size = 0  # 현재 크기
        self._data = [None] * self._capacity  # 동적 배열 데이터
    
    def __len__(self):
        return self._size
    
    def __getitem__(self, index):
        if not 0 <= index < self._size:
            raise IndexError("Index out of range")
        return self._data[index]
    
    def append(self, value):
        if self._size == self._capacity:
            self._resize(2 * self._capacity)  # 용량이 부족하면 두 배로 확장
        self._data[self._size] = value
        self._size += 1
    
    def _resize(self, new_capacity):
        new_data = [None] * new_capacity
        for i in range(self._size):
            new_data[i] = self._data[i]
        self._data = new_data
        self._capacity = new_capacity

동적배열의 한 예시이고, 파이썬은 훨씬 더 복잡하고 최적화되어있는데
아무튼 내부적으로는 이렇게 구현되어있음!
쉽게 말해서 리스트라는 클래스에 속성과 메서드가 다 선언되어있고
함수를 사용할 때는 그 속성값이나, 메서드결과를 반환한다.

리스트 삽입

    def insert(self, index, value):
        if self._size >= self._capacity:
            self._resize()  # 용량이 부족하면 배열 크기 조정
        for i in range(self._size, index, -1):
            self._data[i] = self._data[i - 1]  # 요소들을 오른쪽으로 한 칸씩 이동
        self._data[index] = value
        self._size += 1
    
    def _resize(self):
        self._capacity *= 2  # 현재 용량의 두 배로 확장
        new_data = [None] * self._capacity
        for i in range(self._size):
            new_data[i] = self._data[i]  # 기존 요소들을 새로운 배열로 복사
        self._data = new_data

삽입의 과정을 요약하면
인덱스로 값이 들어갈 자리를 찾고, 그 인덱스부터 마지막까지 요소들을 한칸씩 오른쪽으로 옮기고, 그 자리에 값을 삽입한다.
따라서 삽입은 오버헤드를 제외하면 최악의 경우(모든 요소들을 한칸씩 옮길 때) O(n)이 걸린다. - (for문으로 진짜 옮겨버림..)
제거도 마찬가지라고 생각할 수 있음! 옮기고 왼쪽으로 이동, 최악의경우 O(n)

리스트 정렬 - 삽입정렬 + 병합정렬 (런은 삽입정렬로 정렬, 정렬된 런들을 병합정렬로 정렬)

Timsort 알고리즘의 시간 복잡도는 일반적으로 최악의 경우 O(n log n)입니다. 여기서 n은 정렬할 리스트의 크기를 나타냅니다. 그러나 최선의 경우와 이미 정렬된 리스트와 같은 특정한 상황에서는 선형 시간 복잡도 O(n)에 가까운 성능을 보입니다.(대략적으로 이렇게 말하는 것 같음)
Timsort는 삽입 정렬과 병합 정렬을 결합하여 사용하는데, 이는 각각의 장점을 활용합니다. 작은 런들을 삽입 정렬을 통해 정렬하고, 이후에 병합 과정을 통해 정렬된 런들을 병합합니다. 이러한 접근 방식으로 Timsort는 최악의 경우에도 안정적인 성능을 보장하면서 효율적인 정렬을 제공합니다.
따라서, 일반적인 상황에서 Timsort는 다른 정렬 알고리즘들보다 우수한 성능을 보이며, 이미 정렬된 리스트나 일부분이 이미 정렬된 리스트에서는 더욱 빠른 성능을 보입니다.






리스트 컴프리헨션

list_1 = [i for i in range 20 if i%3==0]

list_2 = [i*i for i in range(1,10)]

list_1=[1,2,3,4,5,6,7,8]

list_2=["success"if i>5 else "fail" for i in list_1]
print(list_2)

-> 조건을 먼저 적어주면 리스트 컴프리헨션을 통해서 간편하게 리스트를 작성할 수 있다.


언더바 (_) : 리스트 컴프리헨션에서 자주 사용. 변수의 값과 상관없이, 반복만 필요할 때

2차원 리스트를 생성할 때는 반드시 리스트 컴프리헨션으로 사용해야 한다(내부적으로 레퍼런스가 변수마다 달라야 하기 때문)

# 4*3 2차원 리스트 생성
m=4
n=3
list_2d=[[0]*4 for _ in range(3)]

#[0]*4를 3번 반복한 리스트

오름차순 정렬과 원소 뒤집기는 다름..! 원소 뒤집기는 그냥 물리적으로 뒤집는거 뿐임
insert, remove는 삽입과 제거. 시간복잡도가 O(n)임. 남발하면 사망임.
따라서 새로운 리스트로 생성하면 좋음

list_1 =[2,3,3,5,56,7,6,5,54,5,55,5,5]
remove_set=[3,5]

result=[i for i in list_1 if i not in remove_set]

문자열

내부적으로 리스트와 같이 처리된다.
따라서 문자 하나당 인덱스가 붙기 때문에 인덱스로 접근이 가능하다.
그러나 변경은 불가능한 자료형이다 (왜지)

딕셔너리 자료형

내부적으로 해시테이블로 구현되어있다
따라서 키(key)를 이용하여 값(value)에 O(1)의 시간복잡도 안에 접근 가능하다
-> 탐색(검색), 수정은 O(1)의 시간복잡도 안에 처리 가능
키와 값의 쌍으로 구성된 데이터를 처리함에 있어서는 리스트보다 훨씬 빠르다
(리스트 - 수정, 제거 O(n))

특정 키(값이라고 해도되지만)를 입력했을 때 이 키에 해당되는 값의 존재의 유무나 값을 출력할 때 유용하다 -> O(1)의 시간복잡도로 탐색 가능하기 때문에~
(A : 야 ”사과“가 영어로뭐냐?)
(B : “사과”가 있긴하냐?)

data = dict()
data[‘사과‘] = ’apple’
data[‘바나나‘] = ’banana’
data[‘코코넛‘] = ’coconut’

if ‘사과‘ in data : 
	print(“‘사과’를 키로 가지는 데이터가 존재합니다.“,data[‘사과‘])

Key값 또는 Value 값만 뽑아내기

#키 데이터만 담은 리스트
key_list = data.keys()
#값 데이터만 담은 리스트
value_list = data.values()

키에 따른 값을 출력하기

for key in key_list :
	print(data[key])

집합 자료형

리스트 혹은 문자열을 이용해서 만들 수 있다.

• 중복을 허용하지 않는다
• 순서가 없다
• 인덱스가 없어서 인덱스로 접근 불가능
• 탐색 시간 복잡도는 O(1)이다 (왜즤)

선언

data_set=set()

연산

a|b #합집합
a&b #교집합
a-b #차집합

관련함수

data_set.add(data0) #새로운 원소 하나 추가
data_set.update([data1,data2]) #새로운 원소 여러개 추가
data_set.remove(data3) #특정 원소 삭제

그 외 함수들은 이미 배웠으니.. 알아서 잘 사용해 보렴..

if ~ :
elif ~ :
else ~ :

반복문은 for문이 소스코드가 짧은 경우가 더 많다

for ~ :

while ~ : 
	if ~ : 
		break or continue

조건문에서 실행될 소스코드가 한줄이면 줄바꿈 안해도 된다

x in list
x not in list

조건부 표현식,,, 리스트 컴프리헨션만 편한 것이 아니였다.. 변수에도 조건부 표현식을 사용할 수 있다,, 놀라워,,

score = 85
result = “Success” if score>=80 else “Fail”

함수(def)

이것도 배웠으니 알아서 하시고,,
함수 밖의 변수를 바로 참조하려면 다음과 같다

a=0

def func():
	global a
	a+=1

for i in range(10):
	func()

print(a)

람다표현식

간단한 함수를 정의해야할 때
정렬 라이브러리를 사용할 때, 정렬 기준을 설정할 때 자주 사용.

def add(a,b)
	return a+b

#같은 것
print((lambda a,b:a+b)(3,7))

입출력

알고리즘 문제 풀이의 첫 번째 단계
읿