본문 바로가기

Algorithm/algorithm8

에라토스테네스의 체 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법 체로 거르듯 수를 걸러낸다고 하여 에라토스테네스의 체 라고 불린다. 시간복잡도: O(n log log n) 소수를 빠르게 찾는 방법으로, 전체 범위를 확인하며, 배수를 빠르게 걸러준다. if 문을 통해 for문을 전범위 확인 할 필요가 없어지므로 큰 시간복잡도의 시간이 n**2에서 n log log n 으로 줄어든다. 아래는 파이썬 코드로 확인해볼 수 있는 예시 문제 N = int(input()) prime = [] check = [0] * (N + 1) for i in range(2, N + 1): if not check[i]: prime.append(i) for j in range(i + i, N + 1, i): check[j] = 1.. 2022. 8. 24.
다익스트라(dijkstra) 알고리즘 다익스트라: 최단경로 탐색 알고리즘 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 찾는대 사용됨 단 음수인 경우 사용못함 그 전에 구한 최단거리 정보를 그대로 사용한다는 점이 DP와 유사하다(DP개념에 다익스트라가 들어있는게 맞는듯) 정렬을 사용하기 때문에 그리디 알고리즘에 포함되기도 한다. 알고리즘 순서 출발 노드를 설정한다(대체로 문제에서 주어질 수 있음) 출발 노드를 기준으로 각 노드의 최소비용(최단거리)을 저장한다. 방문하지 않은 노드중 가장 비용이 적은 노드를 선택한다. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소비용(최단거리)를 갱신한다 3,4번을 반복한다 이에 예제를 적자면.. N = int(input()) # 노드 수 start = int(input()) # .. 2022. 8. 4.
플러드 필(flood fill) 플러드 필 알고리즘은 다차원 배열의 어떤 연결된 영역을 찾는 알고리즘이다. 시간복잡도: 0(N) BFS나 DFS 둘 다 그래프 자료구조에서 모든 노드를 방문하기 때문에 둘다 플러드필을 구현 가능하다. 둘중 하나인 BFS만으로 flood fill을 구현 해보기 위해 예제를 만들어 진행을 해 보겠다. ex) 0으로만 이루어진 2차원배열에 어느 한 점이 1이다 [[0,0,0,0], [0,0,0,0], [0,1,0,0], [0,0,0,0]] 이를 상하좌우로 한칸씩 움직이며 0인 구역을 기준배열에 +1 을 진행을 시켜본다. [[4,3,4,5], [3,2,3,4], [2,1,2,3], [3,2,3,4]] 이를 만들기 위한 flood fill 예제코드는 arr=[[0,0,0,0], [0,0,0,0], [0,1,0,0.. 2022. 6. 22.
너비우선탐색(bfs) bfs는 최솟값, 최소거리등. level을 깊히 돡전 branch를 전부 돌며 값을 도출하는 방법이다. # bfs꼴 def bfs(st): q = [] q.append(st) while q: now = q.pop(0) ~~ #값을 도출하기 위한 코드를 작성 ~~ q.append(x) # x는 다음 now가 되기 위해 q에 append된다. 2022. 4. 16.
깊이우선탐색(dfs) branch와 level이 정해져 있다면 사용하는 것이 좋다(재귀를 사용하기 때문) --> 문제설계시, 방향, 배열범위, dfs를 몇번타는지를 확인하고 설계하는게 좋다. #dfs 꼴 def dfs(level): #(깊이가 깊고 branch가 많다면 이곳에 back tracking용 if문을 사용하는 것이 좋다.) if level ==n: # (도출할 값을 만드는 코드가 이곳에 들어감) return for i in range(len(arr)): dfs(level+1) # 재귀로 깊이우선탐색을 함. dfs(0) 2022. 4. 16.
그리디 알고리즘(greedy) 그리디 알고리즘이란 내게 주어진 정보에서 뒷일을 생각안하고 지금 당장 이득을 취할 수 있는것을 택하여 문제를 해결하는 방법이다. 윗말은 ssafy교육을 들으며 정리한 개념이고, 사실 우리가 알고리즘을 배우는대엔 문제에 적용하는 능력을 기르기위해 배운다고 생각한다. 고로 나만의 생각으로 정리를 해보자면 greedy로 풀수 있는지 없는지 판단하는게 중요! ex) 동전교환 문제 but 동전이 서로 배수관계일때만 사용할 수있다. 그리고 시간이나 횟수로 나오는 문제의 최대횟수, 최소동전갯수등을 구할때 유용하게 사용될 수 있다. 입력된 데이터를 sort해서 greedy의 형태로 풀 수 있는지 확인해보기 시간복잡도: O(k) 여기서 k는 문제마다 다르지만 예시로 드는 문제로 치면 동전의 종류가 될 것이다. 위의 글을.. 2022. 4. 14.

티스토리툴바