구현 알고리즘

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

• 피지컬로 승부하기 ⇒ 프로그래밍 언어의 문법에 능숙하고 코드 작성 속도가 빠른 사람
• 구현 : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
• 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념
• 라이브러리 사용 경험을 익숙하게 하자

📝 알고리즘을 풀 때 과정

1. 생각해낸 문제 풀이 방법을 우리가 원하는 프로그래밍 언어로 정확히 구현
2. 프로그래밍 언어의 문법을 정확히 알고 있어야 함

📝 문제 해결 분야에서 구현 유형의 문제란?

1. 풀이를 떠올리는 것은 쉬우나 소스코드로는 옮기기 어려운 문제
2. 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
3. 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
4. 적절한 라이브러리를 찾아서 사용해야 하는 문제

📝 구현의 유형

1. 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결방법
2. 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례로 직접 수행
   ⇒ 방향 벡터가 자주 활용

📝행렬

• 2차원 공간(반복적으로 캐릭터 이동 문제)
• 열과 행이 있음

(0, 0)(0,1)(0, 2)(0, 3)

(1, 0)	(1, 1)	(1, 2)	(1, 3)
(2, 0)	(2, 1)	(2, 2)	(2, 3)

for i in range(5):
    for j in range(5):
        print('(', i, ',', j ')', end=' ')
print()

# 동 북 서 남
dx = [0, -1, 0, 1] # 세로축 기준으로
dy = [1, 0, -1, 0]

# 현재 위치
x, y =1, 2

for i in range(4):
    # 다음 위치
    nx = x + dx[i]
    ny = y + dy[i]
    print(nx, ny) 

부가설명 : 동쪽으로 내려가면 열은 증가하지 않고 행은 증가함

EX. (1, 0) → (2, 0)

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

1. C/C++에서 변수의 표현 범위
- 정수형 int(4바이트) < int보다 큰 long long(8바이트) < BigInteger(클래스)
: 가변적이며, 자료형의 범위는 제한 없음
- 하지만 c++의 경우 표준 라이브러리에 포함되어 있지 않기 때문에 외부 라이브러리 형태를 가져와 사용

2. 파이썬
- 프로그래머가 직접 자료형 지정할 필요 없음, 매우 큰 수의 연산 또한 기본으로 지원
- 정수형 변수의 연산 때문에 고민 No!
- but, 실수형 변수는 다른 언어와 마찬가지로 유효숫자에 따라서 연산 결과가 원하는 값이 나오지 않을 수 있음

1. 파이썬에서 리스트의 고려사항✨
   1. 파이썬에서는 여러 개의 변수 사용시 리스트 이용
   2. 메모리 사항 고려
      • 코딩테스트에서 128~512MB로 메모리 제한 염두에 두고 풀어야 함
      • 크기가 1,000만 이상 리스트가 있다면, 메모리 용량 제한으로 풀지 못함
      • int 자료형 데이터의 개수에 따른 메모리 사용량
      데이터의 개수(리스트의 길이)메모리 사용량

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

📚 채점 환경

• 시간 제한 : 1초
• 메모리 제한 : 128MB ⇒ 파이썬의 경우 1초에 2,000만번의 연산 수행 가능한 것만 알면 됨
• 시간 제한 : 1초, 데이터의 개수 : 100만개 ⇒ 시간 복잡도 O(NlogN) 이내의 알고리즘 이용해서 문제를 풀어야 함

💡 TIP) 알고리즘 문제를 풀 때는 시간 제한과 데이터의 개수를 먼저 확인 한 뒤, 이 문제를 어느 정도의 시간복잡도의 알고리즘으로 작성해야 풀 수 있을 것인지 예측

📚 구현 문제에 접근하는 방법

• 사소한 입력 조건 등 문제에서 명시해주며, 문제의 길이 큰 편
• 파이썬으로 알고리즘을 풀 시 좋은 점 다른 언어와 비교

구현 난이도프로그램 실행 시간

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

• 파이썬으로 프로그램을 개발시, 그래픽 처리 장치(GPU)를 연동하며, 반복적인 행렬 계산을 요구하는 복잡한 수학 문제시 C언어로 작성된 파이썬 코어 소프트웨어 동작
• BUT, 알고리즘 환경에서는 GPU 연산 쓰는 경우가 없음
• 자동 채점방식 코딩 테스트 환경에서는 PyPy3를 지원하는 곳이 증가 ⇒ PyPy3란 파이썬 3의 문법을 그대로 지원, 파이썬3보다 실행 속도가 빠르다
• 파이썬 이용시 API 개발 문제를 보더라도 상대적으로 무난하게 대처 가능

예제 4-1 상하좌우

• 문제 p.110
• 여행자 A는 N*N 크기의 정사각형 공간 위 서 있음
• 가장 왼쪽 위 좌표 (1,1), 가장 오른쪽 아래 좌표(N, N)
• 시작 좌표는 항상 (1,1) 상,하,좌,우 이동 가능
• 계획서 : 하나의 줄에 띄어쓰기 기준으로 L,R,U,D 중 하나의 문자가 반복적으로 적혀 있음
• L : 왼쪽으로 한 칸 이동, R : 오른쪽으로 한 칸 이동, U : 위로 한 칸 이동, D : 아래로 한 칸 이동
  • N*N 크기의 정사각형 공간을 벗어나는 움직임은 무시
  • 계획서가 주어졌을 때 여행자 A가 최종적으로 도착할 지점의 좌표

❓ 입력조건
- 첫째 줄 공간의 크기를 나타내는 N이 주어진다$(1\leq N  \leq 100)$
- 둘째 줄에 여행자 A가 이동할 계획서 내용이 주어진다 ($1 \leq 이동횟수 \leq 100)$

❓ 출력조건
- 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표(X,Y)를 공백으로 구분하여 출력

👌 문제 해결

• 시간 복잡도 : O(N) 시간 복잡도가 넉넉한 편
• 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점 : 시뮬레이션 유형
• 참고 for문
  - 파이썬에서 for문은 들여쓰기가 중요
  - for[변수1] in [문자열1, 리스트1, 튜플1]:
• arr = [1, 2, 3, 4, 5] for i in arr: print(i)

# N을 입력받기
n = int(input())
x, y = 1, 1 # 현재 위치
plans = input().split()

# L,R,U,D 방향에 따른 이동 이동, **방향 벡터**
dx = [0,0,-1,1] # x좌표는 좌우
dy = [-1,1,0,0] # y좌표는 위아래
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 ny<1 or nx>n or ny>n:
            countinue # 중간에 멈추고 처음으로 돌아가자
        # 이동 수행
        x, y = nx, ny

print(x, y)

⇒ 입력받을 게 무엇인지 생각해보고 차례로 수행해 나가기

📝 예제 4-2 시각

---

• 문제 p.113
  • 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중 3이 하나라도 포함되는 모든 경우의 수 구하기❓ 입력조건
  • 첫째 줄에 정수 N이 입력된다(0≤N≤23)❓ 출력조건
  • 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중 3이 하나라도 포함되는 모든 경우의 수 구하기

👌 문제해결

• 모든 시각의 경우를 하나씩 모두 셈
• 모든 경우의 수가 100,000개가 안되기 때문에 문자열 연산 이용해도 시간 제한 2초안에 문제 해결 가능
• 단순히 시각을 1씩 증가시키면서 확인 ⇒ 완전 탐색 유형(비효율적이라 데이터 개수가 큰 경우 작동 안할 수 있음)
• 경우의 수 24(시간)60(분)60(초) ⇒ 3중 반복문 이용
• 문자열로 바꿔서 확인 ⇒ EX. 03시20분23초라면 ‘032023’로 만들어서 확인
• 참고 str 파이썬 문자열 변환 - str()

# H를 입력받기
h = int(input())

count = 0

# h부터 1씩 증가
for i in range(h + 1): 
    for j in range(60): # 입력받는 것은 시간 뿐이기 때문에 분, 초는 0부터 60까지로 **범위 설정 및 증가 하게**
        for k in range(60):
        # 매 시각 안에 3이 포함되어 있다면 카운트 증가
            if '3' in str(i) + str(j) + str(k): # 시각을 **문자열 바꾼 다음** 문자열에 '3'이 포함됐는지 확인
                count+=1

print(count)

📚 실전문제 왕실의 나이트

• 문제 p.115
• 왕실 정원 8*8 좌표 평면
• 나이트는 말을 타고 있기에 이동시, L자 형태로만 이동 가능, 정원 밖으로 이동 불가
  1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동
  2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동

❓ 입력조건

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

❓ 출력조건

- 첫째 줄에 나이트가 이동할 수 있는 경우의 수 출력

👌 문제해결

• 나이트가 이동할 수 있는 경로를 하나씩 확인하여 이동
• 다만, 8*8평면을 벗어나지 않도록 꼼꼼히 검사
• 나이트 이동 경로를 steps 변수에 넣는다면

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

• <코드>

# 현재 나이트 위치 받기
input_data = input()
# 두 번째 위치의 숫자를 바꾼 것이 행
row = int(input_data[1])
# 문자로 들어온 값을 아스키 코드로 바꾸고 
column = int(ord(input_data[0]))-int(ord('a')) + 1

# 나이트가 이동할 수 있는 8가지 뱡향 정의, dx, dy사용해도 가능
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)