[sw정글 2주차] 탐색하다. Tom-ssaek

📚SW정글 2.4주차

🔎탐색

다음과 같은 배열이 있다.

fruits = ['orange', 'apple', 'banana']

만약 apple이 fruit에 있는지 알고싶다면 어떻게 해야할까? 두둥!!

💳멤버십테스트와 set

if 'apple' in fruits 로 검사하면 된다. 이와같이 x in my_array 와 같은 형태로 요소가 배열에 있는지 없는지 검사하는 행위를 멤버십테스트라고 한다.

다음은 백준1920번(링크) 문제를 풀며 실험해 본 결과이다.

1. 멤버십 테스트로 문제를 풀었는데 ⏰시간초과가 났다. 따라서 다른 방법을 사용하여 문제를 풀어보았다.

2. sort()롤 정렬을 시킨 후 멤버십 테스트를 해보았다.

   warehouse.sort()
   for i in range(target_how_many):
   if targets[i] in warehouse:
   answer_sheet[i] = 1
   

두근두근… ) 통과! sort를 쓰다가 멤버십 테스트의 알고리즘이 궁금해졌다. 서치를 하던 와중 한번 set을 사용 해 보았다.

1. set+멤버십을 사용했다. 훨씬 빠르게 통과했다.

2. 시간이 훨씬 많이 줄었다. 그렇다면 sort를 사용한 뒤 set으로 하면 더 빠르지않을까? 아니였다. 똑같은 결과가 나왔다. 그렇다면 얻을 수 있는 결론은 두가지다.

정렬된 배열은 멤버십테스트를 조금 더 빠르게 통과할 수 있다.

멤버십 테스트 쓸 때, set을 안쓰고 돌리면 바보다

어떻게 이런 결과를 얻을 수 있는지 set() 에 대하여 알아보도록 하겠다. 우리가 알다시피 set()을 사용하면, 중복되어있는 요소들을 없애준다. 그렇다면 중복된 요소가 없음에도 불구하고 어떻게 이렇게 멤버십테스트(탐색) 성능이 빨라졌을까?

"" 정답은 set()은 해시값으로 저장을 한다는 것이다. ""

해시로 저장이 되어있다면 시가복잡도는 O(1)이다. decoding을 시킨 후, 해당 인덱스를 바로 팍! 찍으면 툭! 튀어나오는 것이 해시이기 때문이다. 원소가 어디있는지 뒤적이는게 아니라, 원소가 들어있는 상자를 한번에 찾을 수 있는것이다. (그 상자의 인덱스는 특정 알고리즘(sah256, hexdigest 등)들로 알 수 있는 것이고…) 그렇기 때문에 set자료형으로 들어있는 값들은 정렬이 되어있건 되어있지 않건 한번에 찾을 수 있기 때문에 sort()가 성능에 영향을 주지 않았던 것이다.

따라서 set()을 사용함으로써, membership-test의 성능을 비약적으로 올릴 수 있다. 사실 해싱을 하고, 그 값을 불러오는 과정을 set-멤버십 테스트로 가독성 좋게 적어둔 것 뿐인 것이다. 요소에 접근할 때의 시간복잡도는 O(n)이지만 해시는 O(1)이기 때문에 비약적으로 빨라졌던 것이다.

🔎이진탐색

이번 주차에는 많은 이진탐색 문제들을 풀어보았다. 그렇다면 순열조합인지 이진탐색 문제인지 어떻게 알 수 있을까? 꿀팁아닌 꿀팁이라면… 문제에서 숫자의 범위가 1,000,000,000 까지 가능하다면, 해당 인덱스는 이진탐색으로 풀어야 할 것이다.

만약 1억이 넘는 숫자에 대해 순열조합, 및 재귀 등 곱셈을 몇번만 해주면 억을 넘어서, 조,경,해 단위 연산을 돌려야 한다. 따라서 문제가 억단위의 숫자를 우리에게 내밀 때, 이진탐색을 먼저 떠올리는 것은 꽤나 설득력 있는 (나의)주장이라고 볼 수 있다. 무엇을 이진탐색 할지에 대해서도, 이처럼 숫자의 범위를 통해서 유추할 수 있다.

🫀내장함수 vs 직접 구현

백준1920번 문제를 위에서는 membership-test로 풀어 보았다. 이번에는 주제에 이진탐색으로 풀어보았다.

1. bisect 이진탐색 내장함수

2. 이진탐색 직접 구현

그렇다. 당!연!히! 내장함수가 더 빠를까 생각했지만, 직접 구현된 이진탐색이 조금 더 빨랐다. bisect는 원소가 있을때, 없을 때에 대한 다른 기능도 가지고 있기 때문에 직접 구현된 이진탐색이 아주 조금 더 좋은 성능으로 문제를 풀어낸게 아닌가 추측된다. (그게 아니면 딱히 의심스러운 부분이 없다)

🤖문제풀이 팁

백준에서 2805, 2110, 2470, 8983… 등 다양한 이분탐색 문제들을 풀어보았다. 하지만 이분탐색을 구현할 때의 코드들은 모두 달랐다. 다음 코드들을 보자.

while start <= end:
if mid >= target: //미드가 타겟보다 크거나같음
end = mid -1
else: //안되면
start = mid+1
print(end)

while start < end:
if mid >= target: //미드가 타겟보다 크거나 같음
result = mid
start = mid+1
elif: mid < target: //안되면
end = mid
print(result)

탈출조건과 출력 방법이 달랐다. 문제에 다른 탈출조건으로 바꾸어보면 풀리는 문제도 있었고, 풀리지 않는 문제도 있었다. 따라서 이분탐색을 했을 때 마지막 탈출 조건을 정확히 생각하고 코드를 마무리하는 힘이 필요하다. [4,5,6] 중 5 를 찾아내는 이분탐색 알고리즘을 작성할 수 있는가? 그렇다면 그 알고리즘은 4를 찾아낼 때에도 동일하게 동작하는가?

이와같이 마지막 탈출조건에 대해 세심한 정의가 필요하다. 단순 배열에서 숫자를 찾는 것이라면, if A == B: break과 같이 간단하게 탈출조건을 짤 수 있다. 실수하기가 어렵다. 하지만 다양한 이분탐색 문제들을 풀어나갈 때, 탈출조건 적용 방법이 조금씩 다르며 이를 의식하고 마무리하는 연습이 필요할 것 같다. (다풀고 틀리면 억울하다)

🔎탐색 팁

아래와 같이 보초법을 적용시킬 수 있다. 보초가 근무를 서듯이, 탈출조건을 미리 입력 해 두는 것이다. 안그러면… 매번, iteration을 돌 때 마다 if문으로 들어가서 탈출조건에 대해서 연산을 해야한다. 따라서 아래와 같이 보초를 하나 둠으로써 조건연산을 줄여줄 수 있다.

//기본 선형검색
while True:
if(i==n) return -1; // 종료 조건 1. 검색 실패
if(arr[i] == key) return i; // 종료 조건 2. 검색 성공
i++;

//보초법 적용

arr[n] = key; // 배열 마지막에 보초값 추가
while True:
if(arr[i] == key) break; // 종료 조건 2. 검색 성공
i++;

🍔해싱

위에서 이야기 했던 해싱이다. 비둘기집 원리(링크) 처럼, 해싱을 하다보면 무조건 충돌이 일어난다. 이럴 때 hashing conflict가 일어났다고 하거나 혹은 버킷이 부족하다라고 한다. 둘 다 해싱법의 데이터를 담는 특징을 잘 표현한 용어인 것 같다.

충돌 해결

충돌을 해결하기 위해서는 두가지 방법이 있다.

1. 체인법

• 해시값이 같은 데이터를 체인모양의 연결리스트로 연결하는법
• 오픈해시법이라고도 함
• 구현
  • Node 클래스 만들기
  • ChainedHash 해시클래스 만들기

1. 오픈주소법

• 충돌이 발생할 때 rehashing 작업을 통하여 빈 버킷을 찾는 방법을 말함
• closed hashing이라고도 함
• 파이썬도 오픈어드레싱으로 되어있음
• 삭제했다? 그러면 거기에 deleted되었음을 알리는 마크를 삽입 해 둔다
  • 다시 찾을 때, 삭제완료 해두면 그 다음 위치를 보면됨
  • 데이터를 삭제했다면, 지웠다고 마킹을 해두고 다음 해싱에 넣는거니까 쓰다보면 연산량이 조금씩 늘어나지 않을까 싶다(추측)

직접 구현한 체인법(조금 김)

class Node: #해시를 구성하는 노드
def **init**(self, key, vlaue, next) -> None:
self.key = key
self.value = Value
self.next = next

class ChainedHash:
def **init**(self, capacity) -> None: #초기화
self.capacity = capacity
self.table = [None]\* self.capacity

    def hash_value(self, key) -> int:
        if isinstance(key, int):
            return key% self.capacity
        return (int(hashlib.sha256(str(key).encode()).hexdigest(), 16) % self.capacity)

    def search(self, key):
        hash = self.hash_value(key)
        p = self.table[hash]

        while p is not None:
            if p.key == key:
                return p.value
            p = p.next

        return None

    def add(self, key, value):
        hash = self.hash_value(key)
        p = self.table[hash]

        while p is not None:
            if p.key ==key:
                return False
            p = p.next

        temp = Node(key, value, self.table[hash])
        self.table[hash] =  temp
        return True

    def remove(self, key:Any) -> bool:
        hash = self.hash_value(key)
        p = self.table[hash]
        pp = None # 더 앞쪽(테이블과 가까운 쪽)의 값을 임시로 가지고 있음

        while p is not None:
            if p.key ==key:
                if pp is None:
                    self.table[hash] = p.next
                else:
                    pp.next = p.next
                return True # key deleted
            pp = p
            p = p.next  #뒤쪽 노드
        return False

    def dump(self) -> None:
        for i in range(self.capacity):
            p = self.table[i]
            print(i, end= '')
            while p is not None:
                print(f' ->{p.key} ({p.value})', end = '')
                p = p.next
            print()

---

😵배우면서 깨달은 내용을 정리해 보았습니다. 오개념을 아래 댓글에 달아주시면 감사하겠습니다😵

🌜 Thank you for reading it. Please leave your comments below😄

맨 위로 이동하기

swjungle survive 카테고리 내 다른 글 보러가기