본문 바로가기

DP

[LEETCODE] 542. 01 Matrix 사용 알고리즘 DP 사용 풀이 로직 각 원소가 이웃한 가장 가까운 0과의 거리를 구해아한다. 최소값을 구해야하므로 dp를 inf로 두고 진행한다. 왼쪽 위부터 돌면서 왼쪽과 위쪽을 비교해 최소값 찾기 오른쪽 아래부터 돌면서 오른쪽과 아래쪽을 비교해 최소값 찾기 코드 어려웠던 점 처음에 matrix[i][j] == 1인 경우마다 bfs를 이용해 풀었는데, 무한루프로 잘 돌아가지 않았습니다. 더보기
[programmers] 땅따먹기 로직 - 계속 더해가면서 최대값을 찾는다. 이때, 바로 아래에 있는 값은 사용하지 못한다. - 위 -> 아래 가려면 아래 값을 "val = 아래값" 으로 지정해두고나서 더하면서 max값을 찾아야한다. - 아래 -> 위 가면 그냥 최대값을 찾으면 됨. 이때, 바로 위의 값을 제외한 리스트의 max값을 찾는다. 코드 주의할 점 1. DP사용하기! 더보기
[programmers] 정수 삼각형 로직 1. 가쪽에서 더해지는 값은 계속 더해진다. 2. 왼쪽, 오른쪽에서 더해질 수 있는 값 중 최대값을 더해준다. 코드 더보기
[programmers] N으로 표현 로직 1. 계산된 값들을 저장하면서 그 값들을 가지고와서 계산한다. -> DP사용 1번 사용 : 5 2번 사용 : 55, 5+5=10, 5-5=0, 5*5=25, 5/5=1 3번 사용 : 555, 5+5+5=15, 5+5-5=5, 5+5*5=30, 5+5/5=6, 5-5+5=5, 5-5-5=-5, 5-5*5=-20, 5-5/5=4, 5*5+5=30, 5*5-5=20, 5*5*5=125, 5*5/5=5, 5/5+5=6, 5/5-5=-4, 5/5*5=5, 5/5/5=0, 555 + 1번사용->2번사용, 2번사용->1번 사용(중복은 제거) 4번 사용 : 555 + 1번사용->3번사용, 2번사용->2번 사용, 3번사용->1번 사용(중복은 제거) 코드 주의할 점 1. num_ls에 넣을 때, x-y, y-x를 동.. 더보기

티스토리툴바