1. 문제 https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 출력예시에 맞게 챗봇의 응답을 출력하는 문제이다. 문제 이름에서도 알 수 있듯이 재귀함수를 활용해야 한다. 입력과 출력의 예시는 다음과 같다. 2. 풀이 입력받은 숫자 T는 재귀함수를 몇 번 호출하는지를 나타내는 숫자이다. 최초로 함수가 한번 호출되고, 재귀로 T번 호출되기 때문에 함수는 총 T+1번 실행이 되는데 이 부분을 생각하는 게 포인트였다. 우선 주어진 예시에서 각 문장이 어..

1. 문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 문제이다. 2. 풀이 BFS 알고리즘을 활용하여 풀이할 것이다. BFS 하면 queue바로 떠올려야 하고 queue하면 deque가 바로 떠올라야 한다. 행렬 역시 그래프로 생각할 수 있으므로 주어진 행렬을 그래프에 저장한다. 그래프에서 (N, M)까지 가는 길은 연결되어 있으므로 BFS 함수는 한번만 호출해주면 된다. BFS..

1. 문제 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 1로 구성된 영역이 총 몇개가 있는지 찾는 문제이다. 상, 하, 좌, 우 중 하나가 연결되어 있다면 인접한 것이고 같은 영역으로 카운트 된다. 하지만 4방향 중 어느 하나에도 연결되어 있지 않다면 인접하지 않은 것이고 다른 영역으로 카운트 해줘야 한다. 2. 풀이 BFS를 이용하여 풀이할 것이므로 deque를 활용할 것이다. 그래프를 탐색하기 위해 x, y좌표를 변화시킬 때 사용할 리스트가 필요하다..

1. 문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 저번에 풀었던 문제이다. 지난번 포스팅 링크: https://daily-stack.tistory.com/70 [Python]Baekjoon 2606번: 바이러스(BFS) 1. 문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨..

1. 문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 1번 컴퓨터와 연결된 컴퓨터가 몇 개인지를 구하는 문제이다. 첫 그래프 탐색 문제이다. 2. 풀이 우선 BFS를 이용하여 풀이하여 보자. 파이썬에서 queue를 구현할 때는 list가 아닌 deque를 활용하는데 그 이유는 시간 복잡도 측면에서 deque가 유리하기 때문이다. 리스트를 활용하여 큐를 구현할 수는 있지만, 큐의 연산을 수행할 때(리스트의 앞쪽에서 요소를 삭제하거나 추가할 때) ..

간단한 DFS 구현해 보기 깊이 우선 탐색 알고리즘인 DFS는 스택 자료구조에 기초한다는 점에서 구현이 간단하다. 실제로는 스택을 쓰지 않아도 되며 탐색을 수행함에 있어서 데이터의 개수가 N개인 경우 O(N)의 시간이 소요된다는 특징이 있다. 또한 DFS는 스택을 이용하는 알고리즘 이기 때문에 실제 구현은 재귀 함수를 이용했을 때 매우 간결하게 구현할 수 있다. 예제 코드는 다음과 같다. # DFS 메서드 정의 def dfs(graph, v, visited): # 현재 노드를 방문 처리 visited[v] = True print(v, end= '') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not visited[i]: dfs(graph , i , visi..