[これがコードテスト]21日目

▼▼緒論

今日私たちがしなければならないのは、前回学んだ順序探索とバイナリ探索を利用する問題です.
教材に収録された問題と標準におけるステップアルゴリズム−二分探索部分を解く.

▼▼本題

📍 [問題1]部品検索(教材収録)

この問題は、宣言されたリストに検索したい値があるかどうかを判断する問題です.
解決策はいろいろありますが、最も基本的なバイナリ検索アルゴリズムで解決しましょう.
まず、宣言されたリストを番号順に並べ替え、各売り場に探している部品があるかどうかを確認します.
このとき、売り場の部品が並んでいるので、バイナリ検索ができます.

にソートされていない値はバイナリナビゲーションを実行できません.ソート後に使用してください.

'''
5
8 3 7 9 2
3
5 7 9
'''

import sys

def binary_search(array, target, start, end):
    if start > end:
        return False
    mid = (start + end) // 2
    if array[mid] == target:
        return True
    if array[mid] > target:
        return binary_search(array, target, start, mid-1)
    else:
        return binary_search(array, target, mid+1, end)

n = int(input())
array = list(map(int, sys.stdin.readline().split()))

m = int(input())
target = list(map(int, sys.stdin.readline().split()))

for i in target:
    if binary_search(array, i, 0, n-1):
        print("yes", end=' ')
    else:
        print("no", end=' ')
👉🏽 no yes yes

したがって,このように問題を解くと,最悪の場合にはO(M x logN回の時間的複雑度の演算が必要となり,理論的には最大2,000,000回の演算が可能となる.
逆に,N個の部品を並べ替えるのに要する時間的複雑さはO(N x logN)であり,理論的には最大約20,000,000であり,より多くの演算が必要である.
その結果、バイナリ検索を用いた解題方法では、時間的複雑さは、O((M+N) x logN)のソート数を含む.
なお、この問題は이진탐색の他、계수정렬、집합자료형を用いて解くこともできる.계수정렬は、すべての要素番号を含むサイズリストを作成し、リストのインデックスにアクセスして、番号の部品が売り場に存在するかどうかを決定するだけです.
このとき、すべての要素はn+1の範囲内に制御される.

'''
5
8 3 7 9 2
3
5 7 9
'''
import sys

n = int(input())
array = [0] * 100001

for i in input().split():
    array[int(i)] = 1

m = int(input())
target = list(map(int, sys.stdin.readline().split()))

for i in target:
    if array[i] == 1:
        print('yes', end=' ')
    else:
        print('no', end=' ')

👉🏽 no yes yes

また、집합자료형は、ある特定の数が一度発生したかどうかをチェックすればよいため、使用することができる.
このような集合データ型は、特定のデータが存在するか否かを調べるのに非常に効果的である.

'''
5
8 3 7 9 2
3
5 7 9
'''
import sys

n = int(input())
array = set(map(int, sys.stdin.readline().split()))

m = int(input())
target = list(map(int, sys.stdin.readline().split()))

for i in target:
    if i in array:
        print('yes', end=' ')
    else:
        print('no', end=' ')

👉🏽 no yes yes

しかし、バイナリ検索で解決することもでき、アルゴリズムの問題の時間とメモリが非常に限られている場合は、他のアルゴリズムで解決することもできます.

📍 [問題2]トッポッキ作り(教材収録)

典型的なバイナリ探索問題であり,파라메트릭 서치(Parametric Search)型の問題でもある.파라메트릭 서치(Parametric Search)は、最適化問題を決定問題に変換して解決する技術である.
詳細については、講義を参照してください.
たとえば、最適化問題が範囲内で条件を満たす最大値を見つけることを要求する場合、決定問題をバイナリ検索で解決し、範囲を縮小することができます.
符号化テストまたはプログラミングコンテストでは、通常、パラメトリック検索タイプはバイナリ検索を使用して解決される.
この問題の考えは以下の通りです.
適切な高さが見つかるまで、切断機高さ

を繰り返し調整します.

は今Hまで切って条件を満たしますか?

検索範囲は、

条件が満たされているかどうか(はいまたはいいえ)に応じて縮小されます.

このとき,バイナリ探索の原理を利用して半分に縮小する.

切断機の高さは1億から10億の整数で、このような大きな数字を見ると、最初に行った探索を思い出すのは当然だ.

'''
4 6
19 15 10 17
'''
n, m = list(map(int, input().split()))
array = list(map(int, input().split()))

start = 0
end = max(array)

result = 0
while start <= end:
    total = 0
    mid = (start + end) // 2
    for x in array:
        if x > mid:
            total += x - mid
            
    if total < m:
            end = mid - 1
    else:
            result = mid
            start = mid + 1

print(result)
👉🏽 15

また、この問題は現在入手可能なトッポッキの量に応じて物差しの位置を決める必要があるため、再実現は面倒な作業になる可能性がある.
したがって,この問題のようなパラメトリック探索問題タイプは,再帰アルゴリズムではなく繰返し文でバイナリ探索を実現すれば,より簡潔に問題を解くことができる.

📍 [問題3]伯俊-192(数字を探す)

質問する
問題は、与えられた単純数に対応する整数が存在するかどうかである.Hと이진탐색で問題を解いた.

# 이진탐색(재귀)
'''
5
4 1 5 2 3
5
1 3 7 9 5
'''
import sys

def find_number(array, target, start, end):
    if start > end:
        return False
    mid = (start + end) // 2

    if array[mid] == target:
        return True
    elif array[mid] > target:
        return find_number(array, target, start, mid-1)
    else:
        return find_number(array, target, mid+1, end)

n = int(input())
array = sorted(list(map(int, sys.stdin.readline().split())))

m = int(input())
target = list(map(int, sys.stdin.readline().split()))

for i in target:
    if find_number(array, i, 0, n-1):
        print(1)
    else:
        print(0)
👉🏽 
1
1
0
0
0
1

# set 자료형
'''
5
4 1 5 2 3
5
1 3 7 9 5
'''
import sys

n = int(input())
array = set(map(int, sys.stdin.readline().split()))

m = int(input())
target = list(map(int, sys.stdin.readline().split()))

for i in target:
    if i in array:
        print(1)
    else:
        print(0)
👉🏽 
1
1
0
0
0
1

どちらの問題も正解が得られたが,set 자료형資料型を用いた解答がsetの解答時間より3.8倍程度短縮されたことが確認できた.

📍 [問題4]伯俊-10816(デジタルカード2)

質問する
この問題を実施するのは少し難しい.
明らかにバイナリ探索段階の問題であり,実際に問題を解く際にバイナリ探索を利用するのではなく,이진탐색(재귀),딕셔너리を用いて問題を解く.
最初のパズルはCounterで、n_dictと比べてarrayの中にarrayの値がなければ、1を加えて、n_dictが何回加算されたかを知ることができます.
例えばnです.
最後に{'6': 1, '3': 2, '2': 1, '10': 3, '-10': 2, '7': 1}の値をtargetと比較し、この値が存在する場合はn_dictの値出力に設定し、そうでない場合は0に設定する.

'''
10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10
'''

# 딕셔너리 선언 후 값 비교
import sys

n = int(input())
array = sys.stdin.readline().split()
n_dict = {}

for i in array:
    if i in n_dict:
        n_dict[i] = n_dict[i] + 1
    else:
        n_dict[i] = 1

m = int(input())
target = sys.stdin.readline().split()

for i in target:
    if i in n_dict:
        print(n_dict[i], end=' ')
    else:
        print(0, end=' ')
👉🏽 3 0 0 1 2 0 0 2 

2つ目はn_dict[i]関数を用いてCounter値と比較し、target内に存在する場合、いくつかの値を出力するプロセスである.

'''
10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10
'''
# Counter 함수 사용
import sys
from collections import Counter

n = int(input())
array = sys.stdin.readline().split()

m = int(input())
target = sys.stdin.readline().split()

count = Counter(array)

for i in target:
    if i in count:
        print(count[i], end=' ')
    else:
        print(0, end=' ')
👉🏽 3 0 0 1 2 0 0 2 

count関数と比較して,Counter資料型が発表され,メモリと時間が少し減少したことを示した.

▼▼結論

今まで、私はすでにこの探求を学んで、完璧ではありませんが、これは概念を悟る時間です.
まだdictを完全に理解していないので、白俊の他の問題は解決できません.
もっと勉強して問題を解きます.