구현 문제

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

• 풀이를 떠올리긴 쉽지만 소스코드로 옮기기 어려운 문제
  1. 알고리즘은 간단하지만 코드가 길어지는 문제
  2. 파싱 문제 등 사소한 조건이 많은 문제
• 구현의 유형
  1. 완전 탐색: 모든 경우의 수를 주저없이 다 계산하는 방식
  2. 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형

구현 시 메모리 제약 사항

C/C++에서 변수의 표현 범위

• int자료형은 4바이트로 표현 범위는 -2,147,483,648~2,147,438,647
• int의 표현 범위보다 더 큰수는 크기가 8바이트인 long long 자료형으로 이용 (9,223,372,036,854,775,807까지 표현)
• long long보다 더 큰 수는 BigInteger 이용

파이썬에서 리스트 크기

• 코딩 테스트의 메모리 제한 주의
• 1000개당 4KB정도의 메모리 사용량
• 크기가 1000만 이상인 리스트는 문제를 풀 수 없게 되는 경우가 있다.

구현 문제 접근법

• 사소한 입력 조건 드을 문제에서 명시해주며 문제의 길이가 긴 경우가 많다.
• 고차원적 사고력을 요구하는 문제는 나우지 않는다.
• C/C++이나 자바로 풀면 어렵게 느껴질 수 있다.

에시 문제

1. 상하좌우 문제

여행가 A가 N*N 크기의 정사각형 공간 위에 서있다. 이 공간은 1*1 크기의 정사각형으로 나누어져있다. 여행가는 상하좌우 방향으로 이동할 수 있으며 시작 좌표는 가장 왼쪽 위 좌표인 (1, 1)이다. 여행가에겐 L. R, U, D가 적힌 계획서가 주어지고 계획서대로 움직인다. 지도를 정사각형 공간을 벗어나는 명령은 무시한다. 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.

• 입력: 공간의 크기를 나타내는 N, 계획서의 내용

• 출력: 도착 좌표

    n = int(input())
    plans = input().split()
    x, y = 1, 1
  
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]
    move_type = ['L', 'R', 'U', 'D']
  
    for plan in plans:
        for i in range(len(move_type)):
            if plan == move_type[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)
  

2. 시각

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

• 입력: 정수 N

• 출력 모든 경우의 수(횟수)

• 완전 탐색으로 푸는 것이 효율적
  – 탐색해야할 전체 데이터 개수가 100만개 이하일 경우 사용

    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)