파이썬 코딩 공부 - 구현

오늘은 지난 번에 공부했던 그리디 알고리즘 파트에 이어서 구현 파트를 리뷰해보고자 합니다. 이 책에서는 구현(implementation)에 대해서  '머릿 속에 있는 알고리즘을 소스코드로 바꾸는 과정'이라고 정의하였습니다. 사실 어떻게 보면 코딩 테스트의 모든 문제는 구현해야하기 때문에 좀 이상한 유형이다. 모든 코딩 테스트 문제에 해당하는걸 '유형' 이라고 부를 수는 없기 때문이다. 

 

그래서 본 교재에서는 이걸 인정하면서도 구현 유형의 문제에 대해서 이렇게 정의하였다. '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제' 라고 정의하였습니다. 그래서 완전 탐색 및 시뮬레이션 유형의 문제를 구현 유형으로 다루고 있습니다. 

 

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

 

c/c++ => 정수형을 표현할 때 int를 활용하나 int는 4바이트로 -2,147,483,648 ~ 2,147,438,647 의 범위에 대해서만 처리할 수 있다 이 이상은 long long을 활용하여야 한다. 8바이트인 long long은 제한이 존재하긴 하나 매우 큰 수/ 코딩 테스트에서 Biginteger와 같이 무한대까지 다루는데 필요한 클래스를 활용한 문제를 제출하지 않음 

 

파이썬 => 파이썬의 경우 이런 문제가 없음. 그러나 리스트가 커지면 메모리 용량에 제한이 생길 수 있어서 유의해야 한다. 

 

1) 상하좌우 문제 

 

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

계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀 있다. 각 문자의 의미는 다음과 같다.

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

이때 여행가 A가 N x N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 예를 들어(1,1)의 위치에서 L 혹은 U를 만나면 무시된다.

이 경우 6개의 명령에 따라서 여행가가 움직이게 되는 위치는 순서대로 (1, 2), (1, 3), (1, 4), (1, 4), (2, 4), (3, 4)이므로 최종적으로 여행가 A가 도착하게 되는 곳의 좌표는 (3, 4)이다.
다시말해 3행 4열의 위치에 해당하므로 (3, 4)라고 적는다. 계획서가 주어졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오

 

(1) 내 풀이 

LRUD = { 'L' : [0,-1],
         'R' : [0, 1],
         'U' : [-1,0],
         'D' : [1, 0]
        }

def list_add(a, b):
    return [ x + y for x, y in zip(a, b) ]
    
def shjw(n,path):
    now_wich = [1,1]
    for pt in path: 
        now_wich2 = list_add(now_wich, LRUD[pt])
        if now_wich2[0] > 0 and now_wich2[0] <=  n  and now_wich2[1] <= n and now_wich2[1] > 0:
            now_wich = now_wich2
            print(now_wich)
    return now_wich[0], now_wich2[1]
    
n = int(input())
path = input().split()

print(shjw(n, path))

 

(2) 정답 풀이 

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

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]
            nu = y + dy[i]
         if nx < 1 or ny < 1 or nx > n or ny > n:
         	continue
         x, y = nx , ny
         
 print(x, y)

 

두 코드 모두 이동 계획의 개수 m에 비례하는 O(m) 시간이 걸립니다. 다만 상수 계수(constant factor) 차이가 있어, 실제로는 첫 번째 코드가 약간 더 효율적입니다:

1. 첫 번째 코드 (dict+zip)
   • 매 스텝마다
     • 한 번의 해시 조회(LRUD[pt])
     • zip(a,b)를 돌며 길이 2의 리스트 컴프리헨션
     • 네 번의 정수 비교
   • 총합: 해시 조회 1회 + 리스트 생성 1회 + 비교 4회
2. 두 번째 코드 (이중 루프)
   • 매 스텝마다
     • 4번의 문자 비교(plan == move_types[i])
     • 일치할 때 한 번의 리스트 인덱스 접근(dx[i], dy[i])
     • 네 번의 정수 비교
   • 총합: 비교 4회 + 인덱스 접근 2회 + 비교 4회

비교만 놓고 보면 두 번째 코드도 “비교 4회 → 비교 4회”로 비교 연산 8회지만, 첫 번째는 “해시 조회 1회 + 리스트 컴프리헨션(내부 두 덧셈) + 비교 4회”로, 전체 연산 횟수가 더 적습니다.
또:

• 첫 번째는 “키→값” 매핑이 직관적이고, 리스트 컴프리헨션 혹은 zip을 쓰면 곧바로 좌표 덧셈을 표현할 수 있어 가독성도 좋습니다.
• 두 번째는 “이중 루프” 구조라 약간冗長(장황)하고, break를 빠뜨리면 불필요한 비교를 더 하게 되기 쉬워 버그 위험이 있습니다.

(3) GPT의 추천 

moves = {
  'L': (0, -1),
  'R': (0,  1),
  'U': (-1, 0),
  'D': (1,  0),
}

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

for p in plans:
    dx, dy = moves[p]
    nx, ny = x + dx, y + dy
    if 1 <= nx <= n and 1 <= ny <= n:
        x, y = nx, ny

print(x, y)

 

2. 시각 

 

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다.

• 00시 00분 03초
• 00시 13분 00초

반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각이다.

• 00시 02분 55초
• 01시 27분 45초

입력조건

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

출력조건 

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

 

(1) 내풀이 및 정답 풀이 

def count_time_3(n):
    count = 0
    for i in range(n+1):
        for j in range(60):
            for k in range(60):
                if '3' in str(i) + str(j) + str(k):
                    count += 1
    return count

n = int(input())
print(count_time_3(n))

 

일단 굉장히 간단하게 작성을 했지만 반복문을 세번이나 썼습니다. 이것보다 더 효율적인 방법이 있을 것 같습니다. 그래서 한 번 gpt한테 물어봤습니다.  이 때 조합론을 활용할 경우 조금 더 효율적인 연산이 가능하다고 합니다. => O(N)

 

n = int(input())

# 1) '3'이 없는 시(hour) 개수 계산
h_no3 = sum(1 for h in range(n+1) if '3' not in str(h))

# 2) 분·초 각각 '3' 없는 조합 수
m_s_no3 = 5 * 9  # tens 자리(0~5 중 3제외=5) × ones 자리(0~9 중 3제외=9)

# 3) 전체 – 전혀 3 없는 경우
total = (n+1) * 60 * 60
no3   = h_no3 * m_s_no3 * m_s_no3

print(total - no3)