KEEP GOING!

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

프로그래머스 3xn 타일링의 문제 설명은 여기서 볼 수 있고 풀어볼 수도 있다. 이전에 2xn 타일링 문제를 풀어봤기 때문에 3n 타일링 문제에 도전해보았다. 원리는 비슷하고 조금 응용하면 되겠지.. 하고 쉽게 생각했지만 생각보다 그 응용이 쉽지 않았다.. 3xn 타일링도 2xn 타일링과 마찬가지로 DP로 풀 수 있는 문제였다. 문제 풀이를 시작하면, n이 홀수일 경우에는 크기가 2인 타일을 채울 수 없기 때문에 n이 짝수인 경우만 생각한다. 먼저 n=2인 경우 3가지 경우의 타일 모양이 나오고, 그 다음 단계로 진행할 때마다 아래와 같이 매번 2개씩 새로운 모양의 타일이 생긴다. f(n) = 가로의 길이가 n인 타일을 채울 수 있는 경우의 수 라고 하자. n = 4일 때는 이전 단계(n=2)에서 2칸이..

프로그래머스 카드게임은 DP로 분류된 문제로, 설명은 여기서 볼 수 있고 풀어볼 수도 있다. DP를 풀어본지 오래 돼서 풀어보려고 했으나 아이디어가 떠오르지 않아서 정답을 올려놓은 블로그 글을 참고했다. 그랬더니 DP를 푸는 방법에 대해 설명하는걸 보고 다시 DP에 공부했던 기억이 새록새록 떠올랐다. 다시 알게 된 김에 아래 3가지 방법 모두 구현해 보았다. Top-Down: 큰 문제들을 풀 때 작은 문제가 아직 풀리지 않았다면 작은 문제를 먼저 푸는 방식 ex) 재귀함수, Memoization Bottom-Up: 작은 문제부터 차근차근 풀어나가는 방식 이 문제의 기본 아이디어는 다음과 같다. i) 왼쪽 카드가 오른쪽 카드보다 크면, 오른쪽 카드를 버리고 점수를 높인다. ii) 그렇지 않으면, 왼쪽만 버..

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