알고리즘
-
이진 탐색 트리알고리즘 2021. 2. 10. 00:30
이진 트리는 정렬 여부와 관계없이 모든 노드가 둘 이하의 자식을 갖는 단순한 트리 형태를 말했다. 그렇다면 이진 탐색 트리(BST) 란 무엇일까? 이진 탐색트리란 정렬된 트리를 말하는데, 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이뤄져있는 반면, 노드의 오른쪽 서브트리에는 그 노드의 값과 같거나 큰 값들을 지닌 노드들로 이루어 있는 트리를 뜻한다. 이렇게 왼쪽과 오른쪽의 값들이각각 값의 크기에 따라 정렬되어 있는 트리를 이진탐색트리라 한다. 이 트리의 가장 훌륭한 점은 탐색시 시간 복잡도가 O(log n)이라는 것이다. 이진탐색트리를 이용해 숫자 8을 찾는 과정을 확인해보자. 이 그림에서 루트는 15이며 8은 15보다 작다. 따라서 왼쪽 자식 노드를 탐색한다. 10 또한 8보..
-
python sorted알고리즘 2021. 2. 5. 15:48
파이썬에서 기본적으로 sort는 timsort를 사용한다. 오늘 해볼 포스팅은 파이썬에서 정렬 할 때 이런 생각이 많이 든다. "사람의 이름을 나이순으로 정렬해라. 근데 나이가 같으면 키 순으로 정렬해라" 이렇게 물을 때 어떻게 해야 하는지 포스팅 하려고 한다. 원래 기본적으로 파이썬에서는 리스트에서 sorting을 할 때 some_list = [1,2,3,4,5] some_list.sort() # 결과값 [1,2,3,4,5] 이렇게 sort는 기본적으로 오름차순으로 정렬된다. 물론 내림차순으로 정렬할 수 도 있다. 그럴땐 some_list.sort(reverse=True) # 결과값 [5,4,3,2,1] 가 나온다. 여튼 이제 내가 하려고 하는 사람의 이름을 나이순으로 정렬해라. 근데 나이가 같으면 키..
-
leetcode 5번 Longest_palindrom알고리즘 2020. 12. 29. 18:14
해당 문제는 문자열 s가 들어왔을때 가장 긴 palindrom을 찾는것이다. palindrom이란 회문으로 "토마토" , "기러기" 처럼 거꾸로해도 같은 말을 의미한다. 해당문제는 이번주 leetcode를 풀면서 가장 어려웠던 문제다 각설하고 해설해보겠다. 항상 느끼는 거지만 남의 코드가 제일 어렵다. 이번에도 천천히 해보자. 첫째로 예외처리이다. 만약 애초부터 입력 s가 회문구조이면 이것은 그냥 리턴하는 것이다. 이렇게 되면 s의 길이가 1일때 2일때도 다 처리할수 있다. 내가 현재 사용하려는 방법은 어떤 글자를 기준으로 왼쪽 한글자와 오른쪽 한글자를 포함하여 회문이면 더 넓혀서 또 회문인가를 찾는것이다. 그럼 회문의 구조는 어떻게 생기는 것일까? case1 : bb (길이가 짝수인 경우) case2 ..
-
leetcode_334(Reverse_String)알고리즘 2020. 12. 20. 13:39
해당 문제는 input으로 들어온 문제를 뒤집어서 풀이하는 형태이다. 예를 들어 "Happy" 가 들어왔을 경우 "yppaH"로 들어오면 된다. 여기서 주의사항은 공간복잡도가 O(1)이므로 새로운 변수를 추가하면 안된다는 것이다. 파이썬으로는 쉽게 풀이 할 수 있다. input 변수를 s 라고 가정할 때 s.reverse() 를 이용하면 쉽게 풀이할 수 있다. 또한 s[:] = s[::-1] 로도 쉽게 풀이할 수 있다. 하지만 s = s[::-1] 로는 풀이할 수 없다. 여기서 궁금한것은 s[:] 와 s의 차이는 무엇이길래 둘이 다른 결과가 나오는 것일까 일것이다. 이는 추후에 설명하도록 하겠다.
-
Insertion sort알고리즘 2020. 12. 8. 16:29
Insertion Sort shell sort의 Base가 되는 sort는 insertion sort 라고 할 수 있다. 또한 Insertion sort의 시간 복잡도는 O(N^2)이지만 selection sort와 bubble sort 보다 실제 sort를 돌려보면 위의 둘보다는 빠른 속도에 sort 가 되는 것을 알 수 있다. 위의 그림과 같이 insertion sort는 시작인 index가 0인 원소는 이미 정렬되어 있다고 생각한다. 그다음 첫번째 부터 그 이전의 원소와 비교하면서 만약 자신보다 앞에 있는 원소가 크면 옮긴다. 그렇지 않으면 그대로 위치한다. Second Pass를 보게 되면 1이 23보다 작기 때문에 앞으로 옮겨진것을 볼 수 있다. Third pass를 보면 10은 23보다 작기 ..