본문 바로가기

알고리즘141

[Baekjoon] 1080. 행렬 ( 탐욕 알고리즘 ) # Problem 0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오. 행렬을 변환하는 연산은 어떤 3*3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 -> 1, 1 -> 0) 입력 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. 출력 첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다. # Solution n,m = map(int,input().split()) a = [list(map(int,input()))for _ in ran.. 2021. 5. 16.
[Baekjoon] 2437. 저울 ( 탐욕 알고리즘) # Problem 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다. 무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오. 예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다. 입력 첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 무.. 2021. 5. 16.
[Baekjoon] 16676. 근우의 다이어리 꾸미기 # Problem 곧 2018년이 끝나고, 2019년이 온다. 근우는 2019년에는 꼭 다이어리를 쓰기로 했다. 하지만, 처음 써보는 다이어리에 쓸 내용이 없어 고민하던 중 자신의 목표 연봉을 다이어리 앞에 쓰기로 했다. 다이어리를 쓰는 사람은 알겠지만 예쁜 다이어리의 핵심은 스티커다. 그렇기 때문에 근우는 목표 연봉을 손으로 쓰지 않고, 스티커로 붙이려고 한다. 목표연봉이 100이라면 [1] [0] [0]과 같이 붙이는 것이다. [1]이란 1이 써져있는 스티커로, 다른 숫자에 대해서도 동일한 규칙이 적용된다. 근우는 자신의 연봉 최댓값이 N임을 안다. 그렇기에 근우는 0부터 N까지의 수를 하나씩 스티커를 통해 모두 표현하고자 한다. 최댓값 N이 10이면 만드는 과정은 다음과 같다. 스티커 더미에서 [0.. 2021. 5. 15.
[Baekjoon] 12849. 본대 산책 (DP) # Problem 숭실 대학교 정보 과학관은 캠퍼스의 길 건너편으로 유배를 당했다. 그래서 컴퓨터 학부 학생들은 캠퍼스를 ‘본대’ 라고 부르고 정보 과학관을 ‘정보대’ 라고 부른다. 준영이 또한 컴퓨터 학부 소속 학생이라서 정보 과학관에 박혀있으며 항상 본대를 가고 싶어 한다. 어느 날 준영이는 본대를 산책하기로 결심하였다. 숭실 대학교 캠퍼스 지도는 아래와 같다. (편의 상 문제에서는 위 건물만 등장한다고 가정하자) 한 건물에서 바로 인접한 다른 건물로 이동 하는 데 1분이 걸린다. 준영이는 산책 도중에 한번도 길이나 건물에 멈춰서 머무르지 않는다. 준영이는 할 일이 많아서 딱 D분만 산책을 할 것이다. (산책을 시작 한 지 D분 일 때, 정보 과학관에 도착해야 한다.) 이때 가능한 경로의 경우의 수를.. 2021. 5. 8.
[Baekjoon] 1915. 가장 큰 정사각형 (DP) # Problem n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오. 위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다. 입력 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. 출력 첫째 줄에 가장 큰 정사각형의 넓이를 출력한다. # Solution n,m = map(int,input().split()) a = [[0]*(m+1) for _ in range(n+1)] dp = [[0]*(m+1) for _ in range(n+1)] #dp[i][j] = i,j 까지 왔을 때, 가장 큰 정사각형의 한 변의 길이 #dp[i][j] = min(dp[i-1][j],d.. 2021. 5. 8.
[Baekjoon] 2167. 2차원 배열의 합 (DP) # Problem 2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i, j) 위치는 i행 j열을 나타낸다. 입력 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(i ≤ x, j ≤ y). 출력 K개의 줄에 순서대로 배열의 합을 출력한다. 배열의 합은 231-1보다 작거나 같다. # My Answer n,m = map(i.. 2021. 5. 7.
반응형

티스토리툴바