아이디어를 코드로 바꾸는 구현
머리 속에 있는 알고리즘을 소스코드로 바꾸는 과정
구현 유형의 문제는 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 의미
피지컬을 요구하는 문제
구현하기 어려운 문제
- 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
- 특정 소수점 자리까지 출력해야 하는 문제
- 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱을 해야 하는) 문제
완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형
구현 시 고려해야 할 메모리 제약 사항
- C/C++에서 변수의 표현 범위 제약 → 파이썬에서는 프로그래머가 직접 자료형을 저장할 필요가 없으며 매우 큰 수의 연산 또한 기본으로 지원
- 파이썬에서 리스트 크기 제약 → 메모리 사용량 제한보다 더 적은 크기의 메모리를 사용해야 한다는 점 정도만 기억, 복잡한 최적화를 요구하지 않는 것이 일반적
채점 환경
보통 1초의 시간 제한, 128MB의 메모리 제한
파이썬으로 제출한 코드가 1초에 2000만 번의 연산을 수행한다고 가정하면 무리 없음
데이터의 개수가 100만 개인 문제가 있다면 일반적으로 시간 복잡도 O(NlogN) 이내의 알고리즘을 이용하여 문제를 풀어야 함
알고리즘 문제를 풀 때는 시간 제한과 데이터의 개수를 먼저 확인한 뒤에 이 문제를 어느 정도의 시간 복잡도의 알고리즘으로 작성해야 풀 수 있을 것인지 예측해야 함
구현 문제에 접근하는 방법
구현 유형의 문제는 문자열을 처리하거나 큰 정수를 처리하는 문제가 출제되는 경우가 많아서 파이썬으로 문제를 푸는 경우 유리하다.
- 예제 4-1 상하좌우
이 문제의 연산 횟수는 이동 횟수에 비례함
시간 복잡도 O(N) - 넉넉한 편
이러한 문제는 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션 유형으로 분류되며 구현이 중요한 대표적인 문제 유형
시뮬레이션 유형, 구현 유형, 완전 탐색 유형은 서로 유사한 점이 많음n = int(input()) plans = input().split() x, y = 1, 1 # L, R, U, D에 따른 이동 방향 dx = [0, 0, -1, 1] dy = [-1, 1, 0, 0] move = ['L', 'R', 'U', 'D'] # 이동 계획을 하나씩 확인 for plan in plans: # 이동 후 좌표 구하기 for i in range(len(move)): if plan == move[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)
- 예제 4-2 시각
이 문제는 모든 시각의 경우를 하나씩 모두 세서 쉽게 풀 수 있는 문제
00시 00분 00초부터 23시 59분 59초까지의 모든 경우는 86,400가지밖에 존재하지 않기 때문
시각을 1씩 증가시키면서 3이 하나라도 포함되어 있는지 확인 - 3중 반복문완전 탐색(Brute Forcing) 유형
완전 탐색 알고리즘은 가능한 경우의 수를 모두 검사해보는 탐색 방법
구현이 중요한 대표적인 문제 유형인데, 비효율적인 시간 복잡도를 가지고 있으므로 데이터 개수가 큰 경우 정상적으로 동작하지 않을 수 있음
일반적으로 탐색해야 할 전체 데이터의 수가 100만 개 이하일 때 완전 탐색 사용하는 것이 적절# H를 입력받기 h = int(input()) count = 0 for i in range(h + 1): for j in range(60): for k in range(60): # 매 시각 안에 '3'이 포함되어 있다면 카운트 증가 if '3' in str(i) + str(j) + str(k): count += 1 print(count)
