728x90 반응형 Python3173 2022.04.09 [백준] (파이썬 python) 빙산 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 풀이 이 문제는 bfs를 이용하여 문제를 해결하였다. 문제에서 주어지는 빙산의 배열을 arr에 담고 bfs를 돌려 각 빙산이 몇개의 바다에 접해 있는지 체크하여 빙산의 위치에 해당하는 melt배열에 접해있는 수를 저장해 주었다. 바로 arr배열에서 빙산이 녹은 값을 업데이트해주지 않은 이유는 만약 빙산이 녹아 바다(0)이 되었을 때, 다음의 빙산에 영향을 주기 때문에 bfs를 모두 돌고 난 .. 2022. 4. 9. 2022.03.29 [백준] (python 파이썬) 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 이 문제는 최단 거리를 구하는 bfs문제이다. 여기서 한가지를 더 생각해야 한다. 1,1에서 n,m까지 이동하면서 벽을 하나 부수고 이동할 수 있다. 그래서 벽을 부수지 않았을 때, 벽을 부수었을 때, 총 2가지 경우를 생각해 주어야 한다. 그래서 기존의 2차원배열에서 2가지 경우를 더한 3차원배열을 만들어 문제를 해결해야한다. 그래서 3차원 배열 visited을 만.. 2022. 3. 29. 2022.03.22 [백준] (python 파이썬) 가장 큰 정사각형 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 문제를 해결하기 위해 우선 arr배열에 문제에서 주어진 배열을 넣었다. 그리고 dp배열을 (n+1)X(m+1)크기로 만들었다. 이유는 이전 값을 비교해야하기 때문이다. 만약 arr[i][j]가 0이면 정사각형을 만들 수 없으므로 넘어가고 1이면 dp[i+1][j],dp[i][j+1],dp[i][j]을 비교하여 가장 작은 값의 +1 값을 dp[i+1][j+1]에 넣어준다. dp[i+1][j+1]에는 arr[i][j]를 정사각형의 우측하단 꼭짓점으로하여 만들수 있는.. 2022. 3. 22. 2022.03.18 [백준] (python 파이썬) 팰린드롬? https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이 우선 이 문제를 풀기 위해선 팰린드롬이 무엇인지 알아야 한다. 팰린드롬은 앞에서 부터 읽거나 뒤에서 부터 읽어도 같은 문장을 말한다. 예를 들면 aba, 131과 같은 문장이다. 이 문제를 다이나믹 프로그래밍으로 풀기 위해 2차원 배열을 사용했다. dp[시작인덱스][종료인덱스]로 해서 해당 시작인덱스에서 종료인덱스까지의 문장이 팰린드롬이면 True 아니면 False로 선언했다. 그리고 2중 for문을 이용해서 각 문장이 팰린드롬인.. 2022. 3. 18. 이전 1 ··· 8 9 10 11 12 13 14 ··· 44 다음 728x90 반응형
