Sso

선형탐색은 O(n)의 시간 복잡도

이진탐색은 O(log n)의 시간 복잡도

입력 데이터의 크기가 큰 경우 이진탐색을 떠올려야 함

리스트에서 특정 숫자가 몇 번 나왔는지 확인

from bisect import bisect_left, bisect_right

start, end = map(int, input().split())
array = list(map(int, input().split()))

# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
# bisect_right(list, num) : list에 num을 넣을 가장 오른쪽 인덱스 반환
def count_by_range(array, left_value, right_value):
    left_index = bisect_left(array, left_value)
    print(left_value ,' 의 첫번째 인덱스 : ', left_index)
    right_index = bisect_right(array, right_value)
    print(right_value,' 의 마지막 인덱스 : ', right_index-1)
    return right_index - left_index

count = count_by_range(array, end, end)
if count == 0:
    print(-1)
else:
    print(count)

리스트에서 특정 숫자들(범위)이 몇 번 나왔는지 확인

from bisect import bisect_left, bisect_right

start, end = map(int, input().split())
array = list(map(int, input().split()))

# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
# bisect_right(list, num) : list에 num을 넣을 가장 오른쪽 인덱스 반환
def count_by_range(array, left_value, right_value):
    left_index = bisect_left(array, left_value)
    print(left_value ,' 의 첫번째 인덱스 : ', left_index)
    right_index = bisect_right(array, right_value)
    print(right_value,' 의 마지막 인덱스 : ', right_index-1)
    return right_index - left_index

count = count_by_range(array, start, end)
if count == 0:
    print(-1)
else:
    print(count)

리스트 내 특정 숫자의 인덱스 찾기

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start+end)//2
        # 찾은 경우 중간점 인덱스 반환
        if array[mid] == target:
            return mid
        # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        elif array[mid] > target:
            end = mid - 1
        # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        else:
            start = mid + 1
    return None

# n(원소의 개수)과 target(찾고자 하는 값) 입력 받기
n, target = list(map(int, input().split()))
# 전체 원소 입력 받기
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n-1)
if result == None:
    print('원소가 존재하지 않습니다.')
else:
    print(result + 1)

찾은 숫자의 첫번째 인덱스 값을 출력함

BFS : 1 - 2 - 3 - 8 - 7 - 4 - 5 - 6

DFS : 1 - 2 - 7 - 6 - 8 - 3 - 4 - 5

미로 찾기

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())

maze = []
for _ in range(n):
    maze.append(list(map(int, input().rstrip())))

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

def bfs(x, y):
    queue = deque()
    queue.append((x, y))

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
            if maze[nx][ny] == 0:
                continue
            if maze[nx][ny] == 1:
                
                maze[nx][ny] = maze[x][y] + 1
                queue.append((nx, ny))
    
    return maze[n-1][m-1]


print(bfs(0, 0))

음료수 얼려먹기

import sys

input = sys.stdin.readline

n, m = map(int, input().split())

graph = []
for _ in range(n):
    graph.append(list(map(int, input().rstrip())))

def dfs(x, y):
    if x <= -1 or y <= -1 or x >=n or y >= m:
        return False
    if graph[x][y] == 0:
        graph[x][y] = 1
        dfs(x-1, y)
        dfs(x+1, y)
        dfs(x, y-1)
        dfs(x, y+1)
        return True
    return False

result = 0

for i in range(n):
    for j in range(m):
        if dfs(i, j) == True:
            result += 1

print(result)