[코딩 테스트] - 구현

구현

• 구현: 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

• 알고리즘 대회에서 구현 문제: 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제

  • 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
  • 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
  • 문자열을 특정 기준에 따라 끊어 처리해야 하는 문제
  • 적절한 라이브러리를 찾으면 매우 쉽게 풀리는 문제 (모든 순열, 모든 조합을 찾는 문제 등 - itertools 사용)

• 일반적으로 알고리즘 문제에서 2차원 공간은 행렬(Matrix)

  

  • 왼쪽 위가 첫번째 원소 (0,0)

• 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터 활용
  

• 파이썬에서 리스트 크기 주의

  • 코딩테스트에서는 128~512MB로 메모리를 제한하는데 알고리즘 문제 중 수백만 개 이상의 데이터를 처리해야하는 문제가 출제되면 메모리 제한을 고려해야함

---

<문제> 상하좌우

• 문제 해결 아이디어

  • 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션(Simulation) 유형으로도 분류되며 구현이 중요한 대표적 유형
  • 시뮬레이션, 구현, 완전 탐색 유형은 서로 유사한 점이 많음

• 내 풀이

  n = int(input())
  m = list(input().split())
  x, y = 1, 1
  
  dx = [0, 0, -1, 1]
  dy = [-1, 1, 0, 0]
  directions = ["L", "R", "U", "D"]
  
  for d in m:
      for i in range(len(directions)):
          if d == directions[i]:
              nx = x + dx[i]
              ny = y + dy[i]
  
      if nx == 0 or ny == 0 or nx > n or ny > n:
          continue
  
      x, y = nx, ny
  print(x, y)

• 정답 예시

  n = int(input())
  x, y = 1,1
  plans = input().split()
  
  # L,R,U,D에 따른 이동 방향
  dx = [0, 0, -1, 1]
  dy = [-1, 1, 0, 0]
  move_types = ["L", "R", "U", "D"]
  
  # 이동 계획을 하나씩 확인
  for plan in plans:
      # 이동 후 좌표 구하기
      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)

---

<문제> 시각

• 문제 해결 아이디어
  • 가능한 모든 시각의 경우를 하나씩 모두 세서 푸는 문제
  • 하루는 86400초이므로 모든 경우는 86400가지이므로 충분히 계산 가능
  • 단순히 시각을 1씩 증가시키면서 3이 하나라도 포함되어 있는지 확인
  • 완전 탐색(Brute Forcing) 유형 → 가능한 경우의 수를 모두 검사해보는 탐색 방법
• 내 코드

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) or '3' in str(j) or '3' in str(k):
        count += 1

print(count)

• 답안 예시
  

# H 입력 받기
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)

---

<문제> 왕실의 나이트

• 문제 해결 아이디어

  • 나이트의 8가지 경로를 하나씩 확인하며 각 위치로 이동이 가능한지 확인
  • 리스트를 이용하여 8가지 방향에 대한 방향 벡터를 정의

• 내 코드

n = input()
moves = [(-1, -2),(-2, 1),(-2, 1),(-1, 2),(1, 2),(2, 1),(2, -1),(1, -2)]
row = int(ord(n[0])-96)
column = int(n[1])
position = (row, column)
result = 0
for move in moves:
  row = row + move[0]
  column = column + move[1]
  if row >= 1 and column >= 1 and row <=8 and column <= 8:
    result +=1
  row = position[0]
  column = position[1]
print(result)

• 답안 예시
  

# 현재 나이트의 위치 입력받기
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)

---

<문제> 문자열 재정렬

• 문제 해결 아이디어

  • 문자열이 입력되었을 때 문자를 하나씩 확인
  • 숫자인 경우 따로 합계를 계산하고 알파벳인 경우 별도의 리스트에 저장
  • 리스트에 저장된 알파벳을 정렬해 출력하고, 계를 뒤에 붙여 출력하는 정답

• 내 코드

string = input()
l = []
result = 0
for i in string:
  if i in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':
    l.append(i)
  else:
    result += int(i)
l.sort()
for j in l:
  print(j,end='')
if result !=0:
	print(result,end='')

• 답안 예시

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

# 문자를 하나씩 확인하며
for x in data:
	# 알파벳인 경우 결과 리스트에 삽입
	if x.isalpha():
			result.append(x)
	# 숫자는 따로 더하기
	else:
		value += int(x)

# 알파벳을 오름차순으로 정렬
result.sort()

# 숫자가 하나라도 존재하는 경우 가장 뒤에 삽입
if value != 0:
	result.append(str(value))

# 최종 결과 출력(리스트를 문자열로 변환하여 출력)
print(''.join(result))	

참고: 이것이 취업을 위한 코딩 테스트다 with 파이썬 (취업과 이직을 결정하는 알고리즘 인터뷰 완벽 가이드), 유튜브 강의 영상