THIS IS ELLIE

좋아하는 유투버가 라이브 스트리밍으로 Leetcode 알고리즘을 푸시던데 그것도 IDE 없이 풀더라구요. 우와 나도 IDE 없이 풀어야겠다 하면서 찾게 된 문제가 요 문제입니다. 344번 문제이며, 70.5% 난이도는 당연히 이지ㅋ 문제를 살펴봅시다. 문자열을 뒤집는 함수를 작성해주세요. 인풋 문자열은 문자 배열 char []로 제공됩니다. 다른 배열에 추가적인 공간을 할당하지 마세요. O(1) 추가적인 메모리로 in place하게 수정해야 합니다. 예제를 살펴봅시다. 주어진 문자 배열을 뒤집어주면 됩니다. class Solution { func reverseString(_ s: inout [Character]) { s.reverse() } } 이렇게 좋은 함수를 사용 안 하면 섭섭하지라고 생각해서 요 ..

오늘은 208번 Implement Trie문제를 풀어보겠습니다. 난이도는 중간이고 성공률은 52.1%네요. 일주일에 몇 개씩 풀고 있는데 이 문제가 첫 번째 페이지의 마지막 문제였어요. 물론 번호 왼쪽에 체크가 아닌 물음표 표시도 꽤 보이네요. 시도는 했으나 실패했던 문제도 있어서 다시 풀어봐야 하지만 하기 싫은 언젠가는 풀겠지.. 화이팅 문제를 풀기 전에 트라이에 대한 개념을 정리해보려 합니다. 트라이는 탐색 트리의 일종이며, 트리 자료구조입니다. 문자열 검색을 빠르게 해 주기로 유명합니다. 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유하며, 루트는 빈 문자열에 연관됩니다. 문자열에 한 문자만 넣고 다음 문자는 자식 노드에서 찾도록 합니다. 즉 문자열은 세로로 저장되게 됩니다. 문자열이..

오늘은 200번 Number of Islands문제를 풀어보겠습니다. 난이도는 중간 난이도며 성공률은 49%로 꽤 높습니다. 문제는 아래와 같습니다. m * n의 2차원 배열 grid이 주어지고 1은 땅이고 0은 물이며, 섬의 개수를 리턴해줘야 합니다. 아래와 같은 예시를 살펴보겠습니다. 1이 땅이고 0이 물이니 섬을 개수를 세기 위해서 1의 시작점을 봅니다. 1로만 이루어져 있고 0에 둘러싸여 있으면 섬이라고 생각하면 됩니다. 섬만 표시하다면 아래와 같이 3개의 섬이 있고 정답으로 3을 리턴해주면 됩니다. 코드를 살펴보겠습니다. 저는 전형적인 방법 DFS로 풀었습니다. import Foundation /// 200. Number of Islands let xArr = [1,0,-1,0] let yArr..

알고리즘 문제를 풀다가 좋은 솔루션을 배우게 되어 포스팅하려 합니다. 오늘은 포스팅할 문제는 189번이고 난이도는 중간 난이도입니다. 문제를 살펴봅시다. 배열이 주어지면 배열을 오른쪽으로 k 단계씩 회전합니다. 여기서 k는 음수가 아닙니다. - 가능한 많은 해결책을 찾아보세요. 이 문제를 해결하는 방법은 적어도 3가지 존재합니다. - 너는 인플레이스로 공간 복잡도 O(1)로 처리할 수 있니 제약은 아래와 같습니다. 예제를 살펴보겠습니다. 아래 코드는 제가 처음 풀었던 방식입니다. func rotate(_ nums: inout [Int], _ k: Int) { for _ in 0.. 0 && k > 0 else { return } let k = k % nums.count guard k != 0 else {..

팰린드롬 알고리즘에 대해서 작성해보려 합니다. 팰린드롬 알고리즘은 면접에서 물어보는 알고리즘으로 유명하기도 합니다. 팰린드롬 알고리즘에 대해서 살펴보기 전 팰린드롬의 정의를 찾아보면 팰린드롬은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열입니다. (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 알고리즘 문제를 풀어보겠습니다. 처음부터 차근차근 :) 문제 제목은 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문을 돌면..