클라우드 낚시꾼

제한 조건과 설계 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 있어, 그 배추들 역시 해충으로부터 보호가 가능하다. 1은 배추가 심어진 땅, 0은 배추가 없는 땅이다. 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그래프 탐색 문제이다. DFS로 탐색하기에는 그래프 크기가 2500이므로 RecursionError가 뜰 수도 있을 거 같아 BFS가 좋아 보인다. 자연어 알고리즘과 코드 1. 데이터를 입력 받는다 2. 배추 지점은 cabbage_locations에 저장한다. 3. 각 배추 지점을 시작 지점으로 BFS 탐색을 한다. BFS..

문제 해석 미로 찾기 문제와 비슷하다. 1 ≤ R, C ≤ 500 이므로 최대 250000 크기의 그래프가 생성될 수 있다. 시간 제한은 2초이므로 O(N^2) 이하가 적절해 보인다. 양(S)은 가만히 있고, 늑대(W)가 움짇인다. 늑대가 양을 잡아 먹는 그 순간의 지점에 울타리 D를 설치 해야 한다. 스페셜 저지 문제이므로 쉽게 생각하면, 모든 빈 공간에 울타리 D를 설치하면 된다. 늑대와 양이 붙어 있는 그래프는 어떤 수를 써도 늑대를 막을 수 없다. 자연어 알고리즘과 코드 그래프 정보를 입력 받는다. 그래프 요소에 차례 차례 접근한다. if 요소 빈 공간 -> 빈 공간에 울타리를 친다. if 요소가 늑대 -> 상,하,좌,우로 양 있는지 확인한다. 만약, if 양이 있다. -> 0을 출력하고 즉시 종..

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

시간 복잡도와 공간 복잡도 N과 M의 최댓값은 100이기에 미로의 최대 크기는 10000이다. 미로 탐색을 10000번 하더라도 1초에 2000만번 연산이 가능한 Python3에 10000번의 연산은 그리 무거운 연산이 아니다. 시간 복잡도는 O(n^3) 이상만 아니면 될 거라고 생각했다. 자연어 알고리즘과 코드 참고) 2차원 리스트 graph의 요소 값이 1이면 처음 방문한 좌표, 0이면 벽, 음수면 맵 범위 밖이다. 만약, graph의 좌표 값이 2이상 양수면 시작 점으로부터 그 좌표까지의 거리를 의미한다. 1. 미로 그래프와 상하좌우 방향을 지정하는 리스트를 생성한다. 2. 시작 지점을 0,0으로 설정하여 미로 탐색을 시작한다. 3. queue에 시작 지점 좌표를 append 한다. 4. qeueu..

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

시간 복잡도와 공간 복잡도(런타임 에러 RecursionError) BFS, DFS의 시간 복잡도는 O(V+E)이다. 노드의 개수는 최대 100000개이고 간선의 개수는 99999개이기에 O(199999)가 최악의 시간 복잡도이다. Python3는 1초에 2000만번 연산이 가능하기에 O(199999)가 문제가 되지 않아 보이지만, Python3 기준 최대 재귀 깊이는 1000이기에 199999번 재귀호출 할 경우 RecursionError가 발생한다. 그래서 재귀 호출을 이용하는 DFS보다는 반복문 베이스인 BFS를 이용해서 이 문제를 해결해야 한다. 자연어 알고리즘과 코드 1. 입력을 받고 조건대로 Graph와 방문 테이블을 생성한다. 2. bfs 함수를 정의한다. 3. bfs 함수 내부에 부모 노드..

시간 복잡도와 공간 복잡도 입력 조건에 "첫째 줄에 정점의 개수 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..