Techbrad

등굣길 문제 풀이: BFS와 DP의 비교문제 설명어떤 학교에서는 학생들이 집에서 학교로 갈 때, ( m \times n ) 크기의 격자 모양 마을을 지나야 합니다. 학생들은 오른쪽 또는 아래쪽으로만 이동할 수 있으며, 일부 칸에는 물웅덩이가 있어 지나갈 수 없습니다. 좌측 상단 ( (1,1) )에서 우측 하단 ( (m,n) )까지 갈 수 있는 최단 경로의 수를 구하세요. 결과는 ( 1,000,000,007 )로 나눈 나머지를 반환합니다.제한사항격자의 크기 ( m )과 ( n )은 ( 1 ) 이상 ( 100 ) 이하인 자연수입니다.물웅덩이는 ( 0 )개 이상이며, 위치는 ([x, y]) 형태로 주어집니다.시작점과 도착점은 물웅덩이가 아닙니다.입출력 예mnpuddlesresult43[[2, 2]]4BFS 풀..

">  문제문제 설명N×M 크기의 배열로 표현되는 미로가 있습니다.예시:1 0 1 1 1 11 0 1 0 1 01 0 1 0 1 11 1 1 0 1 1미로에서 '1'은 이동할 수 있는 칸을 나타내고, '0'은 이동할 수 없는 칸을 나타냅니다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하세요. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있습니다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함합니다.입력첫째 줄에 두 정수 N, M (2 ≤ N, M ≤ 100)이 주어집니다. 다음 N개의 줄에는 M개의 정수로 미로가 주어집니다. 각각의 수들은 붙어서 입력으로 주어집니다.출력첫째 줄에 지나야 하는 ..

https://www.acmicpc.net/problem/1309  풀면서 어려웠던 점1. DP 테이블을 만들면서 사자를 한마리도 배치하지 않는 경우를 생각해내기 힘들었다.2. 메모리 초과 DP 테이블에서 한마리도 배치않는 경우 0, 1에 배치할 경우 1, 2에 배치할 경우 2로 정한 후에 풀게되면 수월하게 풀 수 있었다.그리고 int 형은 4Byte라 문제가 없어보이는데 왜 메모리 초과가 발생하는지에 대해 의문이다. 혹시라도 지나가다가 명확히 아시는 분이 있으면 댓글을 부탁드립니다. ㅜ.ㅜ N이 100,000이 최대이니까 300,000 개의 int가 있고 이는 1,200,000 byte이고 1.2M 정도 밖에 안되지만 무슨 이유일까... 아무튼 dp를 계산해줄 때 9901을 나눈 나머지를 사용하면 된다..

문제를 풀었지만 정말 복잡하게 풀었다... 그리고 메모리 초과가 나서 코드를 살펴보니 del의 경우 O(N)이기 떄문에 for 문과 함께 전체적으로 O(N^2) 이기 때문에 효율적이지 못한 코드이다. 요새 코딩테스트를 보면서 메모리 효율적으로 사용해야하는 코드가 필요하다는 것을 절실히 느낀다.import syss = list(sys.stdin.readline())n = int(sys.stdin.readline())c_idx = len(s)for _ in range(n): input_ = list(map(str, sys.stdin.readline().split())) if input_[0] == "L": # 왼쪽 if c_idx == 0: # 커서가 맨 왼쪽에 있다면 ..