목록코딩 문제/LeetCode (22)

늘 겸손하게

LeetCode 1277 - Count Square Submatrices with All Ones

안녕하세요 besforyou 입니다 이번 글에서는 LeetCode 문제 1277번 풀이를 써보겠습니다 문제 풀이 방법 1. 그냥 다 찾아보는 방법 정사각형의 개수를 찾아야 하는 문제이다. 우선 m과 n 중 작은 숫자를 min_side라고 하고, 한 변의 길이가 1인 정사각형부터 한 변의 길이가 min_side인 정사각형을 2차원 배열에서 다 찾아본다. 2차원 배열 안에서 인덱스 i, j를 정사각형의 왼쪽 위 꼭지점이라고 가정하고 한 변의 길이가 l이라고 가정하자 그러면 i, j ~ i, j+l / i + l , j ~ i + l , j + l / i , j + l ~ i + l , j + l 안쪽의 숫자가 모두 1이면 정사각형인 것이다. 이를 반복문으로 구현한다. 코드 1 2 3 4 5 6 7 8 9 1..
코딩 문제/LeetCode 2021. 8. 30. 14:03
LeetCode 746 - Min Cost Climbing Stairs ( C++ )

문제 풀이 DP (Dynamic Programming) 문제이므로 기록해둔 과거 계산 값을 이용해서 현재 값을 계산해야 한다. i번째 계단까지 올라가는데 최소한의 cost를 기록하자. i번째 계단을 올라갈때 계단을 한 칸 올라가거나, 두 칸 올라갈 수 있으므로, cost [i-1]와 cost [i-2] 중 작은 값을 cost [i]에 더해준다. cost의 마지막 원소까지 계산하고, 뒤에서 첫번째 원소 값과 두 번째 원소 값 중 작은 값을 정답 값으로 반환한다. + dp를 기록할 새로운 배열을 만들 필요가 없으므로 주어진 cost 배열을 dp에 이용하여 메모리 사용량을 줄이자 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution { public: int minCostClim..
코딩 문제/LeetCode 2021. 8. 28. 11:39
LeetCode 118 - Pascal's triangle ( C++ )

처음으로 한방에 풀어버린 dp 문제네요 문제 풀이 numRows의 범위가 1 이상 30 이하이므로 파스칼의 삼각형을 미리 만들어버리고 numRows값에 따라 알맞은 vector
코딩 문제/LeetCode 2021. 8. 26. 10:30
LeetCode Q - Broken Calculator ( Java )

February LeetCoding Challenge 2021 ( Week 3, day 21 ) Q : Broken Calculator 문제 해설 계산기가 고장나 곱하기 2 와 빼기 1 밖에 되지 않는다. 화면에 표시되는 숫자 X를 Y로 바꾸기 위한 최소한의 계산 횟수를 반환하라. 문제 풀이 거꾸로 풀자. 2로 나누기 를 작업 1 이라 하고 1 더하기 를 작업 2 라고 하자 1. Y 값을 X 값보다 작아질때까지 2로 나눈다. (작업 1) 2로 나누다가 Y값이 홀수가 된다면 +1 (작업 2) 작업 1 과 작업 2 의 횟수를 기록 2. Y 값이 X 값보다 작아지면 작업 1 과 작업 2의 횟수에 X - Y 값을 더해 반환 작아진 Y 값을 X 값과 같게 하려면 작업 2 를 X - Y 번 해야하므로.. 1 2 3..
코딩 문제/LeetCode 2021. 2. 22. 12:03
이전 Prev 1 2 3 4 5 6 Next 다음