SQLAlchemy + MySQL 10054 Error & MySQL 2006 Error

Lost connection to MySQL system error: 10054 An existing connection was forcibly closed by the remote host

Error Code: 2006 - MySQL server has gone away

SQLAlchemy와 FastAPI 또는 Flask를 활용하여 백엔드 서버를 구축할 때, 어쩌면 한 번쯤은 만났을 수도 있는 에러입니다.

문제는 어쩌다가 딱 한 번 발생하고, 한 번 발생한 후에는 문제없이 서버가 동작한다는 것입니다.

에러 자체는 여러 환경에서 발생할 수 있지만, SQLAlchemy를 사용한다면 하나의 대표적인 원인을 꼽을 수 있습니다.

DB에서는 폐기한 Connection을 SQLAlchemy(server 단)에서 사용하려 했기 때문입니다.

Connection Pooling

SQLAlchemy는 DB와의 통신을 위해 Connection Pooling 방식을 사용합니다.

Connection은 DB와 Server가 각각 연결한 대상에 대한 정보입니다.

이러한 Connection은 생성 시에 연결, 인증, 권한확인 등, 여러 절차를 거쳐야 하기에 오버헤드가 큰 작업입니다.

모든 query마다 Connection의 생성/삭제를 거칠 경우 안 그래도 심한 병목현상이 심해질 것입니다.

이를 위해, 변경 사항이 없을 경우 일종의 캐시처럼 한번 연결된 Connection을 재사용합니다.

그리고 SQLAlchemy 또한 이러한 Connection을 생성한 뒤 Pool에 넣어두고,

요청마다 Pool에 존재하는 Connection을 가져와 사용하는 것입니다.

요청이 정상적으로 수행되고 session을 close()하면 Connection은 다시 Pool로 반환됩니다.

마치 프로세스가 CPU를 점유하는 것처럼, session은 Connection을 점유하는 것입니다.

여기서, 두 가지 대표적인 문제가 발생합니다.

1. close()를 수행하지 않아, session이 connection을 반환하지 못하고 계속 점유하는 경우

2. sqlalchemy와 DB의 connection 유지 기간이 달라 통신 에러가 발생하는 경우.

이번 포스팅에서는 2번 문제를 다루도록 하겠습니다.

Connection의 유지 기간

먼저, SQLAlchemy의 Connection의 특징을 짚고 넘어가겠습니다.

1. 풀에 사용할 수 있는 커넥션이 없을 경우, db에 커넥션 생성 요청을 보내고 정상적으로 생성이 된 경우 이 커넥션 정보를 풀에 넣는다.
2. 사용할 수 있는(비어있는, 점유 가능한) 커넥션이 있을 경우, 이를 활용해 db에 접근한다.
3. 커넥션은 별도의 설정이 없는 경우 영구히 유지된다.
4. SQLAlchemy(Python 프로그램)과 DB는 서로의 상태를 모른다.

3번과 4번 때문에 문제가 발생합니다.

MySQL(MariaDB)의 Connection 타임 아웃은 8시간(28800초)입니다.

다만, 타임 아웃 전에 한 번이라도 사용될 경우 타임 아웃이 초기화됩니다.

그런데 SQLAlchemy의 경우, 별도의 설정이 없으면 Connection은 영구히 유지됩니다.

즉, DB와 연결된 서버를 8시간 이상 열어놓지만 요청이 없어, DB측 커넥션이 타임아웃 된 경우에 문제가 발생합니다.

DB는 이미 폐기한 Connection을 SQLAlchemy가 사용했기 때문에

Lost connection to MySQL system error: 10054 An existing connection was forcibly closed by the remote host

MySQL 연결이 끊어졌습니다: 시스템 오류 10054 - 기존 연결이 원격 호스트에 의해 강제로 종료되었습니다.

이렇게 원격 연결을 DB측에서 닫아버린 것이죠.

10054에러를 반환 받았으니 SQLAlchemy도 Connection을 Pool에서 제거합니다.

그러나 이러한 문제가 발생했음에도 SQLAlchemy는 다시 요청을 보내지 않습니다.

다음 요청에서는 커넥션 풀을 새로 생성해서 통신하기 때문에 문제가 발생하지 않는 것처럼 보입니다.

이제 문제를 파악했으니 해결해봅시다.

해결 방법

해결 방법은 여러 가지가 있습니다.

먼저 SQLAlchemy 단에서 해결하는 방법입니다.

1. pool_pre_ping

engine = create_engine("mysql+pymysql://user:pw@host/db", pool_pre_ping=True)

모든 요청마다 먼저 "Select 1"과 같은 쿼리를 던져 Connection 상태를 확인

그야말로 돌다리도 두들겨보고 건넌다는 느낌입니다.

아무리 가벼운 쿼리여도 쿼리를 보내는 수 자체가 많아지면 오버헤드가 될 수 있다는 단점이 있습니다.

2. pool_recycle

engine = create_engine("mysql+pymysql://user:pw@host/db", pool_recycle=3600)

Connection에 타임 아웃을 설정해 자동으로 새 Connection을 생성

커넥션이 생성된 뒤, 요청 없이 3600초(1시간)이 지나면 타임아웃시키고 새 커넥션을 생성합니다.

이를 통해 커넥션이 오랜 기간 대기하며 발생하는 문제를 줄일 수 있습니다.

이 방법이 가장 좋은 방법이라 생각합니다.

3. 크론잡/ 배치를 활용한 강제 갱신

DB의 Connection timeout이 일어나기 전, 크론잡 등을 활용해 자동으로 쿼리를 던져 커넥션을 갱신하는 방식입니다.

1번 방법과 2번 방법을 적절히 섞은 방법이긴 한데, 굳이?인 방법입니다.

개인적으로는 2번 방법을 선호하는 편입니다.

4. wait_timeout 설정

SHOW VARIABLES LIKE 'wait_timeout';

MySQL(MariaDB)에서는 위의 명령어를 통해 타임아웃을 확인할 수 있습니다.

당연히 재설정도 가능하니, 이 시간을 보다 길게 잡아 커넥션의 유지 시간 자체를 늘리는 것도 방법입니다만,

그다지 좋은 방법은 아닌 것 같습니다...

Python은 접근 제어자가 없다.

애석하게도, 파이썬으로 작성한 코드는 어디서든 접근할 수 있습니다.

숨기는 것과 "이 요소에는 접근하지 마시오" 라고 명시하는 것은 가능하지만, 여전히 접근이 쉽습니다.

Java에서 public, private 등의 접근 제어자를 활용해 요소 마다 접근 가능 범위를 수 있는 것과는 상당히 대비됩니다.

(물론 Reflection을 적극 활용할 경우, 얼마든지 접근이야 가능합니다.)

그럼에도, 숨기기 정도와 접근하지 마라고 일러주는 것까지는 가능합니다.

언더 스코어를 통한 접근 제어 표기

Python에서 클래스 내부 요소를 숨기기 위해서 보통 언더 스코어(언더바, _)를 활용합니다.

이를 활용한 네이밍 컨벤션은 클래스 내부 값 뿐만 아닌 함수와 내부 클래스에도 적용이 가능합니다.

변수, 함수, 클래스 모두 1급 객체이므로 취급이 같기 때문이죠.

_ 한 개로 시작하는 요소

클래스 내부와 해당 클래스를 상속받은 클래스의 내부 요소로만 사용하기를 권고

어떠한 강제도 없고, 코드 상 제약도 없는 그저 권고의 의미일 뿐입니다.

Java와 비교하자면, protected 접근 제어와 유사한 범위를 의미한다고 볼 수 있습니다.

__ 두 개로 시작하는 요소 (mangling)

클래스 내부에서만 사용하기를 어느정도 강제

Java의 private 접근 제어자와 동일한 범위를 뜻합니다.

이 경우, 런타임 단계에서 name mangling이 되어 직접 접근을 막아줍니다.

이를 통해 상속 관계에서 이름의 충돌을 막아주는 역할도 합니다.

class Spam:

    def __init__(self):
        self.x = 1
        self._y = 2
        self.__z = 3

spam = Spam()

spam.x     # 1
spam._y    # 2 / 강제성이 없다.
spam.__z   # AttributeError: type object 'Spam' has no attribute '__z'

이렇듯, _y에는 문제없이 접근 가능하지만, __z는 직접적인 접근 자체가 막힙니다.

다만, IDE 기능으로 내부 코드를 뜯어 요소를 확인할 수 있고, 이를 알면 우회적으로 접근할 수 있습니다.

class Spam:

    def __init__(self):
        self.x = 1
        self._y = 2
        self.__z = 3

spam = Spam()

spam._Spam__z  # 에러가 발생하지 않는다.

{ClassName}._{ClassName}__{attribute} 와 같은 식으로 만들면 외부에서도 접근할 수는 있습니다.

물론, 해당 코드 설계자의 의도에 완전히 반하는 행동인만큼, 쓰지 맙시다!

그럼 repr 이건 뭐예용?

매직 메서드입니다.

__repr__은 객체의 "개발자용 표현"을 정의하는 매직 메서드로, 디버깅이나 로깅 시 객체를 어떻게 보여줄지 결정합니다.

일반적이지 않은 특수한 동작을 원할 경우 이를 오버라이드하여 원하는 방식으로 동작하게 만들 수 있습니다.

예를 들어, 객체의 대표 이름을 출력하고 싶은 경우, 클래스 내부에 __repr__ 메서드를 오버라이드하여 마음대로 바꿀 수 있죠.

class Spam:

    def __repr__(self):
        return "언제부터 내가 스팸일 거라고 생각했지?"

spam = Spam()
print(spam)  # 언제부터 내가 스팸일 거라고 생각했지?

따라서, 앞뒤로 언더스코어 2개가 오는 경우는 접근 제어의 의미는 아닙니다.

물론 둘 다 멋대로 가져다 쓰다가 낭패보기 쉽다는 건 같으니, 잘 알아보고 써야합니다!

Python의 class의 속성과 객체의 속성은 별개입니다.

선요약

class의 __init__ 즉, 생성자에서 할당하는 것이 아닌,

class 자체에 선언된 속성은 instance.attribute가 아니라 instance.__class__.attribute에 존재합니다.

다만 instance.attribute에 무언가를 할당한 상태가 아니라면, instance.attribute를 통해 접근이 가능하긴 합니다.

class로 생성할 객체마다 변하기 쉬운 기본 속성을 주고 싶다면, 클래스 속성이 아닌 인스턴스 생성자에 기본값을 설정합시다.

class 하나를 만들어봅시다.

class Cat:
    race = 'Domestic Shot hair'

    def __init__(self, name, age):
        self.name = name
        self.age = age

    def change_race(self, race):
        self.race = race

클래스의 기본 속성으로 도메스틱 숏 헤어라는 종 분류가 들어갑니다.

생성자에서 이름과 나이를 설정할 수 있으며,

메서드를 통해 race를 변경 할 수 있는 것처럼 만들어놨습니다.

위와 같은 코드는 만들면 안 됩니다.

change_race 메서드는 과연 어떻게 동작할까?

oia_cat = Cat('oai', 2)
huh_cat = Cat('huh', 3)

oia_ca.change_race('american shot hair')

과연 위의 코드는 어떤 동작을 의미할까요?

1. Cat 클래스의 클래스 속성인 race 값이 변하여, huh_cat의 race도 바뀌었다.
2. oia_cat 객체(인스턴스)의 race 값만 변한다. huh_cat은 그대로다.
3. 둘 다 아니다.

정답은 3번입니다.

겉으로 드러나는 부분만 보면 2번이 될 수도 있지만, 파고 들면 아예 다릅니다.

class 속성은 모든 인스턴스가 공유한다.

class의 속성은 class의 인스턴스 전체가 공유하는 변수입니다.

# 위의 코드에서 이어진다.

print(oia_ca.race)
print(huh_cat.race)

# ======
american shot hair
domestic shot hair

보다시피 Cat 클래스의 두 객체의 race는 다릅니다.

앞서 말씀드렸다시피, 한 클래스의 모든 객체가 공유해야 하는 값이므로 서로 달라서는 안 됩니다.

단순히 값이 같은 수준(==)이 아닌, 하나의 메모리에 존재하는 똑같은 객체 (is)가 되어야 합니다.

어째서 같은 클래스인데 클래스 속성이 다른가?

chage_race 메서드는 클래스 속성인 race의 값을 바꾼 것이 아닌, 인스턴스 속성 스페이스에 race 값을 생성했기 때문입니다.

클래스 속성과 객체 속성은 다른 스페이스에 선언되어 있습니다.

클래스 속성에 보다 명시적으로 접근하기 위해서는,

{class_instance}.__class__.{attribute}로 접근 할 수 있습니다.

(당연하지만, getter를 만드는 게 최고입니다.)

같은 변수명으로 객체 속성을 선언하지 않는 이상, {class_instance}.attribute는

{class_instance}.__class__.attribute를 불러옵니다.

코드로 설명하면 다음과 같습니다.

oia_cat = Cat('oia', 2)
huh_cat = Cat('huh', 3)

print(oia_cat.race is oia_cat.__class__.race) # True
print(oia_cat.race is huh_cat.race) # True
print(oia_cat.__class__.race is huh_cat.__class__.race) # True

oia_cat.change_race('american shot hair')

print(oia_cat.race is oia_cat.__class__.race) # False
print(oia_cat.race) # american shot hair
print(oia_cat.__class__.race) # domestic shot hair
print(huh_cat.race) # domestic shot hair

print(oia_cat.__class__.race is huh_cat.__class__.race) # True

oia cat의 change_race 메서드로 클래스 속성과 이름을 공유하는 객체 속성을 생성한 뒤에는,

객체 속성을 먼저 호출하게 바뀝니다.

이 때문에 클래스 속성과 객체 속성을 혼동하는 경우가 잦은 것 같습니다.

클래스 속성은 모든 인스턴스가 공유해야만 하는 값, 하나가 바뀌면 모든 값이 바뀌는 값, 또는 상수가 들어가야 합니다.

Cat 클래스를 예로 든다면, 모든 고양이 객체가 변함 없이 공유하는 평균 수명, 학명 정도를 넣을 수 있겠죠.

(물론 세부 품종마다 다를 수는 있으니, 단순 예시입니다!)

위의 클래스를 조금 더 올바르게 수정한다면 다음과 같이 다듬을 수 있을 것 같습니다.

class Cat:
    avg_life_span = 15
    scientific_name = 'Felis catus'

    def __init__(self, name, age, race = 'Domestic Shot hair'):
        self.name = name
        self.age = age
        self.race = race

    def change_race(self, race):
        self.race = race

클래스의 속성은 객체 전체가 공유하는 값으로 바꾸고,

race(품종)의 경우, 기본값은 Domestic shot hair로 하되, 클래스 생성 시 값이 들어올 경우 해당 값으로 할당합니다.

그렇다면 클래스 속성은 어떻게 바꾸지?

@classmethod 데코레이터를 활용하여 클래스 속성을 다룰 수 있는 메서드를 만들어야 합니다.

class Cat:
    avg_life_span = 15
    scientific_name = 'Felis catus'

    def __init__(self, name, age, race = 'Domestic Shot hair'):
        self.name = name
        self.age = age
        self.race = race

    @classmethod
    def change_avg_life_span(cls, new_value):
        cls.avg_life_span = new_value

@classmethod로 선언된 메서드의 경우, 인스턴스를 나타내는 self 대신 클래스 참조를 나타내는 cls가 첫 번째 인자로 들어갑니다.

이 방법으로는 class.__class__ 내에 존재하는 클래스 속성을 바꿀 수 있습니다.

근데 그럼 이것도 되는 거 아니냐?

oia_cat.__class__.avg_life_span = 50

얌전히 setter 만들어 씁시다.

SQLAlchemy란

Java의 JPA와 같이, Python의 ORM 라이브러리입니다.

Django를 사용할 경우 전용 ORM 모듈이 있으나,

FastAPI, Flask를 사용하거나 단순한 Python 실행 파일에서 DB와 연결이 필요할 경우,

거의 무조건 쓰게 되는 라이브러리가 됩니다.

애석하게도 Python backend는 java spring에 비하면 비주류에 속하고,

그 작은 파이 안에서도 절대적 다수는 아직까지 Django입니다.

그렇기 때문에 SQLAlchemy에 대한 정보는 찾기가 쉽지 않은 편이죠.

공식 문서도 있으나, 당연히 영어 버전밖에 없습니다.(그와중에 공식문서 테마가 심히 y2k스럽습니다.)

FastAPI를 깊게 파면서, 당연히 SQLAlchemy도 깊게 팔 수밖에 없었고, 이를 통해 알게 된 정보들을 포스팅하고자 합니다.

Session Maker를 활용한 다양한 연결 방식

1. Try-Yield-Finally 블럭활용

FastAPI는 다음과 같은 연결 방식을 권장합니다.

from sqlalchemy import create_engine, Integer
from sqlalchemy.orm import sessionmaker, DeclarativeBase

DB_URL = f'mysql+pymysql://{USER}:{PASSWORD}@{HOST}:{PORT}/{DATABASE}'
engine = create_engine(url=DB_URL)
session_maker = sessionmaker(bind=engine, autoflush=False)

# ==== 핵심입니다. =======
async def get_db():
    db = session_maker()
    try:
        yield db
    finally:
        db.close()

app = FastAPI()
# =====================

class Base(DeclarativeBase):
    pass

class Item(Base):
    __tablename__ == "items"
    item_id = Column(Integer, primary_key = True)

@app.get('/item')
async def get_item(n, db = Depends(get_db)):

    item = db.query(Item).get(n)

    return item

DB연결 정보를 담은 engine을 바탕으로 session_maker객체를 생성합니다.

session_maker 객체는 펑션 콜이 발생할 시, 새로운 세션(db)를 반환합니다.

FastAPI의 DI용 함수인 Depends를 통해 get_db 함수 자체를 객체로써 파라미터에 넣으면

해당 요청 내에서 db와 연결된 세션을 얻는 것이죠.

이 방식은 Try-Finally 블럭을 통해 자동으로 세션의 커넥션 풀 반환을 시행하므로, 커넥션 누수 문제가 발생하지 않습니다.

Depends(get_db)같은 의존성 주입 방식이 아닌 다른 방식을 쓸 수도 있습니다.

함수 내에서 session_maker의 펑션 콜을 직접 시행해도 괜찮습니다.

2. with 블럭을 통한 생명주기 자동 관리

마치 file open을 with를 통해 안전하게 실행하는 것처럼,

session도 다음과 같이 with블럭을 통해 만들 수 있습니다.

@app.get("/item")
async def get_item(n):
    with session_maker() as db:
        item = db.query(Item).get(n)
    # with 블럭 밖에서도 db 객체 사용이 가능하지만, 하면 안 됩니다!

    return item

with블럭에서 생성한 session 객체는 with블럭 밖에서도 사용이 가능하지만, 하면 안 됩니다!

사실상 강제로 새 세션을 생성한 것이므로, with 블럭의 자동 생명 주기 관리 범위를 벗어나게 되어 문제가 발생합니다.

3. 그냥 만들기

대단히 복잡해져 로직 상 문제가 생길 여지가 많아지고,

쓸 데 없는 반복으로 코드가 길어질 것이며,

한 번의 실수가 매우 치명적으로 다가오는 방법입니다.

@app.get("/item")
async def get_item(n):
    db = session_maker()
    item = db.query(Item).get(n)
    db.close()

이 방법 자체를 쓰지 않았으면 하지만, 만약 쓴다면 세션 사용이 끝난 후에 반드시 .close()로 세션을 마쳐줘야 합니다.

그러지 않을 경우, session 객체가 DB와 Sqlalchemy의 소통 창구인 커넥션을 계속 점유하기 때문에 문제가 발생합니다.

웹서버가 아니라 필요한 때 한 번 세션을 열어줘야 하는 그런 프로그램이 아니라면, 권장하지 않습니다.

이 문제는 다음 번에 다뤄보도록 하겠습니다!

요약

개인적으로는 session_maker를 쓸 경우 1번 방법을 가장 권하는 편입니다.

session_maker 방식이 아닌, engine.connect()를 통한 직접 연결 방식도 있으나,

웹 서버를 개발하고자 한다면 session_maker를 쓰는 게 훨씬 효율적이고 객체지향적입니다.

처음에는 3번을 사용하다가, 2번을 써보고, 1번으로 정착하게 되면서 확실히 느꼈습니다.

1번을 씁시다!

Python은 편하지만 느립니다.

Python은 정말 느립니다. 정말 정말 느립니다.

하지만 편하고 쉽기 때문에 러닝 커브 낮고 접근성이 매우 높습니다.

특히 List 자료형은 매우 쉽고 편합니다.

당연히 그만큼 많은 리소스를 사용하고, 느린 편입니다.

리스트를 조금만 활용하면 stack, queue는 물론, tree, heap, 연결 리스트, 해시 테이블 등등등...

수많은 고급 자료형도 어렵지 않게 구현할 수 있습니다.

다만 알고리즘을 풀 때든, 개발을 할 때든 직접 구현을 하진 않습니다.

시간도 시간이지만 가독성과 성능이 굉장히 떨어지기 때문이죠.

stack이나 queue가 필요할 때는 collections의 deque를

heap이 필요할 때는 그냥 heapq를 가져오면 됩니다.

해시 테이블 구조는 dict로 구현되어 있습니다.

그런데 하남자 같잖아

물론 농담입니다.

저는 어떤 자료형이나 알고리즘을 쓸 때

내부가 어떻게 굴러가는지 모르는 채로 모듈이나 라이브러리 가져와 쓰고 싶진 않았습니다.

Tree든, Queue든, heap이든, 직접 구현해서 쓰고 싶었습니다.

물론, 개념과 구조를 이해하기 전까진 매우 좋은 경험이라 생각합니다.

개념이 익숙해진 이후에도 굳이 그런 일을 반복하는 것은 별로 좋지 않습니다.

그럴 거면 Python이 아니라 C++을 썼어야지.

안 그래도 느린 파이썬으로 자료구조와 동작들을 하나하나 구현하면

어지간해선 알고리즘 저지 사이트의 시간제한을 맞추지 못합니다.

실제 서비스 개발이면 더더욱 큰 문제입니다.

꼭 모듈이나 라이브러리를 들고 옵시다.

Python은 기본 구현체가 C입니다.

그래서 Python을 굳이 분류해서 말하면 기본이자 메인인 Python은 CPython이라 표현합니다.

(Java/Jvm의 Jython, C++의 Pyston, Python(!?)과 JIT 컴파일을 활용하는 PyPy 등, 여러 구현체가 있다.)

어쨋든 C로 시작했기 때문에, 기본적인 함수와 자료구조, 모듈 및 유명 외부 라이브러리들은

내부 핵심 로직이 C/C++로 구현된 경우가 상당히 많습니다.

이전에 find()함수를 python으로 직접 구현한 탓에 시간을 맞추지 못한 적이 있습니다. 백준 - ioioi [SILVER 1]

python 구조체를 직접 건드릴 수 있는 수준이 아니라면 대부분의 경우에 이런 일이 발생합니다.

직접 Tim sort를 구현해도 .sort() 메서드보다 빠르지 않습니다.

해시 테이블을 아무리 잘 만들어도 dict 타입보다 느리고 불편합니다.

heap을 직접 구현해도 heapq를 가져와 쓰는 것보다 느립니다.

직접 구현한 최대 힙 vs heapq 모듈 가져오기

백준 - 최대 힙 [SILVER 3]

최대 힙을 '구현'만 하면 끝나는 문제입니다.

즉, import heapq하면 거의 문제의 반 이상을 해결한 것입니다.

import heapq

oper = [int(input()) for _ in range(int(input()))]

Q = []

for o in oper:
    if not o:
        if Q:
            print(-heapq.heappop(Q))
        else:
            print(0)
    else:
        heapq.heappush(Q, -o)

위의 스탠다드한 방법에서는 110ms 정도가 소요되었습니다.

이러한 문제에서 heap을 직접 구현해서 쓰면 어지간해선 시간 초과가 발생합니다.

def h_pop(Q):
    p = Q[1]
    Q[1] = Q[-1]
    Q.pop()
    i = 1
    while i*2 < len(Q):
        lc, rc = i*2, i*2+1
        if lc == len(Q)-1:
            if Q[i] < Q[lc]:
                Q[i], Q[lc] = Q[lc], Q[i]
            return Q, p

        if Q[i] <= Q[lc] or Q[i] <= Q[rc]:
            c = lc if Q[lc] > Q[rc] else i*2 + 1
            Q[i], Q[c] = Q[c], Q[i]
            i = c
        else:
            return Q, p
    return Q, p

def h_push(Q, n):
    Q.append(n)
    i = len(Q) - 1

    while i > 1:
        if Q[i] >= Q[i//2]:
            Q[i], Q[i//2] = Q[i//2], Q[i]
            i = i//2
    return Q

oper = [int(input()) for _ in range(int(input()))]

Q = [0]

for o in oper:
    if not o:
        if len(Q) == 1:
            print(0)
        else:
            Q, n = h_pop(Q)
            print(n)
    else:
        Q = h_push(Q, o)

위의 코드는 시간 초과가 발생합니다.

물론 이보다 훨씬 효율적인 방법으로 heap을 구현하여 시간을 감소시킬 수는 있겠으나,

파이썬 상의 구현이라는 한계로 인해 절대 기본 모듈 이상의 성능을 낼 수 없습니다.

여담으로, global scope에 선언된 Q를 함수에서 참조하는 방법보다

함수에 파라미터로 Q(heap)을 넣고 반환받는 편이 효율적입니다.

이는 파이썬의 변수 스코프 탐색 룰인 LEGB 룰에 관한 것으로, 따로 이야기 해보도록 하겠습니다.

두 코드의 실제 실행 시간 차이

문제의 최대 조건으로 설정하여 두 코드를 비교해보았습니다.

N은 100,000으로, 요소는 0 또는 1부터 2³¹까지의 수 중에 하나로 채워넣었습니다.

실행 시간은 다음과 같았습니다.

보다시피, 거의 4배 정도 차이가 나는 것을 확인할 수 있습니다.

물론 다양한 조건 및 구현 방식에 따라 큰 오차가 발생할 것이겠지만,

백준에 문제를 제출할 때 이 정도 차이가 날 수 있다는 것 정도는 알 수 있습니다.

핵심

• 구현된 게 있다면, 모듈과 라이브러리를 가져다 쓰자.

visited 배열을 만들 때 하는 실수들

N = 10

visited = [[0] * N] * 10

Python으로 알고리즘 문제 풀이를 할 때, 위와 같이 코드를 짜면 문제가 발생합니다!

visited[0][1] = 1

print(visited[5][1])

>>> 1       / ?????

이는 리스트 내부의 0번 부터 9번까지의 리스트가 똑같은 메모리를 참조하기 때문에 벌어지는 문제입니다.

즉, 0번째 리스트의 1번째 값을 1로 바꿨으나, 실제로는 모든 2차원 배열의 1열 전체가 1로 바뀌는 것이죠.

[0] * N 으로 생성된 리스트 객체가 c8이라는 메모리를 가졌다고 하면,

[[0] * N] * M으로 생성한 visited 리스트 내부는 [c8, c8, c8, c8, c8...] 이렇게 되어있는 것입니다!

이러한 문제는 어째서 발생하고, 2차원 이상 리스트를 복사하려면 어떻게 해야 할까요?

2차원 이상의 리스트 복사하기

내부의 요소가 모드 기본 자료형인 1차원 배열과 달리,

2차원 배열부터는 리스트를 복사할 때 의도치 않은 문제가 발생하곤 합니다.

보통 알고리즘 문제를 풀 때 그러한데,

BFS 문제로 visited를 만들 때나 기존 리스트를 복사할 때 문제가 발생합니다.

먼저 기존의 리스트와 똑같은 요소를 갖고 있지만,

변경 사항이 전혀 공유되지 않는 독립된 리스트 만들기를 알아봅시다!

깊은 복사 - 값은 똑같지만 완전히 독립된 객체 생성

이는 내부의 모든 요소를 새로운 메모리에 할당하여 새 객체를 만드는 것을 의미합니다.

copy 모듈의 deepcopy 함수를 쓰면 됩니다.

당연히 내부의 모든 값을 새로운 객체로 만들기 때문에 그 즉시 메모리가 * 2 됩니다!

from copy import deepcopy

origin_list = [[1, 2], [2, 4], [4, 6]]

copy_list = deepcopy(origin_list)

print(origin_list[0][0] is copy_list[0][0])

# False

그러나 deepcopy를 사용할 경우, 내부의 모든 요소들이 새로운 메모리에 할당되어 새 객체가 됩니다.

따라서, 리스트 객체 자체는 물론 모든 요소들이 원본 리스트 및 그 내부 요소와 완전 독립되어 있습니다.

한 개의 리스트에서 값을 바꾸고 원본과 비교하는 방법을 쓸 것이라면, 이를 활용할 수 있습니다.

이를 제외한 다른 거의 모든 방법에서 가장 바깥 리스트를 제외한 내부의 요소들의 메모리 주소는 똑같이 설정됩니다.

즉, 껍데기만 갈아치울 뿐이죠.

바로 이 문제 때문에 2차원 이상의 배열에서는 바뀐 값이 공유되는 문제가 벌어집니다.

deepcopy 이외의 대부분의 경우...(얕은 복사)

list생성자 - list(arr)

얕은 복사 메서드 - list.copy()

슬라이싱 객체 대입 - list[:]

컴프리헨서(재귀로 모든 내부 요소를 갈아치우면 deepcopy입니다.) - [i for i in ~~]

A = [[1, 2], ['X', 'Y']]

B = A.copy()

A[1][0] = 'Z'

print(B[1][0])

# Z

위와 같이 원본 리스트에서 2depth 이상 내려간 요소를 변경할 경우,

해당 변경사항이 원본 객체 뿐만 아니라 복사한 객체에도 적용됩니다.

A = [[1, 2], ['X', 'Y']]

B = A.copy()

print(A is B)

# False

print(A[0] is B[0])

# True

print(A[0][1] is B[0][1])

# True

위의 경우처럼 말이죠!

즉, A나 B나 내부 리스트와 요소들이 같은 메모리를 참조한다는 것인데

아예 그냥 동일한 객체가 다른 리스트에 담겨있을 뿐이죠.

A와 B가 똑같이 생긴 물건을 가지고 있는 게 아니라,

대여점에 하나 뿐인 물건을 번갈아 가져오는 것입니다.

A가 책에 코딱지를 붙여 놓으면, 당연히 이후에 빌린 B가 본 책에는 코딱지가 붙어있습니다.

그렇기 때문에 2차원 이상의 배열을 원본과 완전히 독립된 객체로 만들기 위해서는

내부를 완전히 풀어헤치는 재귀 컴프리헨서를 쓰거나 해야합니다!

그러니 깊은 복사가 필요한 경우, 편하게 deepcopy를 씁시다!

다만, 2차원 배열을 만들어야 할 경우에는 [list for _ in range(n)]와 같이 컴프리헨션을 쓰는 것을 조금 더 추천드립니다!

dict는 python 프로그래밍에서 가장 많이 사용되는 복합자료형 중 하나입니다.

dict의 경우, 입력과 조회에서 평균 시간복잡도 O(1)을 차지하므로,

다양한 부분에서 빠른 작업을 해낼 수 있다는 장점이 있습니다.

dictionary는 그럼 단점이 없을까요?

모든 자료구조가 각각의 쓰임이 있듯, 딕셔너리도 모든 작업에서 만능인 것은 아닙니다.

다른 복잡 자료형들과 비교했을 때의 단점들은 다음과 같습니다.

임의의 인덱스 접근 불가

list의 경우, list[0], list[5:], list[1:-3] 등, 다양한 index 접근이 가능합니다.

증가하는 정수형의 인덱스를 갖고 있기 때문이죠.

하지만 key : value로 매핑되는 딕셔너리의 특성상, 이러한 임의, 범위 접근은 사실상 불가능합니다.

임의, 범위 접근이 필요할 때는 keys() 메서드를 통해 key 배열을 만들어서 접근해야 합니다.

메모리 사용률 차이

이번 포스팅의 주제이기도 한, 메모리 사용률의 차이입니다.

이는 어디까지나 알고리즘 문제 풀이에 활용하는 경우에 한한 것입니다.
실제 프로그램 개발에서 자료구조의 선택은 다양한 요인을 따져야 합니다.

백준 1620 - 나는야 포켓몬 마스터 이다솜 문제로 알아보자

해당 문제는 N개의 포켓몬 이름을 받은 뒤, M개의 질의가 들어오는데,

질의가 자연수일 경우 해당 순서의 포켓몬 이름을,

질의가 포켓몬 이름일 경우 해당 순서를 출력하는 문제입니다.

python으로 풀게 될 경우, 일반적으로 dict를 활용하도록 유도된 문제입니다.

두 가지 방법이 있는데,

pokemon = {}
for i in range(1, N+1)
    name = input()
    pokemon[name] = i
    pokemon[i] = name

위와 같이 딕셔너리 하나에 {이름:인덱스}와 {인덱스:이름}의 모든 경우 저장하는 것이고,

pokemon = {}
for i in range(1, N+1)
    pokemon[input()] = i

index_list = [0] + list(pokemon.keys()) # 인덱스가 0이 아닌 1부터 주어지므로

위와 같이 {이름:인덱스}의 dictionary를 만들고, list로 포켓몬 도감을 또 하나 만드는 것입니다.

Python의 dict형태는 입력순서가 보전되므로, keys() 메서드를 활용해 list를 만들어도 순서가 유지됩니다.

또한 리스트에 대한 임의 인덱스 접근(list[n])의 경우, 시간 복잡도가 고정 O(1)이므로 딕셔너리와 거의 같습니다.

두 번째 방법을 쓰는 이유는 메모리를 적게 쓰고, 빠를 수도 있기 때문입니다.

백준의 입력 예시를 넣은 뒤, sys.getsizeof(pokemon)으로 확인할 경우,

첫 번째 방법의 pokemon dict는 총 2264바이트를 점유하고 있고,

두 번째 방법의 pokemon dict는 832바이트를, index_list는 272바이트를 점유하여,

총 1104바이트를 점유하고 있는 것을 확인할 수 있습니다.

이는 내부 객체들의 값을 모두 더한 게 아니라, 해당 복합 자료형의 메모리만 계산한 것입니다!

첫 번째 방법 두 번째 방법에 비해 거의 두 배의 메모리를 점유하고 있는 것이죠.

두 방법을 모두 활용해 문제를 해결할 경우, 각각 풀이의 메모리 점유는 다음과 같습니다.

1. dict 안에 인덱스와 네임 키를 모두 넣은 경우

2.dict 네임 키, index list 따로 생성한 경우

백준에서 Python 런타임 환경은 약 31100kb를 점유하고 있으므로,

1번 방법은 26000kb 가량의 메모리를 사용했고,

2번 방법은 16000kb 가량의 메모리를 사용하고 있다고 할 수 있겠습니다.

딕셔너리는 키와 값의 조합을 따로 저장하며, 해시 테이블도 갖고 있기 때문에

점유하는 메모리가 리스트보단 클 수밖에 없습니다.

약 1.6배의 메모리 차이를 보이며, 풀이속도에서도 어느정도 유의미한 차이가 있었습니다.

딕셔너리의 경우, 키를 통한 접근에 평균 O(1)의 시간 복잡도를 가진다고 하는데,

사실 해시 함수 수행과 해시 충돌 문제로 인해 실제로는 그보다 조금 더 높을 수 있기 때문입니다.

정리

대부분의 알고리즘 문제 풀이에서는 사실 메모리 점유율보단 실행속도를 훨씬 우선시 하기 때문에

메모리 점유율은 딱히 고려의 대상이 되지 않는 편입니다.(물론 극단적인 문제가 분명 존재하긴 하지만)

다만, 딕셔너리를 사용한다고 하더라도 입력 순서를 지켜준다는 특성을 활용하면

실행 속도도 줄이고 메모리 점유율도 낮출 수 있는 방법을 찾을 수 있을 것이라 생각합니다!

컴파일 단계가 아닌, 실행시간(런타임)에 자료형 검사가 이루어지는 것을 뜻합니다.

def type_example():
    number = 42
    print(number)
    number = "42"
    print(number)

type_example()

>>> 42
>>> 42

Python에서는 위와 같이 int 형태로 number라는 변수를 생성한 뒤,

string 형태로 바꾸어도(재할당) 해도 아무런 문제가 없습니다.

다만 이러한 방식은 정적 타이핑 언어에서는 문제가 많이 발생합니다.

동적 정형과 정적 정형

public class TypeConversionExample {

    public static void main(String[] args) {
        // 정수형으로 선언된 변수
        int number = 42;

        // 같은 변수명을 가진 다른 타입의 객체 생성 시도
        String number = "42";
    }
}

// 에러 발생
>>> Variable 'number' is already defined in the scope

동적 정형의 대척점에 있는 것은 정적 정형(Static Typing, 정적 타이핑)으로,

자료형 검사가 컴파일 단계에서 실행되는 것을 말합니다.

컴파일 단계에서는 작성된 소스 코드가 바이너리 코드로 변환되는데,

이 과정에서 변수에 대한 모든 정보가 변환되고, 사용할 메모리 영역이 지정됩니다.

즉, 이 단계에서 사용할 메모리까지 지정이 되므로 런타임 환경에 진입한 시점에 변수의 타입은 이미 정해진 상태입니다.

그럼 왜 정적 정형을 쓰는가?

정적 정형의 장점은 다음과 같습니다.

1. 에러 방지와 안정성
   • 특별한 이유와 수단을 동원하지 않는 한 번 지정된 타입은 프로그램이 종료될 때까지 유지되는 것이죠.
   • 따라서 동적 타이핑 언어에서는 자주 벌어지는 타입 변환 오류가 거의 발생하지 않게 됩니다.
   • 이는 코드를 작성하는 개발자의 입장에서도 타입에 대해 더욱 유의하게끔 만들 수밖에 없습니다.
2. 속도 및 메모리 최적화
   • 컴파일러가 이미 해당 변수의 자료형을 알고 있기 때문에, 최적화된 기계어 코드를 실행할 수 있습니다.
   • 또한, 메모리 할당과 해제가 더욱 철저하게 이루어지기 때문에 메모리 사용에서도 효율적이라 할 수 있습니다.
   • 컴파일 타임에서 자료형 검사가 끝나기 때문에 런타임에서 굳이 자료형을 검사하지 않습니다.
3. IDE의 지원
   • python의 경우 mypy를 활용하면 되지만, 이를 위한 많은 모듈과 라이브러리를 요하게 됩니다.
   • 소소하지만 코드를 작성하는 때에 큰 도움이 되는 부분이라 생각합니다.
   • 정적 타이핑은 IDE 입장에서도 타입 에러를 표시해주기 쉬워집니다.

그럼 동적 정형은 느리기만 한가?

런타임에서 타입 검사가 이루어지기 때문에 느릴 수밖에 없습니다.

하지만 프로그래머 입장에서는 편의성과 유연성이라는 매우 큰 효용을 가져다줍니다.

1. 유연성
   • 얼마든지 새로운 값과 타입을 지정해줄 수 있다는 점은 코딩에 큰 유연성과 편의성을 제공합니다.
   • 아마 이 단 하나의 이유가 동적 정형을 쓰는 가장 큰 이유가 아닐까 싶습니다.
2. 코드의 간결성과 생산성 확대
   • java나 Kotlin을 사용하다가 python으로 돌아오면 빠른 걸 넘어서 허전할 정도입니다.
   • 변수의 선언문이 매우 간결해집니다.

https://ko.wikipedia.org/wiki/%EC%9E%90%EB%A3%8C%ED%98%95_%EC%B2%B4%EA%B3%84#%EC%A0%95%EC%A0%81_%EC%A0%95%ED%98%95

백준 18114 - 블랙 프라이데이 [GOLD5]

골드5 문제치고는 정답률이 20%대입니다.

시간 제한은 국룰 2초가 아닌 1초인걸 보면, 시간 복잡도 낮추기가 관건인 문제인 것 같습니다.

문제의 특징은 다음과 같습니다.

1. 최대 3개 내의 물품으로 무게 C를 맞춰야 합니다.
2. 중복 없는 조합이며, 당연히 주어지는 무게는 모두 다릅니다.
3. 가능한 조합 수가 아닌, 가능 여부를 출력합니다.

브루트 포스?

위의 1번과 3번 제약으로 인해, 당연히 모든 조합을 일일이 뒤져봐야 하는 거 아닌가? 하는 생각을 했습니다.

가능 여부는, 결국 모든 조합을 확인해야 불가능한지 파악이 가능하니까요!

또한 3개 고정이 아닌, 1개나 2개도 가능하기 때문에 더더욱 일일이 확인해야하는 줄 알았습니다.

물론, 브루트 포스 형식으로 구현하게 되면 시간복잡도는 N³이 됩니다.

N은 최대 5000이니, 대략 125억 정도입니다. 20분 정도 걸리겠네요.

다양한 방법으로 시간 복잡도를 줄이려 했으나, 어떻게 온몸을 비틀어도 절대 1초 안에 해결할 수는 없을 것 같았습니다.

저는 보통 30분 넘게 헤매면 문제 유형이라도 확인을 하는 편입니다.

문제 유형은...

무려 네 개의 유형이 합쳐진 콤비네이션 유형!

브루트포스는 방금 완전탐색으로 시전을 했습니다.

완탐 온몸비틀기에서 정렬로 c보다 큰 값을 쳐내기도 했죠.

이분 탐색은 감이 잡히지만, 투 포인터는 어따 써먹을지 감도 안 잡혔습니다만,

이분탐색과 투 포인터의 조합

세 개를 구해야하는데, 투 포인터는 어디에 쓰는가?

투 포인터를 이분탐색의 top과 bottom으로 쓰면 해결되는 것입니다!

(left, right를 많이들 쓰지만, 저는 top/bottom을 선호하는 편입니다.)

문제 풀이 순서는 다음과 같습니다.

1. 최대 3개 조합으로 무게 C를 맞춰야 합니다.1-2. 무게는 m으로 설정하겠습니다.
   1. 1-1. 변수명은 편의상 a, b, c로 하겠습니다.
2. a는 arr[0], c는 arr[-1]로 시작합니다.
3. a + c = m이라면 답입니다.
4. a + c > m면 초과하면 c의 인덱스를 1씩 줄입니다.
5. a + c < m 미만이라면 b를 이분탐색으로 구합니다.
6. b를 이분탐색으로 구해도 답이 없다면, a의 인덱스를 전진시킵니다.
7. 어떤 요소 x가 m과 같을 수 있으니, 시작 전에 검사합니다.

위의 순서에 따라 코드를 구현하면 됩니다.

한 개 물품의 값으로 C를 만족하는 경우는 7번에서 찾아집니다.

두 개 물품의 값으로 C를 만족하는 경우는 a와 c의 인덱스가 조절되며 자동으로 구해집니다.

세 개 물품의 값으로 C를 만족하는 경우는 이분탐색으로 b를 찾는 때에 구해집니다.

정답 코드

n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())))

def bs(b, t, target):
    while b <= t:
        mid = (b+t) // 2
        if arr[mid] > target:
            t = mid - 1
        elif arr[mid] < target:
            b = mid + 1
        else:
            return 1
    return 0

def two_point(i, j):
    while i < j:
        a, c = arr[i], arr[j]
        # 2개 조합은 여기서 해결
        if a + c == m:
            return 1
        elif a + c > m:
            j -= 1
        # 3개 조합은 여기서 해결
        else:
            b = m - (a + c)
            # b가 a또는 c와 같을 수는 없다!
            if b not in [a, c] and bs(i, j, b):
                return 1
            i += 1

    return 0

i, j = 0, n-1

# 1개 조합은 여기서 해결
if m in arr:
    print(1)
else:
    print(two_point(i, j))

결과는 다음과 같습니다.

백준 1300 - K번 째 수 [GOLD 1]

두 개의 입력이 들어옵니다.

N과 K.

길이가 N인 정사각형 형태의 행렬이 arr이 있고, arr[i][j]에는 i*j가 존재합니다.

단, 인덱스는 1부터 시작합니다.

즉, N이 5일 때, 행렬은 다음과 같이 생성됩니다.

[[1, 2, 3, 4, 5],
 [2, 4, 6, 8, 10],
 [3, 6, 9, 12, 15],
 [4, 8, 12, 16, 20],
 [5, 10, 15, 20, 25]]

그리고 해당 2차원 행렬을 1차원 리스트로 풀어내고, 오름차순 정렬을 시킨 뒤, [K] 값을 출력하면 됩니다.

K가 12라고 가정하면,

arr = [1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 6, 8, 8, 9, 10, 10, 12, 12, 15, 15, 16, 20, 20, 25]

arr[12] // 6

위와 같이, 6을 출력하면 됩니다.

이분 탐색

정답은 이분 탐색입니다.

행렬을 직접 만든 다음 정렬을 시키려고 하면 1분 넘게 걸리니 포기합시다.

처음에는 도대체 이게 왜 이분 탐색인데? 라는 생각이 많이 들었는데, 내가 이분 탐색 문제를 안 풀어서 그런 것 같습니다.

문제를 푸는 데에는 몇 가지 키 포인트가 있습니다.

1. arr[K]의 값은 K가 2이상이고 N**2 미만일 때 무조건 K보다 작다. (arr[K] <= K, 단, 2 <= K < N**2)
2. arr[K]의 값보다 작은 값이 K-1개가 있다면, 그것이 정답이다. 따라서 arr[K]값을 이분 탐색으로 추측해가며 값의 범위를 좁혀나가자.

1번의 키포인트에 따라, arr[K]의 값의 한계는 '사실상' K이므로, 이분 탐색의 한계는 K로 설정하면 됩니다.

start를 1로, end를 K로 둔 뒤, 둘을 더하고 2로 나누어 추측을 시작할 중간값 mid를 만듭니다.

그렇다면, 어떻게 mid보다 작은 값을 구할 수 있을까요?

cnt = 0 # mid보다 작은 값의 수 카운트

for i in range(1, N+1):
    for j in range(1, N+1):
        if i*j <= mid:
            cnt += 1

위와 같은 방식으로 구할 수는 있으나, 연산량이 N^2가 되어버립니다.

행렬은 정사각형에 좌상단-우하단 대각선을 기준으로 대칭된다.

따라서, 첫 번째 열은 1로 시작하여 1씩 증가합니다.

두 번째 열은 2로 시작하여 2씩 증가합니다.

세 번째 열은 3으로 시작하여 3씩 증가합니다.

mid를 i(열의 번호)로 나누면, 보다 적은 연산량으로 mid보다 작은 값이 몇 개가 있는지 파악할 수 있습니다.

다만, mid가 N을 초과할 경우, 해당 열의 원소 개수를 초과하여 값을 더해버릴 수 있기 때문에, 더할 수 있는 최대 값은 N으로 설정합니다.

cnt = 0

for i in range(1, N+1):
    cnt += min(mid/i, N)

이제, cnt가 K와 같거나 넘은 경우, 넘지 못한 경우를 따지면 됩니다.

1. cnt가 K와 같거나 넘었다?

같다면 답이 될 수 있지만, 이분 탐색이 끝나기 전에는 잘못된 값이 나올 수 있으므로 일단 answer에 mid를 할당합니다.

넘었다면, 설정한 추측값(mid)가 높으므로, end를 mid로 설정하여 낮추고, 1을 빼줍니다.

2. cnt가 K를 넘지 못했다?

설정한 추측값(mid)가 너무 낮으므로, start를 mid로 설정한 뒤, 1을 더합니다.

while문의 반복 조건으로 걸어두면 되는 것이죠.

cnt와 K의 값이 같다고 해도, start와 end의 범위가 넓을 경우,

조건은 만족하지만 정답이 아닌 값이 나올 수 있으므로 start가 end와 같거나 넘어설 때까지 반복해야 합니다.

정답 코드

N, K = int(input()), int(input())

s, e = 1, K
a = 0

while s <= e:

    m = (s + e) // 2
    cnt = 0
    for i in range(1, N+1):
        cnt += min(m//i, N)

    if cnt >= K:
        a = m
        e = m-1
    else:
        s = m+1

print(a)