구현

구현

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

코딩테스트에 자주 출제됨, 완전 탐색과 시뮬레이션 유형을 같이 공부함

완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 방법을 말하고,

시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형을 말한다.

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

파이썬에서는 리스트 크기를 고려해야 한다.

대체로 코딩 테스트에서는 128~51MB로 메모리를 제한하는데 알고리즘 문제 중 때로는 수백만 개 이상의 데이터를 처리해야 하는 문제가 출제되곤 한다.

 

int 자료형 데이터의 개수에 따른 메모리 사용량

데이터의 개수 (리스트의 길이) 메모리 사용량

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

리스트 크기가 1,000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없게 되는 경우도 있지만 드물다. 일반적인 코딩 테스트 수준에서는 메모리 사용양 제한보다 더 적은 크기의 메모리를 사용하려고 해야함

구현 문제에 접근하는 방법

문제의 길이가 꽤 긴편이나 , 고차원적인 사고력을 요구하는 문제는 나오지 않는 편이라 문법에 익숙하면 쉽게 풀 수 있다.

---

예제 4-1 상하좌우

문제

여행가 A는 NN 크기의 정사각형 공간 위에 서 있다. 이 공간은 11 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1,1)이며 가장 오른쪽 아래 좌표는 (N,N)에 해당한다. 여행가 A는 상,하,좌,우 방향으로 이동할 수 잇으며 시작 좌표는 항상 (1,1)이다. 명령대로 움직였을 때 도착할 지점의 좌표를 출력하시오

 

나의 답안

1. N 크기를 입력 받는다.
2. 시작점 위치를 (1,1)로 세팅해야 한다
3. 현재 좌표를 나타낼 변수를 정함
4. 방향대로 좌표를 이동한다dx = [-1,+1,0,0]     ,    만약 이동한 좌표가 1보다 작으면 무시한다
5. dy = [0,0,-1,+1]
6. 방향 = [왼쪽,오른쪽,위,아래]

n = int(input())
plan = list(map(str,input().split()))
# 현재 위치
x=1
y=1

#방향 = [왼쪽,오른쪽,위,아래]
dx = [-1,+1,0,0]
dy = [0,0,-1,+1]
ind = -1

for p in plan:
    if p == "L":
        ind = 0
    elif p == "R":
        ind = 1
    elif p == "U":
        ind = 2
    else:
        ind = 3
    px = x + dx[ind]
    py = y + dy[ind]
    if px < 1 or py <1 or px>n or py>n:
        continue
    x = px
    y= py

print(py,px)

---

ㅇㅖ제 4-2 시각

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

정답

N = int(input())
count = 0
for h in range(N+1):
    for m in range(60):
        for s in range(60):
            if '3' in str(h)+str(m)+str(s) :
                count +=1

print(count)

 

 

 

예제 4-3 왕실의 나이트

8*8 좌표 평면 체스판에서 나이트의 이동 경로를 구하라

p = input()
row = int(p[1])
col = int(ord(p[0])) - int(ord('a'))+1

steps = [(-2,-1),(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1)]

result = 0
for step in steps:
    next_row = row +step[0]
    next_col = col+step[1]
    if next_row >= 1 and next_col <= 8 and next_col >=1 and next_col <= 8:
        result +=1
print(result)