THIS IS ELLIE

안녕하세요 :) 오늘은 알고리즘 포스팅이에요 재밌는 문제가 있길래 오랜만에!!!! 가져왔습니다 105번 문제이고 난이도는 Medium, 현재 Acceptance는 63.5%입니다 문제로 넘어갈게요 먼저 두 인티저 배열들인 preorder과 inorder이 주어집니다 preorder은 이진트리의 전위(preorder) 순회이고 inorder은 같은 트리의 중위(inorder) 순회래요 이 두 배열을 보고 우리는 이진트리를 생성하고 반환해야 해요 즉 인풋으로 preorder, inorder 배열들이 주어질 건데 이 정보를 가지고 이진트리를 만들어서 리턴해! 첫 번째 예제 두 번째 예제 제약들도 있으니 참고 자 이제 문제를 풀어봅시다 ⭐️ 문제 풀기 전에 알아야 할 중요한 두 가지 사실이 있어요 ⭐️ 1. p..

안녕하세요 오늘은 371 문제를 풀어보겠습니다. 난이도는 Medium, Acceptance는 50.6%입니다. 문제를 봅시다아 두 정수 a,b가 주어지면 두 정수를 더한 값을 리턴해라. 단 +,- 연산자는 쓰지마 Example 1번을 살펴보면 1, 2를 더한 값인 3을 리턴해주고 Example 2번을 살펴보면 2,3을 더한 값인 5를 리턴해줍니다. 마음으로는 advanced(by: ) 함수 써서 끝낼 텐데^^,, func getSum(_ a: Int, _ b: Int) -> Int { return a.advanced(by: b) } 조금 남은 양심이 말리네요. 근데 21년 5월 30일에 그렇게 풀었음ㅋ 심지어 22년 9월 15일에도 동일하게 advanced(by: )로 풀었음ㅋ 이 정도면 잔머리 대마왕..

오늘은 118,119 문제를 풀어보겠습니다. 모두 파스칼 삼각형 관련 문제고 난이도 Easy, Acceptance는 64.3%, 57.4%입니다. 먼저 118부터 ㄲ 정수형 numRows가 주어지면, 파스칼의 삼각형에서 첫 번째 numRows를 리턴하세요. 파스칼의 삼각형에서 각 숫자는 바로 위 두 수들을 더한 값입니다. 3번째 줄에서 2는 바로 위 1과 1를 더한 값입니다. 마지막 5번째 줄에서 6은 바로 위 3과 3을 더한 값입니다. 여기서 파스칼의 삼각형 규칙은? 첫 번째 줄은 무조건 1입니다. 각 row의 시작과 끝은 무조건 1입니다. n번째 row에는 모두 (n)개의 수가 있습니다. (index라고 치면 n번째에 n + 1개) 주어진 예를 보겠습니다. 1번 예제 numRows로 5를 받았으면, ..

오늘은 11번을 풀어보겠습니다. 중간 난이도고 53.9%의 성공률을 보입니다. ㄱㄱ 길이가 n인 height 정수 배열이 제공됩니다. i번째 선의 두 점이 (i, 0) 그리고 (i, height[i])처럼 n개의 수직선이 그려집니다. 컨테이너에 가장 많은 물이 포함될 수 있는 x축인 두 개의 선을 찾으세요. 컨테이너가 저장할 수 있는 최대 물의 양을 리턴해야합니다. 컨테이너를 기울이는 건 안된다고 합니다. 주어진 예시를 보겠습니다. [1,8,6,2,5,4,8,3,7] 9개의 높이를 받았고 인덱스에 맞게 높이를 그려주면 위 이미지와 같습니다. 컨테이너가 저장할 수 있는 최대 물의 양을 리턴해야 하니 컨테이너가 클수록 좋습니다. 해당 예제에서는 1번째 인덱스 8 그리고 8번째 인덱스 7에서 직선을 만들었을 ..

오늘은 트라이에 대해서 공부해보겠습니다. 사실 전화번호부 검색 알고리즘이 궁금해서 찾아보다가 트라이 개념이 나와서 시작하게 된 포스팅ㅇㅇ 그래서 이번 포스팅은 트라이 개념에 대해서 포스팅하고 다음은 트라이 한국어 탐색에 대해서 포스팅 예정입니다. 트라이란? 트라이(trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 검색 트리의 일종입니다. 일반적으로 키가 문자열인, 동적 배열 또는 연관 배열을 저장하는 데 사용되는 정렬된 트리 자료구조입니다. 트라이의 어원? 트라이가 왜 트라이인지 궁금해서 어원을 찾아봤습니다. 트라이의 개념은 1959년에 처음 공개되었고 검색을 뜻하는 retrieval(리트리벌)의 중간 음절에서 용어를 따왔다고 합니다. 당시에는 트리(tri:)로 불렀다고 하는데 기존에 존재하는 트리..

오늘은 1975문제를 풀어보겠습니다. 중간 난이도며 43.9%의 성공률을 보이고 있네요. 문제를 살펴봅시다. n x n 정수 행렬이 주어지고 행렬의 인접한 두 요소를 선택해 각각에 -1을 곱하는 연산을 마음껏 할 수 있습니다. (단 border를 공유하는 경우에만 인접하다고 간주됩니다.) 그렇게 만든 행렬 요소의 합이 최댓값이 된다면 리턴하면 됩니다. 예시를 봅시다. 1번 예시: [1, -1] [-1, 1] 첫 번째 행에 -1을 곱해줍니다. [-1, 1] [-1, 1] 다음 첫 번째 열에 -1을 곱해줍니다. [1, 1] [1, 1] 모든 원소의 합은 4가 되고 최댓값이 됩니다. 2번 예시: [1 ,2, 3] [-1, -2, -3] [1, 2, 3] 두 번째 행에 마지막 두 원소에 -1을 곱해줍니다. [1..

안녕하세요 :) 오랜만에 블로그 포스팅을 해보려 합니다. 그동안 포스팅을 하지 않은 구질구질한 이유는? 사실 요 몇 주 롤체토스에 빠졌다가 실버4 찍고 관뒀습니다. 무튼... 오늘 공부해 볼 주제는 공간복잡도(space complexity) 입니다. 공간복잡도란? 프로그램을 실행시킨 후 완료하는데 필요로 하는 자원 공간의 양입니다. 공간복잡도는 총 공간요구 = 고정 공간 요구 + 가변 공간 요구로 나타낼 수 있고 수식으로는 S(P) = c + Sp(n)으로 표기합니다. 공간복잡도는 어떻게 표기하느냐? 공간복잡도는 Big-O표기법을 사용합니다. 시간복잡도를 표현할 때도 Big-O 사용했었죠? Big-O는 알고리즘의 성능을 수학적으로 표현해주는 표기법이기 때문에 시간복잡도 공간복잡도 모두 Big-O 표기법을..

알고리즘 문제 풀면서 성능 비교하는 건 아주 중요하죠! 애용하는 LeetCode(https://leetcode.com)는 사이트 자체에서 런타임 소요 시간과 메모리 사용량을 보여주지만, LeetCode에 제출하지 않고 알고리즘 성능 비교할 때는 아래 코드를 사용합니다. struct AlgoTimer { private var startTime: TimeInterval = 0.0 private var endTime: TimeInterval = 0.0 // 타이머 시작 mutating func start() { startTime = NSDate().timeIntervalSince1970 } // 타이머 멈춤 mutating func stop() -> TimeInterval { endTime = NSDate()..