Day21) 비트연산자, 이진 검색 알고리즘, sort 함수 작동방식

1. 비트 연산자

컴퓨터는 모든 자료를 0과 1로 이루어진 2진수로 다룬다. 

그래서 모든 숫자는 0과 1이라는 비트로 표현하는데, 그 비트 단위끼리 연산할 때 사용하는 것을 비트 연산자라고 부른다.

연산자	표현	설명
NOT(부정) 비트 연산자	~A	A의 비트를 반전한 결과를 반환
AND 비트 연산자	A & B	A와 B의 비트 AND 논리 연산 수행
OR 비트 연산자	A | B	A와 B의 비트 OR 논리 연산 수행
XOR 비트 연산자	A ^ B	A와 B의 비트 XOR 논리 연산 수행
비트 이동 연산자 (시프트 연산자)	A >> B A << B	A의 비트를 B만큼 시프트(이동)
시프트 연산 후 빈자리는 0으로 채워지고, 비트의 범위를 벗어나면 버려진다.

let a = 1      // 0001
let b = 3      // 0011

// AND
print(a & b)   // 1 = 0001

// OR
print(a | b)   // 3 = 0011

// XOR
print(a ^ b)   // 2 = 0010

// 시프트 연산
print(a << 2)  // 4 = 0100
print(a >> 1)  // 0 = 0000

 

 

비트 연산자는 위 코드처럼 사용하는 수학적 연산보단 비트를 검출하거나 옵션을 전달하는 목적으로 주로 사용된다.

let iPhone: Int = 1   // 0001
let iPad: Int = 2     // 0010
let macBook: Int = 3  // 0100
let iMac: Int = 4     // 1000

func printMyAppleFarm(_ myAppleProduct: Int) {
    print("iPhone: \(iPhone & myAppleProduct != 0)")
    print("iPad: \(iPad & myAppleProduct != 0)")
    print("MacBook: \(macBook & myAppleProduct != 0)")
    print("iMac: \(iMac & myAppleProduct != 0)")
}

let myAppleFarm: Int = iPhone | iPad | macBook  // 0111

printMyAppleFarm(myAppleFarm)
// iPhone: true
// iPad: true
// MacBook: true
// iMac: false

 

비트 연산 실습 --> 프로그래머스 Lv1 [1차] 비밀지도

 

 

 

2. 이진 검색 알고리즘

1. 이진 검색과 선형 검색 알고리즘
   • 선형 검색: 가장 원초적인 방식으로 배열의 요소들을 하나씩 비교해가면서 검색하는 방식이다. 가장 구현하기 쉽지만 배열의 크기가 거대할수록 검색에 소요되는 시간이 오래 걸린다. (검색하는 값이 배열의 맨 마지막에 위치하거나 배열에 존재하지 않는 최악의 경우 시간이 굉장히 오래 소요됨)
   • 이진 검색: 정렬이 되어있는 배열에서 효과적인 검색 방법이다. 검색하는 값과 배열의 가운데 값의 크고 작음을 비교하여 검색에 필요하지 않은 부분을 무시하는 방법이다. 검색하는 값이 가운데 값보다 작다면 배열의 중간 이후의 값은 무시하고 중간 이전의 리스트를 대상으로 과정을 반복한다. 리스트의 요소가 2배로 증가해도 1단계만 추가하면 되므로 선형 검색에 비해 검색 시간이 압도적으로 단축된다. 하지만 이진 검색은 검색 방식의 특성상 정렬된 리스트에서만 사용 가능하며 값을 추가할 때 정렬하여 삽입해야 하므로 데이터 삽입에 있어서는 시간이 오래 소요된다는 단점이 있다.
2. 이진검색 실습 (백준 1920) https://www.acmicpc.net/problem/1920

1920번: 수 찾기

// 이진검색을 사용하긴 했지만 백준에서는 시간초과 뜸.! 
// 비교되는 배열을 Set으로 바꾼 후 contain()메서드를 사용하여 해결 --> Set에서 contain()은 O(1)
func binarySearch(sortedList: [Int], item: Int) -> Int {
    if sortedList.count == 1 {
        return item == sortedList[0] ? 1 : 0
    }

    let midIndex: Int = sortedList.count / 2

    let range: Range<Int> = item < sortedList[midIndex] ? (0..<midIndex) : (midIndex..<sortedList.count)

    return binarySearch(sortedList: [Int](sortedList[range]), item: item)
}

let aCount: Int = Int(readLine()!)!
var aArray: [Int] = readLine()!.split(separator: " ").map({Int($0)!}).sorted()
let mCount: Int = Int(readLine()!)!
var mArray: [Int] = readLine()!.split(separator: " ").map({Int($0)!})

for num in mArray {
    print(binarySearch(sortedList: aArray, item: num))
}

 

 

3. swift에서의 sort함수 작동방식

sort(), sorted() 메서드들의 시간 복잡도는 O(N log N)이다.

시간 복잡도가 이렇게 나오는 이유는 swift에서는 정렬할 때 Timsort를 사용하기 때문이다.

어제 시간 복잡도를 정리하면서 정렬 알고리즘 방식이 궁금해져서 오늘 찾아봤다.

정리가 잘 되어있는 글을 찾았는데 시간 관계상(=내용이 길고 어려워 보여서...) 다음에 다시.. 차분히 읽어봐야겠다.

https://d2.naver.com/helloworld/0315536