본문 바로가기

Dev/Algorithm15

12. [알고리즘] K번째 약수 내 생각 1. 약수의 리스트를 구함 2. 정렬 3. k-1 번째 수를 리턴해준다. 구현 # K번째 약수 def solution(a,b): def sol1(n): li = list() for i in range(1,n): if n % i == 0: li.append(i) return li def sol2(li,b): if len(li) < b: return -1 li.sort() return li[b-1] li = sol1(a) answer = sol2(li,b) return answer print(solution(6,3)) print(solution(25,5)) print(solution(100,5)) print(solution(100,7)) print(solution(1000,12)) 다른사람 생각 c.. 2021. 4. 29.
[백준] 플러드필 2667번. 단지번호 붙이기 dx, dy 는 행열의 의미이다. dfs,bfs 의 기본을 잘 알면 쉽게 풀 수 있는 문제. https://www.acmicpc.net/problem/2667 더보기 bfs def solution(x,y): global arr,check,dx,dy q = [] q.append((x,y)) check[x][y] = True count = 1 while q: x,y = q.pop(0) for i in range(4): nx, ny = x+dx[i], y+dy[i] if 0 2021. 4. 1.
[백준] 그래프의 탐색 (DFS, BFS) 그래프의 탐색에는 깊이우선 탐색과, 너비우선 탐색 방법 두가지 방법이 존재한다. 각각을 구할 때, 인접행렬로 구하는 방식이 있고, 간선 리스트로 구하는 방식이 존재한다. 인접행렬은 이차원배열이기 때문에 O(N^2)의 시간이 걸리고, 간선리스트는 간선의 합만큼만 시간복잡도가 걸리기 때문에 O(V+E) 의 시간복잡도가 존재한다. 시간을 최소화 하고싶다면 간선리스트로 구현하자! 1260번. DFS와 BFS https://www.acmicpc.net/problem/1260 더보기 def dfs(n,v): global arr,check check[v] = True print(v,end=' ') for i in range(1,n+1): if arr[v][i] == 1 and check[i] == False: dfs.. 2021. 3. 27.
[백준] 그래프와 BFS 그래프 그래프는 정점과 간선으로 이루어져 있다. 간선 : 연결 관계 경로 : 간선의 연속성으로, 최단경로가 중요한 의미를 가진다. + 가중치의 합이 가장 작을 경우가 중요하다. 차수 : 정점과 연결되어있는 간선의 갯수 그래프를 이용하는 방법 인접행렬, 인접 리스트 2021. 3. 22.

티스토리툴바