728x90 반응형 Python169 2022.02.14 [백준] (python 파이썬) DNA https://www.acmicpc.net/problem/1969 1969번: DNA DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오 www.acmicpc.net 풀이 처음 이 문제를 이해하기가 어려웠다. 그래서 구글링 중, 위 그림을 발견하였다. 위의 그림처럼 같은 위치에 있는 DNA중 가장 많이 나온 DNA와 그 DNA를 제외하고 나온 DNA의 갯수를 모두 더해주면 답을 구할 수 있다. 이 문제는 각 상황에서의 최선을 찾는 문제이기 때문에 그리디 알고리즘을 사용할 수 있다. 1 2 3 4 5 6 7 8 9 1.. 2022. 2. 14. 2022.02.14 [백준] (python 파이썬) DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 이 문제는 dfs와 bfs를 모두 사용하여 답을 구하는 문제이다. 먼저 각 정점과 연결된 정점들을 graph에 저장한다. 문제에서 연결된 정점들이 많으면 번호가 작은거 부터 방문하라고 했으니 각각의 graph를 sort로 정렬해 준다. dfs함수를 먼저 실행시켜주고 bfs함수를 실행하기 전, vis배열을 초기화 시켜준다.(dfs함수를 실행하면서 이미 사용.. 2022. 2. 14. 2022.02.14 [백준] (python 파이썬) 바이러스 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 풀이 이 문제는 최단거리나 방향성이 있는 문제가 아니기 때문에 bfs와 dfs를 모두 사용할 수 있다. 아래의 코드는 bfs를 이용하여 작성한 코드이다. graph배열을 생성 후, 각 정점에서 연결된 정점들을 저장한다. 그리고 vis배열을 이용하여 각 정점에 방문했는지의 여부를 체크한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2.. 2022. 2. 14. 2022.02.14 [백준] (python 파이썬) 미로 탐색 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 이 문제는 최단 거리를 구하는 문제이기 때문에 bfs를 이용하여 코드를 작성했다. 문제에서 주어진 배열을 저장할 arr배열과 거리를 저장할 vis배열을 만들었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 from collections import deque n,m=map(int, input().split()) arr=[].. 2022. 2. 14. 이전 1 ··· 31 32 33 34 35 36 37 ··· 43 다음 728x90 반응형
