KEEP GOING!

파이썬은 학부 강의 때 이후 따로 잘 사용하지 않았던 언어였는데, 코드가 간결하고 내부적으로 지원해 주는 기능이 많아 알고리즘 언어로 파이썬을 선택했다. 알고리즘 문제를 풀면서 알게 된 유용한 문법들이 필요한 곳에서는 기억나지 않거나 아예 있는지도 몰라 사용하지 못할 때도 있고, 심지어 가끔은 기본 사용 문법도 헷갈려서 엄한 데 시간을 쏟기도 했다. 이런 문제를 해결하고자 이 포스팅은 알고리즘을 위한 파이썬 문법 정리 노트로 사용하려고 한다. 그렇기 때문에 앞으로 새롭게 알게 된 문법을 계속해서 업데이트 해 나갈 예정이다. List 사용법 [기본 문법] # 생성 a = list() a = [] # 추가 & 삭제 a.append(3) a.remove(3) # 배열 뒤에 합치기 a.extend([5, 10,..

이번 포스팅에서는 알고리즘을 공부하면서 출제 빈도가 높은 BFS와 DFS 문제를 위한 기본 구현을 정리하려고 한다. BFS와 DFS는 이름에서부터 알 수 있듯 그래프 탐색 알고리즘이다. 탐색 알고리즘은 그래프 전체를 순회해야 하는 고비용 연산으로 효율적으로 코드를 짜는 것이 중요하다. BFS와 DFS 모두 시간 복잡도는 동일하다. 그래프는 인접 행렬과 인접 리스트 자료구조를 이용해 표현이 가능한데, 어떤 자료구조를 사용하느냐에 따라 시간 복잡도가 아래와 같이 달라진다. (V = Vertex, E = Edge) 인접 행렬: O(V^2) 인접 리스트: O(V+E) 최소 비용 문제나 이동에 가중치가 없는 미로탐색 문제는 BFS로 푸는 것이 유리하고, 이동에 제약이 있거나 이동마다 가중치가 붙는 미로탐색 문제는..