JW's dev blog

오늘 풀어볼 문제는 Anagram끼리 묶는 문제다. 여기서 Anagram이란 단어의 문자열은 같지만 순서는 다른 것들을 말한다. 예를 들면 "eat"과 "tea"는 모두 a, e, t 로 이루어진 단어지만 순서는 다르다. Leetcode에서 문제보기 솔루션 1. 내가 처음 생각해낸 코드는 아래와 같았다. 우선 모든 단어를 돌며 정렬한 후 anagram이 존재하면 그 array에 넣어주고 없으면 result에 새로운 배열을 추가한다. 즉 ["eat", "tea", "hi", "hello", "ate"]가 있다고 했을 때 "eat"를 정렬하면 "aet"이다. anagrams에 존재하지 않는다. 추가해준다. anagrams = ["aet"] result = [["eat"]] "tea"를 정렬하면 "aet"다...

이미 정렬된 두 개의 배열을 병합하는 문제를 풀어보자. Leetcode에서 문제보기 Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6] 문제에서는 정렬된 두 배열 nums1, nums2 그리고 각 배열의 길이인 m과 n이 주어진다. nums1의 길이는 m+n이다. 이 문제는 기존 병합 정렬 코드보다 더 간단하다. (병합 정렬에 대해 알아보기 : https://jwdevv.tistory.com/3) [알고리즘, Python] 정렬 1 - 병합 정렬(Merge Sort) 정렬은 크게 다섯가지로 나눌 수 있다: 버블정렬, 선택정렬, 병합정렬, 퀵정렬, 기수정렬(Radix Sort) 그 중 버블정렬과 선택정렬은 메모리..

트리 (Tree)란? 트리는 노드로 구성된 자료구조이다. - 트리는 루트노드(root node)를 가진다. - 루트노드는 0개 이상의 자식노드(child nodes)를 가진다. - 각 자식노드 또한 0개 이상의 자식노드를 가진다. - 트리는 cycle을 가질 수 없다. - 노드는 특정한 순서로 있을수도 없을수도 있다. - 노드는 어떤 데이터 타입도 값으로 가질 수 있다. - 노드는 부모 노드로 가는 링크를 가지고 있을수도 없을수도 있다. Node 예시 class Node: def __init__(self, data): self.data = data self.children = [] Tree 예시 class Tree: def __init__(self): self.root = None 트리의 타입 - 이진 ..

https://jwdevv.tistory.com/3 [알고리즘, Python] 정렬(sorting) - 병합 정렬(Merge Sort) 정렬은 크게 다섯가지로 나눌 수 있다: 버블정렬, 선택정렬, 병합정렬, 퀵정렬, 기수정렬(Radix Sort) 그 중 버블정렬과 선택정렬은 메모리 측면에서는 공간 복잡도 O(1)로 좋지만, 시간 복잡도는 O(n^ jwdevv.tistory.com 이전 글과 동일한 '배열을 정렬'하는 문제를 퀵정렬로 구현해보자. 퀵정렬은 랜덤한 요소를 피봇(pivot)으로 정해서 피봇값보다 작은 요소는 왼쪽으로, 큰 요소는 오른쪽으로 정렬하는 방법이다. 평균 시간복잡도는 O(n log(n)) 이지만 피봇값을 어떻게 정하냐에 따라 최악의 경우에는 시간복잡도가 O(n^2)가 될 수도 있다. ..

정렬은 크게 다섯가지로 나눌 수 있다: 버블정렬, 선택정렬, 병합정렬, 퀵정렬, 기수정렬(Radix Sort) 그 중 버블정렬과 선택정렬은 메모리 측면에서는 공간 복잡도 O(1)로 좋지만, 시간 복잡도는 O(n^2)로 비효율적이다. 반면 병합정렬과 퀵정렬은 시간 복잡도가 O(n logn)으로 조금 더 나은 성능을 보인다. 오늘은 배열을 정렬하는 문제를 통해 병합 정렬을 구현해보자. LeetCode - Sort an Array 병합 정렬은 가운데를 기점으로 배열을 반 씩 나눠 정렬 후 병합하는 방법이다. 읽는 것 보다 보는게 이해하기 더 쉽다. GeeksforGeeks의 예시 영상을 보자 : 링크 Python 코드 class Solution: def sortArray(self, nums): tmp = nu..

Q. 집합(set)의 모든 부분 집합(subset)들로 구성된 집합(power set)을 구하라 출처 : Cracking the Coding Interview - Q8.4 먼저 하나하나 적어보자. P([1]) = [[], [1]] P([1,2]) = [[], [1], [2], [1,2]] P([1,2,3]) = [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]] 자세히 살펴보면 P(n)은 P(n-1)에 집합의 마지막 값을 하나 더 넣어준 것과 같다. 내 Python 코드 def subsets(nums: List[int]) -> List[List[int]]: subset = [[]] for num in nums: prevLength = len(subset) for i ..