본문 바로가기
REVIEW/CODING TEST

구현(implementation) 총 정리

by 진자이 2023. 6. 29.

안녕하세요 진자이입니다 :) 이번 포스팅에서는 이코테 내용 중 구현에 대해서 공부한 내용을 기록하려고 합니다.

 

아이디어를 코드로 바꾸는 구현

코딩 테스트에서 구현이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 문제 해결 분야에서 구현 유형의 문제는 풀이를 떠올리는 것은 쉽지만, 소스코드로 옮기기 어려운 문제를 의미한다. “프로그래밍의 언어의 문법에 능숙하고, 코드 작성 속도(타자)가 빠른 사람이 구현 능력이 좋은게 일반적이다.

예를 들면, 알고리즘은 간단하지만 코드가 지나칠 만큼 길어지는 문제, 특정 소수점 자리까지 출력하는 문제, 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제 등 사소한 조건 설정이 많은 문제이다.

이 책에서는 완전 탐색, 시뮬레이션 유형을 모두 구현 유형으로 묶어서 다루고 있다. **[완전 탐색]**은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미하고, **[시뮬레이션]**은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형을 의미한다.

파이썬에서 고려해야 할 사항은 리스트 크기이다. 파이썬에서 여러 개의 변수를 사용할 때는 리스트를 이용하는데, 메모리제한을 고려해야 한다. 대체로 코딩 테스트에서는128~512MB로 메모리를 제한하는데, 가끔 때로는 수백만 개 이상의 데이터를 처리해야 하는 문제가 출제 되곤한다. 정수형(INT)의 예로 들면, 데이터의 개수가 10,000,000 개만 돼도 약 40MB를 사용한다. 입출력에 많은 시간이 소요되어 다양한 문제가 발생할 수 있으니 주의하자.

일반적인 코딩테스트 환경에서는 ‘시간 제한 및 메모리 제한 정보가 다음과 같다. “시간 제한 1초, 메모리 제한 :128MB” 만약 데이터 개수가 100만 개인 문제가 있다면, 일반적으로 시간 복잡도는 O(NlogN) 이내의 알고리즘을 사용해야 한다. 왜냐하면 일반적으로 1초에 2000만 번의 수행을 가정한다고 했을 때 N이 최대값이 1,000,000에 가깝기 때문이다.

Pypy3은 파이썬3 문법을 그대로 지원하며, 대부분 파이썬3보다 실행 속도가 빠르기 때문에 실행 시간을 줄일 수 있다. 특히 반복문이 많을 수록 더 좋다고 한다.

알고리즘의 대표적인 예시인 상하좌우 문제와 시각 문제를 풀어보려 한다. 2문제를 가볍게 읽은 다음, 다음 2절의 실전 문제를 풀어보자.

 

예제 4-1 상하좌우

여행가 A는 NN 크기의 정사각형 공간 위에 서있다. 이 공간은 11 크기의 정사각형으로 나누어져 있으며, 가장 왼쪽 위 좌표는 (1,1), 가장 오른쪽 아래 좌표는 (N,N)이다. 여행가 A는 상하좌우 방향으로 이동할 수 있으며 시작 좌표는 (1,1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여있다.

계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀있다. 각 문자의 의미는 다음과 같다. 정사각형을 벗어나는 움직임은 무시된다.

  • L : 왼쪽으로 한 칸 이동
  • R : 오른쪽으로 한 칸 이동
  • U : 위로 한 칸 이동
  • D : 아래로 한 칸 이동

예를들어, ‘R R R U D D’라고 입력되면 (3,4)가 반환된다.

입력조건

  • 첫째 줄에 공간의 크기를 나타내는 N이 주어진다 (1 ≤ N ≤ 100) → 5
  • 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다 (1 ≤ 이동 횟수 ≤ 100) → R R R U D D

출력조건

  • 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X,Y)를 공백으로 구분하여 출력한다. → 3 4

아이디어 구상

핵심 부분은, 이동하지 않는 경우를 처리하는 것이다! 좌표의 형식은 [x,y] 형식으로 두고 각각의 경우를 생각해보면,

작동하지 않는 경우

  • x가 1일 때 L이 나오면 작동하지 않는다.
  • x가 n일 때 R이 나오면 작동하지 않는다.
  • y가 1일 때, U이 나오면 작동하지 않는다.
  • y가 n일 때, D가 나오면 작동하지 않는다.

작동하는 경우

  • L이 나오면 x값이 -1
  • R이 나오면 x값이 +1
  • U가 나오면 y값이 -1
  • D이 나오면 y값이 +1
  • #예제 4-1 상하좌우 #공간 크기 입력 n = int(input()) #5 #이동할 계획서 내용이 주어진다.
#예제 4-1 상하좌우

#공간 크기 입력
n = int(input()) #5

#이동할 계획서 내용이 주어진다.
plan = list(map(str, input().split())) #R R R U D D

#현재 위치
location = [1,1]

for i in range(n):
    temp = plan[i]
    if (temp == 'L' and location[0] == 1) or (temp == 'R' and location[0] == n) or (temp == 'U' and location[1] == 1) or (temp == 'D' and location[1] ==n):
        continue
    else:
        if temp == 'L':
            location[0] -= 1
        elif temp == 'R':
            location[0] += 1
        elif temp == 'U':
            location[1] -= 1
        else:
            location[1] += 1

print(location[0],location[1])

현재 코드의 문제점 → for if , if문의 3중첩으로 되어있음!!

 

 

예제 4-2 시각

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오.

입력조건

첫째 줄에 정수 N이 입력된다. (0 ≤ N ≤ 23) → 5

출력조건

00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다. → 11475

아이디어 구상

일단 숫자를 어떤 유형으로 적용해볼 지 구상해야 한다.

  • 시간의 개념은 사용할 필요가 없다. (초가 60이 되면 분이 1분이 되는 것 같은)
  • 시(hour)가 3의 배수인 경우, 60*60의 경우의 수이므로 따로 생각하자
  • 시(hour)가 3의 배수가 아닌 경우, 분-초의 경우에서 3이 포함되는 개수를 적자
    • 이 경우, 생각할 수 있는 조합을 for문을 이중으로 중첩해서 ‘문자열을 합쳐서 생각하자.
  • if ‘3’ in ‘문자열’: 문장을 이용하면 쉬울 것 같다!

그리고, 전체를 for 문으로 설정해서 0~n시까지의 시간을 더하

# 예제 4-2 시각

# 다시
n = int(input())

a = 3600
b = 0
for m in range(60):
    m = str(m)
    for s in range(60):
        if s <= 9:
            s = str(s)
            s = '0' + s
        s = str(s)
        ms = m + s
        if '3' in ms:
            b += 1

count = 0
for i in range(n+1):
    if i%3 == 0 and i!=0:
        count += a
    else:
        count += b

print(count)

중첩을 최대한 완화!

 

 

왕실의 나이트

행복 왕국의 왕실 정원은 8*8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서 있고, 이동할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 이동할 수 있는 경우는 다음 2가지다.

  • 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
  • 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기

이처럼, 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오. 이때 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a부터 h로 표현한다.

예를 들어 만약 나이트가 a1에 있을 때 이동할 수 있는 경우의 수는 2가지다.

  • 오른쪽으로 두 칸 이동 후 아래로 한 칸 이동하기 (c2)
  • 아래로 두 칸 이동 후 오른쪽으로 한 칸 이동하기 (b3)

입력 조건

첫째 줄에 8*8 좌표평면 상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다. 입력문자는 a1처럼 열과 행으로 이루어진다.

출력 조건

첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력하시오

아이디어 구상

  • 일단 가능한 경우가 8가지이고, 만약 이동할 수 없는 경우가 생기면 8에서 차감하는 식으로 구성해보자.
  • 이동은 크게 두 가지로 구성된다. 처음 두 칸 이동 + 이동한 좌표가 아닌 반대 좌표가 -1 or +1
    • 처음 이동하는 경우, x가 +2, -2 / y가 +2, -2 될때 만약 수행되지 않으면 -2를 적용
      • 첫 이동을 마치고, 반대 좌표가 이동했을 때 수행되지 않으면 -1을 적용
  • 이동이 불가능한 경우는 다음과 같다.
    • 위로 움직일 때 행 위치가 1
    • 아래로 움직일 때 행 위치가 8
    • 왼쪽으로 움직일 때 열 위치가 a(1)
    • 오른쪽으로 움직일 때 열 위치가 h(8)
  • 고려해야할 변수!!
    • → 첫 이동은 2칸을 움직이기 때문에
    • 위로 움직일 때 행 위치가 1 or 2
    • 아래로 움직일 때 행 위치가 7 or 8
    • 왼쪽으로 움직일 때 열 위치가 1 or 2
    • 오른쪽으로 움직일 때 열 위치가 7 or 8
  • 열은 a~h까지 입력되며, 이 값들은 각각 1~8로 변환한 뒤 사용
  • 이번엔 이동할 수 있는 지 없는지를 나타내는 변수, isTrue를 만들어보
# 예제 4-2 시각

#입력
input_loc = input()
location = [int(input_loc[1]),input_loc[0]]
y_list = ['a','b','c','d','e','f','g','h']
location[1] = y_list.index(location[1]) + 1

#일단 그냥 쭉 적어보자
k = 8

#처음 위로 갈 때
if location[0] == 1 or location[0] == 2:
    k -= 2
else:
    if location[1] == 1 or location[1] ==8:
        k -= 1

#처음 아래로 갈 때
if location[0] == 7 or location[0] == 8:
    k -= 2
else:
    if location[1] == 1 or location[1] ==8:
        k -= 1

#처음 왼쪽으로 갈 때
if location[1] == 1 or location[1] == 2:
    k -= 2
else:
    if location[0] == 1 or location[0] ==8:
        k -= 1

#처음 오른쪽으로 갈 때
if location[1] == 7 or location[1] == 8:
    k -= 2
else:
    if location[0] == 1 or location[0] ==8:
        k -= 1

print(k)

if 문이 너무 많다..!

'REVIEW > CODING TEST' 카테고리의 다른 글

BFS/DFS 개념 정리  (0) 2023.06.30
그리디(Greedy) 개념 정리  (0) 2023.06.23
복잡도(Complexity) 개념 총 정리  (0) 2023.06.23
이코테 시작, 코테 개요  (0) 2023.06.23