목차
- 서론
- 구현 (implementation)
- 예시
- 구현 문제를 풀 때 유의해야 할 점
- 구현 문제 해결 팁
- 레퍼런스
서론
블로그 챌린지를 시작하고 나서는 알고리즘 관련 문제를 풀고 포스팅을 하는 식으로 조금씩 공부를 했지만 요즘들어 PS 공부에 많이 해이해진 느낌이 들었다.
그래서 알고리즘의 각 카테고리별로 알아보면서 관련 문제도 풀어보는 시간을 가지려 한다.
구현 (implementation)
구현 알고리즘은 딱히 정형화 된 알고리즘이 아니라 머릿속에 있는 알고리즘을 코드로 바꾸는 과정을 말한다.
사실 거의 모든 알고리즘 문제가 단순 ‘구현’이나 특정 알고리즘을 ‘구현’해서 푸는 문제이기 때문에 좀 포괄적인 개념이라고 할 수 있다.
그럼에도 구별해둔 것은 단순 구현 만으로 어려운 문제들이 있기 때문이다. (소위 빡구현 문제라고 한다)
예시
- 단순 연산문제, 수학문제
- 문자열을 다루는 문제
- 적절한 라이브러리를 사용하는 문제
- 알고리즘은 간단하지만 소스 코드가 길어지는 문제
단순 연산문제는 아주 기본적인 A+B 문제부터
a, b = map(int, input().split())
print(a+b)최소공배수와 같은 수학 문제가 있다.
import math
for i in range(int(input())):
a,b = map(int, input().split())
print((a*b)//math.gcd(max(a,b),min(a,b)))문자열을 다루는 문제는 단순하게는 별 찍기 문제 (아래와 같은 유형이 코드 길이는 적지만 빡구현 문제라고 봐도 될 것 같다..)
N = int(input())
for i in range(N, 0, -1):
for j in range(N-i):
print(" ", end="")
for j in range(2*i - 1):
print("*", end='')
print()
for i in range(2, N+1):
for j in range(N-i):
print(" ", end="")
for j in range(2*i - 1):
print("*", end="")
print()다양한 조건들이 존재하는 문자열 문제등이 있다.
N, M = map(int,input().split())
voca = {}
for _ in range(N):
word = input().rstrip()
if len(word) < M:
continue
else:
if word in voca:
voca[word] += 1
else:
voca[word] = 1
for key, value in sorted(voca.items(), key = lambda x : (-x[1], -len(x[0]), x[0])):
print(key)적절한 라이브러리를 사용하는 문제로는 자료구조 문제중 하나인 최대 힙 문제가 있다.
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
N = int(input())
max_heap = []
for i in range(N):
num = int(input())
if num != 0:
heappush(max_heap, (-num, num))
else:
try:
print(heappop(max_heap)[1])
except IndexError:
print(0)구현 문제를 풀 때 유의해야 할 점
파이썬을 사용한다면 자바나 C와 같은 언어와 달리 자료형에 대해 깊게 생각하지 않아도 된다.
모든 알고리즘 문제에 해당하는 것이지만 메모리 제한과 시간 제한에 신경 써야 한다.
간단한 문제라면 조금 코드를 비효율적으로 짠다해도 시간과 메모리에는 걸리지 않겠지만, 조금 난이도가 올라가면 파이썬으로는 시간초과가 뜰 수가 있다.
구현 문제 해결 팁
사실 구현 문제는 많이 풀어볼 수 밖에 없다고 한다.
그럼에도 소소하게 팁이 있다고 한다면,
- 입출력 간소화
알고리즘의 시간 복잡도를 개선하거나, sys.stdin.readline() 와 sys.stdout.write() 같은 빠른 입출력 처리 방식을 써서 I/O에 성능을 높이는 방법이 있다.
- 미리 계획하고 작성하기
사소한 조건들이 많아서 코드가 길어지는 경우 조건문과 예외 처리가 많아서 코드가 길어질 수 있다. 조건이 여러 개면서 서로 중복되는 케이스가 있다면 헷갈릴 수 있기 때문에 충분히 설계를 해놓고 코드 구조를 깔끔하게 만들고 시작하는 것이 좋다.
- 딕셔너리 활용
빠른 탐색을 위해 O(1)로 탐색이 가능한 딕셔너리 객체를 사용하는 것도 방법이다.
- 방향 처리를 간단하게
2차원 맵을 탐색하는 문제같은 경우 이동에 필요한 코드를 작성할 때가 많다.
그럴 때는 dx, dy 리스트를 활용하면 깔끔하게 처리할 수 있다.
# 오른쪽 부터 시계방향
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < N and 0 <= ny < M:
...