2. 구현

https://zero0205.notion.site/2-1d3d5393ddb349dba1c18f33dcbe2976

2. 구현

• 구현 : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
• ⇒ 구현 문제 유형은 모든 범위의 코딩 테스트 유형을 포함하는 개념이다.
• 흔히 ‘풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제’를 의미
• 구현하기 어려운 문제 유형
  • 알고리즘은 간단한데 코드가 지나칠만큼 길어지는 문제
  • 특정 소수점 자리까지 출력해야하는 문제
  • 문자열이 입력으로 주어졌을때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱을 해야 하는) 문제
  ⇒ 사소한 조건 설정이 많은 문제
• 구현이 핵심이 되는 문제 유형
  • 완전 탐색
  • : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
  • 시뮬레이션
  • : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 문제 유형

구현 시 고려해야할 메모리 제약 사항

• 대체로 코딩 테스트에서는 메모리를 128 ~ 512MB로 제한
• C++와 자바에서 정수형 종류에 따른 범위정수형 종류 자료형 크기 자료형 범위

  int	4 bytes	-2 ^ 31 ~ 2 ^ 31
  long long	8 bytes	- 2 ^ 63 ~ 2 ^ 63
  BigInteger(클래스)	가변적	제한 없

• 파이썬
  • 프로그래머가 직접 자료형을 지정할 필요 X
  • 매우 큰 수의 연산을 기본적으로 지원
  • 주의점 : 실수형 변수는 다른 언어와 마찬가지로 유효숫자에 따라서 연산 결과가 원하는 값이 나오지 않을 수 있음
  • 리스트 크기
    • int 자료형 데이터 개수에 따른 메모리 사용량데이터 개수 (리스트의 길이) 메모리 사용량

      1,000	약 4KB
      1,000,000	약 4MB
      10,000,000	약 40MB

• 근데 메모리 용량 제한으로 문제를 풀 수 없게 되는 경우는 잘 없다
• ⇒ 메모리 사용향 제한보다 더 적은 크기의 메모리를 사용해야 한다는 점 정도만 기억하자

구현 문제에 접근하는 방법

• 보통 구현 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴 편
• 고차원적인 사고력을 요구하는 문제는 나오지 않는 편
• ⇒ 문법에 익숙하다면 오히려 쉽게 풀 수 있음
• 구현 문제 유형에는 C/C++이나 자바보다 파이썬이 유리 ⇒ 문자열 처리가 쉬워서구현 난이도 프로그램 실행 시간

  파이썬	쉬운 편	긴 편
  PyPy	쉬운 편	다소 짧은 편
  C/C++	어려운 편	짧은 편

  • PyPy3는 파이썬의 문법을 그대로 지원하며, 대부분 파이썬3보다 실행 속도가 더 빠름

예제 1. 상하좌우

• 내가 작성한 코드

# 구현
# 예제 1. 상하좌우

n = int(input())    # 공간의 크기 : n X n
move = input().split()

row = 1
col = 1

for mv in move:
    if mv == 'R':
        if col < n:
            col += 1
        else:
            continue
    elif mv == 'L':
        if 1 < col:
            col -= 1
        else:
            continue
    elif mv == 'U':
        if 1 < row:
            row -= 1
        else:
            continue
    elif mv == 'D':
        if row < n:
            row += 1
        else:
            continue

print(row, col)

• 책의 해답

# N을 입력받기
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 nx > n or ny < 1 or ny > n:
            continue
        # 이동 수행
        x, y = nx, ny

print(x, y)

예제 2. 시각

• 내가 작성한 코드

# 구현
# 예제 2. 시각

n = int(input())

h, m, s = 0, 0, 0
res = 0

# 시간
for i in range(n+1):
    if str(i).find('3') != -1:
        res += 60 * 60
        continue
    # 분
    for j in range(60):
        if str(j).find('3') != -1:
            res += 60
            continue
        # 초
        for k in range(60):
            if str(k).find('3') != -1:
                res += 1

print(res)

⇒ 문자열 처리가 쉽다는 파이썬의 장점을 못 살린 쓰레기 코드

⇒문자 위치 찾을거 아니면 쓸데없이 메소드 같은거 쓰지 말고 in으로 찾자

• 책의 해답

# N을 입력받기
h = int(input())

count = 0

for i in range(h+1):
    for j in range(60):
        for k in range(60):
            # 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
            if '3' in str(i) + str(j) + str(k):
                count += 1

print(count)

왕실의 나이트

• 내가 작성한 코드

# 구현
# 1. 왕실의 나이트

#나이트의 현재 위치 입력
location = input()

# 나이트의 현재 위치 숫자 정보로 저장
row = int(location[1])
col = ord(location[0]) - ord('a') + 1

res = 0

# 나이트의 움직임의 경우의 수
move = [(2,1), (2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)]

for el in move:
  if 0 < row + el[0] < 9:
    if 0 < col + el[1] < 9:
      res += 1

print(res)

• 책의 해답

#현재 나이트의 위치 입력받기
input_data = input()
row = int(location[1])
column = int(ord(location[0]) - 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)

게임 개발

• 내가 작성한 코드(답지 참고ㅠㅠ)

# 구현
# 2. 게임 개발

# 맵 생성 (n : 세로, m : 가로, 3 <= n,m <= 50)
n, m = map(int, input().split())

# 캐릭터 위치 입력 (방향 => 0:북쪽, 1:동쪽, 2:남쪽, 3:서쪽)
x, y, d = map(int, input().split())

# 맵 정보 입력
input_map = []
for i in range(n):
    input_map.append(list(map(int, input().split())))

cnt = 1
turn = 0

# 북 동 남 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 가봤는지 체크하는 맵 생성
map_check = [[0 for col in range(m)] for row in range(n)]

# 현재 좌표 방문 처리
map_check[x][y] = 1

# 왼쪽으로 회전
def turn_left():
  global d
  d -= 1
  if d == -1:
    d = 3

# 뒤쪽이 바다라서 뒤로 갈 수 없는 상황이 올 때까지 반복
while True:
    turn_left()
    next_x = x + dx[d]
    next_y = y + dy[d]

    # 갈 수 있는 칸인가?
    if input_map[next_x][next_y] == 0 and map_check[next_x][next_y] == 0:
        x = next_x
        y = next_y
        map_check[x][y] = 1
        cnt += 1
        turn = 0
        continue
    else:
      turn += 1

    # 네 방향 모두 못 가는 상황
    if turn == 4:
        next_x = x - dx[d]
        next_y = y - dy[d]

        # 뒤로 갈 수 있음?
        if input_map[next_x][next_y] == 0:
            x = next_x
            y = next_y
        else:
            break

        turn = 0    

print(cnt)

• 실수
  • 처음 좌표를 방문한걸로 체크 안 함
  • 동서남북 방향 설정 처음에 잘못함
• 방향을 설정해서 이동하는 문제의 경우, dx, dy라는 별도의 리스트를 만들어 방향을 정하는 것이 효과적
• ⇒ 반복문을 이용하여 모든 방향을 차례대로 확인할 수 있다는 점에서 유용
• 리스트 컴프리헨션
  • 2차원 배열 만들기
  • : map_check = [[0 for col in range(m)] for row in range(n)] : d = [[0] * m for _ in range(n)]
• 책의 해답

# N, M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())

# 방문한 위치를 저장하기 위한 맵을 생성하여 0으로 초기화
d = [[0] * m for _ in range(n)]
# 현재 캐릭터의 X 좌표, Y 좌표, 방향을 입력받기
x, y, direction = map(int, input().split())
d[x][y] = 1 # 현재 좌표 방문 처리

# 전체 맵 정보를 입력받기
array = []
for i in range(n):
    array.append(list(map(int, input().split())))

# 북, 동, 남, 서 방향 정의
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

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

# 시뮬레이션 시작
count = 1
turn_time = 0
while True:
    # 왼쪽으로 회전
    turn_left()
    nx = x + dx[direction]
    ny = y + dy[direction]
    # 회전한 이후 정면에 가보지 않은 칸이 존재하는 경우 이동
    if d[nx][ny] == 0 and array[nx][ny] == 0:
        d[x][y] = 1
        x = nx
        y = ny
        count += 1
        turn_time = 0
        continue
    # 회전한 이후 정면에 가보지 않은 칸 없거나 바다인 경우
    else:
      turn_time += 1
    # 네 방향 모두 갈 수 없는 경우
    if turn_time == 4:
        nx = x - dx[direction]
        ny = y - dy[direction]
        # 뒤로 갈 수 있다면 이동하기
        if array[nx][ny] == 0:
            x = nx
            y = ny
        else:
            break
        turn_time = 0    
# 정답 출력
print(count)

느낀점

• 파이썬은 여러 변수에 값을 넣을 때 아래와 같은 식으로 편리하게 할 수 있다 잊지말자
• ex) x, y = 1, 1
• 함수 이름을 변수 이름으로 쓰지 말자...
• 구현 : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
• ⇒ 구현 문제 유형은 모든 범위의 코딩 테스트 유형을 포함하는 개념이다.
• 흔히 ‘풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제’를 의미
• 구현하기 어려운 문제 유형
  • 알고리즘은 간단한데 코드가 지나칠만큼 길어지는 문제
  • 특정 소수점 자리까지 출력해야하는 문제
  • 문자열이 입력으로 주어졌을때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱을 해야 하는) 문제
  ⇒ 사소한 조건 설정이 많은 문제
• 구현이 핵심이 되는 문제 유형
  • 완전 탐색
  • : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
  • 시뮬레이션
  • : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 문제 유형구현 시 고려해야할 메모리 제약 사항
    • 대체로 코딩 테스트에서는 메모리를 128 ~ 512MB로 제한
    • C++와 자바에서 정수형 종류에 따른 범위정수형 종류 자료형 크기 자료형 범위

      int	4 bytes	-2 ^ 31 ~ 2 ^ 31
      long long	8 bytes	- 2 ^ 63 ~ 2 ^ 63
      BigInteger(클래스)	가변적	제한 없음

    • 파이썬
      • 프로그래머가 직접 자료형을 지정할 필요 X
      • 매우 큰 수의 연산을 기본적으로 지원
      • 주의점 : 실수형 변수는 다른 언어와 마찬가지로 유효숫자에 따라서 연산 결과가 원하는 값이 나오지 않을 수 있음
      • 리스트 크기
        • int 자료형 데이터 개수에 따른 메모리 사용량데이터 개수 (리스트의 길이) 메모리 사용량

          1,000	약 4KB
          1,000,000	약 4MB
          10,000,000	약 40MB

    • 근데 메모리 용량 제한으로 문제를 풀 수 없게 되는 경우는 잘 없다
    • ⇒ 메모리 사용향 제한보다 더 적은 크기의 메모리를 사용해야 한다는 점 정도만 기억하자
    구현 문제에 접근하는 방법
    • 보통 구현 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴 편
    • 고차원적인 사고력을 요구하는 문제는 나오지 않는 편
    • ⇒ 문법에 익숙하다면 오히려 쉽게 풀 수 있음
    • 구현 문제 유형에는 C/C++이나 자바보다 파이썬이 유리 ⇒ 문자열 처리가 쉬워서구현 난이도 프로그램 실행 시간

      파이썬	쉬운 편	긴 편
      PyPy	쉬운 편	다소 짧은 편
      C/C++	어려운 편	짧은 편

      • PyPy3는 파이썬의 문법을 그대로 지원하며, 대부분 파이썬3보다 실행 속도가 더 빠름
    예제 1. 상하좌우
    • 내가 작성한 코드

    # 구현
    # 예제 1. 상하좌우
    
    n = int(input())    # 공간의 크기 : n X n
    move = input().split()
    
    row = 1
    col = 1
    
    for mv in move:
        if mv == 'R':
            if col < n:
                col += 1
            else:
                continue
        elif mv == 'L':
            if 1 < col:
                col -= 1
            else:
                continue
        elif mv == 'U':
            if 1 < row:
                row -= 1
            else:
                continue
        elif mv == 'D':
            if row < n:
                row += 1
            else:
                continue
    
    print(row, col)
    

    • 책의 해답

    # N을 입력받기
    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 nx > n or ny < 1 or ny > n:
                continue
            # 이동 수행
            x, y = nx, ny
    
    print(x, y)
    

    예제 2. 시각
    • 내가 작성한 코드

    # 구현
    # 예제 2. 시각
    
    n = int(input())
    
    h, m, s = 0, 0, 0
    res = 0
    
    # 시간
    for i in range(n+1):
        if str(i).find('3') != -1:
            res += 60 * 60
            continue
        # 분
        for j in range(60):
            if str(j).find('3') != -1:
                res += 60
                continue
            # 초
            for k in range(60):
                if str(k).find('3') != -1:
                    res += 1
    
    print(res)
    

    ⇒ 문자열 처리가 쉽다는 파이썬의 장점을 못 살린 쓰레기 코드
    • 책의 해답

    # N을 입력받기
    h = int(input())
    
    count = 0
    
    for i in range(h+1):
        for j in range(60):
            for k in range(60):
                # 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
                if '3' in str(i) + str(j) + str(k):
                    count += 1
    
    print(count)
    

    왕실의 나이트
    • 내가 작성한 코드

    # 구현
    # 1. 왕실의 나이트
    
    #나이트의 현재 위치 입력
    location = input()
    
    # 나이트의 현재 위치 숫자 정보로 저장
    row = int(location[1])
    col = ord(location[0]) - ord('a') + 1
    
    res = 0
    
    # 나이트의 움직임의 경우의 수
    move = [(2,1), (2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)]
    
    for el in move:
      if 0 < row + el[0] < 9:
        if 0 < col + el[1] < 9:
          res += 1
    
    print(res)
    

    • 책의 해답

    #현재 나이트의 위치 입력받기
    input_data = input()
    row = int(location[1])
    column = int(ord(location[0]) - 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)
    

    게임 개발
    • 내가 작성한 코드(답지 참고ㅠㅠ)

    # 구현
    # 2. 게임 개발
    
    # 맵 생성 (n : 세로, m : 가로, 3 <= n,m <= 50)
    n, m = map(int, input().split())
    
    # 캐릭터 위치 입력 (방향 => 0:북쪽, 1:동쪽, 2:남쪽, 3:서쪽)
    x, y, d = map(int, input().split())
    
    # 맵 정보 입력
    input_map = []
    for i in range(n):
        input_map.append(list(map(int, input().split())))
    
    cnt = 1
    turn = 0
    
    # 북 동 남 서
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    
    # 가봤는지 체크하는 맵 생성
    map_check = [[0 for col in range(m)] for row in range(n)]
    
    # 현재 좌표 방문 처리
    map_check[x][y] = 1
    
    # 왼쪽으로 회전
    def turn_left():
      global d
      d -= 1
      if d == -1:
        d = 3
    
    # 뒤쪽이 바다라서 뒤로 갈 수 없는 상황이 올 때까지 반복
    while True:
        turn_left()
        next_x = x + dx[d]
        next_y = y + dy[d]
    
        # 갈 수 있는 칸인가?
        if input_map[next_x][next_y] == 0 and map_check[next_x][next_y] == 0:
            x = next_x
            y = next_y
            map_check[x][y] = 1
            cnt += 1
            turn = 0
            continue
        else:
          turn += 1
    
        # 네 방향 모두 못 가는 상황
        if turn == 4:
            next_x = x - dx[d]
            next_y = y - dy[d]
    
            # 뒤로 갈 수 있음?
            if input_map[next_x][next_y] == 0:
                x = next_x
                y = next_y
            else:
                break
    
            turn = 0    
    
    print(cnt)
    

    • 실수
      • 처음 좌표를 방문한걸로 체크 안 함
      • 동서남북 방향 설정 처음에 잘못함
    • 방향을 설정해서 이동하는 문제의 경우, dx, dy라는 별도의 리스트를 만들어 방향을 정하는 것이 효과적
    • ⇒ 반복문을 이용하여 모든 방향을 차례대로 확인할 수 있다는 점에서 유용
    • 리스트 컴프리헨션
      • 2차원 배열 만들기
      • : map_check = [[0 for col in range(m)] for row in range(n)] : d = [[0] * m for _ in range(n)]
    • 책의 해답

    # N, M을 공백으로 구분하여 입력받기
    n, m = map(int, input().split())
    
    # 방문한 위치를 저장하기 위한 맵을 생성하여 0으로 초기화
    d = [[0] * m for _ in range(n)]
    # 현재 캐릭터의 X 좌표, Y 좌표, 방향을 입력받기
    x, y, direction = map(int, input().split())
    d[x][y] = 1 # 현재 좌표 방문 처리
    
    # 전체 맵 정보를 입력받기
    array = []
    for i in range(n):
        array.append(list(map(int, input().split())))
    
    # 북, 동, 남, 서 방향 정의
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    
    # 왼쪽으로 회전
    def turn_left():
      global direction
      direction -= 1
      if direction == -1:
        direction = 3
    
    # 시뮬레이션 시작
    count = 1
    turn_time = 0
    while True:
        # 왼쪽으로 회전
        turn_left()
        nx = x + dx[direction]
        ny = y + dy[direction]
        # 회전한 이후 정면에 가보지 않은 칸이 존재하는 경우 이동
        if d[nx][ny] == 0 and array[nx][ny] == 0:
            d[x][y] = 1
            x = nx
            y = ny
            count += 1
            turn_time = 0
            continue
        # 회전한 이후 정면에 가보지 않은 칸 없거나 바다인 경우
        else:
          turn_time += 1
        # 네 방향 모두 갈 수 없는 경우
        if turn_time == 4:
            nx = x - dx[direction]
            ny = y - dy[direction]
            # 뒤로 갈 수 있다면 이동하기
            if array[nx][ny] == 0:
                x = nx
                y = ny
            else:
                break
            turn_time = 0    
    # 정답 출력
    print(count)
    

    느낀점
    • 파이썬은 여러 변수에 값을 넣을 때 아래와 같은 식으로 편리하게 할 수 있다 잊지말자
    • ex) x, y = 1, 1
    • 함수 이름을 변수 이름으로 쓰지 말자...
  • ⇒문자 위치 찾을거 아니면 쓸데없이 메소드 같은거 쓰지 말고 in으로 찾자