취업 리부트 코스 3주차(3) - 이분 탐색

김선은·2024년 4월 6일

알고리즘 취업리부트코스

취업 리부트코스

목록 보기

13/20

취리코 3주차 - 알고리즘 과정 (2)

4/3

4, 6, 7이 stack의 성질을 이용해서 N의 시간으로 푸는 문제들
블로그 완료

4/4 해시(dict), 우선순위 큐 heap

블로그 완료

4/5 이분 탐색, 정렬

블로그 아직

내용 정리

이분 탐색

정렬된 배열에서 원하는 값을 빠르게 찾는 탐색 방법
탐색 범위를 절반 씩 줄여나간다
시간 복잡도는 O(log n)

이분 탐색

# 이분탐색의 중요한 점은 정렬된 배열이어야 한다는 점

def brnary_search(arr, target):
    left = 0 #처음 시작할 곳은 각각 왼쪽과 오른쪽 끝
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
# 중간부터 탐색하기 위해서 양 끝을 더한 값 % 2 (몫만)
        if arr[mid] == target:
            print(mid)
        # 맞췄다면 출력
        elif arr[mid] < target:
            left += mid + 1
        elif arr[mid] > target:
            right = mid - 1

정렬

"sort()는 반환값이 없다!"
a = [2, 3, 1, 4]
b = a.sort()

print(a) # [1, 2, 3, 4] 
print(b) # None

# 내림차순
a.sort(reverse=True) # [4, 3, 2, 1]

"정렬 기준을 바꿀 수 있다. sort의 key 사용"
a = [2, -1, 4, 3]

# x의 제곱 값을 기준으로 오름차순 정렬
a.sort(key=lambda x: x*x)

print(a) # [-1, 2, 3, 4]

# key에는 어떤 값을 받아서 다른 값을 반환하는 함수를 넣음
# lambda x: x * x -> 람다 x는 x의 제곱을 하는 함수.
# lambda fun를 만들어서 key에 넣어줬다고 보면 됨

백준 1181: 단어정렬

https://www.acmicpc.net/problem/1181

defaultdict 사용

# 길이가 짧은 순, 길이가 같다면 사전 순, 중복 단어 제거
# 사전에 단어의 길이를 key로 단어 추가하기
# 사전의 key 값으로 정렬하기

from collections import defaultdict

n = int(input())
len_word = defaultdict(set)

for _ in range(n):
    word = input()
    len_word[len(word)].add(word)

keys = list(len_word.keys())
# [3, 1, 4, 8, 2, 6, 5] -> word 글자수들

keys.sort()
# keys 값을 정렬, 그 값으로 len_word에 단어들 꺼내기

for key in keys:
    words = list(len_word[key])
    words.sort() # 단어 여러개, 같은 글자라면 사전순
    for word in words:
        print(word)

lambda 함수 사용

튜플로 기준을 제시하는게 유용함
heap에서도 튜플로 기준을 제시했었음

# words를 set으로 입력받기 (중복 제거)
# 정렬하려면 list로 변환
# sort()의 key에 튜플로 정렬 기준을 두개 제시
# 튜플 (1차 기준 정렬, 2차 기준 정렬)

n = int(input())

words = list({input() for _ in range(n)})

words.sort(key=lambda x: (len(x), x))

for word in words:
    print(word)