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)

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

li=[1,3,2,5,4]
for now, next in zip(li,li[1:]):
	print(now, next)

📌각 인덱스마다 모든 원소 대소 비교

1. 이중 for문

li = [-1, 6, 3, 4, 7, 4]

for i in range(len(li)-1):
   now = li[i]
   next = li[i+1:]
   for n in range(len(next)):
      if now > next[n]:
         print(now)

2. permutations ( 모든 조합, 중복 조합 포함 O )

from itertools import permutations

nums = [1, 2, 3, 4]
print(list(permutations(nums, 2)))

3. combinations ( 중복 조합 포함 X )

from itertools import combinations

nums = [1, 2, 3, 4]
print(list(combinations(nums, 2)))

4. product  : 두 개 이상의 리스트 ( 중복 조합 포함 X)

from itertools import product

nums = [[1, 2, 3], ['a', 'b'], ['ㄱ','ㄴ', 'ㄷ']]
print(list(product(*nums)))

li=[1,0,1]

#filter 사용
list(filter(lambda e:li[e] == 1, range(len(li))))
 
#enumerate 사용
[i for i, ele in enumerate(li) if ele == 1]

아스키코드 활용

print(chr(ord('a') + (ord('z') + 5 - ord('a')) % 26))

z에서 5번째 후 알파벳 구하기

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)

import sys

input = sys.stdin.readline

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

빠르게 입력 받기 위해 input보다는 sys.stdin.readline을 사용한다.

graph 입력을 아래와 같은 코드로 입력 받았다.

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

코드를 실행한 후

3 3

010 을 입력하자

ValueError: invalid literal for int() with base 10: '\n'오류가 발생했다.

📌input  과  sys.stdin.readline

input : 입력에 rstrip() 후 리턴

sys.stdin.readline : 개행문자(\n)를 포함한 값 리턴

따라서 아래와 같은 코드로 바꿔줘야 한다.

import sys

input = sys.stdin.readline

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