[파이썬] 코딩테스트에서 사용되는 함수 기본기 - 탐색, 소수찾기, 소인수분해, k진수 등

 

DP

DP(Dynamic Programming)

botton-up : 보통 for문으로 풀며 밑에서부터 위로 문제해결 타고 올라감

top-down : 보통 재귀함수로 풀며 위에서부터 아래로 부분문제로 쪼개지며 해결함

 

많은 경우의 수, 큰 숫자의 경우는 높은 확률로 DP를 사용해서 푸는 문제

혹은 첫 경우의 수의 최댓값을 구한 후 한줄한줄 차근차근 누적 + 그 다음단계 경우의 수를 더해나가는 문제

->어떤 규칙으로 최적화 값을 구할 수 있을지 점화식을 세울 수 있어야 함

 

 

 

정렬

문제푸는방식

정렬문제는 딕셔너리, 리스트를, 내장함수(sort, sorted 등)를 잘 이용해서 풀어야함.

또한 시간제한과 메모리제한을 잘 확인해서 풀어야 함

 

 

정렬시간복잡도

+계수정렬 O(N + 데이터 최대값)

#INPUT

10
5
2
3
1
4
2
3
5
1
7

 

 

def sort3():
    n = int(sys.stdin.readline())
    arr = [0] * 10001

    for i in range(n):
        val = int(sys.stdin.readline())
        arr[val] += 1

    for i in range(1, 10001):
        for j in range(arr[i]):
            print(i)

 

 

 

 

STACK

LIFO - 후입선출

문제푸는방식

새로운 배열에 스택으로 쌓고, 매칭되면 pop()

->https://www.acmicpc.net/problem/10799

아주 간단한 로직으로 설명해보자면 아래와 같다.

def stack():
    arr = list(input())
    stack = []

    for i in range(len(arr)):
        if arr[i] == "(":
            stack.append(arr[i])
        else :
            stack.pop()

 

 

 

QUEUE

FIFO - 선입선출

문제푸는방식

list기준 append, pop(0) 을 쓰게 되는데 그것보단 deque를 이용하여 popleft()를 쓰는 것이 시간복잡도 상 더 좋음

 

 

 

K진수

#2진수 bin(n) 
#8진수 oct(n) 
#16진수 hex(n)

 

# 10진수 -> k진수 (2 to 16진수까지 가능) 
def convertK(n, k):
    res = ''
    while n > 0:
        n, mod = divmod(n, k)
        res += str(mod)

    return res[::-1]


# k진수 -> 10진수 (2 to 9진수까지 가능) 
def convertD(n, base):
    res = 0
    for idx, val in enumerate(str(n)[::-1]):
        res += (3 ** idx) * int(val)

    return res


# k진수 -> 10진수 (내장함수) 
int(n의 문자열형태, 진수k)
int(str(21), 3)
int("a12f", 12)

 

 

 

소수찾기

number가 소수인지 아닌지 판별하는 함수

def primenumber(number): 
	if number==1: 
		return False 
	for i in range(2, int(number**(0.5)) + 1): 
		if number%i==0: 
			return False 
	return True

 

 

특정 범위내에서 소수인 수 모두 찾기

def prime(n): 
	m = int(n ** 0.5) 
	for num in range(2, m + 1): 
	if primes[num] : 
		for i in range(2*num, n, num): 
			primes[i] = False 

primes = [True] * MAX_NUM 
primes[0],primes[1] = False, False 
prime(MAX_NUM+1)

 

 

 

 

소인수분해

number 소인수분해 시 모든 결과 출력

# n=20 / answer=[2, 2, 5] 
def div(n): 
	answer=[] 
	x=2 
	while x <= n: 
		if n%x == 0: 
			answer.append(x) 
			n//=x 
		else: 
			x+=1 
	return answer

 

 

number 소인수분해 시, 공통 숫자는 하나로 취급하여 출력

# n=20 / answer=[2, 5] 
def div(n): 
	answer=[] 
	x=2 
	while x <= n: 
		if n%x == 0: 
			if x not in answer : 
				answer.append(x) 
				n//=x 
			else: 
				x+=1 
		return answer

 

 

 

BFS

너비우선탐색 - 대부분 queue방식 / 최단거리 문제 위주

 

기본로직

n, m, v = map(int, input().split())
graph = [[0] * (n + 1) for _ in range(n + 1)]
visited = [False] * (n + 1)

# 인접행렬  
for _ in range(m):
    f, t = map(int, input().split())
    graph[f][t] = graph[t][f] = 1


def BFS(v):
    q = deque()
    q.append(v)
    # 상황에 따라 visited를 내부에서 초기화해서 써야할 수도 있음
    while q:
        val = q.popleft()
        if not visited[val]:
            print(val, end=' ')
            visited[val] = True

            for i in range(n + 1):
                if graph[val][i] == 1 and not visited[i]:
                    q.append(i)


visited = [False] * (n + 1)

BFS(v)

 

기본로직2

n = int(input())
tree = [[] for _ in range(n + 1)]
q = deque()


def BFS(v):
    visited = [-1] * (n + 1)
    q.append(v)
    visited[v] = 0
    while q:
        val = q.popleft()
        for node in tree[val]:
            if visited[node[0]] == -1:
                q.append(node[0])
                visited[node[0]] = visited[val] + node[1]

    return max(visited), visited.index(max(visited))


# 인접리스트
for _ in range(n - 1):
    v, node, l = map(int, input().split())
    tree[v].append([node, l])
    tree[node].append([v, l])

# 무방향 최대거리(가중치)
dis, node = BFS(1)
dis2, node2 = BFS(node)

print(dis2)

 

 

문제를 읽으며 고려해야할 부분

graph를 어떤 방식으로 담을 것 인지

인접행렬 / 인접리스트

visited에 어떤 값을 담을 것 인지

True,False / 혹은 가중치

BFS(v) 호출방식

대부분은 루트에서 출발하고 끝이지만

모든 경로를 탐색할 경우는 for _ in range 가 필요할 수 있음

 

n= int(input())  
graph = []    #문제에 따라 이차원배열을(인접행렬) 바로 선언하거나 인접리스트로 쓰기위해 리스트만 선언함
visited = []  #문제에 따라 없을 수도 있고, True/False일 수도 있고, 가중치가 들어갈 수도 있음
q = deque()   #graph에서같은 너비 친구들을 담아서 반복시켜 보기위한 큐

# 인접리스트
for i in range(n):  
    graph.append(list(map(int, input().split())))

def BFS(v):
    #상황에 따라 visited를 여기서 초기화 하고 시작할 수도 있음
    q.append(v)
    visited[v] = True

    while q:
        val = q.popleft()

        if not visited[val] (and 기타 조건) :
            q.append(val)
            visited[val] = True
BFS(root)

 

 

 

 

DFS

깊이우선탐색 - 대부분 stack방식 / 특정경로 + 가중치

 

기본로직

n, m, v = map(int, input().split())  
graph = [[0] * (n + 1) for _ in range(n + 1)]  
visited = [False] * (n + 1)
res = 0

# 인접행렬  
for _ in range(m):  
    f, t = map(int, input().split())  
    graph[f][t] = graph[t][f] = 1

def DFS(v): 
	nonlocal res
    visited[v] = True 
    print(v, end= " ")  
    for i in range(1, n+1):  
        if not visited[i] and graph[v][i] == 1:  
            DFS(graph, i, visited

DFS(v)

 

 

기본로직2

n = int(input())
graph = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
res = sys.maxsize  # 최솟값 찾을 때 기본셋팅을 가장 큰 값으로 해야할 때 씀
sep = 2

# 인접리스트
for i in range(n):
    graph.append(list(map(int, input().split())))


def DFS(a, b):
    nonlocal sep
    graph[a][b] = sep
    for i in range(4):
        ax = a + dx[i]
        by = b + dy[i]
        if 0 <= ax < n and 0 <= by < n and graph[ax][by] == 1:
            DFS(ax, by)


for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            DFS(i, j)
            sep += 1

print(res)

 

 

문제를 읽으며 고려해야할 부분

graph를 어떤 방식으로 담을 것 인지

인접행렬 / 인접리스트

visited에 어떤 값을 담을 것 인지

True,False / 혹은 가중치

어떤 조건일 때 return 시킬 것 인지

재귀를 이용하는 만큼 굳이 재귀호출 할 필요없는 상황일 때는 return 할 수 있도록 함수 상위에 선언

혹은 어떤 조건일때만 재귀호출을 할 수 있도록 선언

DFS() 호출방식

대부분 DFS는 재귀긴 하지만 visited = True와 같은 조건을 기반으로 시행시킴

 

n= int(input())  
graph = []             #문제에 따라 이차원배열을(인접행렬) 바로 선언하거나 인접리스트로 쓰기위해 리스트만 선언함
visited = [False] * n  #문제에 따라 없을 수도 있고, True/False일 수도 있고, 가중치가 들어갈 수도 있음

# 인접리스트
for i in range(n):  
    graph.append(list(map(int, input().split())))

def DFS(v):
    visited[v] = True   #방문여부를 체크한다는 가정하에 시작노드는 True설정
    next = graph[v]     #다음에 봐야 할 인접노드를 추출함. popleft()도 좋음
    if not visited[next] :  #방문하지 않았던 노드면
        DFS(next)           #체크하러 DFS(next)를 태운다.

for i in range(n):
    if not visited[i] :
        DFS(i)