Save my data

재귀를 이용하여 풀 수 있는 쉬운 문제이다. 예전에 재귀함수쪽을 학습할 때 비슷한 문제를 푼 적이 있어서 쉽게 풀었다. import sys s = sys.stdin.readline().strip() l = len(s) - 1 def palindrome(front:int, rear:int, s:str) -> bool: if front >= rear: return 1 if s[front] == s[rear]: ans = palindrome(front + 1, rear - 1, s) return ans else: return 0 print(palindrome(0, l, s)) 자꾸 틀렸다고 나와서 코드를 이리저리 바꿔가면서 했는데도 안됬다. 한 네 번째 시도를 하고 다시 코드를 보니 sys.stdin.read..

BFS 문제이다. 부끄럽지만 계속 메모리 초과가 나서 구글링해서 올바른 해답을 찾은 문제이다. 실전에서는 이런 일이 발생하지 않도록 더 실력을 키워야겠다. 우선 문제가 트리 구조를 떠올리면 쉽게 풀 수 있을것이라고 생각은 했다. 어떤 입력 v 가 시작값으로 주어지면, 그 입력 v 에 대해 v - 1, v + 1, v * 2 가 v 의 자식 노드로 생겨나면서 노드의 값이 k 와 일치할 때, 그 노드가 속해있는 레벨을 구하면 되는 문제였다. DFS와 BFS에 대해 얼마 전에도 포스팅 한 적이 있는데, BFS는 트리의 각 레벨에 있는 모든 노드를 queue에 넣고 앞에서부터 pop 하면서 너비 우선으로 탐색하는 방식이다. 여기서 처음에 아이디어를 얻은 것은, queue에 각 층의 마지막 계산값들을 넣고 그 뒤..

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차원 배열로 만들고 온갖 헛수고를 했는데, 다시 생각해보면 문제풀이를 시작한 극초반에 다양한 아이디어가 스쳐가던 중 배낭 알고리즘 활용하는 방법이 뇌리에 스쳤었는데 그것을 구체화하지 못했던 것이 아쉽게 느껴진다. 난 항상 ..