[백준][11723][실버5] 집합

Created

2025/02/03 16:24

import sys

input = sys.stdin.readline

m = int(input())
s = set()

for i in range(m):
    cmd = str(input())
    if 'all' in cmd:
        s = set([_ for _ in range(1, 21)])
    elif 'empty' in cmd:
        s = set()
    else:
        op, x = cmd.split(' ')
        x = int(x)
        if 'add' == op:
            s.add(x)
        elif 'remove' == op:
            s.discard(x)
        elif "check" == op:
            if x in s:
                print(1)
            else:
                print(0)
        elif "toggle" == op:
            if x in s:
                s.discard(x)
            else:
                s.add(x)
Python
복사

파이썬 메모리 관리

[Python] 메모리 초과, 메모리 줄이기

메모리 초과, 메모리 줄이기 백준 파이썬 문제를 풀면서 분명 쉬운 문제이고 직접 돌려보았을 때에는 아무 문제없이 잘 작동되었고 값도 제대로 나왔는데 제출을 하면 자꾸 메모리 초과가 떴던 문제가 있는다. 그 문제를 풀면서 메모리를 줄일려고 for문의 개수를 줄이고 코드를 간략화하는 등 별 노력을 다 해보았는데도 결국 해결되지 않았고 검색을 통해서 해결을 하게 되었는데 우선 메모리 최적화를 진행하지 않고 무작정 프로그램이 잘 돌아간다고해서 그 코드가 마냥 좋은 코드라고 하기에는 부족하다. 결론적으로 파이썬의 메모리가 어떻게 구현되는지 알아보고 더 좋은 메모리 할당을 위한 좋은 습관을 들여주는 게 중요하다. 그래서 메모리 관련해서 정리를 하면서 이해를 하면 조금 더 좋을 것 같아 써 보려고 한다. 💡 파이썬의..

https://jongseoung.tistory.com/40

PyPy large memory usage compared to CPython

I used python to solve SPOJ's large input test problem and met with a very strange occurrence. I submitted the same code using PyPy and Python 2. The results are shown below: The code ran much fa...

https://stackoverflow.com/questions/45117672/pypy-large-memory-usage-compared-to-cpython

정리

•

일반적으로, set은 list보다 더 많은 메모리를 사용한다.

•

집합 문제에서는 입력된 값(원소)가 있는지 없는지 확인하는 게 핵심이다. 따라서 x in s 같은 연산이 자주 사용된다.

•

list 는 각 원소를 연속된 메모리 블록에 저장한다.

•

set 은 해시 테이블 기반의 자료구조고, 원소를 해시값을 이용해 저장한다. 따라서 중복을 허용하지 않고, 중복 검사를 자동으로 수행한다.

•

in 연산의 경우, list 에서는 선형 탐색으로 O(n) , set 에서는 해시 기반으로 (1) 이 된다.

⇒ 따라서, in 연산을 계속해서 사용하는 집합 문제에서는 set 의 성능이 압도적으로 좋다.

•

'all' in cmd: ← 경우에 따라서는 이런 연산도 성능 저하에 영향을 준다. 위 내용을 알았다면 처음부터 split() 으로 인풋을 받아서 사용했을 것이다.