파이썬 알고리즘 기초 점검 / 정리

올리브수

|2022. 10. 30. 23:39

728x90

☑️ To-do

컴퓨팅 사고로의 전환 문제 다 풀기(파이썬)
컴퓨팅 사고로의 전환 문제 다 풀기(자바)
- ~15번 -> (❌중단) New 문제 풀기!
do-it 알고리즘 Ch 2까지 보고 정리하기
- 새로 안 내용 위주!

복합문의 구조

[keyword] [식]: -> header
    ...    
    명령문 -> suite
    ..

파이썬 스타일 가이드 PEP 8
- 클래스명 : 카멜 케이스
- 함수명 : 스네이크 케이스
- 인덴트 : 4

$$sum = n * (n + 1) // 2$$

가우스 덧셈
- 1부터 n까지 정수의 합 구하는 방법

비교 연산자 사용 🆚 드모르간 법칙

# 비교 연산자를 사용하는 방법
if 10 <= no <= 90:

# 드모르간 법칙
if not(no < 10 or no > 99)

< 드모르간 법칙>

각 조건을 부정하고 논리곱을 논리합으로, 논리합을 논리곱으로 바꾸고 다시 전체를 부정하면 원래의 조건 과 같다.
🔎 모든 조건을 부정해서 참으로 표현하는 방법

파이썬에서의 변수

파이썬은 데이터, 함수, 클래스, 모듈, 패키지 등을 모두 object로 취급한다.
객체는 데이터 타입을 가지며 메모리를 차지한다.

객체를 참조하는 객체에 연결된 이름에 불과하다.

💡 통상적인 데이터 저장 구조와 같지 않음을 유의!

모든 객체는 메모리를 차지하고 자료형뿐만 아니라 식별 번호(identity)를 가진다.

line1 > n = 17
line2 > id(17) # 식별 번호를 리턴하는 함수
line3 > id(n)

line2와 line3의 식별 번호가 동일하게 나온다.

변수에 어떤 값을 대입하고 값이 변경되면 값을 복사하는 것이 아니라 값을 참조하는 객체의 식별 번호가 변경된다.

등가성(equality) 🆚 동일성(identity)
- 등가성 비교 == : 두 객체의 값이 같은지 판단
- 동일성 비교 is : 값, 객체 식별 번호까지 같은지 판단

Mutable 🆚 Immutable
- Mutable : 값을 변경할 수 있음(리스트, 딕셔너리, 집합)
- Inmutable : 값을 변경할 수 없음(수, 문자열, 튜플)

모듈

모듈 : 프로그램이 처음 임포트되는 시점에 모듈 객체가 생성되며 초기화되는 구조
소스코드의 재사용화를 위해 모듈을 사용한다.
- 보통 알고리즘에서는 문제 풀이 로직을 solve() 함수에 담아서 작성하고 if __name__ == "__main__" 에서 호출하여 사용한다.

if __name__ == "__main__":
    //코드
    //코드

__name__ : 해당 모듈이 임포트된 경우가 아니라 인터프리터에서 직접 실행된 경우에만 if문 이하의 코드를 돌리라는 명령어
- 모듈을 실행할 수 있는 방법 : 직접 실행 or 임포트
Example : __loader__, __package__ , __space__, __path__, __file__ : 인터프리터가 실행 전에 만들어둔 글로벌 변수

n진수 변환 함수

# 숫자 x를 r진수로 바꿈

def card_conv(x: int, r: int) -> str:
    d = ''
    dchar = '0123456789ABCDEFGHIJKLMNOPQRStUVWXYZ'

    while x > 0:
        d += dchar[x % r] # x를 r로 나눈 나머지에 해당하는 문자 d에 저장
        x //= r # 남은 숫자 저장

    return d[::-1] # 저장된 문자열의 역순으로 반환

파이썬에서의 인수 전달

Call by Value
- 인수가 immutable 일 경우
Call by Reference
- 인수가 mutable 일 경우

💡 정수론 : 수의 성질을 탐구하고 공부하는 분야

( 실제 코테에는 잘 출제되지 않는다.)

소수 구하기

에라토스테네스의 체
1. 구하고자 하는 소수 범위만큼 1차원 배열을 생성한다.
2. 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하며 지운다.
3. 배열의 끝까지 2.를 반복한 후 배열에서 남아 있는 모든 수를 출력한다.
일반적으로는 $O(n^2)$ 라고 생각할 수 있지만 $O(Nlg(lgN))$ 이다.

에라토스테네스의 체 소스코드

import math

n = 1000
array = [True for _ in range(n + 1)]

# 소수일 경우 True, 소수가 아닐 경우 False로 표현
for i in range(2, int(math.sqrt(n)) + 1):
    if array[i] == True:
        j = 2
        while i * j <= n: # i의 배수 모두 제거
            array[i * j] = False
            j += 1

# 남은 소수 모두 출력
for i in range(2, n + 1):
    if array[i]:
        print(i, end=' ')

⭐️ 시간복잡도에 있어서는 효율성이 높은데, 공간복잡도에 있어서는 효율성이 떨어진다.

부동소수점 방식

💡 여기서의 ‘부동’은 움직이지 않는다는 뜻의 부동이 아닌, 떠다니며 움직인다는 의미의 부동이다.

$$ N = (-1)^s * M * 2^E $$

숫자를 부동소수점 방식으로 표현하기

💡 자료형 float 는 부동소수점 방식을 사용한다.

부동소수점 방식의 오차

부동 소수점 방식은 고정 소수점 방식보다 훨씬 더 많은 범위까지 표현이 가능하다.
- But, 항상 오차 존재

double num = 0.1;

for(int i = 0; i < 1000; i++) {
    num += 0.1;
}

System.out.print(num);
> 100.09999999999859

str.format(args, kwargs)
boj. 4344
- "{ n : 0 k . j f}".format( p1, p2, ... ) : p1, p2, ... 중에 n 번째 요소를 k자리수로 맞춘다. 정수 부분의 빈 자리는 0으로 채우고 소수점이하는 j개만 표시한다. 마지막에 f가 아닌 d를 사용하면 정수로 읽어온다.

python

a=123
b=3.1415

print('a:{0:05d}'.format(a))
print('b:{1:07.2f}'.format(a,b))

java

System.out.println(String.format("%.3f", 24.2));

➕ 문자열에서 특정 문자 개수 구하기

static int countChar(String str, String s) {
        return str.length() - str.replace(String.valueOf(s),"").length();
}

🙋 Question

[파이썬에서의 변수] 식별 번호가 고유한 값을 나타내는 거면 식별 번호 is 메모리 주소값 ?
- Yes.
- "CPython implementation detail: CPython 의 경우, id(x) 는 x 가 저장된 메모리의 주소입니다."

🌟 Summary

Scan : 배열의 원소를 하나씩 주목하여 살펴보는 방식(알고리즘 용어)
파이썬에서의 모든 객체는 식별 번호를 가진다.
-> , :는 Python에서의 주석 표시

🔗 Reference

PEP 8 : 파이썬 스타일 가이드
- (https://peps.python.org/pep-0008/)
if name == “main”은 왜 필요할까?
- (https://medium.com/@chullino/if-name-main-%EC%9D%80-%EC%99%9C-%ED%95%84%EC%9A%94%ED%95%A0%EA%B9%8C-bc48cba7f720)
3. 데이터 모델 — Python 3.11.0 문서
- (https://docs.python.org/ko/3/reference/datamodel.html)