본문 바로가기
728x90
반응형

Python169

2022.04.12 [백준] (python 파이썬) 철로 https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 풀이 아래 문제는 처음 해결방법이 떠오르지 않아 구글링을 통해 여러 코드를 참고하여 해결하였다. 우선 각 정수 쌍을 오름차순 정렬하여 arr배열에 저장했다. 이후, arr배열을 x[1]을 기준으로 오름차순 정렬했다. 이유는 철로를 확인할 때, 가장 작은 위치부터 확인하기 위해서 이다. 그리고 집, 사무실의 거리가 d보다 큰 경우는 제외하고 h_o.. 2022. 4. 12.
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.
728x90
반응형

티스토리툴바