코딩테스트 대비 swift 기본 문법 정리

코딩테스트 대비 swift 기본 문법 정리를 해보았습니다. 공부를 하면서 계속 업데이트할 예정입니다! ⭐️

시작전... swift에서 지원하지 않는 자료구조 구현하기

1. 큐 (Queue)

큐는 FIFO(First-In-First-Out) 구조를 가지며, 배열을 기반으로 구현할 수 있습니다.

struct Queue<T> {
    private var elements = [T]()

    mutating func enqueue(_ element: T) {
        elements.append(element)
    }

    mutating func dequeue() -> T? {
        return elements.isEmpty ? nil : elements.removeFirst()
    }

    func peek() -> T? {
        return elements.first
    }

    var isEmpty: Bool {
        return elements.isEmpty
    }

    var count: Int {
        return elements.count
    }
}

2. 우선순위 큐 (Priority Queue)

우선순위 큐는 요소들이 우선순위에 따라 정렬되어 처리되는 자료구조입니다. 보통 Heap을 사용하여 구현할 수 있습니다.

struct PriorityQueue<T> {
    private var heap = MinHeap<T>() // MinHeap 또는 MaxHeap 선택

    mutating func enqueue(_ element: T) {
        heap.insert(element)
    }

    mutating func dequeue() -> T? {
        return heap.remove()
    }

    func peek() -> T? {
        return heap.peek()
    }

    var isEmpty: Bool {
        return heap.isEmpty
    }

    var count: Int {
        return heap.count
    }
}

위의 우선순위 큐 구현을 위해 MinHeap 또는 MaxHeap을 구현해야 합니다.

3. 힙 (Heap)

힙은 부모 노드가 자식 노드보다 우선순위가 높은(또는 낮은) 트리 구조입니다. Max Heap과 Min Heap을 구현할 수 있습니다.

struct MaxHeap<T: Comparable> {
    private var elements = [T]()

    mutating func insert(_ element: T) {
        elements.append(element)
        heapifyUp()
    }

    mutating func remove() -> T? {
        guard !elements.isEmpty else { return nil }
        elements.swapAt(0, elements.count - 1)
        let removed = elements.removeLast()
        heapifyDown()
        return removed
    }

    func peek() -> T? {
        return elements.first
    }

    var isEmpty: Bool {
        return elements.isEmpty
    }

    var count: Int {
        return elements.count
    }

    private mutating func heapifyUp() {
        var index = elements.count - 1
        while index > 0 {
            let parentIndex = (index - 1) / 2
            if elements[index] > elements[parentIndex] {
                elements.swapAt(index, parentIndex)
                index = parentIndex
            } else {
                break
            }
        }
    }

    private mutating func heapifyDown() {
        var index = 0
        while true {
            let leftChildIndex = 2 * index + 1
            let rightChildIndex = 2 * index + 2
            var newIndex = index

            if leftChildIndex < elements.count && elements[leftChildIndex] > elements[newIndex] {
                newIndex = leftChildIndex
            }
            if rightChildIndex < elements.count && elements[rightChildIndex] > elements[newIndex] {
                newIndex = rightChildIndex
            }

            if newIndex == index {
                break
            }

            elements.swapAt(index, newIndex)
            index = newIndex
        }
    }
}

struct MinHeap<T: Comparable> {
    private var elements = [T]()

    mutating func insert(_ element: T) {
        elements.append(element)
        heapifyUp()
    }

    mutating func remove() -> T? {
        guard !elements.isEmpty else { return nil }
        elements.swapAt(0, elements.count - 1)
        let removed = elements.removeLast()
        heapifyDown()
        return removed
    }

    func peek() -> T? {
        return elements.first
    }

    var isEmpty: Bool {
        return elements.isEmpty
    }

    var count: Int {
        return elements.count
    }

    private mutating func heapifyUp() {
        var index = elements.count - 1
        while index > 0 {
            let parentIndex = (index - 1) / 2
            if elements[index] < elements[parentIndex] {
                elements.swapAt(index, parentIndex)
                index = parentIndex
            } else {
                break
            }
        }
    }

    private mutating func heapifyDown() {
        var index = 0
        while true {
            let leftChildIndex = 2 * index + 1
            let rightChildIndex = 2 * index + 2
            var newIndex = index

            if leftChildIndex < elements.count && elements[leftChildIndex] < elements[newIndex] {
                newIndex = leftChildIndex
            }
            if rightChildIndex < elements.count && elements[rightChildIndex] < elements[newIndex] {
                newIndex = rightChildIndex
            }

            if newIndex == index {
                break
            }

            elements.swapAt(index, newIndex)
            index = newIndex
        }
    }
}

4. 콤비네이션 (Combinations)

Swift에서는 itertools 모듈과 같은 콤비네이션 함수를 제공하지 않으므로, 필요한 경우에는 직접 구현해야 합니다. 재귀나 반복문을 사용하여 모든 조합을 생성할 수 있습니다.

func combinations<T>(from elements: [T], choose k: Int) -> [[T]] {
    guard k > 0 else { return [[]] }
    guard !elements.isEmpty else { return [] }

    if k == 1 {
        return elements.map { [$0] }
    }

    var result = [[T]]()

    for (index, element) in elements.enumerated() {
        var reducedElements = elements
        reducedElements.removeFirst(index + 1)
        let combos = combinations(from: reducedElements, choose: k - 1)
        result += combos.map { [element] + $0 }
    }

    return result
}

이와 같이 Swift에서 필요한 자료구조나 알고리즘을 직접 구현하거나 외부 라이브러리를 활용하여 사용할 수 있습니다. 필요에 따라 자료구조를 직접 구현해보고, 코딩 테스트나 문제 해결에 활용해보세요!

 

---

0. Swift 기본 문법

• 기본 자료형
  • Int: 정수
  • Double & Float: 소수점이 포함된 실수 값
    • Double: 64bit 부동소수점 자료형
    • Float: 32bit 부동소수점 자료형
  • Bool: 논리값 → true/false
  • String: 여러 글자로 이루어진 문자열 → 큰따옴표 사용
  • Character: 한 개의 문자를 저장할 수 있는 단일 자료형 → 큰따옴표 사용
• Optional
  • nil을 사용할 수 있는 타입
  • 옵셔널 강제 해제: 옵셔널 타입의 값 뒤에 ! 기호만 붙여주면 됨
• 자료형 변환
  • 문자열로 변환
    • 새로운 문자열 인스턴스를 만들어줘야함

    String(문자열로 바꾸고 싶은 정수값 또는 변수)

  • 정수형으로 변환
    • 새로운 정수 인스턴스를 만들어줘야함

    Int(정수로 바꾸고 싶은 문자열)
    

1. 빌트인 데이터 타입

• 변수는 var → 변경 가능
• 상수는 let → 변경 불가능

정수형

var a = 1
var b = 2
print(a + b, a - b, a / b, a % b) // 더하기, 빼기, 몫, 나머지
print(pow(Double(a), Double(b))) // a의 b승

// 나누기 자세히 보기
// 1) 나누기 결과가 Double인 경우
var result_Double: Double = Double(a) / Double(b)
// 2) 나누기 결과가 Int인 경우
var result_Int = a / b

비교 연산

print(a == b)
print(a != b)
print(a > b)
print(a < b)
print(a >= b)
print(a <= b)

논리 연산

var c = false
var d = true
print(c && d) // and
print(c || d)
print(!c)

범위 연산자

// 닫힌 범위 연산자
1...5

// 반 닫힌 범위 연산자
1..<5

대입 연산자

a = 1
a += 1
a -= 1
a *= 3
a /= 3
a %= 3
a <<= 3
a >>= 3
a &= 3
a ^= 3
a |= 3

부동소수형

var e = 0.199
print(String(format: "%.2f", e)) // 0.20

문자열

var str: String = "hello"
print(str.count) // 5 -> 배열에도 똑같이 사용 가능함.

// 문자열 안에 문자열 포함하는지 확인 가능!
if str1.contains(str2) {
    return 1
}

// 공백을 기준으로 나누기
var lst = letter.components(separatedBy: " ") // Letter -> String

// 문자열이 숫자인지 확인
if char.isNumber {
}

• 긴 문자열은 +으로 이어주기
• let poem = "계절이 지나가는 하늘에는" + "가을로 가득 차 있습니다."
• 멀티 라인 스트링
  • """ ~ """ 내부에 자유롭게 문자열 정의 가능

2. 컬렉션 데이터 타입

2-1. 배열 (Array)

• 배열의 가장 큰 값 찾기: lst.max()
• 배열의 가장 작은 값 찾기: lst.min()
• 배열에서 원하는 값의 인덱스 값 찾기: lst.firstIndex(of: 3)

배열 선언

var arr = [0, 1, 2, 3]
arr = Array(repeating: 0, count: 6)

데이터 추가

var myList = [1, 2, 3, 4]
myList.append(5)
myList.insert(999, at: 2)
myList.append(contentsOf: [5, 6, 7]) // 여러 개의 요소 추가 가능!

데이터 삭제

myList.remove(at: 2)
myList.removeAll { $0 == 2 }  // 2인 요소 모두 제거
myList.removeLast()
myList.removeFirst()

배열 ↔ 문자열 변환

// 문자열 -> 배열로 변경하기
let lst = Array("Hello")
// 배열 -> 문자열로 변경하기
let before_lst = Array(before)
// 배열 반복문 (인덱스 없이)
for char in before_lst {
    dic1[char, default: 0] += 1
}

배열 컴프리헨션

let myList = [1, 2, 3, 4]
let squares = myList.map { $0 * $0 }

배열 슬라이싱

let temp = Array(myList[0..<2])
let temp2 = Array(myList[myList.count-4..<myList.count-2])
let temp3 = Array(myList[0...3]) // 0부터 3까지 슬라이싱

배열 뒤집기

// 배열 뒤집기
Array(my_lst.reversed())

// 문자열 뒤집기
String(my_string.reversed())

2-2. 스택

var stack = [Int]() // 빈 정수형 배열 선언
stack.append(1) // 요소 추가
let lastValue = stack.popLast() // 요소 삭제

if stack.isEmpty {
    // 스택이 비었는지 확인
}

let lst = ["Hello", "world", "this", "is", "Swift"]
let joinedString = lst.joined(separator: " ")

2-3. 큐

var queue = [Int]()
queue.append(1) // 요소 추가
let firstValue = queue.removeFirst() // 맨 앞의 요소 삭제

if queue.isEmpty {
    // 큐가 비었는지 확인
}

2-4. 딕셔너리 (Dictionary)

// 딕셔너리 선언
var myDic: [String: Int] = ["apple": 2, "banana": 3]
var dic1: [Character: Int] = [:] // 빈 딕셔너리 선언

print(myDic["apple"] ?? 0) // 2

myDic["apple"] = 10
myDic.removeValue(forKey: "banana")

if let value = myDic["banana"] {
    print(value)
} else {
    print("No value for key 'banana'")
}
if myDic.keys.contains("apple") {
    print("apple exists")
}

myDic.updateValue(1004, forKey: "angel")
let removedValue = myDic.removeValue(forKey: "angel")

// 딕셔너리 순회 탐색
for row in myDic {
}

for (key, value) in myDic {
}

2-5. 집합 (Set)

var myList = [1, 2, 3, 4]
var lstToSet = Set(myList) // 배열을 집합으로 바꾸기

var mySet: Set<Int> = [1, 2, 3]

mySet.insert(4)
mySet.remove(2)
mySet.removeAll() // 모든 아이템 삭제

let unionSet = mySet.union([5, 6])
let intersectionSet = mySet.intersection([3, 4, 5])
let differenceSet = mySet.subtracting([1, 2])

if lstToSet.isEmpty {
    // 비었는지 확인 가능
}

// 부분집합과 포함관계 판단 연산
B.isSubset(of: A) // 주어진 집합의 값 전체가 특정 집합에 포함되는지 B가 A의 부분집합이니?
B.isSuperset(of: A) // 주어진 집합이 특정 집합의 모든 값을 포함하는지 B가 A의 상위집합이니?
B.isDisjoint(with: A) // 두 집합 사이의 공통 값을 확인하여 아무런 공통값이 없을 때 true 하나라도 있으면 false

2-6. 튜플 (Tuple)

let myTuple = (1, 2, 3)
print(myTuple.0) // 1
print(myTuple.1) // 2

3. 흐름제어문

3-1. 반복문

• while 반복문
  • while 구문
  • while <조건식> { <실행할 구문> }
  • repeat while 문
  • repeat { <실행할 구문> } while <조건식>
• for 반복문
  • for <루프 상수> in <순회 대상> { <실행할 구문> }
  • 순회 대상: 배열, 딕셔너리, 집합, 범위 데이터, 문자열

  for i in 0..<6 {
      print(i)
  }
  
  return dic1 == dic2 ? 1 : 0 // 맞으면 왼쪽 값, 틀리면 오른쪽 값 반환
  
  for char in my_string {
      answer += String(repeating: char, count: n) // n번 반복하여 저장
  }
  

• enumerated()

for (index, letter) in ["A", "B", "C"].enumerated() {
print("\\\\(index): \\\\(letter)") }

• zip()

let numbers = [1, 2, 3] 
let letters = ["A", "B", "C"] 
for (number, letter) in zip(numbers, letters) {
print("\\\\(number): \\\\(letter)") }

3-2.조건문

• if

if a == 2 { 
} else if a == 3 { 
} else { }

• guard
  • 주어진 표현식의 결과가 참인지 거짓인지에 따라 구문의 실행 여부를 결정짓는 방식의 조건문
  • else 블록이 필수, 참일 때 실행되는 블록이 없음
  • 후속 코드가 실행되기 전, 특정 조건을 만족하는지 확인하는 용도 → 조기 종료를 위한 목적

  guard <조건식 또는 표현식> else {         
      <조건식 또는 표현식의 결과가 false 일 때 실행되는 코드>     }

• switch

switch <비교 대상> { 
    case case1, case2: // case1 또는 case2 인 경우 
    case case3: 
    default: }

• [참고] #available 구문
  • OS 버전 별로 구문을 나누어 작성해야 할 때

  if #available(<플랫폼 이름 버전>, <...>,<*>) {
  } else {
  }
  

3-3. 제어 전달문

• break
• continue
• return

4. 함수

• 함수 정의 및 호출

func function(param: Int) -> Int {
    return param * 2
}

let result = function(param: 3)
print(result)

5. 계산 (Math)

내장 함수

import Foundation

let t = 3

// 2의 t제곱 -> 안에 넣는 애들 다 double로 처리해줘야 함.
print(pow(2.0, Double(t)))

// 제곱근
print(sqrt(5.0))

// 팩토리얼
func factorial(_ n: Int) -> Int {
    if n == 0 {
        return 1
    }
    return n * factorial(n - 1)
}
print(factorial(5))

// 원주율 π
print(Double.pi)

// 자연상수 e
print(Double.e)

// 내림
print(floor(3.14))

// 올림
print(ceil(3.14))

// 반올림
print(round(3.14))

// 대문자, 소문자 확인 및 변환
let myString = "U"

var result = ""
if myString.isUppercase {
    print("The string is uppercase")
} else if myString.isLowercase {
    print("The string is lowercase")
}

result = myString.lowercased()
print(result)

result = myString.uppercased()
print(result)

reduce()

let numbers = [1, 2, 3, 4, 5]
let sum = numbers.reduce(0, +) // 배열의 sum 구하기
print(sum) // 15

let concatenatedString = ["Hello", " ", "World", "!"].reduce("", +)
print(concatenatedString) // "Hello World!"

6. 정렬

6-1. 일반 정렬과 객체 정렬

// 일반 정렬
var numbers = [5, 3, 8, 6, 2]
numbers.sort() // 오름차순 정렬
numbers.sort(by: >) // 내림차순 정렬
var sortedArray = numbers.sorted()

// 객체 정렬
struct Student {
    var kor: Int
    var eng: Int
    var math: Int
    var number: Int
}

var students = [
    Student(kor: 90, eng: 80, math: 90, number: 1),
    Student(kor: 20, eng: 80, math: 80, number: 2),
    Student(kor: 90, eng: 30, math: 60, number: 3),
    Student(kor: 60, eng: 10, math: 50, number: 4),
    Student(kor: 80, eng: 20, math: 10, number: 5),
]

students.sort { $0.kor > $1.kor }
for (idx, student) in students.enumerated() {
    print("\\\\(idx + 1)등: \\\\(student.number)번")
}

6-2. 구조체

• 함수와 달리 생략되는 부분이 많음, 함수 이름 생략
• 초기화 구문은 내부

// 기본 문법
struct Resolution {
    var width = 0 // 저장 프로퍼티: 클래스 내에 선언된 변수나 상수를 부르는 이름
    var height = 0

    func desc() -> String {
        return "Resolution 구조체"
    }
}

let res = Resolution()
print("\\\\(res.width)")

6-3. 클래스

• 함수와 달리 생략되는 부분이 많음, 함수 이름 생략

// 기본 문법
class VideoMode {
    var interlaced = false
    var framRate = 0.0
    var name: String?

    func desc() -> String {
        return "VideoMode 클래스"
    }
}

let vMode = VideoMode()
print("\\\\(vMode.interlaced)")

7. 코딩 테스트 구현 노하우

조기 반환 (Early Return)

func earlyReturn(possible: Bool) -> Bool {
    if possible {
        return true
    }
    return false
}

보호 구문 (Guard Clauses)

func guardClauses(inputValue: Int?) -> Bool {
    guard let value = inputValue else {
        return false
    }
    // ... 이후 로직 진행
    return true
}

합성 함수 (Composite Method)

func addThree(x: Int) -> Int {
    return x + 3
}

func square(x: Int) -> Int {
    return x * x
}

let composedFunction = { (x: Int) -> Int in
    return square(addThree(x: x))
}

print(composedFunction(2)) // 25

최대공약수와 최소공배수 구하기 (gcd, lcm)

// 최대공약수
func gcd(_ a: Int, _ b: Int) -> Int {
    var x = a
    var y = b
    while y != 0 {
        let temp = x % y
        x = y
        y = temp
    }
    return abs(x)
}
print(gcd(35, 14))

// 최소공배수
func lcm(_ a: Int, _ b: Int) -> Int {
    return a * b / gcd(a, b)
}
print(lcm(2, 3))

소인수 분해 구하기

import Foundation

func solution(_ n: Int) -> [Int] {
    var n = n
    var factors: [Int] = []

    // 2로 나누어 떨어지는 동안 나눈다.
    while n % 2 == 0 {
        factors.append(2)
        n /= 2
    }

    // 3부터 시작하여 홀수들로 나눈다.
    var divisor = 3
    while divisor * divisor <= n {
        while n % divisor == 0 {
            factors.append(divisor)
            n /= divisor
        }
        divisor += 2
    }

    // 남은 수가 소수인 경우 추가
    if n > 2 {
        factors.append(n)
    }
    return Array(Set(factors)).sorted()
}

이진수 변환

import Foundation

func solution(_ bin1: String, _ bin2: String) -> String {
    // 이진수를 정수로 변환
    let bin1_num = Int(bin1, radix: 2) ?? 0
    let bin2_num = Int(bin2, radix: 2) ?? 0

    // 두 정수를 더한 값을 이진수 문자열로 변환
    let sum = bin1_num + bin2_num
    let result = String(sum, radix: 2)

    return result
}

클로저 표현식

• 이름이 없으며 주변 환경으로부터 값을 캡처할 수 있는 경량 문법으로 작성된 클로저
• 함수와 달리 생략되는 부분이 많음, 함수 이름 생략

// 기본 문법
{ (매개변수) -> 반환 타입 in
    실행할 구문
}

고차 함수: filter

• 함수를 인수로 받아들이고 다른 함수를 반환하거나 조작할 수 있음
• 코드의 가독성을 높이고, 반복문을 사용하는 것보다 더 간결하게 조건을 적용할 수 있음

// 1. 배열에서 filter 사용
let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

// 짝수만 필터링
let evenNumbers = numbers.filter { $0 % 2 == 0 }
print(evenNumbers)  // 출력: [2, 4, 6, 8, 10]

let vowels = ["a","e","i","o","u"]
return my_string.filter { !vowels.contains(String($0)) } // 특정 문자를 포함시키지 않기

// 2. 문자열에서 filter 사용
let myString = "Hello, World!"

// 'o'를 제거
let filteredString = myString.filter { $0 != "o" }
print(filteredString)  // 출력: "Hell, Wrld!"

let words = ["apple", "banana", "cherry", "date", "elderberry"]

// 'a'로 시작하는 단어만 필터링
let wordsStartingWithA = words.filter { $0.hasPrefix("a") }
print(wordsStartingWithA)  // 출력: ["apple"]

// 3. 집합(Set)에서 짝수 필터링
let numberSet: Set = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

// 짝수만 필터링
let evenNumberSet = numberSet.filter { $0 % 2 == 0 }
print(evenNumberSet)  // 출력: [2, 4, 6, 8, 10]

// 4. 딕셔너리에서 특정 조건에 맞는 키-값 쌍 필터링
let people = ["John": 28, "Jane": 34, "Paul": 45, "Anna": 22]

// 나이가 30 이상인 사람만 필터링
let adults = people.filter { $0.value >= 30 }
print(adults)  // 출력: ["Jane": 34, "Paul": 45]

8. 완전 탐색

최대, 최소

import Foundation

let maxSize = Int.max
let minSize = Int.min

print(maxSize)
print(minSize)

완전 탐색

import Foundation

let n = 3
for i in 0..<n {
    for j in (i+1)..<n {
        for k in (j+1)..<n {
            print(i, j, k)
        }
    }
}

9. 유니온-파인드 알고리즘

// 유니온-파인드 알고리즘
class UnionFind {
    private var parent: [Int]
    private var rank: [Int]

    init(n: Int) {
        self.parent = Array(0..<n)
        self.rank = Array(repeating: 1, count: n)
    }

    func find(_ x: Int) -> Int {
        if parent[x] != x {
            parent[x] = find(parent[x])  // 경로 압축
        }
        return parent[x]
    }

    func union(_ x: Int, _ y: Int) {
        let rootX = find(x)
        let rootY = find(y)

        if rootX != rootY {
            if rank[rootX] > rank[rootY] {
                parent[rootY] = rootX
            } else if rank[rootX] < rank[rootY] {
                parent[rootX] = rootY
            } else {
                parent[rootY] = rootX
                rank[rootX] += 1
            }
        }
    }
}

10. 트리

// 이진트리 순회
class TreeNode {
    var value: Int
    var left: TreeNode?
    var right: TreeNode?

    init(_ value: Int) {
        self.value = value
        self.left = nil
        self.right = nil
    }
}

func inOrderTraversal(_ root: TreeNode?) {
    guard let root = root else { return }
    inOrderTraversal(root.left)
    print(root.value, terminator: " ")
    inOrderTraversal(root.right)
}

func preOrderTraversal(_ root: TreeNode?) {
    guard let root = root else { return }
    print(root.value, terminator: " ")
    preOrderTraversal(root.left)
    preOrderTraversal(root.right)
}

func postOrderTraversal(_ root: TreeNode?) {
    guard let root = root else { return }
    postOrderTraversal(root.left)
    postOrderTraversal(root.right)
    print(root.value, terminator: " ")
}

11. 그래프

func dfs(_ graph: [[Int]], _ v: Int, _ visited: inout [Bool]) {
    visited[v] = true
    print(v, terminator: " ")

    for i in graph[v] {
        if !visited[i] {
            dfs(graph, i, &visited)
        }
    }
}

var graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]
var visited = Array(repeating: false, count: 9)
dfs(graph, 1, &visited)

import Foundation

func bfs(_ graph: [[Int]], _ start: Int, _ visited: inout [Bool]) {
    var queue = [start]
    visited[start] = true

    while !queue.isEmpty {
        let v = queue.removeFirst()
        print(v, terminator: " ")

        for i in graph[v] {
            if !visited[i] {
                queue.append(i)
                visited[i] = true
            }
        }
    }
}

var graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]
var visited = Array(repeating: false, count: 9)
bfs(graph, 1, &visited)

12. 백트래킹

func backtracking(_ n: Int, _ arr: inout [Int], _ visited: inout [Bool]) {
    if arr.count == n {
        print(arr)
        return
    }

    for i in 0..<n {
        if !visited[i] {
            visited[i] = true
            arr.append(i)
            backtracking(n, &arr, &visited)
            arr.removeLast()
            visited[i] = false
        }
    }
}

var arr = [Int]()
var visited = Array(repeating: false, count: 4)
backtracking(4, &arr, &visited)

13. 동적 계획법 (DP)

func minCoins(_ coins: [Int], _ k: Int) -> Int {
    var dp = Array(repeating: Int.max, count: k + 1)
    dp[0] = 0

    for coin in coins {
        for i in coin...k {
            if dp[i - coin] != Int.max {
                dp[i] = min(dp[i], dp[i - coin] + 1)
            }
        }
    }

    return dp[k] != Int.max ? dp[k] : -1
}

print(minCoins([1, 2, 5], 11)) // Output: 3

14. 그리디 (탐욕법)

func getMinCoins(_ change: Int) -> Int {
    let coins = [500, 100, 50, 10, 5, 1]
    var change = change
    var count = 0

    for coin in coins {
        count += change / coin
        change %= coin
    }

    return count
}

print(getMinCoins(1260)) // Output: 6

15. 시뮬레이션

let dx = [-1, 0, 1, 0]
let dy = [0, 1, 0, -1]

var x = 1, y = 1
for (dx, dy) in zip(dx, dy) {
    let newX = x + dx
    let newY = y + dy
    print("New position: (\\(newX), \\(newY))")
}

16. 이진 탐색

func binarySearch(_ target: Int, _ data: [Int]) -> Int? {
    var data = data.sorted()
    var start = 0
    var end = data.count - 1

    while start <= end {
        let mid = (start + end) / 2

        if data[mid] == target {
            return mid
        } else if data[mid] > target {
            end = mid - 1
        } else {
            start = mid + 1
        }
    }

    return nil
}

if let result = binarySearch(3, [1, 2, 3, 4, 5]) {
    print("Found at index \\(result)")
} else {
    print("Not found")
}