2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net ** 문제 유형 DFS, BFS ** 풀이 단순히 시작 정점에서부터 도달할 수 있는 노드의 수를 계산하는 문제 DFS or BFS를 이용하여 방문하게 되는 노드의 개수를 계산 컴퓨터의 수가 적으므로, DFS를 이용해 빠르게 문제를 푸는 것이 유리 def dfs(now_pos): global count visited[now_pos] = True for next_pos in adj[now_pos]: if not visited[next_pos]: count += 1 dfs..

1236번: 성 지키기 첫째 줄에 성의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 성의 상태가 주어진다. 성의 상태는 .은 빈칸, X는 경비원이 있는 칸이다 www.acmicpc.net ** 문제 유형 순차 탐색 ** 풀이 모든 행과 열에 한명 이상의 경비원이 있어야 함 행 기준/열 기준으로 필요한 경비원의 수를 계산하여 더 큰 수를 출력 # 방법 1 n, m = map(int, input().split()) array = [] for _ in range(n): array.append(input()) row = [0] * n column = [0] * m for i in range(n): for j in range(m): if arr..

1668번: 트로피 진열 민식이는 “오민식”이라는 팀이름으로 수없이 많은 로봇대회를 우승했다. 따라서 민식이의 집에는 트로피가 많다. 민식이는 트로피를 어떤 선반 위에 올려놨다. 이 선반은 민식이의 방문을 열 www.acmicpc.net ** 문제 유형 순차 탐색 ** 풀이 트로피의 개수 N이 최대 50이므로, 단순히 구현하면 됨 def ascending(array): # 오름차순으로 존재하는 원소의 개수 계산 now = array[0] result = 1 for i in range(1, len(array)): if now

1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net ** 문제 유형 순차 탐색 ** 풀이 가장 많이 등장한 문자열을 출력하는 문제와 동일 -> Set or Dictionary 자료형 사용 등장 횟수를 계산할 때는 Dictionary 자료형을 이용하면 효과적 n = int(input()) books = {} for _ in range(n): book = input() if book not in books: books[book] = 1 else: books[book] += 1 max_num = max(book..

1568번: 새 N마리의 새가 나무에 앉아있고, 자연수를 배우기 원한다. 새들은 1부터 모든 자연수를 오름차순으로 노래한다. 어떤 숫자 K를 노래할 때, K마리의 새가 나무에서 하늘을 향해 날아간다. 만약, 현 www.acmicpc.net ** 문제 유형 순차 탐색 ** 풀이 N이 최대 1,000,000,000 시간 복잡도 O(n^2) K가 반복적으로 증가하므로, 날아가는 새의 마리 수는 빠르게 증가 등차수열로 실질적인 시간 복잡도는 약 O(√n) 따라서 문제에서 요구하는 대로 단순히 구현 n = int(input()) k = 1 cnt = 0 while n > 0: # 모든 새가 날아갈 때 까지 if n

1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net ** 문제 유형 순차 탐색 ** 풀이 문서의 길이는 최대 2,500이고, 단어의 길이는 최대 50 시간 복잡도 O(NM)의 알고리즘으로 해결 가능 단순히 모든 경우의 수를 계산하여 문제 해결 가능 문서와 단어의 위치를 맞추어서 반복적으로 비교 # 방법 1 document = input() word = input() index = 0 result = 0 while len(document) - index >= len(word): # 문서에서 보고 있는 단어가 찾고자 하는..