본문 바로가기
반응형

파이썬 알고리즘5

DFS와 BFS 탐색: DFS와 BFS 데이터 탐색(그래프 탐색) = 원하는 데이터 도달 DFS(Depth-First Search) ; 깊이 우선 탐색은 그래프에서 깊은 부분을 우선으로 탐색 BFS(Breadth-First Search) ; 너비 우선 탐색은 그래피에서 가까운 노드를 우선으로 탐색 DFS: # DFS 메서드 정의 def dfs(graph, v, visited): visited[v] = True # 현재 노드를 방문 처리 print('DFS 탐색 순서', [v], v, end=' ') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not visited[i]: print('방문 하지 않은 노드 발견 : ', graph[i]) dfs(graph, i, visited.. 2022. 7. 27.
DFS와 BFS 탐색: DFS와 BFS 데이터 탐색(그래프 탐색) = 원하는 데이터 도달 DFS(Depth-First Search) ; 깊이 우선 탐색은 그래프에서 깊은 부분을 우선으로 탐색 BFS(Breadth-First Search) ; 너비 우선 탐색은 그래피에서 가까운 노드를 우선으로 탐색 DFS: # DFS 메서드 정의 def dfs(graph, v, visited): visited[v] = True # 현재 노드를 방문 처리 print('DFS 탐색 순서', [v], v, end=' ') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not visited[i]: print('방문 하지 않은 노드 발견 : ', graph[i]) dfs(graph, i, visited.. 2022. 7. 25.
구현 구현 2차원 공간 벡터 예) 특정 좌표를 기준으로 방향 이동하는 문제 : 상 하 좌 우 이동 공간을 벗어나는 움직임을 무시, RRRUDD 등 계획에 따라 이동하는 문제 문제 : 모험가 A가 N의 공간에서 계획서에 따라 이동하는 경우, 최종 도착하는 좌표의 (X, Y)를 출력하시오. N X N의 2차원 행렬, 모험가의 시작 좌표는 1, 1 입력 예) 5 R R R U D D 출력예) 3 4 코드 정리 1. 정사각형 크기 n입력받기 2. 이동계획 입력받기 3. 반복문: 이동 계획에 따라 좌표이동 4. 공간을 벗어나면 무시 5. 최종 도착지 좌표 출력 n=int(input()) plans=input().split() x,y=1,1 dx=[0,-1,0,1] #동,북,서,남 dy=[1,0,-1,0] move=['.. 2022. 7. 21.
그리디 알고리즘 그리디=탐욕법, 욕심쟁이 문제해결에 최소한의 아이디어를 요구 예) 최단경로 동적계획: 모든 경로(경우의 수)를 탐색 탐욕법: 현재 갈 수 있는 가장 가까운 길만을 사용 문제1: 문제 : N이 1이 될 때까지 두 과정 중 하나를 반복적으로 선택 수행하는 방법은? 최소값을 출력하시오. 입력예) 25 5 출력 예) 2 n,k=map(int,input().split()) result=0 while True: target=(n//k)*k //k로나누어 떨어지는 수를 구함 result+=(n-target) n=target if n 나누기 빼기의 기준은 k로 나누어 떨어지지 않으면 -1 , 나누어떨어지면 나누기 문제: 마을에 모험가 N명을 대상으로 공포도를 측정했다. 공포도가 높으면 던전 입장이 어렵다. 공포도가 X.. 2022. 7. 21.
반응형

티스토리툴바