THIS IS ELLIE

팰린드롬 알고리즘에 대해서 작성해보려 합니다. 팰린드롬 알고리즘은 면접에서 물어보는 알고리즘으로 유명하기도 합니다. 팰린드롬 알고리즘에 대해서 살펴보기 전 팰린드롬의 정의를 찾아보면 팰린드롬은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열입니다. (A palindrome is a word, phrase, number or sequence of words that reads the same backward as forward.) 팰린드롬의 예로는 기러기, 요기요 등이 있습니다. 그럼 주어진 문자열이 팰린드롬인지 아닌지는 어떻게 확인할 수 있을까요. 그냥 뒤집어보면 압니다. func isPanlindrome(_ s: String) -> Bool { if s == String(s.reve..

오랜만에 알고리즘 포스팅을 해보려 합니다. 오늘은 Leetcode 94번 문제를 풀어볼 거예요. 제목은 Binary Tree Inorder Traversal이고 64.1%의 성공률을 가지고 중간 난이도입니다. 이진트리 중위 순회하는 문제입니다. 문제를 풀기 전에 이진 트리 순회 개념부터 살펴봅시다. 트리 순회는 트리 구조에서 각각의 노드를 정확히 한 번만 체계적인 방법으로 방문하는 과정을 말합니다. 연결 리스트와 1차원 배열과 같은 선형 자료 구조에서는 한 가지의 논리적인 순회 방법이 존재하지만, 트리 구조의 순회에는 많은 방법이 존재합니다. 전위 순회 (preorder) 1. 노드를 방문합니다. 2. 왼쪽 서브 트리를 전위 순회합니다. 3. 오른쪽 서브 트리를 전위 순회합니다. 전위 순회는 깊이 우선 ..

오늘 풀어볼 문제는 LeetCode에서 난이도는 Easy인 Reverse Integer문제입니다. 문제는 이렇습니다. Given a 32-bit signed integer, reverse digits of an integer. 부호 있는 32비트 정수가 주어지고 역으로 정수로 나타내라. Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [-2^31, 2^31 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows..

오늘은 LeetCode 알고리즘 문제를 풀어보겠습니다. 처음부터 차근차근 :) 문제 제목은 Two Sum이며 설명은 아래와 같습니다. Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice. 정수 배열이 주어지며, 두 수를 더해 타겟이 되는 수의 인덱스를 리턴해라. 각 입력에는 하나의 답만 존재하며, 동일한 원소가 두 번 나오지 않는다고 가정한다. 음 예시를 보면 확실히 알 것 같습니..

이전에 전화번호부 관련 프로젝트를 진행한 경험이 있다. 하지만 전화번호부에 있는 이름들을 다 선형 탐색으로 필터링하고 있었다. 사실 유저가 많지 않기 때문에 선형탐색으로 해도 특별히 문제점을 느끼지 못했다. 하지만 유저의 수가 증가할수록 선형 탐색이 아닌 이진 탐색이 필요하다는 것을 느끼게 되었다. 때문에 이 부분은 수정이 필요했다. 왜 선형 탐색보다 이진 탐색이 나았는지는 아래 코드 결과를 보면 정확하게 파악할 수 있다. 선형 탐색과 이진 탐색을 비교하기 위해 먼저 정렬된 배열을 준비했다. for문을 돌려 0부터 1000까지의 숫자를 붙여주고 그 배열을 가지고 탐색을 진행했다. 먼저 선형 탐색을 보자. linear 말 그대로 하나씩 탐색하며 검사하는 방법이다. 30을 찾는다고 가정한다. for문을 돌면..

전화번호부에서 이름을 검색할 때 이진 탐색을 사용한다. 이전 프로젝트에서도 전화번호부에서 이름을 검색해야 했는데 배열의 처음부터 다 매칭 해보는 방법을 사용해 O(n)의 시간 복잡도를 가졌습니다. 그때 이진 탐색을 사용했더라면 O(logn)의 시간 복잡도를 가져 배열이 길수록 훨씬 더 효율적으로 검색할 수 있었겠죠. ㅠ_ㅠ 사실 이진 탐색 알고리즘이 무엇인지는 학교에서 배워서 대충은 알고 있었으나 실전에서 이렇게 사용되는지는 와 닿지 않았습니다. 그래서 이번 기회에 이진 탐색 알고리즘을 학습하고 정리하려 합니다. 먼저 이진 탐색 알고리즘의 조건은 데이터가 정렬되어 있어야 합니다. 스위프트로 작성한 코드를 봅시다. 중간 인덱스를 찾아서 중간 인덱스의 값이랑 비교를 합니다. 중간 인덱스 값과 내가 원하는 값..

퀵 정렬은 pivot을 기준으로 큰 숫자와 작은 숫자를 나누어줍니다. 코드를 살펴봅시다. pivot을 array의 중간인 array.count / 2로 잡아주고 less는 pivot보다 작은 것 equal은 pivot이랑 같은 것 greater은 pivot보다 큰 것들로 나누어줍니다. 각 less, equal, greater은 스위프트의 고차함수filter를 사용해줍니다. 간단하게 나뉘는 흐름을 살펴봅니다. array의 count가 1보다 작으면 return해주고 less, equal, greater을 분리하면 최종적으로 정렬된 배열을 얻을 수 있습니다. 단점은 피봇 값에 따라 편향되게 분할될 가능성도 있습니다. 예를들어 이미 정렬할 데이터가 정렬되어 있거나 역으로 정렬되어 있는경우 피봇이 한쪽으로 치우..

병합 정렬은 반으로 나누고 합치면서 정렬합니다. 코드를 살펴봅시다. 위 코드에서 mergeSort 함수는 반으로 나누는 역할을 하며 merge함수는 합치는 역할을 합니다. 큰 흐름을 살펴보면 mergeSort함수를 통해 중간 인덱스를 잡고 왼쪽 오른쪽으로 나눕니다. 나눈 배열을 재귀로 다시 mergeSort로 넘깁니다. 그리고 배열의 길이가 1이면 리턴하게 됩니다. 그럼 배열 count가 1이 될 때까지 나누어지겠죠. 이후 나뉜 배열에 대해서 merge가 실행됩니다. merge가 실행되는 순서는 위와 같습니다. [1][5]에서 처음 merge가 실행되며 [4][1,5]에서 두 번째 merge가 실행되며 [3][6]에서 세 번째 merge가 실행되며 [2][7]에서 네 번째 merge가 실행되며 [3,6]..