Save my data

BFS로 풀 수 있는 문제이다. BFS의 queue에 집어넣고 빼면서 탐색하는 방식을 잘 이해하고 있다면 어렵지 않게 풀었을 것이다. 이 문제와 다른 기초 문제들간의 차별점은 예제 3번과 같이 시작점이 두 개가 되는 경우도 고려해야 한다는 점이다. 이 경우 시작이 되는 Queue 에 두 점의 좌표를 같이 넣어주면 양 방향에서 동시에 탐색을 시작한다. 그 외의 조건들은 단순히 반복문을 돌려서 검출해내도 되기 때문에 그다지 어려운 점은 아닌 것 같다. import sys from collections import deque M, N = map(int, sys.stdin.readline().split()) def bfs(box, start): mx = 0 dx = [-1, 0, 1, 0] dy = [0, 1,..

BFS, DFS로 풀 수 있는 연결 요소의 개수 찾기 문제이다. (DFS로 풀 때는 재귀함수로 푸는 경우가 많은데 재귀 깊이 제한으로 인한 에러를 조심할 것) 백준 1260 : DFS와 BFS (파이썬) 깊이 우선 탐색과 너비 우선 탐색 기초문제이다. 깊이 우선 탐색 - Depth First Search 트리나 그래프에서 임의의 분기를 마주칠 때 마다 어떤 노드에 어떤 형태의 분기가 있다는 것을 기억만 해 놓고 mhd329.tistory.com DFS, BFS 에 대한 기본 작동원리에 대해 자세하게 포스팅 한 적이 있으니 아래 코드가 이해되지 않는 경우 한 번 보고 오자. DFS 코드 : import sys sys.setrecursionlimit(10 ** 6) # 재귀 깊이 제한 해제 def dfs(x..

기초적인 탐색 문제이다. 이 문제는 BFS와 DFS 모든 방법으로 풀 수 있는 문제인데, 나는 어제 BFS를 활용한 탐색 문제를 풀었으니 오늘 이 문제는 DFS로 풀기로 했다. import sys apart = [] N = int(sys.stdin.readline()) for _ in range(N): apart.append([*map(int, sys.stdin.readline().strip())]) total = 0 cnt = 0 res = [] def dfs(x, y): global cnt if x = N or y = N: return False if apart[x][y] == 0: return False if apart[x][y] == 1: cnt += 1 apa..

BFS 를 이용한 탐색 문제이다. 미로의 탈출 가능한 최단 경로를 찾는 문제인데, 사방 탐색은 여러 가지 구현 문제를 풀었던 경험으로 쉽게 떠올릴 수 있었지만 탐색 후 올바른 경로에 대해 BFS를 적용하려고 하니 난해했다. 코드를 완성시킨 후 다시 리뷰하면서 파악해보니 눈에 좀 익으면서 어느 정도 파악이 되었는데, 정해진 범위 내에서 탐색을 진행하며 현재 보고있는 정점과 인접한 정점 중 이어진 곳 따라 탐색을 진행하면서 자신이 왔던 길이 아닌 앞으로 가야할 길의 좌표, 즉 자기가 왔던 곳을 제외한 인접정점들을 for 문을 통해 순서대로 queue 에 넣고 그 인접정점의 값에는 기존의 1 이라는 값 대신 (인접 정점의 기존 값 + 자기 자신의 값) 을 새로 넣어준다. queue 의 왼쪽에서 하나씩 꺼내며 ..

깊이 우선 탐색과 너비 우선 탐색 기초문제이다. 깊이 우선 탐색 - Depth First Search 트리나 그래프에서 임의의 분기를 마주칠 때 마다 어떤 노드에 어떤 형태의 분기가 있다는 것을 기억만 해 놓고 계속 내려간다. 그러다가 막다른 곳(자식 노드가 없는 노드 == 리프 노드) 을 마주하게 되면 전에 기록해놓았던 분기로 되돌아가서 그 분기부터 다시 파고들어가는 것을 그 그래프의 모든 노드를 방문할 때 까지 계속 반복한다. 말 그대로 깊이를 우선해서 탐색하는 방법이다. 너비 우선 탐색 - Breadth First Search 트리나 그래프에서 임의의 분기를 마주치면 분기 하위의 자식 노드들을 너비 방향으로 방문해간다. 어떤 분기에서 그 분기의 뿌리가 되는 부모 노드의 형제 노드들을 우선적으로 방문..

배낭 문제와 비슷한 원리로 풀리는 문제인데, 처음에 아이디어를 잘못 가져다가 고민을 하는 바람에 시간이 엄청 걸렸다. 한 번에 안 풀려서 방치하고 있다가 푸는데 거의 이틀이 걸렸다... 핵심 아이디어 : 내가 현재 몇 종류의 동전을 가지고 있다면, 그 때 그 동전들을 가지고 목표값을 만들 수 있는 모든 경우의 수를 저장하는 것 처음에 나는 dp에 경우의 수를 저장하지 않고 각 동전이 입력될 때 그것을 가지고 만들 수 있는 누적합 비슷하게 저장하려고 시도했었다. 그러기 위해서 dp 를 2차원 배열로 만들고 온갖 헛수고를 했는데, 다시 생각해보면 문제풀이를 시작한 극초반에 다양한 아이디어가 스쳐가던 중 배낭 알고리즘 활용하는 방법이 뇌리에 스쳤었는데 그것을 구체화하지 못했던 것이 아쉽게 느껴진다. 난 항상 ..

자주 등장했던 문제유형이다. 리스트 슬라이싱 후에 해당되는 부분만 매번 원본에서 바꿔주면 된다. import sys N, M = map(int, sys.stdin.readline().split()) basket = [0] + [i for i in range(1, N + 1)] for _ in range(M): i, j, k = map(int, sys.stdin.readline().split()) mid_to_rear = basket[k:j + 1] front_to_mid = basket[i:k] basket[i:j + 1] = mid_to_rear + front_to_mid print(*basket[1:]) 간단했던 구현문제

DP 문제이다. DP 문제는 반복의 맨 처음 단계에서 어떤 패턴을 찾으면 그 다음은 빠르게 풀린다. 그리고 항상 그걸 못 찾아서 문제다... 다만 확실히 DP 문제를 풀면 풀수록 뇌가 DP 화 되는 느낌이 있다. 나 같은 범재도 이런식으로 반복하면 그래도 요령이 생기는구나 싶어서 보람은 있었다. ※ 결국 노력과 반복이 답이다... 문제 풀이 아이디어 공유 : 줄 == 가로방향, 칸 == 세로방향 먼저 각 줄의 i 번째까지 누적합을 저장해 줄 dp 리스트를 만든다. 0 으로 마진을 두는게 편해서 인덱스 번호는 항상 1 부터 시작하게 만드는 편이다. 다른 사람들은 그렇게 안 한 사람도 있었다. 누적합의 패턴이 어떤지는 모르지만 여타 DP 문제가 그래왔듯 이번에도 비슷하겠거니 싶어서 일단 그렇게 만들었다. 2..