📚 아이디어를 코드로 바꾸는 구현
- 피지컬로 승부하기
⇒ 프로그래밍 언어의 문법에 능숙하고 코드 작성 속도가 빠른 사람- 구현 : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
- 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념
- 라이브러리 사용 경험을 익숙하게 하자
📝 알고리즘을 풀 때 과정
- 생각해낸 문제 풀이 방법을 우리가 원하는 프로그래밍 언어로 정확히 구현
- 프로그래밍 언어의 문법을 정확히 알고 있어야 함
📝 문제 해결 분야에서 구현 유형의 문제란?
- 풀이를 떠올리는 것은 쉬우나 소스코드로는 옮기기 어려운 문제
- 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
- 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
- 적절한 라이브러리를 찾아서 사용해야 하는 문제
📝 구현의 유형
- 완전 탐색 :
모든 경우의 수를 주저 없이 다 계산하는 해결방법 - 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩
차례로직접 수행
⇒ 방향 벡터가 자주 활용
📝행렬
- 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, 실수형 변수는 다른 언어와 마찬가지로 유효숫자에 따라서 연산 결과가 원하는 값이 나오지 않을 수 있음
- 파이썬에서
리스트의 고려사항✨-
파이썬에서는 여러 개의 변수 사용시 리스트 이용
-
메모리 사항 고려
- 코딩테스트에서 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이 입력된다
❓ 출력조건 -
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자 형태로만 이동 가능, 정원 밖으로 이동 불가
- 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동
- 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동
❓ 입력조건
- 첫째 줄에 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) 
내 지식을 기록하여, 다른 사람들과 공유하여 함께 발전하는 사람이 되고 싶다. gitbook에도 정리중 ~