알고리즘풀이 (38) 썸네일형 리스트형 LeetCode: Number of 1 Bits 문제풀이 unsigned Int가 주어졌을 때 1 비트의 개수를 구하라. (정수에서 1비트의 개수를, 해밍 웨이트(Hamming weight)라고 불린다.) 문제 풀이 최대 32비트까지 검사하면 되므로 32번 순회한다. 첫번째 비트를 1과 AND 비트 연산하여 1이 나오는지 확인하여 합계를 계산해준다. 한번 순회가 끝나면 다음 비트를 검사해야 하므로, ">>" 연산을 사용하여 오른쪽으로 1 비트 옮긴다. func hammingWeight(_ n: Int) -> Int { var num = n var total = 0 for _ in 0..> 1 } return total } print(hammingWeight(3)) // 2 print(hammingWeight(256)) // 1 print(hamming.. Leetcode: Roman to Integer 문제설명 로마 숫자를 정수로 변환하라 로만 숫자는 다음 7가지 심볼로 표현된다. Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000문제풀이 enum Roman: Int{ case I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000 static func parse(_ char: Character) -> Int { switch char { case "I" : return I.rawValue case "V" : return V.rawValue case "X" : return X.rawValue case "L" : return L.rawValue case "C" : return C.rawValue case "D" : retu.. LeetCode: Is Power Of Three 문제설명 정수 n이 주어졌을 때 n이 3의 제곱 수이면 true를 반환하고 아니라면 false를 반환하라. 문제풀이 꼬리 재귀로 풀 수 있다. 3의 제곱수를 올려가며 함수를 호출한다. 3의 제곱수가 n과 같으면 true이고 더 크다면 false를 반환한다. func isPowerOfThree(_ n: Int) -> Bool { if n == 1 { return true } return isPowerOfThreeHelper(n, 3) } func isPowerOfThreeHelper(_ n: Int, _ power: Int) -> Bool { if n == power { return true } if n < power { return false } return isPowerOfThreeHelper(n, p.. LeetCode: Best Time to Buy and Sell Stock 문제설명 인자로 정수 배열이 주어진다. 배열의 각 항목은 날짜의 순서대로 나열되있으며, 주식의 가격을 의미한다. 배열 중 하루를 선택하고 다른 날짜에 주식을 팔아서 가장 크게 수익이 나는 가격을 반환하라. 수익이 0보다 크지 않으면, 0을 반환하라 문제풀이 배열을 순회하면서 가장 가격이 저렴한 날짜를 선별한다. 가장 저렴한 날짜와 현재 순회하고 있는 주식 가격의 시세 차이를 계산한다. 이렇게 계산한 값과 이전에 저장된 수익을 비교하여 가장 큰 값을 저장한다. func maxProfit(_ prices: [Int]) -> Int { var buyAt = 0 var maxProfit = 0 for i in 1.. LeetCode: Climbing Stairs 문제설명 당신은 계단을 오르려고 한다. 계단의 끝까지 올라가기 위해 n 걸음이 필요하다. 계단은 한번에 1단계 또는 2단계 씩만 올라갈 수 있다. 계단에 끝까지 올라가는 모든 방법의 수는 얼마인가? 문제풀이 재귀로 풀 수 있으며, 최적화를 위해 메모이제이션을 사용할 수 있다. 동적 프로그래밍으로 풀 수 있다. 1. Brute-force로 풀기 func climbStairs(_ n: Int) -> Int { return climbStairsHelper(0, n) } func climbStairsHelper(_ i: Int, _ n: Int) -> Int { if i > n { return 0 } if i == n { return 1 } return climbStairsHelper(i + 1, n) + cl.. Leetcode: Merge Sorted Array, 정렬된 배열 병합하기 문제설명 두 정렬된 배열이 주어졌을 때 배열을 병합하라 병합된 배열은 오름차순으로 정렬되어야 한다. 첫 번째 배열은 두 번째 배열만큼의 크기를 더 갖는다. 첫 번째 배열에 병합 결과를 넣는다. 문제풀이 가장 쉬운 방법은 첫 번째 배열에 두 번째 배열을 그대로 이어 붙이고 정렬하면 된다. 다만 O(log n)의 시간복잡도를 갖는다. 시간 복잡도를 O(N)로 풀려면, 첫번째 배열을 따로 복사하여 두 배열의 항목을 하나씩 비교하여 첫 번째 배열에 넣는다. func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) { let nums1Copy = Array(nums1) var p1 = 0, p2 = 0 for i in 0..= n || (p1 < .. Leetcode: Convert Sorted Array to Binary Search Tree, 정렬된 배열을 이진 탐색 트리로 변환 문제설명 오름차순으로 정렬된 배열이 주어졌을 때, 이것을 높이가 균형잡힌 이진 탐색 트리로 변환하라. 높이가 균형잡힌(height-balanced) 이진 탐색 트리는 모든 노드의 두 서브트리의 깊이 하나 이상 차이나면 안된다. 문제풀이 배열이 이미 정렬되어 있으므로, 배열의 중간의 값을 선택하여 preorder 방식으로 노드를 탐색하며 노드를 추가한다. 배열의 중앙의 값을 선택하고 다음 중앙의 값은 서브 배열은 왼쪽과 오른쪽에서 각각 구하면 된다. // MARK: - Answer func sortedArrayToBST(_ nums: [Int]) -> TreeNode? { return helper(arr: nums, 0, nums.count) } func helper(arr: [Int], _ left: I.. Leetcode: Binary Tree Level Order Traversal, 이진 트리 레벨 순서 순회 문제설명 이진트리가 주어졌을 때, 트리를 level 순서로 순회한 노드의 값들을 반환하라 순서는 왼쪽에서 오른쪽, 위에서 아래로가 된다. 문제풀이 이진 트리를 너비우선탐색(BFS)로 순회한다. 각 레벨마다 리스트에 리스트를 추가한다. 각 레벨은 어떻게 알 수 있을까? 큐에 남아있는 갯수만큼 다돌면 하나의 레벨을 순회한 것이다. // MARK: - Answer func levelOrder(_ root: TreeNode?) -> [[Int]] { var result = [[Int]]() guard let root = root else { return result } var queue = [TreeNode]() queue.append(root) var level = 0 while !queue.isEmpty {.. 이전 1 2 3 4 5 다음