[Python] 이것이 코딩테스트다 4장 구현

구현 파트의 핵심

 

구현은 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다.

 

그리고 공간복잡도와 시간복잡도를 얼추 따져보는 것이 완점탐색을 할 것인지를 결정할 수 있다.

 

 

 

공간복잡도의 관한 얘기

 

int 는 4바이트 이며 데이터 갯수가 1000개라 하면 약 4KB 메모리를 쓰게 된다.

그렇다면 128MB의 메모리 제한이 있는 곳에선 32000000개의 데이터까지 쓸 수 있다는 말이 된다.

 

 

 

시간복잡도의 관한 얘기

 

일반적으로 파이썬은 1초에 2000만번 (20000000)번의 연산을 수행하는 속도이다. 

시간제한이 1초라는 것은 20000000번의 연산이하로 수행할 수 있다면 된다는 것이다.

 

그렇다면 데이터 제한을 보고 어느정도 시간복잡도가 허용되는 지 유추할 수 있다.

 

예를들어,

데이터가 2000만개까지 수행될 수 있어야 한다면 이 문제의 시간복잡도 마지노선은 O(n)이 될 것이다.

 

또하나 예를 들면,

100만개 (1000000)의 데이터 까지 수행될 수 있어야 하는 문제가 있다면, O(nlogn)까지의 시간복잡도까지 허용됨을 유추 할 수 있다. 왜냐하면 O(nlogn)은 데이터가 100만번 일때 약 2000만번 수행되기 때문이다.

 

또하나 예를 들면,

어떤 문제가 데이터가 4000개 ~5000개  사이까지 수행될 수 있어야 한다고 하면, 이 문제의 시간복잡도 마지노선은 O(n^2)이라는 것이다.

 

 

---

상하좌우

 

🎨 내가 짠 코드

 

 

 

🎨 좀 더 효율적인 코드

 

 

 

 

🔑 Key Point 

 

나는 반복문을 1개 썻고, 답은 반복문을 2개 썻지만 시간복잡도는 결국 같다.

답의 반복문 하나는 끝이 4로 일정한 O(1)의 성능을 보이기 때문이다. 

결국 시간복잡도는 같지만 코드는 더 짧은 답의 답안이 더욱 좋아 보인다.

 

 

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

이런식으로 📌방향을 인덱스에 맞추어 리스트로 미리 구현해놓는 아이디어가 편리한 것 같다.

이렇게 구현해놓으면 머리 아플 필요 없이 원하는 것을 가져다 쓸 수 있다.

 

nx = x + dx[i]
ny = y + dy[i]

 

그리고 x 와 y를 무작정 업데이트 하기 전에 우선은 업데이트 한 값을 다른 변수에 저장하고 그 값이 조건을 만족하면 업데이트 하는 아이디어도 편리하다.

 

 

 

---

시각

 

 

🎨 내가 짠 코드

 

 

 

 

🎨 좀 더 효율적인 코드

 

 

 

 

 

 

🔑 Key Point 

 

이 부분에서는 시간이 한정되어 있다는 것을 풀기전에 인지하여야 한다. 총 검사하여야 할 수는 24x60x60 으로 3중문을 쓰면 완전 탐색하여 충분히 계산할 수 있다.

 

거의 답과 비슷하지만 파이썬 문법 String안에 문자가 포함되어 있는지 안되어 있는지 검사하는 in을 사용하면 코드가 매우 짧아진다.

if '3' in str(i)+str(j)+str(k) :

 

한줄이면 충분하게 된다.

 

 

---

 

왕실의 나이트

 

 

 

🎨 내가 짠 코드

 

 

 

 

🎨 좀 더 효율적인 코드

 

 

 

 

🔑 Key Point 

 

답안이 더 좋은 코드라고 할 수는 없지만, 더 짧은 코드는 맞기에 가져왔다.

dx = [-2, -2, 2, 2, -1, 1, -1, 1]
dy = [-1, 1, -1, 1, -2, -2, 2, 2]

이런식으로 잡아도 되지만

steps = [(-2,-1), (-1,-2), (1,-2), (2,-1),(2,1), (1,2),(-1,2), (-2,1)]

이렇게 한번에 잡을 수도 있다. 리스트 안에 튜플을 넣엇는데 리스트 안에 리스트를 넣어도 인덱스 조회가 가능하다.

 

 

 

---

게임 개발

 

 

🎨 내가 짠 코드

 

 

 

 

🔑 Key Point 

 

답안의 코드와 내가 짠 코드가 시간복잡도는 같지만, 내 코드가 훨씬 짧기 때문에 답안의 코드는 쓰지 않았다.

저자는 방문할 위치를 저장할 리스트를 따로 생성하였다. 하지만 전체 맵에 방문할 위치를 저장한다면 굳이 그러지 않아도 된다.

사실 저자가 따로 리스트를 왜 생성했는지 이유를 모르겠다..

 

구현파트 답게 , 조건이 붙은 그대로 파이썬에 옮겨 썻다. 

 

파이썬에선 한가지 아쉬운점이 삼항연산자가 난해하다. 구글링에서 된다고 나온 삼항연산자가 파이참이라서 그런건지 뭔지 쓰면 오류난다.

 

그래도 답안에서 쓰인 부분에서 주목해야할 문법적인 부분이 있다.

 

# 2차원 리스트를 0으로 초기하는 방법
# n x m 을 0으로 초기화 하는것. 
# 인덱스를 굳이 사용하지 않을 땐 언더바_ 를 이용하기도 한다.
d = [[0] * m for _ in range(n)]


# 2차원 리스트를 사용자로부터 입력 받는법
array =[]
for i in range(n) :
	array.append(list(map(int, input().split())))