데이터를 표현하고 관리하고 처리하기 위한 구조
Stack
Queue
그래프
자기 자신을 다시 호출하는 함수(Recursive Function)
깊이 우선 탐색 (Depth First Search)
너비 우선 탐색 (Breath First Search)
풀이특징
moves = [(-1, 0), (1, 0), (0, -1), (0, 1)] #상, 하, 좌, 우
n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
visited = [[False]*m for _ in range(n)]
def dfs(x, y):
visited[x][y] = True
# (x, y) 기준 인접한 상, 하, 좌, 우 탐색
for move in moves:
nx = x + move[0]
ny = y + move[1]
if nx < 0 or nx >= n:
continue
if ny < 0 or ny >= m:
continue
if visited[nx][ny] == False and graph[nx][ny] == 0:
dfs(nx, ny)
count = 0
for x in range(n):
for y in range(m):
if visited[x][y] == False and graph[x][y] == 0:
dfs(x, y)
count += 1
print(count)
풀이특징
from collections import deque
moves = [(-1, 0), (1, 0), (0, -1), (0, 1)] #상, 하, 좌, 우
n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
def bfs():
que = deque()
que.append((0, 0))
while que:
x, y = que.popleft()
for move in moves:
nx = x + move[0]
ny = y + move[1]
if nx < 0 or nx >= n:
continue
if ny < 0 or ny >= m:
continue
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y]+1
que.append((nx, ny))
dfs()
print(graph[n-1][m-1])
O(n^2)
def sort(array):
for i in range(len(array)):
min_index = i
for j in range(i+1, len(array)):
if array[j] < array[min_index]:
min_index = j
array[i], array[min_index] = array[min_index], array[i]
거의 정렬되어 있을 때 효율적
O(n^2)
def sort(array):
for i in range(1, len(array)):
for j in range(i, 0, -1):
if array[j] < array[j-1]:
array[j], array[j-1] = array[j-1], array[j]
else:
break
거의 정렬되어 있는 경우 비효율적
O(N log N)
def sort(array):
if len(array) <= 1:
return array
pivot = array[0]
tail = array[1:]
left_side = [x for x in tail if x <= pivot]
right_side = [x for x in tail if x > pivot]
return sort(left_side) + [pivot] + sort(right_side)
데이터 개수(N) 제한, 최댓값(K) 제한 상황
O(N + K)
def sort(array):
count = [0]*(max(array)+1)
for i in range(len(array)):
count[array[i]] += 1
sorted = []
for i in range(len(count)):
sorted.extend([i]*count[i])
return sorted
분할(Divide), 정복(Conquer), 결합(Combine)
O(N log N)
def merge_sort(array):
if len(array) <= 1:
return array
# Devide
mid = len(array) // 2
left_sorted = merge_sort(array[:mid])
right_sorted = merge_sort(array[mid:])
# Combine
sorted = []
l = 0
r = 0
while l < len(left_sorted) and r < len(right_sorted):
if left_sorted[l] < right_sorted[r]:
sorted.append(left_sorted[l])
l += 1
else:
sorted.append(right_sorted[r])
r += 1
sorted.extend(left_sorted[l:])
sorted.extend(right_sorted[r:])
return sorted
n = int(input())
array = [int(input) for _ in range(n)]
array.sort(reverse=True)
for i in array:
print(i, end=" ")
n = int(input())
array = []
for _ in range(n):
name, score = input().split()
array.append((name, int(score)))
array.sort(key = lambda x: x[1])
for student in array:
print(student[0], end=" ")
n, k = map(int, input().split())
array_a = list(map(int, input().split()))
array_b = list(map(int, input().split()))
array_a.sort()
array_b.sort(reverse=True)
for i in range(k):
if array_a[i] < array_b[i]:
array_a[i], array_b[i] = array_b[i], array_a[i]
else:
break
print(sum(array_a))
O(log N)
def binary_search(array, target, start, end):
while start <= end:
mid = (start + end) // 2
if target == array[mid]:
return mid
elif target < array[mid]:
end = mid - 1
else:
start = mid + 1
return -1
풀이특징
import sys
input = sys.stdin.readline
n = int(input())
items = list(map(int, input().split()))
m = int(input())
orders = list(map(int, input().split()))
items.sort()
def binary_search(target, start, end):
while start <= end:
mid = (start + end) // 2
if target == items[mid]:
return True
elif target < items[mid]:
end = mid - 1
else:
start = mid + 1
return False
for i in orders:
print("yes" if binary_search(i, 0, len(items)-1) else "no", end=" ")
import sys
input = sys.stdin.readline
n = int(input())
items = set(map(int, input().split()))
m = int(input())
orders = list(map(int, input().split()))
for i in orders:
print("yes" if i in items else "no", end=" ")
풀이특징
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
heights = list(map(int, input().split()))
heights.sort()
def getSum(h):
sum = 0
for i in heights:
if i > h:
sum += (i - h)
return sum
def parametric_search(start, end, sum):
temp = 0
while start <= end:
mid = (start + end) // 2
currentSum = getSum(mid)
if currentSum == sum:
return mid
elif currentSum < sum:
end = mid - 1
else:
temp = mid
start = mid + 1
return temp
print(parametric_search(min(heights), max(heights), m))