본문 바로가기
반응형

분류 전체보기44

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.
다이나믹 프로그래밍 다이나믹 프로그래밍 개요 다이나믹 &DP: 메모리 추가사용하여 수행 속도를 크게 향상 시키는 방법 : 계산된 결과를 메모리 영역에 저장하고 다시 계산하지 않도록 함. memozaition 기법 메모이제이션: DP의 구현 기법 중 하나로써 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다. 문제: 수열의 합 연산 n개의 정수로 이루어진 수열에서 연속으로 합했을 때 가장 큰 합을 구하는 프로그램을 작성하여라. 시간 제한 1초 이내, 메모리 128MB 입력 예) 10 -4 3 1 5 6 -35 12 21 -1 출력 예) 33 (12+21=33) 단순 더하기 문제가 아닌 합 연산과 1초 이내라는 부분: DP문제구나!! 알 수 있음 다이나믹 프로그래밍 문제의 핵심: 점화식 이용 점화식 찾기 : 자기 자신 & .. 2022. 7. 21.
반응형

티스토리툴바