DFS/BFS 정복기6 -큐의 길이만큼만 순회해야한다면..-

1. 문제 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net S에 존재하는 고슴도치가 탈출지점 D로 이동해야하는데, 지도상에 물이 있고, 이 물도 1초에 1번씩 상하좌우로 퍼져나간다. 여기서 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다 가장 빠른 시간에 탈출할려면 얼마나 걸리는지 구하세요. 2. 나의 풀이 풀이는 전형적인 BFS로 시작점, 도착점을 찾고 물도 퍼져나가기 때문에 물이 어디에 있는지도 큐에 담아놔야겠다 r,c = map(int,stdin.r..

• format_list_bulleted DFS BFS 정복기
• · 2022. 9. 13.
• textsms

정수론 - 합과 곱은 왜 계속 나눠도 문제가 없는가? -

1. 문제 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 00과 1을 이용해서 만들 수 있는 길이 n의 이진수열의 개수를 15746으로 나눈 나머지를 구하는 문제 2. 풀이 가능한 경우의 수를 나열해서 규칙을 찾으면 간단해진다 1,2,3,5,8,...로 이어져서 피보나치 수열이라는 느낌이 온다 그래서 한번 해보면 from sys import stdin n = int(stdin.readline()) dp = [0] * 1000001 dp[1] = 1..

• format_list_bulleted 정수론
• · 2022. 9. 9.
• textsms

다이나믹 프로그래밍 정복기4 - 규칙을 찾으면 되는 쉬운문제들1-

1. 문제1 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 나선형으로 정삼각형을 만들었을때, 정삼각형의 가장 긴 변의 길이를 구하는 방법은? 2. 풀이1 이런 문제는 그냥 몇개 나열해보면서 규칙을 찾으면 되겠다고 생각하는게 제일 편하다 이런 규칙 찾는 문제가 다이나믹 프로그래밍의 가장 기본형태라고 생각하면 된다 그래서 몇개 해보면 규칙이 나올거야 p(1)부터 p(10)까지는 1,1,1,2,2,3,4,5,7,9라고도 친절하게 나와있고 그림에서 p(1..

• format_list_bulleted 다이나믹 프로그래밍
• · 2022. 9. 9.
• textsms

DFS/BFS 완전정복기5 -3차원 배열을 사용해야하는 경우-

1. 문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net N*M 행렬에서 (0,0)에서 출발하여 (n-1,m-1)로 이동하는 최단 거리를 구하는 문제지만, 벽으로 표현되는 1을 뚫고 지나가서 거리가 줄어든다면 단 1번만 허용할때, 최단거리를 구한다면..? 2. 풀이 bfs로 벽이 있더라도, 단 1번도 뚫지 않았다면 1번만 뚫고 1번 뚫었다면 그 뒤로는 벽을 지나가지 않도록 bfs 탐색하면 될것 같았는데 2차원 배열로 ..

• format_list_bulleted DFS BFS 정복기
• · 2022. 9. 9.
• textsms

DFS/BFS 완전정복기4 -상하좌우로 움직이지 않는 경우-

1. 문제1 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 나이트가 최소 몇번 이동하면 주어진 칸으로 이동할 수 있는지 구하는 문제 어렵게 생각할 필요 전혀 없이, 문제에서 주어지는 1번에 이동할 수 있는 경우를 모두 델타배열에 저장하여, 그것을 순회하면 된다 2. 풀이 어렵게 생각할 필요 전혀 없고 일반적인 bfs 흐름으로 가다가 상하좌우 델타배열 [[0,1],[1,0],[0,-1],[-1,0]]을 나이트가 이동할 수 있는 칸으로 바꾼 델타배..

• format_list_bulleted DFS BFS 정복기
• · 2022. 9. 7.
• textsms

다이나믹 프로그래밍 - Kadane algorithm

1. 문제 https://www.acmicpc.net/problem/1912 1912번: 연속합첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.www.acmicpc.net 주어진 n개의 임의의 수열에서 1개 이상의 연속된 부분 수열을 선택할 때, 가장 큰 합을 출력  2. 나의 풀이 단순한 규칙, 점화식으로는 풀기 어렵다 메모리, 시간제한 문제로 $O(N^2)$으로도 통과하기 어렵다 처음에 i번째부터 j번째까지 수열의 합을 dp[i][j]에 저장해서 테이블을 완성하려고 했는데 n의 최대가 100000이라 10만*10만 만들자 마자 메모리 초과 from sys impor..

• format_list_bulleted 다이나믹 프로그래밍
• · 2022. 9. 4.
• textsms