[Python/코테] 구현 알고리즘

구현

★ 시뮬레이션과 완전 탐색을 중심으로

풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제들을 지칭한다. 프로그래밍 언어에 따라 구현 문제의 유형이 달라질 수 있다. ex) 실수 연산을 다루고 특정 소수점까지 출력하기, 문자열을 기준에 따라 끊어 처리하기, 적절한 라이브러리 찾기(순열 등) 등의 문제가 있다.

 

일반적으로 2차원 공간은 행렬(Materix)의 의미로 사용된다. (2차원 리스트)

시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용된다.

 

1. 상하좌우 (시뮬레이션 유형) 

 

여행가 A가 입력된 계획서를 따라 움직였을 때 최종적으로 도착할 지점의 좌표를 출력하라.

 

* 일련의 명령에 따라 개체를 차례대로 이동시킨다는 점에서 시뮬레이션 유형으로 분류됨. 구현의 대표적인 문제 유형.

* Solution: x, y 좌표를 나눠서 다음 이동 위치를 계산한다.

n = int(input())
x, y = 1, 1
data = input().split()

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D']

for plan in data:
    #이동 후 좌표 구하기
    for i in range(len(move_types)):
        if plan == move_types[i]:
            nx = x + dx[i]
            ny = y + dy[i]
    if nx < 1 or ny < 1 or nx > n or ny > n:
        continue
    # 이동 수행
    x, y = nx, ny

print(x, y)

* 나다어

• 리스트를 순회하며 원소 하나씩 검사하는 코드는 아래와 같이 쓴다. range() , len() 사용
• for i in range(len(move_types)):
       if plan == move_types[i]:'
• 인덱스와 방향벡터를 함께 이용할 수도 있다!

2. 시각

* Solution: 하나씩 모두 세서 푸는, 전형적인 완전 탐색 문제 유형. 파이썬은 1초에 20,000,000번의 연산이 가능하다. 이것을 염두에 두면 86,400초를 세는건 어렵지 않은 일.

h = int(input())

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

print(count)

* 나다어

• 조건을 꼼꼼히 확인하기. (12시까지인 줄 착각했는데 23시까지임)
• 사칙연산이면 아무리 중첩이 많아도 상관없다. 파이썬의 계산 능력을 활용하자 (직접 계산하지 말고 ,,)

3. 왕실의 나이트

* Solution: 2차원 배열을 사용한 방향 벡터 정의, 초기 위치에서 이동가능한 모든 위치가 체스판 안에 있는지를 검사

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)]

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)

* 나다어

• 알파벳 순서는 아스키코드로 바꿔서 비교할 수 있다.
  아스키코드 65~90은 알파벳 대문자 A~Z, 아스키코드 97~122는 알파벳 소문자 a~z를 의미하기 때문 (순차적!)
  ord() 메소드 사용
• (x) 방향벡터를 사용하지 않고, 8가지 경우를 조건문으로 직접 나눴다. 
  여러 경우의 수를 고려해야 할 경우, 벡터 등의 작은 기본 단위를 이용할 수 있는지 확인하자. 그게 꼭 방향벡터가 아니고 크기까지 포함된 벡터일 수도 있는 것!!

4. 문자열 재정렬

* Solution: 알파벳은 따로 리스트를 만들어주고, 숫자는 바로 더해준 뒤 문자열 이어붙이기로 결과 출력한다.

→ ispalha() 와 같은 메소드로 한 방에 ..🔥

data = input()
result = []
value = 0

for x in data:
    if x.isalpha():
        result.append(x)
    else:
        value += int(x)
        
result.sort()

# 숫자가 하나라도 존재한다면 (value는 총합이므로 > 0)
if value != 0:
    result.append(str(value))

print(''.join(result))

* 나다어

• 수는 100, 1000 과 같은 정수, 숫자는 0 ~ 9 사이의 한 자리의 숫자 데이터
• list에 원소 추가: list.append(원소)
• 특정 index에 원소 추가: list.insert(위치, 원소)
• 키 값으로 정렬
  (ex.x[1] 기준으로 오름차순 정렬) → list.sort(key = lambda x:x[1]) 
• 그러나.. 알파벳이라고 키 값으로 정렬할 필요 없이 그냥 list.sort() 하면 정렬된다.
• 문자열 구성이 모두 알파벳인지 확인: isalpha()
• 리스트 요소 하나하나를 문자열로 합치기: '문자열'.join(list)

---

본 포스팅은 하단의 책과 유튜브 강의를 참고하여 정리한 포스팅입니다.

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

https://youtu.be/2zjoKjt97vQ?t=1719