구현- 완전탐색

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서를 참고하며 작성하였습니다. 

본 포스팅에서 작성한 코드문제는 해당 저서에 나와있는 문제 일부입니다.

예시답안코드 출처: https://github.com/ndb796/python-for-coding-test

---

 

▶ 구현이란? 

내가 생각한 아이디어를 소스코드로 바꾸는 과정을 말한다. 주로 알고리즘 문제에서 구현유형이란 아이디어를 떠올리는 건 쉽지만 코드로 구현하기 어렵거나 복잡한 문제를 말한다. 해당 유형의 문제를 풀기위해 다양한 라이브러리와 사용법을 알고 많은 문제를 풀어볼수록 더 유리할 수 있다. 

 

▶ 구현 유형

대표적으로 시뮬레이션 및 완전 탐색 문제가 자주 출제된다. 해당 유형의 문제에서 2차원 공간은 행렬을 의미한다. 특히 행렬에서 방향벡터가 자주 활용되므로 이를 잘 숙지하고 있어야한다. 방향벡터란 행렬의 특정 위치에서 행렬의 위, 아래, 오른쪽, 왼쪽으로 위치를 바꾸는 것을 말한다. 해당 유형은 책 예제에서 다루고 있다.

 

▶ 구현 예제

▷왕실의 나이트

> 1. 아이디어: 모든 가능한 방향의 움직임을 나열한 배열을 선언한 후 현재 위치 x,y에서 움질일때 8*8배열 내에 있으면 1씩 count해준다. 입력으로 들어온 알파벳 좌표값에 대해선 알파벳 배열에서 좌표가 위치한 인덱스를 뽑아 숫자좌표로 변환해준다.

 

> 2. 내가 작성한 코드:

where= input()
alphabet= ['a','b','c','d','e','f','g','h']
y= int(alphabet.index(where[0]))+1
x= int(where[1])

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

result=0
for i in range(len(direction)):
    nx= x+direction[i][0]
    ny= y+direction[i][1]
    
    if nx<1 or nx>8 or ny<1 or ny>8:
        continue
    else: result +=1
print(result)      

0.9535737037658691

 

>3. 답안예시코드:

# 현재 나이트의 위치 입력받기
input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1

# 나이트가 이동할 수 있는 8가지 방향 정의
steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]

# 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
result = 0
for step in steps:
    # 이동하고자 하는 위치 확인
    next_row = row + step[0]
    next_column = column + step[1]
    # 해당 위치로 이동이 가능하다면 카운트 증가
    if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8:
        result += 1

print(result)

0.7679777145385742

 

> 예시답안과의 차이점이라면 알파벳을 숫자로 바꾸는 부분과 카운트 증가에서 나는 if, else문으로 꼭 필요하지 않은 코드를 추가로 써주었다는 것이다. 조건의 반대조건을 생각하여 하나의 코드로 작성하는 것이 더 시간효율적일것이다. 실제로 해당 if, else부분만 예시답안의 코드로 바꿔보았더니 0.7684197425842285으로 예시답안과 거의 비슷한 시간이 소요되었다. 

 

예시답안에서 사용된 ord()함수는 특정문자를 아스키코드로 변환해주는 값이다. 입력받은 알파벳의 아스키코드와 맨 첫번째 a의 아스키코드 값의 차이를 좌표값으로 설정해주었다.