백준 풀다가 정리(Python)

메모리 사용량 초과

• pypy로 실행하는 것은 python 코드를 컴파일 하여 실행하기 때문에 그 과정을 거치며 속도는 빨라지지만 사용량이 증가한다는 특징이 있다.
• 간단한 문제는 python, 생각할 게 많은 문제이면 pypy

 

딕셔너리에서

card = {}
card[2] = 1

print(card) # {2: 1}

일 경우, card의 key : 2번에 value가 1이다.

 

매우 큰 값을 배열에 저장하여 확인하고 싶을 때나 문자열을 배열에 저장하고 싶을 때는 딕셔너리를 사용한다.
만약 딕셔너리에 저장되어 있는지 체크할 때는 딕셔너리의 get 메서드를 사용한다.

• 들어있는 경우는 그 값으로 한다.
• 들어있지 않는 경우는 0으로 한다.

dist = dict()
dist[2] = 1
dist[1] = 1

print(dist.get(3, 0))
# 결과 : 0

 

for문

for문 배열 역방향 출력

for idx in reversed(arr):
	print(idx)

 

일차원 배열 한 줄에 출력하기

d = [1, 2, 3]

print(' '.join(map(str, d)))

# 결과

1 2 3

 

숫자를 리스트로 변경하기, 리스트에서 해당 인덱스 출력하기

a = 57
num = [57]

# 결과
# num[0] : 5
# num[1] : 7


print(num.index(57))

# 결과
# 0

 

dfs, bfs 언제 사용할까?

백트래킹 - 나무위키 에 따르면

🔔 DFS와 BFS 언제 사용될까?
(1) DFS를 써야할 때

• 모든 경우의 수를 고려해야 하는 문제라면, DFS를 사용한다.
• BFS로도 구현이 물론 가능하지만, BFS로 구현했다간 큐의 크기가 증가한다. 심지어 속도도 똑같다.
• 따라서 경우의 수 구하기는 일반적으로 DFS가 편리하다. 대다수의 문제들은 DFS를 써도 일단 답은 나온다.

(2) BFS를 써야할 때

• 트리의 깊이가 무한대가 될 때이다.
  • 미로찾기에서 루프(회로)가 발생하는 경우, DFS는 이 가지를 탈출할 수 없게 된다. (DFS 사용시, 스택 오버플로우 발생 가능함)
• 트리 깊이 무한대이거나, 미로찾기에서 회로가 발생하는 경우에는 BFS가 편하다.
• 최단거리 구하기 문제에서는 BFS를 사용한다.

 

PyPy 사용할 시

일반 Python에는 해당되지 않는 사항입니다.

 

• 사실 Pypy가 시간 초과더라도 이상할 건 없습니다. 쉬운 문제들은 거의 다 Pypy로 충분히 풀리지만, solved.ac 플래티넘 정도의 문제부터는 조금씩 위험해지기 시작합니다. 상황에 맞는 언어를 사용하도록 합시다.
• Pypy의 재귀 깊이는 파이썬과 달리 딱 정해 놓은 제한이 없습니다. 하지만 10만 단위로 너무 깊이 들어가면 스택 오버플로가 나고, 그 제한은 파이썬보다 낮습니다. 또한 Pypy는 재귀에 굉장히 약합니다.
• print가 sys.stdout.write보다 많은 메모리를 차지합니다. 구체적으로, print를 많이 사용할 수록 메모리도 많이 사용됩니다. 2020년 8월 9일 현재 Atcoder에서도 같은 현상이 나는 것으로 확인했습니다.
• sys.setrecursionlimit에서 설정해 놓은 재귀 깊이가 클 수록 메모리 사용량도 큽니다. 2020년 8월 9일 현재 Codeforces에서도 같은 현상이 나는 것으로 확인했습니다.
• pypy는 재귀에 약하다.

 

dict

dict : 딕셔너리
dict.fromkeys(list, 초기 값)

list_a = [1, 2, 3]

print(dict.fromkeys(list_a, 0))


# 결과 : {1: 0, 2: 0, 3: 0}

---

참고

• https://www.acmicpc.net/board/view/67272

 

Counter, print

card_A = list(map(int, read().split()))

m = int(read())

card_B = list(map(int, read().split()))

count = Counter(card_A)

print(' '.join(str(count[x]) if x in count else '0' for x in card_B))

여기서 ' '.join(str(count[x]) if x in count else '0' for x in card_B) : card_B에서 데이터를 꺼낸다. x가 count 안에 있다면 출력을 count[x]로 하고, 아니면 0을 한다.

 

combinations, permutations

(1) permutations : 순열
nPr : 순서대로 나열하는 경우의 수

from itertools import permutations

data = ['사과', '배', '귤']

result = list(permutations(data, 3))

print(result)

// 결과
[('사과', '배', '귤'), ('사과', '귤', '배'), ('배', '사과', '귤'), ('배', '귤', '사과'), ('귤', '사과', '배'), ('귤', '배', '사과')]

 

(2) combinations : 조합
nCr : 어떤 것들을 묶는 경우의 수

rom itertools import combinations

data = ['사과', '배', '귤']

result = list(combinations(data, 2))

print(result)

// 결과
// [('사과', '배'), ('사과', '귤'), ('배', '귤')]
 

 

(3) product : 중복 순열
순열에서 중복(자신 선택 가능)을 추가한 경우의 수

from itertools import product

data = ['사과', '배', '귤']

result = list(product(data, repeat=2))

print(result)


//결과
// [('사과', '사과'), ('사과', '배'), ('사과', '귤'), ('배', '사과'), ('배', '배'), ('배', '귤'), ('귤', '사과'), ('귤', '배'), ('귤', '귤')]

 

✏️ 순열 vs 조합

• 순열 : 순차적으로 객체 세트를 정렬하는 다양한 방법
• 조합 : 항목을 선택하는 여러 가지 방법을 말한다.(순서는 중요하지 않다.)

ex) (사과, 배, 귤)
순열 : (사과, 배), (사과, 귤), (배, 사과), (배, 귤), (귤, 사과), (귤, 배)
조합 : (사과, 배), (사과, 귤), (배, 귤)

 

sys.stdin.readline()을 하나의 단어로 간단하게

sys.stdin.readline을 이용할 때, 하나의 단어로 사용하고 싶으면 read=sys.stdin.readline 이 후, read를 호출하면 된다. (다만, readline 관련 메소드들을 알고 싶다면 직접 readline을 호출해서 확인해야 한다.)

read().  # 이럴 경우 어떤 메서드를 호출할 수 있는지 잘 안나옴

# 그래서

sys.stdin.readline()을 호출하여, 어떤 메서드들을 호출할 수 있는지 알아낸 후,

read().메서드 와 같이 사용한다.

 

파이썬에서 자료형 변형과 인덱스 조정

arr = '12340567'
arr.index('0')

'0'은 어떤 인덱스에 들어가 있는지 확인할 때 사용

 

str → list
list → str

arr = '12340567'
arr = list(arr)
arr = ''.join(arr) 

 

1 2 3
4 5 6
7 8 9

일 때, 

123
456
789

로 만들려면?

s = '1 2 3'
s = s.replace(' ','').strip()
print(s) # 123

 

매우 큰 숫자, 문자열을 배열 인덱스에 넣어야 한다면?
➡️ 딕셔너리를 사용하자! (key에 넣으면 된다.)

visited = dict()
visited['123456789'] = 1

# 방문한 곳인지 확인할 때
print(visited.get('123456789'))
# 1
print(visited.get('1239'))
# None

 

투 포인터는 어떤 알고리즘일까?

투 포인터 알고리즘은 시작점에서 끝점까지 연결되어 있다.
start += 1 과 end += 1을 하며 각각 (start ~ end)구간의 합을 구하는 알고리즘이다.

1	2	3	4	5	6
	start				end

: 2 + 3 + 4 + 5 + 6

 

이분 탐색을 풀다가 알게된 내용

1 2 3 4 5 6 와 같은 숫자가 있을 때

• 1 2
• 1 3 4
• 1 4 5
  와 같이
  인덱스가 순차적이지 않고 인덱스 간격이 띄워져 있을 때

import sys

read = sys.stdin.readline
n, s = map(int, read().split())

arr = list(map(int, read().split()))

dist = dict()
ans = 0


def leftSeq(idx, cur_sum):
    if idx == n//2:
        dist[cur_sum] = dist.get(cur_sum, 0) + 1
        return

    leftSeq(idx + 1, cur_sum)
    leftSeq(idx + 1, cur_sum + arr[idx])


def rightSeq(idx, cur_sum):
    global ans

    if idx == n:
        ans += dist.get(s - cur_sum, 0)
        return

    rightSeq(idx + 1, cur_sum)
    rightSeq(idx + 1, cur_sum + arr[idx])


leftSeq(0, 0)
rightSeq(n // 2, 0)

if not s:
    ans -= 1
print(ans)

와 같이 재귀적으로 문제를 풀어야 한다.

 

1 2 3 4 5 6 와 같은 숫자가 있을 때

• 1 2
• 1 2 3
• 2 3 4
• 3 4 5
• 4 5

인덱스가 순차적이고 간격이 1씩 띄워질때는 (바로 앞 뒤일 때)

import sys

read = sys.stdin.readline

t = int(read())

n = int(read())
a = list(map(int, read().split()))
m = int(read())
b = list(map(int, read().split()))

cnt = 0

dist = dict()


for i in range(len(a)):
    for j in range(i+1, len(a)+1):
        dist[sum(a[i:j])] = dist.get(sum(a[i:j]), 0) + 1

for i in range(len(b)):
    for j in range(i+1, len(b)+1):
        cnt += dist.get(t-sum(b[i:j]), 0)

print(cnt)

이와 같이 반복문을 통해 문제를 풀면 된다.