(그리디) 백준 1543번 _ 문서검색 (+ Python 3 와 PyPy3는 무엇이 다를까)

이 문제는 맞은 문제이다.

N = input("")
k = input("")
print(N.count(k))

단 세줄의 코드를 PyPy3로 제출하면 정답이 나오는 어떻게 생각하면 되게 쉬운 문제이다.

 

그러나 이렇게 따로 정리하는 것은 두가지 이유 때문이다.

1. 위 파이썬 코드를 Python3 로 제출하면 런타임오류가 나와서 PyPy3로 제출했더니 정답처리가 되었다.

2. count라는 파이썬의 치트키를 사용하지 말고 직접 로직을 구현해보고 싶었다.

 

동일한 코드를 PyPy3로 제출하면 정답, Python3로 제출하면 오답처리가 된다.

 

1. Python3 vs PyPy3

우선 Python3 와 PyPy3가 무엇이 다른지부터 알아보자

PyPy3는 파이썬으로 만든 파이썬이다.

우리가 일반적으로 사용하는 Python은 C언어로 구현 되어있고 그 구현체를 CPython이라고 한다.

이는 가장 처음 만들어진 Python 구현체이다. CPython는 컴파일러면서 인터프리터이다.

 

 

그렇다면 컴파일러는 무엇이고 인터프리터는 무엇일까?

1-1. Compilation vs Interpretation

컴퓨터에서 프로그램이 돌아가기 위해서는 코드를 기계어로 변환해줘야한다.

이때 변환 방법에는 크게 두가지가 있는데 Compilation방식과 Interpretation 방식이 있다.

Compilation방식은 작성된 소스코드 전체가 컴퓨터에서 실행될 수 있도록 기계어 형태의 명령어로 변환하고 그 이후 프로그램을 실행하는 방식이다. 이때 컴파일 후 링크를 거쳐 .exe라는 실행 파일을 만든다. 컴파일언어는 대표적으로 C, C++이 있다.

Interpretation방식은 인터프리터(가상 머신)가 항상 프로그램 주변에서 실행 대기(통역)를 한다. 따라서 별도의 실행 파일이 없고 해당 언어로 된 상태를 딱 한번만 읽고 실행한다. 대표적으로는 Python, Ruby가 있다.

Compilation방식(상)과 Interpretation방식(하)

 

[Compilation방식의 장점]

• Interpretation방식보다 더 나은 수행력을 갖고있다.
  • 이미 기계어로 번역되어 있는 것을 실행만 하면 되므로 실행이 더 빠르다(속도가 빠르다).

[Interpretation방식의 장점]

• Compile방식에 비해 더 유연하고 더 나은 진단(에러메시지)을 할 수 있다.
  • 소스코드가 바로 실행되기때문에, 인터프리터가 소스-레벨 디버깅 역할을 한다.
• 데이터의 타입과 크기를 따로 지정할 필요가 없다.

오늘날의 많은 언어(Java .. )는 위의 두 방식을 혼합해서 실행한다.

=> JIT 컴파일 방식

 

JIT(JustInTime)컴파일러는 바이트코드 컴파일러가 있고 이 컴파일러가 소스코드를 중간 언어인 바이트코드로 변환한다.

바이트 코드는 기계어는 아니지만 가상 머신에 의해 기계어로 손쉽게 변환할 수 있는 코드다.

따라서 JIT 컴파일러는 바이트코드를 빠르게 읽어 기계어를 빠르게 생성 할 수 있다.

 

1-2. PyPy3가 Python 3보다 빠른 이유

다시 돌아와서, CPython는 컴파일러면서 인터프리터라고 했다.

그 말은 CPython은 우리가 작성한 파이썬코드를 bytecode로 컴파일하고 실행한다.

 

그러나, PyPy3에서 사용하는 방식은 JIT 컴파일 방식이다.

이는 프로그램을 실행하기 전에 컴파일 하지 않고, 프로그램을 실행하는 시점에서 필요한 부분들을 그때그때 컴파일 하는 방식이다. 이때 자주 쓰이는 코드를 캐싱하기 때문에 인터프리터의 느린 실행속도를 개선할 수 있다.

 

따라서 PyPy3는 실행시, 자주 쓰이는 코드를 캐싱하기 때문에(메모리에 저장), 실행 속도가 Python3에 비해 훨씬 빠른 것이다. 

PyPy3가 파이썬으로 만든 파이썬이면 인터프리터를 다시한번 인터프리터 언어인 파이썬으로 구현 한 것이므로 속도는 그냥Python보다 더 느려야 하는것이 아닌가?
같은 인터프리터여도, PyPy3는 JIT 컴파일 방식을 제공하는 인터프리터이기 때문에 더 빠른 것이다.

그렇다면 PyPy3만 사용하면 되는것이지 왜 속도가 느린 Python3까지 사용하는 것일까?

바로 자주 쓰이는 코드를 캐싱하기 때문에(메모리에 저장)에 정답이 있다.

메모리 사용량이 Python3에 비해 훨씬 많기 때문이다.

 

따라서

간단한 코드(짧은X)상에서는 Python3를 사용하는 것이 메모리, 속도 측면에서 좋을 것이고,

복잡한 코드(반복문)상에서는 PyPy3가 훨씬 더 빠를 것이다.

 

2. 알고리즘 구현 (count 사용 x)

2-1. Solution 1

doc = input()
word = input()
res = 0

while True:
    idx = doc.find(word)
    if idx == -1:
        break
        
    res += 1
    doc = doc[idx+len(word):]
print(res)

가장 직관적인것 같다.

find로 word의 첫 글자 index를 반환한 후 doc을 재설정 (doc에 word가 없으면 break)

2-2. Solution 2

doc = input()
word = input()
print(len(doc.split(word))-1)

split을 함수를 이용해 word별로 문자열을 자른 후 1을 빼주면 쉽게 구할 수 있다.