구현 : 시뮬레이션과 완전 탐색

이코테 강의를 통해 공부했습니다!!

• 구현이란, 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
• 구현 유형의 문제란?
  • 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제
• 구현 유형의 예시
  • 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
  • 실수 연산은 다루고, 특정 소수점 자리까지 출력해야 하는 문제
  • 문자열을 특정한 기준에 따라서 끊어 처리하는 문제
  • 적절한 라이브러리를 찾아서 사용해야 하는 문제

2차원 공간

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

  # 3행 5열
  arr = [[0, 1, 2, 3, 4],
               [5, 6, 7, 8, 9],
         [10, 11, 12, 13, 14]]
  
  # arr[0] == 1행
  # arr[0] -> [0, 1, 2, 3, 4]
  
  # arr[1][2] == 2행 3열
  # arr[0][2] == 7

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

  # 동, 북, 서, 남
  dx = [0, -1, 0, 1]
  dy = [1, 0, -1, 0]
  
  # 현재 위치
  x, y = 2, 2
  
  # 동, 북, 서, 남 이동
  for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      print(nx, ny)

구현 예제 - 상하좌우

• 방향 벡터를 이용하는게 익숙하지 않아서 조건문을 이용해서 풀었음

  # 상하좌우
  
  x, y = 1, 1
  
  # 입력
  n = int(input())
  plan = list(input().split())
  
  for direction in plan:
      if direction == 'R' and y < n:
          y += 1
      elif direction == 'L' and y > 1:
          y -= 1
      elif direction == 'U' and x > 1:
          x -= 1
      elif direction == 'D' and x < n:
          x += 1
  
  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)

구현 문제 1 - 시각

• 내 풀이 - 1시간 동안 카운트 되는 값을 미리 계산하고 그 값을 이용

  # 시각
  
  # n 입력
  n = int(input())
  
  # 시간에 3이 없는 경우 1시간 동안 1575번 카운트 (15 * 60 + 45 * 15)
  # 시간에 3이 있는 경우 1시간 동안 3600번 카운트
  if n < 3:
      # n : 0, 1, 2
      count = (n + 1) * 1575
  elif n < 13:
      # n : 3 ~ 12
      count = 3600 + n * 1575
  elif n < 23:
      # n : 13 ~ 22
      count = 3600 * 2 + (n - 1) * 1575
  else:
      # n : 23
      count = 3600 * 3 + 21 * 1575
  
  print(count)

• 답안은 for문 중첩을 이용해서 3이 들어가는지를 직접 확인하는 방법을 선택함

  # 시각
  
  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)

  • 미리 계산할 수 있는 것을 하나씩 따져보는게 비효율적이라고 생각했는데 86,400가지밖에..? 안되는 간단한 연산이였음!
  • ‘3’의 존재 여부를 확인할 때 문자열을 활용한 것이 인상적

구현 문제 2 - 왕실의 나이트

• 방향 벡터를 이용하여 해결~ 내 풀이와 해답이 크게 다르진 않았음

  # 왕실의 나이트
  
  # 입력
  position = input()
  row = int(position[1])
  column = ord(position[0]) - 96
  
  # 이동
  # 8가지 이동의 경우의 수
  drow =    [-2, -2, -1, -1, +2, +2, +1, +1]
  dcolumn = [+1, -1, +2, -2, -1, +1, -2, +2]
  
  # count
  count = 0
  for i in range(8):
      new_row = row + drow[i]
      new_column = column + dcolumn[i]
      if new_row in range(1, 9) and new_column in range(1, 9):
          count += 1
  
  print(count)

구현 문제 추가 풀이 (백준)

1157번 : 단어 공부

1157번: 단어 공부

솔루션 흐름

1. 문자열 입력
2. 문자열을 대문자로 통일
3. 문자 목록을 하나씩 돌아가면서 문자열에 몇개가 존재하는지 확인
   1. 기존 최빈값과 같으면 출력값을 ? 로 설정
   2. 기존 최빈값보다 크다면 최빈값을 업데이트
4. 출력

솔루션 코드

# 단어 공부

str = input()
str = str.upper()
letter_count = -1

for letter in set(str):
    if letter_count == str.count(letter):
        output = '?'
    elif letter_count < str.count(letter):
        output = letter
        letter_count = str.count(letter)

print(output)

• str = str.upper() : 대소문자를 구분하지 않기 때문에 문자열 메소드를 이용하여 모든 문자를 대문자로 변경
• letter_count : 최빈 문자의 개수를 저장하는 변수
• for letter in set(str) : set 자료형을 이용하여 입력된 문자열의 문자 목록을 반환하게 함
• str.count(letter) : 문자열의 count메소드를 이용하여 문자의 개수 카운트

2577번: 숫자의 개수

2577번: 숫자의 개수

솔루션 흐름

1. 입력
2. 곱셈 계산
3. 계산 결과를 문자열로 변경
4. 문자열을 하나씩 탐색하며 숫자가 몇번 등장했는지 count
5. 출력

솔루션 코드

# 숫자의 개수

digit_list = [0] * 10

# 입력
a = int(input())
b = int(input())
c = int(input())
products = a * b * c

for char in str(products):
    digit_list[int(char)] += 1

for digit in digit_list:
    print(digit)