전체 글 검색 결과
477 개의 검색 결과가 있습니다.
알고리즘(python)/탐색

[Python]DFS와BFS 백준 1012

문제 https://www.acmicpc.net/problem/1012 앞의 문제와 다르지않다.앞전에는 DFS를 활용하였으므로 이번엔 BFS를 통해 구현해보자. 1234567891011121314151617181920212223242526272829303132333435import sysfrom collections import dequeT=int(sys.stdin.readline()) def whiteworm(row,colume,matrix,N,M): q=deque() q.append([row,colume])#시작위치 넣어주고 시작 matrix[row][colume]=2 dx=[1,-1,0,0] dy=[0,0,1,-1] while q: [x,y]=q.popleft()#큐에 있는거 빼서 저장 for i ..

2020. 2. 13. 21:44
알고리즘(python)/탐색

[Python]DFS와BFS 백준 2667

문제 https://www.acmicpc.net/problem/2667 DFS BFS 모두 사용이 가능하다.나는 DFS를 사용하여 구현해 보았다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546import sysN=int(sys.stdin.readline())map=[]for i in range(N): row=sys.stdin.readline() tmp=[] for i in range(N): tmp.append(int(row[i])) map.append(tmp) def area(start_row,start_colume,map):#아래위 좌우 확인 dfs를 통해 확인 count=1 map[start_row..

2020. 2. 13. 14:22
알고리즘(python)/탐색

[Python]DFS와BFS 백준 2606

문제 https://www.acmicpc.net/problem/2606 해당 노드에 연결된 모든 노드들을 찾는문제라고 볼수있다.DFS를 통해 구현해보자. 12345678910111213141516171819import sysN=int(sys.stdin.readline())#컴퓨터수M=int(sys.stdin.readline())#연결수matrix=[[0 for _ in range(N+1)] for _ in range(N+1)]for i in range(M): x,y=map(int,sys.stdin.readline().split()) matrix[x][y]=1 matrix[y][x]=1 #current_node:시작 컴퓨터,matrix:인접행렬,virus_com:바이러스 걸린컴퓨터터def dfs(curre..

2020. 2. 13. 11:32
알고리즘(python)/탐색

[Python]DFS와BFS 백준 1260

문제 https://www.acmicpc.net/problem/1260 DFS와 BFS는 각각 깊이우선탐색 너비우선탐색이다.방문할수 있는 모든 정점을 방문하는 방법으로 그 순서에 따라 DFS와 BFS로 나뉜다.DFS는 깊이 우선탐색은 Binary tree를 탐색했던 방식인 postorder(전위 순회(부모노드->왼쪽자식->오른쪽자식)) inorder(중위순회(왼쪽자식->부모노드->오른쪽자식)) preorder(후위순회(왼쪽자식->오른쪽자식->부모노드)) 방식이 이에 해당된다.이 문제에서는 전위 순회를 이용하였다.DFS는 스택에 방문한 정점들을 스택에 저장하였다가 다시 꺼내면서 해당노드의 자식노드들을 다시 스택에 쌓는방식이고 BFS는 큐를 이용하여 자식노드들을 모두 넣고 꺼내면서 해당노드의 자식노드들을 큐..

2020. 2. 13. 10:46
알고리즘(python)/기본

[Python]동적계획법2 백준 2618

문제 https://www.acmicpc.net/problem/2618 사건과 가까운 경찰차가 이동하면된다고 생각해보자. 이같이 그리디 알고리즘을 적용하면 쉽게 풀수 있을거같지만같은거리에 사건이 발생했을때가 문제이다. 그다음 사건이 벌어질 위치에서 가까운 경찰차를 나두고 다른 경찰차가 이동해야 가장 짧은 거리가 될수있다. 그리디를 이용하기위해서는 같은거리에 있는 사건이 나왓을때 다른방법으로 처리해 주는 방법을 생각해봐야할것같다.DP문제로 나온걸로 보아 그런방법을 찾기보단 이동하는 모든 경우에 수를 생각해봐야한다.모든 경우를 차례대로 구한다면 2^n이라는 최악의 시간복잡도를 가질것이다.동적계획법을 사용해보자. 123456789101112131415161718192021222324252627282930313..

2020. 2. 10. 01:06
알고리즘(python)/기본

[Python]동적계획법2 백준 10942

문제 https://www.acmicpc.net/problem/10942 팰린드롬이란 반으로 나누어 좌우가 같은 것이다.짝수개일때는 반으로나누어 같은경우 홀수개일때는 중앙값을 기준으로 좌우가 같은것이다.2 2, 4 4 4 4 , 1 ,1 2 1 같은경우 모두 팰린드롬이다.테스트 케이스마다 모두 계산한다면 O(N^2)*M 번이 걸릴것이다.dp를 이용해 모든 경우를 구한뒤 출력만 해주는 방식으로 구현해보자.방법은 먼저 한자리 일때를 모두 1로 초기화 시켜주고 2자리 일때도 각각 구해주었다.그뒤 하나씩 늘려가며 이전값들이 팬린드롬이면서 양끝값을 비교하여 같으면 팬린드롬이고 이를 저장하여 다시 이용한다.작은 예를 들어보자num=[1,2,3,2,1] 이라는 배열이 주어졌을때 4*4의 dp를 만들어주고 초기화시킨다..

2020. 2. 9. 21:40