우주의 IT 소행성

비트 마스크 (Bitmask)

- 0 부터 N - 1 까지 정수로 이루어진 집합을 나타낼 때 사용

- 공간을 매우 절약할 수 있음

- 각종 연산을 조금 변형해서 사용해야 함

- 집합 값의 검사, 추가, 제거의 모든 복잡도가 O(1)임

A << B -> 비트를 왼쪽으로 한 칸 씩 미는 작업으로, A * 2^B과 같은 뜻

A >> B -> 비트를 오른쪽으로 한 칸 씩 미는 작업으로, A / 2^B과 같은 뜻

집합의 값을 검사, 추가, 제거 할 수 있음.

비트마스크 S에 X가 있는지 검사 ( AND 연산 )

- S & (1 << X) == 0 이면 없음, 0이 아니면(1<<X)이면 있음

비트마스크 S에 X를 추가 (OR 연산)

- 이미 있는 수를 또 추가할 때는 무시. (1 OR 1 = 1이기 때문)

-  S | (1 << X) 하는 것

비트 마스크 S에 X를 제거

- AND 연산일 경우 지우려는 값만 0으로 대조시키면 무조건 0으로

- S & ~(1 << X)

토글 연산

- 0 < - > 1 SWAP 연산

- S ^ (1 << X)

전체 집합

- (1 << N) - 1

공집합

- 0

비트 연산의 연산자 우선 순위를 잘 생각해야 한다.

- 비트 연산은 사칙연산보다 후순위 연산 순위를 가진다.

DFS (Depth First Search, 깊이 우선 탐색)

- 그래프에서 깊은 부분을 우선 탐색하는 알고리즘

그래프란?

- 노드와 간선(정점)으로 표현된 자료구조

- 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 그래프 탐색이라고 한다.

- 두 노드가 간선으로 이어져 있으면 '두 노드는 인접(Adjacent) 하다'라고 표현한다.

그래프의 표현 방식

- 그래프를 프로그래밍에서 표현하는 방식은 크게 2가지이다

1. 인접 행렬 방식 (Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현

표로 표현했을 때

INF = 999999999 # 무한

# 2차원 리스트의 인접 행렬 표현
graph = [
	[0, 3, 5],
    [3, 0, INF],
    [5, INF, 0]
}

print(graph)

파이썬 코드로 표현했을 때

- 인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리의 낭비가 심함

- 인접 행렬 방식이 인접 리스트 방식보다 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 빠름

2. 인접 리스트 (Adjacency List) : 리스트로 그래프의 연결 관계를 표현

graph = [[] for _ in range(3)]

graph[0].append((1, 5))
graph[0].append((2, 3))

graph[1].append((0, 5))

graph[2].append((0, 3))

print(graph)

- 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용함

- 인접 리스트 방식은 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느림 (데이터를 하나씩 확인)

# DFS
def dfs(graph, v, visited):
	visited[v] = True
    print(v, end=' ')
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)

graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9
dfs(graph, 1, visited)

BFS (Breadth First Search, 너비 우선 탐색)

- 가까운 노드부터 탐색하는 알고리즘

- DFS와 반대(가장 가까운 노드부터 / 가장 먼 노드부터)

- 선입선출의 큐 자료구조를 사용

- 재귀로 DFS를 구현하면 수행 시간이 느려질 수 있음

- 스택을 사용하여 DFS구현을 빠르게 동작시킬 수 있음

- 일반적인 경우 DFS보다 BFS의 동작이 빠름

# BFS
from collections import deque

def bfs(graph, start, visited):
	queue = deque([start])
    visited[start] = True
    while queue:
    	v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True

graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9
bfs(graph, 1, visited)

탐색(Search)

- 다수의 데이터 속 원하는 데이터를 찾는 과정

- 그래프 트리 등의 자료구조 안에서 사용하는 대표적인 탐색 알고리즘으로 BFS/DFS가 있다.

- BFS/DFS 탐색를 이해하려면 기본 자료구조에 대한 사전 지식이 수반되어야 한다.

자료구조(Data Structure)

- 데이터를 표현/관리/처리 하기 위한 구조

- 스택 / 큐 / 덱 / 그래프 / 트리 등이 있다

오버플로(Overflow)

- 특정 자료구조의 수용 범위를 넘어섰을 때, 추가로 데이터를 삽입할 때 나타나는 연산 오류

- Over(넘쳐) + flow(흐르다) ->> 데이터가 너무 많아서 넘쳐 흘러 버린다.

언더플로(Underflow)

- 오버플로의 반대로, 데이터가 전혀 없는데 데이터를 삭제할 때 나타나는 연산 오류

스택(Stack)

- 박스 쌓기와 같은 구조

- 박스는 아래서부터 위로 차곡차곡 쌓고, 아래의 박스를 꺼내려면 위의 박스를 치워야만 한다.

- 선입후출(First in Last Out / FILO) -> 먼저 들어온게(선입), 나중에 나간다(후출)

- 파이썬 리스트의 append()와 pop() 함수를 사용하면 stack과 동일하게 사용할 수 있다.

큐(Queue)

- 마트의 대기 줄이나 도로의 터널을 생각해보자.

- 먼저 들어온 (대기한) 사람이 먼저 나가는(우선권을 가지는) 자료구조로 선입선출(First In First Out / FIFO)이다.

- 파이썬 collections 모듈의 deque 자료 구조를 사용하자 (스택과 큐의 장점 둘 다를 가짐)

재귀 함수(Recursive Function)

- 자기 자신을 다시 호출하는 함수

# 예시
def recursive_function():
	print("나 불렀어?")
    recursive_function()

recursive_function()

이 경우에는 "나 불렀어?"가 무한히 출력된다.

파이썬에서는 재귀함수의 무한 출력을 방지하기 위해 횟수 제한을 두고있다. (기본 1000회)

따라서 코드 시작에

import sys
sys.setrecursionlimit(횟수)

를 삽입하여 필요에 따라 재귀함수의 출력 최대 횟수를 지정해주자.

하지만 애초에 재귀 함수를 사용할 때는 무한 출력이 발생하지 않도록, 종료 조건을 명시해주어야 한다.

컴퓨터 내부에서 재귀함수는 스택 자료구조를 이용한다.

따라서 가장 마지막에 호출된 재귀함수가 끝나야 순차적으로 앞선 호출이 완료되는 것이다.

오늘은 가장 기초적인 알고리즘 중 하나인 이분 탐색 (이진 탐색)에 대해서 알아보겠습니다.

이분 탐색에 앞서 순차 탐색에 대해서 복습을 해볼 텐데요.

N개의 데이터가 들어있는 어떤 데이터의 모음 DATA가 있을 때 DATA의 0번째 데이터부터 N번째 데이터까지 모두 방문하여 탐색하는 것을 순차 탐색이라고 합니다.

# 리스트에서 주어진 1개의 값을 찾는 소스코드
data = [12, 255, 156, 8798, 15, 487, 212, 11, 98, 9, 878, 999, 445, 54563, 546779, 78]
print("탐색할 데이터는 : , end='')
target = int(input())

for i in data:
	if i == target:
    	print(target, "을 찾았습니다!")
    	break

당연히 N개의 데이터가 들어있으니 탐색에도 N번만큼의 시간이 소요되겠습니다.

그렇다면 데이터가 1억 개가, 10억 개가, 아니 1조 개가 넘게 유입되어도 과연 순차 탐색으로 탐색을 해낼 수 있을까요?

정답은 "아니오" 입니다.

실제 코딩 테스트나 실무에서 사용하게 되는 알고리즘은 항상 최적의 시간 복잡도를 가져야 합니다.

1조 개의 데이터를 1조 번만큼 탐색하지 않고 더 적은 횟수를 탐색하는 알고리즘이 있다면 정말 좋겠습니다.

그런 알고리즘이 바로 오늘 배울 이분 탐색 알고리즘입니다.

이분 탐색 알고리즘이란?

- 탐색 범위를 절반으로 줄여나가면서 탐색하는 알고리즘

조건 : 배열 내부의 데이터가 오름차순으로 정렬되어 있어야 함

사용 시점 (보편적) : 1000만 이상의 데이터 탐색할 때, 정렬되어 있는 데이터를 탐색할 때

장점

- 매우 빠르게 데이터를 찾을 수 있음

- 탐색 범위를 절반씩 좁혀나가며 데이터를 탐색함

- O(logN)의 시간 복잡도를 가짐

이분 탐색은 탐색 범위의 시작점, 끝점, 중간점 세 점 간의 비교로 원하는 데이터를 빠르게 찾아내는 알고리즘입니다.

이분 탐색에 대해서 간단히 알아보도록 하겠습니다.

먼저 1부터 100까지 오름차순으로 정렬된 리스트가 있다고 가정합시다.

이 리스트에서 이분 탐색을 이용해 67을 탐색해봅시다.

시작점 = start = 1

끝 점 = end = 100

중간점 = mid = (시작점 + 끝점) // 2 = 50

타겟(target)인 67이 중간점보다는 크고 끝 점보다는 작습니다.

오름차순으로 정렬되어있는 리스트이기 때문에 중간점부터 끝점 사이에는 50 ~ 100까지의 숫자만 들어있으므로

우리는 시작점 ~ 중간점 ( 1 ~ 50 )를 탐색할 필요가 없습니다.

따라서

시작점 = 50

끝 점 = 100

중간점 = 75로 수정을 해 줍니다.

이번에는 타겟이 시작점보다 크고 중간점 보다 작습니다 (start <= target <= mid)

따라서

시작점 = 50

끝 점 = 75

중간점 = 62로 수정을 해 줍니다.

계속해서 타겟을 찾을 때 까지 탐색 범위를 좁혀줍니다.

축하드립니다! 계속해서 반복하다보니 중간점에 우리가 그토록 찾던 타겟이 나타났습니다!

이처럼 탐색 범위를 절반의 절반으로 줄여가는 방법을 이분 탐색이라고 합니다.

1 ~ 100까지 전체 데이터의 개수는 100개 이지만 이분 탐색을 이용해 총 7번의 탐색으로 원소를 찾았습니다.

만약 순차 탐색이였다면 더 많은 시간이 소요되었을 것입니다.

이제 이분 탐색을 파이썬으로 구현해보겠습니다.

재귀 함수로 구현한 이분 탐색법

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

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)

반복문으로 구현한 이분 탐색법

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 = 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)

질문, 추가, 오류, 오타, 지적 환영합니다.