본문 바로가기

알고리즘풀이

 (38)
Graph 탐색, Depth First Search Graph 깊이 우선 탐색(Depth First Search, DFS)을 stack을 이용하여 풀 수 있다. 가장 중요한 부분은 노드 방문 여부(marked)를 확인하는 부분이다. 위와 같은 그래프가 있을 때, 탐색 순서는 다음과 같다. 노드 0을 방문, 노드 0의 이웃인 1,2,3을 스택에 푸시함 스택에 가장 위에 있는 노드 3을 방문함 그 다음 스택에 가장 위에 있는 노드인 2를 방문함, 노드 2의 이웃인 5,4를 푸시함 노드 4를 방문함 노드 5를 방문함, 노드 5의 이웃인 1을 방문함 스택에는 1이 남아 있지만, 이미 방문하였으므로 방문하지 않음 Swift 풀이 // MARK: - Graph Definition class Node { var val: Int var marked: Bool = fal..
LeetCode: Valid Sudoku 문제설명 9 X 9 크기의 스도쿠 보드가 유효한지 판단하라. 다음 규칙에 따라 보드의 칸이 채워져야 유효하다고 판정한다 각 행은 1-9까지의 숫자를 중복 없이 갖는다. 각 열은 1-9까지의 숫자를 중복 없이 갖는다. 3 x 3 의 작은 박스에서 1-9까지의 숫자를 중복 없이 갖는다. 문제풀이 func isValidSudoku(_ board: [[Character]]) -> Bool { var rows = Array.init(repeating: [Int: Int](), count: 9) var columns = Array.init(repeating: [Int: Int](), count: 9) var boxes = Array.init(repeating: [Int: Int](), count: 9) for i ..
LeetCode: Largest Unique Number 문제설명 정수형 배열 A가 주어졌을 때, 단 하나만 존재하는 정수중 가장 큰 값을 반환하라. 존재하지 않는다면, -1을 반환하라. 1
LeetCode: MoveZeroes 문제설명 정수 배열이 주어졌을 때, 배열의 원소가 0인 정수를 모두 배열의 끝으로 옮겨라. 0을 제외한 정수의 순서는 유지되어야 한다. 배열을 카피하지 않고 in-place로 배열을 수정하라. 문제풀이 배열을 뒤에서부터 순회하여 0이 발견되면 뒤에 넘기는 방식으로 계산할 수도 있다. 이 보다는, 배열을 앞에서부터 순회하여 0이 아닌 것들을 앞으로 밀어주는 방식이 더 깔끔하다. func moveZeroes(_ nums: inout [Int]) { let size = nums.count var j = 0 for i in 0..
LeetCode: Plus One 문제설명 10진수로 구성된 길이가 1 이상인 배열이 주어졌을 때 이 배열은 하나의 정수로 표현된다. 이 정수의 값을 1을 더한 정수를 배열로 반환하라 최상위 수(most significant digit)는 배열의 가장 앞에 위치한다. 이 정수는 0이 아닌 경우를 제외하고, 0으로 시작하지 않는다. 문제풀이 결과를 저장할 배열을 선언한다. 이 배열에 값을 거꾸로 저장하고 뒤집어서 반환한다. 배열을 순회하며 각 위치의 값을 나타내는 val 변수와 자리 옮김 수 carry를 선언한다. val 변수는 carry값과 함께 더해져 10 이상일 수도 있다. 결과 배열에 넣기 전에 10으로 나눈 나머지 값을 넣는다. carry 변수는 10으로 나눈 몫이다. 999에 1을 더하여 1000이 되는 것처럼, 자리수가 하나 ..
LeetCode: Intersection of Two Arrays II 문제설명 두 정수 배열, nums1와 nums2가 주어졌을 때, 두 배열이 서로 교집합이 되는 부분을 반환하라. 결과 배열의 순서는 상관이 없다. 문제풀이 func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] { guard nums1.count > 0 && nums2.count > 0 else { return [] } var nums1Dict = [Int: Int]() var result = [Int]() for num1 in nums1 { var added = 1 if let val = nums1Dict[num1] { added += val } nums1Dict.updateValue(added, forKey: num1) } for num2 in nums2 ..
LeetCode: Single Number 문제설명 크기가 1이상인 정수형 배열이 주어졌을 때, 하나의 원소를 제외하고 나머지 원소는 2번씩 나타난다. 한 번만 나타나는 원소를 찾아서 반환하라. 문제풀이 XOR 연산을 하면 중복된 값이 소거된다. O(n) 시간복잡도를 갖으며 O(1) 공간 복잡도를 갖도록 풀이할 수 있다. func singleNumber(_ nums: [Int]) -> Int { var buf = 0 for num in nums { buf = buf ^ num } return buf } print(singleNumber([4,5,1,5,1])) // 4 print(singleNumber([2,2,1])) // 1 print(singleNumber([1])) // 1
LeetCode: Contains Duplicate 문제설명 정수 배열이 주어졌을 때, 중복된 값이 존재한다면 true를 반환하고 중복된 값이 없다면 false를 반환하라. 문제풀이 값을 저장하고 빠르게 찾을 수 있는 자료구조인 Set을 사용한다. 배열을 한 번만 순회하여 값이 존재한다면 바로 true를 반환한다. 값이 없다면 set에 넣어서 다음 숫자의 검사에 사용될 수 있도록한다. func containsDuplicate(_ nums: [Int]) -> Bool { var set = Set() for num in nums { if set.contains(num) { return true } else { set.insert(num) } } return false } print(containsDuplicate([1,2,3,1])) // true print..

티스토리툴바