본문 바로가기
반응형

Python 코딩테스트

 (65)
DFS/BFS: 백준 1260 파이썬 문제: https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이: from collections import deque n, m, v = map(int, input().split()) array = [[] for _ in range(n+1)] result_dfs = 0 result_bfs = 0 visited_dfs = [False] * (n + 1) visited_bfs = [False] * (n + 1) f..
DFS/BFS: 백준 2606 파이썬 문제: https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 풀이: DFS com = int(input()) vertex = int(input()) array = [[] for _ in range(com+1)] result = 0 visited = [False]*(com+1) for _ in range(vertex): x, y = map(int, input().split()) array[x].append(y) array[y].append(x) def df..
DFS/BFS: 백준 16173 파이썬 문제: https://www.acmicpc.net/problem/16173 16173번: 점프왕 쩰리 (Small) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net 풀이: 1. DFS n = int(input()) array = [] for i in range(n): array.append(list(map(int, input().split()))) visited = [] for _ in range(n): visited.append([False] * n) dx = [1, 0] dy = [0, 1] def dfs(x, y, visited): if x >= n..
DFS/BFS: 깊이 우선 / 너비 우선 탐색 알고리즘 DFS DFS는 Depth-First Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 스택 자료구조에 기초한다는 점에서 구현이 간단하다. 실제로는 스택을 쓰지 않아도 되며 탐색을 수행함에 있어서 데이터의 개수가 N개인 경우 O(N)의 시간이 소요된다는 특징이 있다. 또한 DFS는 스택을 이용하는 알고리즘이기 때문에 실제 구현을 재귀 함수를 이용했을 때 매우 간결하게 구현할 수 있다. DFS 예제 # DFS 메서드 정의 def dfs(graph, v, visited): # 현재 노드를 방문처리 visited[v] = True print(v, end=' ') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: ..
구현: 백준 1236 파이썬(Python) 문제: https://www.acmicpc.net/problem/1236 1236번: 성 지키기 첫째 줄에 성의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 성의 상태가 주어진다. 성의 상태는 .은 빈칸, X는 경비원이 있는 칸이다 www.acmicpc.net 풀이: 이 문제는 해결 아이디어를 잘 생각할 필요가 있었다. 나는 접근을 잘못했고 결국 스스로 해결하지 못했다. 모자란 경비원의 수를 세는 아이디어는 행 기준, 열 기준으로 경비원이 필요한 수를 각각 계산해 더 큰 값을 출력하는 것이다. col, row = map(int, input().split()) castle = [] for _ in range(col): castle.app..
구현: 백준 2851 파이썬(Python) 문제: https://www.acmicpc.net/problem/2851 2851번: 슈퍼 마리오 첫째 줄에 마리오가 받는 점수를 출력한다. 만약 100에 가까운 수가 2개라면 (예: 98, 102) 마리오는 큰 값을 선택한다. www.acmicpc.net 풀이: mush = [] for _ in range(10): mush.append(int(input())) mario, i = 0, 0 while(i 100): if(abs(100-prev) >= abs(100-current)): mario = current break else: mario = prev break mario += mush[i] i ..
구현: 백준 1157 파이썬(Python) 문제: https://www.acmicpc.net/problem/1157 1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net 풀이: word = input() word = list(word.upper()) alphabet = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'] cnt = [] cnt.extend([0] * 26) for i in word: for j ..
구현: 백준 2750 파이썬(Python) 문제: https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 풀이: n = int(input()) arr = [] for i in range(n): arr.append(int(input())) arr.sort() for i in range(n): print(arr[i])
반응형

티스토리툴바