정렬 알고리즘: 계수정렬
계수정렬.. 조건만 잘 맞으면 퀵정렬보다 빠른.. 그런 정렬.. 시간복잡도가 O(N+K)라고한다. N은 숫자개수 K는 최대숫자 근데 이게.. 숫자들이 일단 정수여야함 그리고 배열을 하나 더 만들기 때문에 공간복잡도가 높음. 어떻게하냐면.. 배열을 쭉 돌면서 어떤 숫자가 몇번 나왔는지를 다 카운트함 그러고나서 그냥 0부터 시작해서~최대값까지 각 숫자를 카운트만큼 출력해주면됨 array = [7,5,9,0,3,1,6,2,9,1,4,8,0,6,2] count=[0]*(max(array)+1) for i in range(len(array)): count[array[i]]+=1 #각 숫자가 나오는 횟수를 셈.. for i in range(len(count)): for j in range(count[i]): pri..
2022. 7. 15.
정렬 알고리즘: 선택정렬
가장 작은 수를 찾아서 맨 앞이랑 바꾸고.. 그다음 또 작은수를 찾아서 맨앞으로 바꾸고... ' array=[7,5,9,0,3,1,6,2,4,8] for i in range(len(array)): min_idx=i for j in range(i+1,len(array)): if array[min_idx]>array[j]: min_idx=j array[i],array[min_idx]=array[min_idx],array[i] print(array) i번째 값과 i+1 ~ 끝까지의 범위 중 가장작은 값을 골라 i번째 값과 가장작은 값을 스왑 함
2022. 7. 15.
BFS - 미로 찾기
이코테 p.152 - 미로찾기 N x M 크기의 미로가 있다. (1,1)에서 (N,M)으로 가기위한 최소 이동 칸 수를 구하라. 괴물(0), 길(1) BFS를 이용하고.. 방문한 노드는 (이전 노드값+1)을 해서 방문표시를 한다. (N,M)위치의 노드 값을 읽으면 최소 발자취 수가 나온다. from collections import deque dx=[1,-1,0,0] dy=[0,0,-1,1] def bfs(x,y): queue = deque() queue.append((x,y))#현재 노드 방문처리 while(queue): x, y= queue.popleft() #큐에서 좌표를 꺼냄 for i in range(4):#상하좌우 네방향 확인 nx=x+dx[i] ny=y+dy[i] if nx=N or ny=M..
2022. 7. 13.
탐색 알고리즘 - DFS
DFS (Depth-First Search, 깊이 우선 탐색) 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. def dfs(graph, v, visited): visited[v] = True print(v,end=' ') for i in graph[v]: if not visited[i]: dfs(graph,i,visited) #각 노드가 연결된 정보를 2차원 리스트로 표현 graph=[ [],#1번 [2,3,8], [1,7,], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ] #각 노드의 방문이력을 저장할 1차원리스트 visited=[False]*9 dfs(graph,1,visited) def dfs(graph, v, visited): visited[v] = T..
2022. 7. 12.