알고리즘

Problem) 간단한 문자열 문제입니다. 코딩 문제로 문자열과 정규식 관련 문제를 은근히 자주 마주칠 수 있는데요. 이번 문제를 통해서 다시 한번 문자열 관련 다양한 처리 방법들에 대해서 정리해보면 좋을 것 같네요. Solution) # 문자열 활용 솔류션 class Solution: def isPalindrome(self, s: str) -> bool: strs = [] for char in s: if char.isalnum(): strs.append(char.lower()) while len(strs) > 1: if strs.pop(0) != strs.pop(): return False return True # 정규식 활용 솔류션 import re class Solution: def isPalind..

solution for Container With Most Water Problem) Solution) 2개의 포인터를 활용해서 시간 복잡도 O(n)에 끝낼 수 있다. max_water 변수에는 각 단계별 최대 물의 양을 저장한다. x, y 포인터 초기화하고 각각 x는 시작점, y는 끝점에 위치하고 하나씩 옮기며 최대 물의 양을 계산하고 max_water의 값과 비교하여 최종 최대 물의 양 값을 얻는다. 이때 포인터를 옮기는 과정에서 x, y 포인터가 가르키는 막대의 길이를 비교하여 길이가 짧은 막대의 포인터를 x는 +1, y는 -1로 한칸씩 옮겨야 한다. Example의 예를 들면 최초 x는 0 (height[0] = 1)을 가르키고 y는 8 (height[8] = 7)을 가르킨다. 여기서 물의 양을 ..

solution for Two City Scheduling Problem) Solution) 문제에서 각 cost간의 차이 값을 구했을 때, 차이 값이 작으면 A 도시로 차이값이 크면 B 도시로 가는 것이 비용상 더 효율적이다. 즉 문제에서 제공한 예제에 적용해서 4명의 각 비용의 차이 값을 계산하면 [-10, -170, 350, 10]이 되고 이를 오름차순으로 정렬하면 [-170, -10, 10, 350]이 된다. 여기서 우리는 정렬된 리스트를 기준으로 좌측에서 A로 우측에서 B로 한명씩 보내게되면 최소 비용으로 모든 사람들을 A, B 도시로 반반씩 보낼 수 있게 된다. 특별한 알고리즘에 대한 지식보다는 문제에 대한 이해와 해석 능력이 필요한 문제인 것 같다. class Solution: def two..

solution for Invert Binary Tree Problem) Invert a binary tree. Example) Solution) class Solution: def invertTree(self, root: TreeNode) -> TreeNode: if root: root.left, root.right = self.invertTree(root.right), self.invertTree(root.left) return root else: return None Reference) Recursion (Recursive Function)

프로그래밍에 자주 사용되는 대표적인 자료구조에는 "그래프"가 있습니다. 오늘 포스팅에서는 그래프를 탐색하는 알고리즘 2가지 DFS와 BFS에 대해서 알아보도록 하겠습니다. 그래프는 정점과 간선으로 이루어져 있는데 간선을 통해서 모든 정점을 방문하는 것을 그래프를 탐색한다고 합니다. 위에서 언급했듯이 그래프 탐색 알고리즘에는 대표적으로 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)가 있습니다. 각각의 알고리즘에 대해서 자세히 알아보도록 하겠습니다. 위 그림을 보시면 두 알고리즘의 차이에 대해서 직관적으로 이해하실 수 있습니다. 각 알고리즘의 명칭에서도 볼 수 있듯이 깊이(자식)를 우선으로 탐색하느냐 아니면 너비(형제)를 우선으로 탐색하느냐의 차이가 있습니다. 1. 깊이 우선 탐색깊이 우선 탐색 (De..