[구현: python]개념과 문제 풀이 정리하기

구현

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

 

문자열 처리는 파이썬에서 쉬운 편이다. 

구현 유형 문제는 많은 연습이 필요하다 

 

2차원 공간

행렬 : 2차원 데이터를 표와 같은 형태로 나타날 수 있게 해줌

파이썬 : 2차원 리스트 

방향 벡터

x : 행

y : 열

---

예제 1 상하좌우  풀어보기

1️⃣이동하는 로직

- 방향벡터를 이용해보자

 

L  : 행은 그대로 열은 -1 

R : 행은 그대로 열은 +1

U : 행은 -1 열은 그대로 

D : 행은 +1 열을 그대로 

 

각각 방향 벡터로 나타나면

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

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

 

 

2️⃣정사각형을 벗어나는지 확인 로직

현재의 위치값의 좌표가 >=1 이어야함

x >=1 그리고 y >=1 인 경우 그리고 둘다  n보다는 작거나 같아야 한다.

 

코드 구현 과정

- 예상했던 결과 : x와 y가 1보다 큰 경우에만 아래의 조건문을 통해 x와 y가 업데이트될 것이다.

- 실제 결과 : 무한 루프가 돌았다.....

# 현재 위치
x,y=1,1

#이동 로직


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

while(x,y >=1 ):
  for i in list:
    if i=="L":
      x = x + dx[0]
      y = y+dy[0]
    elif i=="R":
      x = x + dx[1]
      y = y+dy[1]
      print(x,y)
    elif i=="U":
      x = x + dx[2]
      y = y+dy[2]
    else:
      x = x + dx[3]
      y = y+dy[3]

 

for i in list:
    while(x,y >=1 ):
      if i=="L":
        x = x + dx[0]
        y = y+dy[0]
      elif i=="R":
        x = x + dx[1]
        y = y+dy[1]
        print(x,y)
      elif i=="U":
        x = x + dx[2]
        y = y+dy[2]
      else:
        x = x + dx[3]
        y = y+dy[3]

 

원인  

1️⃣우선 조건은 x와 y가 >= 1 그리고 <=  n 이어야한다.

2️⃣현재 로직은 조건이 항상 참이다.

근데 아래에서 업데이트가 되는데 왜 항상 참일까?

 

❓while(x, y >=1 ) 이부분은 튜플인 (x,y)>=1 인지를 검사한다. 여기서 (x,y)>=1  이부분은 파이썬의 튜플 비교연산을 수행하게 되는데 이는 첫번째 요소부터 비교를 시작한다.

 

그래서 x가 1보다 크거나 같으면 참이 되고 y의 값에 상관없이 조건이 항상 참이 되어버린다.

 

하지만 내가 의도한 것은 x도 1보다 크거나 같고, y도 1보다 크거나 같은 상황에서 로직이 돌아가도록 하는 것이었다!!

 

따라서 x>=1 and y>=1 처럼 따로 검사해주어야한다.

 

3️⃣조건에 만족하지 않는 경우 다음 요소로 넘어가는 로직을 추가해야한다.

x와 y가 정사각형 내부에 포함되지 않는 경우에는 다음 이동 로직을 수행해야하므로 continue를 통해 다음으로 넘어가도록 해준다.

 

n = int(input())
list = input().split()

# 현재 위치
x,y=1,1

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

move_types =["L","R","U","D"]

for i in list:
  for j in range(4):
    if i ==move_types[j]:
      nx = x+dx[j]
      ny = y+dy[j]
  if nx <1 or ny<1 or nx>n or ny >n :
    continue
  x,y = nx,ny
      
print(x,y)

 

배운점 

1️⃣while(조건)을 적어준 후에 조건에 맞지 않는 경우 알아서 다음 로직으로 넘어갈 거라는 생각을 했다. 그러나 continue를 사용하여서 다음 반복문으로 넘어가주는 로직을 구현해주어야한다!

continue : 현재 반복의 나머지 부분을 건너뛰고 다음 반복으로 직접 점프한다. 

 

2️⃣조건을 적어줄 때 x>=1 그리고 y>=1인 조건을 걸어주고 싶다면 

 

❌(x,y)>=1 의 형태로 작성해주면 안된다.

🐤반드시 x>=1 and y>=1 처럼 각각 따로 조건을 작성해줘야한다!

 

3️⃣이동 타입은 L R U D였다. 이 로직은 방향 벡터를 사용하여 인덱스만 달라지는 같은 형태를 띤다.

따라서 이동 타입도 리스트로 만들어준 후 방향벡터와 함께 같은 인덱스를 통해 접근할 수 있다.

 

4️⃣x와 y를 같이 출력해주고 싶을 때는 print(x,y)를 해주면 3 2 처럼 출력이 된다.

---

예제 2 : 시각 풀어보기

내 처음 접근

n  = int(input())

count = 0

#1 
# 3 13 23 
if (n<13):
  hour = 1
elif(n<23):
  hour = 2
else:
  hour = 3
count += 3600 *hour

# hour = 3 13 23 즉 24 - 3 = 21
if(n<3):
  hour = n+1
if (n<13): 
  hour = n

elif (n<23): 
  hour = n-1
else:
  hour = n-2
count += 15 * hour * 60 

#3 
if(n<3):
  hour = n+1
if (n<13): 
  hour = n

elif (n<23): 
  hour = n-1
else:
  hour = n-2
count += hour * 45 * 15 

print(count)

 

책을 통해 알게 된 코드

어떻게 시각들을 나타낼지 떠오르지 않아 정수형값으로 처리해야한다는 생각으로 문자열 연산이 안될 것이라고 생각했다.

그러나 가능했던 것이었다.

n  = int(input())

count = 0

for i in range(n+1):
  for j in range(60):
    for k in range(60):
      if '3' in str(i) + str(j) + str(k):
        count +=1
print(count)

 

시각 자체를 문자열 자료형으로 변환하여 처리하고 있다.

5시 59분 59초라면 '055959'로 변환되어 3이 포함되어있는지를 체크한다.

 

완전 탐색 유형

 

완전 탐색 알고리즘은 가능한 경우의 수를 모두 검사해보는 탐색 방법이다. 위의 경우도 완전 탐색에 해당한다. 하지만 만약 데이터의 개수가 매우 클 경우에는 비효율적인 시간복잡도를 가지므로 정상적으로 동작하지 않을 수 있다. 

일반적으로 알고리즘 문제를 풀때 확인(탐색) 해야할 전체 데이터의 개수가 100만개 이하일 때 완전 탐색을 사용하면 적절하다.

 

배운 점

1️⃣데이터의 개수가 100만개 이하일 경우에는 모든 경우의 수를 검사해보는 완전 탐색을 사용할 수 있다. 이를 통해 복잡한 로직구현보다 더 간단하게 구현할 수 있다.

 

2️⃣특정 문자가 문자열에 포함되어있는지를 검사할 때에는 str.contains('검사하고픈 문자') 로 구할 수 있다. 

3️⃣ 특정 문자가 문자열에 포함되어있는지를 검사할 때에는  특정 문자 in 문자열을 통해서도 알 수 있다. 

---

👑왕실의 나이트 문제 

내 코드

position = input()

# 좌표로 변환
x =  int(position[1])
y = ord(position[0]) - ord('a') +1

count =0

# 이동 로직

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

for i in range(8):
  nx = x+dx[i]
  ny = y+dy[i]
  if nx<1 or ny<1 or nx>8 or ny>8:
    continue
  else:
    count +=1
print(count)

 

dx,dy를 사용해서 문제를 해결해보았다.

중단조건이 나오면 다음 인덱스로 넘어가고, 만약 이동을 수행한 좌표가  8*8 내부에 위치한다면 count를 1 증가시켜주었다.

 

문제 해결 로직을 아래 2가지 과정으로 나누어서 생각했다. 

 

1️⃣좌표 변환 

처음에는 알파벳을 열 좌표로 변환해줄 때  파이썬의 딕셔너리 { key : value } 를 이용해서 구하려고 했다. 그런데 파이썬 내장함수인 ord를 사용하면 알파벳의 순서를 구할 수 있다는 걸 알게되었고 ord를 이용해서 구할 수 있었다.

 

2️⃣이동 로직 

이동 로직을 위해 처음에는 리스트 안에[(-2,1) (-1,2) (1,2) , (2,1), (2,-1), (1,-2), (-1,-2), (-2,-1)] 이렇게 8가지의 이동 시 좌표 변화를 담아주고 이 리스트의 각  튜플을 인덱스로 처리해서 nx 와 ny를 구해주는 로직을 떠올렸다.

 

dx, dy와 i 인덱스를 사용해서 구현해보고싶어서 위와 같이 구현했다.

 

🐤새로 배운점 

1️⃣알파벳의 순서 구하기

파이썬에서 알파벳의 순서를 구하려면 아래와 같은 코드로 구할 수 있다. 

ord(문자) - ord('a') +1

 

2️⃣문자열에 접근하기

이 문제에서는 입력이 b3의 형태로 주어진다.  3은 행 값이 되고 b는 열 값이 된다. 

이 때 문자열에 인덱스로 접근할 수 있다. b3을 position 변수에 담았다면 position[0]은 b가 되고 position[1]은 3이 된다.

 

🐣다양하게 구현해보기

1️⃣딕셔너리로 알파벳의 순서 구하기

아래 처럼 딕셔너리를 정의해두고 position[0]에 저장된 알파벳의 순서를알 수 있다.

예를 들어 col['a']를 통해 value 값인 1을 얻을 수 있다.

col = {'a':1,'b':2, 'c': 3,'d':4 , 'e':5,'f':6,'g':7,'h':8}
y = col[position[0]]

 

2️⃣이동 로직 

# 이동 로직 2
steps =[(-2,1), (-1,2), (1,2) , (2,1), (2,-1), (1,-2), (-1,-2), (-2,-1)] 


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

 

🎮게임 개발 문제

필요한 로직

 

입력받기

이동로직

중단조건

 

이동 로직 

지금은 방향이 0, 1, 2, 3인 경우를 다 비교하고 있다. 이 방향 로직을 더 간소화할 수는 없을까?

 

처음 코드는 지금 방향이 0 ,1 , 2, 3인지 에 따라 조건문을 통해 다 비교를 해주었다. 이는 반복도 많았고, 언제 어떻게 중단을 해주어야할지 정하기 어려웠다. 

if current_list[2] == 0:
    nx = current_list[0] + dx[left[0]]
    ny = current_list[1] +dy[left[0]]
    if nx>0 and ny>0 and entire_map[current_list[0]][current_list[1]] ==0:
      count +=1
      current_list[0]=nx
      current_list[1]=ny
      current_list[2]=left[0]
      continue
    else:
      current_list[2] = left[1]

 

 

1️⃣언제 중단해야할까?

네 방향 모두 다 조사 후 뒤로 이동했는데 바다였을 경우! 

 

바라보는 방향은 유지하고 1칸 뒤로 이동

-> 갈 수 있다면 이동하기 

-> 바다라면 끝내기

 

이를 위해 몇 번 회전했는지를 세는 turn_time 변수 추가

 

중단해야할 때는  While True:와 break를 활용해보자 

 

2️⃣왼쪽으로 회전하는 로직을 함수로 빼기

방향이 0일 때 왼쪽으로 회전하면  -> 3

방향이 1일 때 왼쪽으로 회전하면  -> 0

방향이 2일 때 왼쪽으로 회전하면  -> 1

방향이 3일 때 왼쪽으로 회전하면  -> 2

 

그래서 왼쪽으로 회전 시 기본적으로 현재 방향에서 -1만큼 된다.

만약 방향이 -1이 되었다면 그 때만 방향을 3으로 적용해준다.

n, m = map(int,input().split())
x,y,direction = map(int,input().split())



#전체 맵 정보
entire_map = []
for i in range(n):
  entire_map.append(list(map(int,input().split())))

# 이동 시 좌표 변화
dx = [-1,0,1,0]
dy = [0,1,0,-1]

# 경우의 수 
count = 1

# 몇 번 회전했는지 
turn_time =0

# 왼쪽으로 방향 회전 함수
def turn_left():
  global direction
  direction-=1
  if direction == -1:
    direction = 3

while True:
    turn_left()
    nx = x + dx[direction]
    ny = y + dy[direction]
    if nx>0 and ny>0 and entire_map[nx][ny] == 0:
      count += 1
      entire_map[nx][ny] = 1
      x =nx
      y = ny
      turn_time = 0
      continue
    else:
      turn_time +=1

    # 중단 조건 
    if turn_time ==4:
      nx = x - dx[direction]
      ny = y - dy[direction]
      if entire_map[nx][ny] ==0:
        x = nx
        y = ny
      else:
        break
      turn_time = 0
      
print(count)

 

🐤새로 배운 점

1️⃣2차원 리스트를 초기화할 때 리스트 컴프리헨션를 사용하자!

 

특히 특정 크기의 2차원 리스트를 초기화할 때에는 반드시 리스트 컴프리헨션을 사용해야한다. 

아래 로직을 통해 3*4 리스트를 초기화할 수 있다.

n = 3
m = 4

array = [ [0] * m for _ in range(n) ]

 

 

2️⃣중단 조건이 있을 경우 While True와 break문을 활용하자

3️⃣파이썬에 내장되어있는 이름을 쓰지 않도록 주의하자

 

나는 처음에 리스트를 초기화할 때 list라는 변수명을 사용했는데 이는 이미 파이썬에 내장되어있는 함수명과 같아서 에러가 발생했다!