클라우드 낚시꾼

제한 조건과 설계 1. 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. -> 노드가 최대 100개 이므로 메모리와 시간 제한이 널널하다. 2. 탐색 시작 노드에서 특정 노드에 도달하는 데 까지 거리를 묻는 문제이다. -> DFS 자연어 알고리즘 정보를 입력 받는다. 시작 노드와 탐색 노드를 설정하여 DFS 탐색을 시도한다. DFS 탐색 다음 노드로 이동할 때 마다 이동 거리를 1 증가시킨다. 특정 노드에 도달하면 그때 까지의 이동 거리를 출력하고 프로그램을 종료한다. 노드를 재방문할 때는 이동 거리를 1 감소시킨다. 3번에서 특정 노드에 도달하지 못했다면 -1을 출력하고 종료한다. 코드 import sys input = sys.stdin.readline node..

제한 조건과 설계 N이 2000이하이므로 DFS를 쓸 수 있음. 무방향 그래프. 시간 제한과 메모리 제한도 넉넉하다. DFS 탐색으로, 문제의 조건을 만족 시켜야 한다. 자연어 알고리즘 그래프 생성, 방문 테이블, 노드 목록 생성 각각의 노드를 시작 지점으로 DFS 탐색 DFS 탐색 1) 탐색 노드 방문 처리 후, route에 탐색 노드 push 2) route의 길이가 5이면 -> 1을 출력하고 종료 3) 인접 노드 중 아직 방문하지 않은 노드가 있다면 -> 그 인접 노드로 DFS 탐색 4) 인접 노드 모두를 방문했다면 -> route에서 현재 탐색 노드를 pop 한 뒤, 미방문 처리 1 ~ 3 이 종료될때 까지 반복 0 출력 후 종료( ABCDE 관계가 나왔다면 3-(2)에서 종료) 코드 impor..

제한 조건과 설계 1. 무방향 그래프다. 2. 정점의 개수가 1000개 이하다. 3. 시간 제한과 메모리 제한이 굉장히 널널하다. 4. 2번과 3번을 고려했을 때 DFS가 좋아 보인다. 자연어 알고리즘 무방향 그래프, 방문 테이블, 노드 목록를 생성한다. 연결 요소의 개수 cnt를 0으로 초기화 하여 선언한다. 노드 목록 하나 하나를 시작 지점으로 설정하여 DFS 탐색을 시도한다. 노드가 이미 방문된 지점이면 -> continue 노드가 아직 방문되지 않은 지점이면 -> DFS 탐색 DFS 탐색을 리스트 자료구조를 이용한 Stack 또는 재귀 함수를 이용한 Stack을 이용해 구현한다. 가장 중요한 POINT: 스택에 PUSH된 순간 그 지점은 방문될 지점이므로 그 즉시 방문 테이블에 방문 처리를 한다...

시간 복잡도와 공간 복잡도 한 변의 길이가 최대 25인 정사각형이 주어졌으므로 최악의 시간 복잡도는 O(625)였다. 기본 연산이 1000번을 넘어가지 않기 때문에 이 문제는 DFS 재귀 알고리즘을 쓸 수 있겠다고 생각했다. 알고리즘과 코드 시간 복잡도를 분석했을 때 언급한 것처럼 이 문제를 DFS 재귀 알고리즘으로 풀기로 했다. 자연어 알고리즘은 다음과 같다. 1. 그래프를 생성한다. 2. 모든 좌표 각각을 시작 지점으로 삼아 DFS 재귀 알고리즘을 호출한다. 3. DFS 탐색을 시작한다. 좌표가 범위 밖이면 return False로 즉각 종료 집이 있으면(1) 방문한 집의 수(cnt)를 1 증가시킨다 방문한 집이 재방문 되는 것을 막기 위해 값을 0으로 재할당 상,하,좌,우에 대해 DFS를 호출하고 ..

시간 복잡도와 공간 복잡도 문제 조건에 따르면 최대 노드의 개수는 10000 개, 최대 간선의 개수는 100000 개였다. 최악의 시간 복잡도가 O(110000)이고 시간 제한이 5초라서 시간 복잡도는 여유롭다는 판단을 내렸다. 하지만, 노드랑 간선의 개수가 1000개를 넘어가기에 DFS로 구현하면 RecursionError가 발생하기에 BFS로 구현하기로 마음먹었다. 자연어 알고리즘과 코드 1. 방향 그래프를 만든다. 2. 시작 노드를 1~n 순차적으로 설정하여 BFS 탐색을 한다. 3. 시작 노드를 x으로 설정하여 BFS 탐색을 할 때, 탐색된 노드의 개수가 해킹할 수 있는 컴터의 개수이다. 4. 3번의 정보를 리스트 a에 담고 max를 찾는다. 5. 리스트a에서 max를 가진 요소의 인덱스 탐색하고..

시간 복잡도와 공간 복잡도 입력 조건에 "첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다." 라는 조건이 있었다. DFS와 BFS의 시간 복잡도는 O(|V+E|)이다. 그래서 문제의 조건에 따르면 최악의 경우 O(11000)이라는 시간 복잡도가 나온다. 시간 제한이 2초이고 파이썬이 1초에 2000만번 연산한다는 점을 고려해 봤을 때 시간 복잡도는 굉장히 널널하다. 알고리즘 문제에서 요구하는 것은 정보를 입력받아 그래프를 만들고, 낮은 노드를 우선 방문하는 조건으로 DFS, BFS 탐색하는 것이기에 알고리즘은 굉장히 단순하다. 아래는 자연어 알고리즘과 파이썬 코드이다. 1. 그래프 정보를 입력받아 저장한다. 2..

시간 복잡도, 공간 복잡도 컴퓨터의 수가 100대고 시간 제한과 메모리 제한은 아래와 같았다. 1 초 128 MB 파이썬은 1초에 2000만번 연산이 가능하다. N의 최대가 100이라는 것을 고려해봤을 때 시간복잡도는 여유롭다고 판단했다. 알고리즘 그래프가 주어졌고 "1번 컴퓨터가 감염되어서 2,3,5,6 컴퓨터도 감염된다."를 언급한 것으로 보아 그래프 탐색 유형임을 눈치챘다. 또한, 탐색 순서를 구체적으로 명시하지는 않았지만 감염 컴퓨터를 2,3,5,6으로 나열한 것으로 보아 DFS 탐색이라고 예상했다. 다음, 자연어 알고리즘과 코드다. 1. 입력을 받고 그래프를 만든다. 2. DFS로 그래프를 탐색한다. 3. 1번 컴퓨터로부터 감염된 컴퓨터를 출력한다. # dfs 탐색 def dfs(graph, v..

BFS를 쉽게 말하자면? 위 그래프의 시작 노드는 1 이고, 숫자가 낮은 노드부터 탐색한다고 가정하자. 이 가정 아래, 그래프를 가장 가까운 노드부터 탐색하면 1 -> 2 -> 3 -> 5 -> 4 -> 6 라는 결과를 얻을 수 있다. 이것이 BFS이다. BFS의 가장 주요한 모토는 "그래프를 가까운 노드부터 탐색하자." 라는 것을 잊지 말자! BFS 알고리즘 먼저, BFS를 구현하기 위해서는 FIFO 구조인 큐(Queue) 자료구조를 사용해야 한다. 인접한 노드를 반복적으로 큐에 넣게되면, 자연스럽게 먼저 들어온 것이 먼저 나가게 되어 가까운 노드부터 탐색을 진행하게 된다. 알고리즘의 정확한 동작방식은 아래와 같다. 1) 탐색 시작 노드를 Queue에 Enqueue 하고 방문 처리한다. 2) Front..