이숭간 공부기록

https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 문제유형 : DP 문제풀이 : 숫자X를 n번 사용해서 만들수있는 숫자 숫자 X를 n번 이어붙여서 만든 숫자 숫자 X를 i번 사용해서 만들수있는 숫자와 숫자 X를 n-i번 사용해서 만들수 있는 숫자의 사칙연산의 결과 (1

https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 문제유형 : DP 문제풀이 : 특정 좌표가 웅덩이에 포함되어있는지 확인할때 주어진 좌표는 행,열이 바뀌어잇기때문에 i,j가 아니라 j,i로 확인해줘야했다. 점화식 : S[i][j] = S[i-1][j] + S[j-1][i] 이때 j,i가 puddles에 포함되어있다면 위 점화식을 수행하지 않고 0으로 바꿔주고 넘어간다. 정답코드 : def soluti..

https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 문제유형 : DP 문제풀이 : 이문제가 왜 DP인가? (DP의 조건 : 1. 최적부분구조, 2. 중복되는 부분문제) 현재위치의 가장 큰값은 윗 줄의 가장큰값이 필요하다. 즉 특정 번째까지의 최적해는 앞의 최적해를 이용한다. ( 최적부분구조 ) 특정위치의 값을 구할때 대각선 위 값들을 비교하여 찾아낸다. 이것이 계속 반복된다. ( 중복되는 부분문제 ) 현재위치에서 가장큰 합을 저장하는 배열을 new_val이라고 했을때 new_val[i][..

https://programmers.co.kr/learn/courses/30/lessons/12900 코딩테스트 연습 - 2 x n 타일링 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 programmers.co.kr 문제유형 : DP 문제풀이: n일때 가짓수는 n-1일때의 가짓수 + n-2일때의 가짓수이다. n-1에다가 가로길이가 1인 세로로 길쭉한 사각형을 각각 붙이는 경우 n-2에다가 가로길이가 2인 가로로 길쭉한 사각형을 각각 붙이는경우 위 두경우를 더한것이 n일때의 갯수이다. 정답코드 : 백준에서 똑같은 문제를 풀어봐서 바로 생각나서 풀수 있었다! def..

한달동안 알고리즘문제에 손도 안댔더니.. 다 까먹어버린것같다.. 큰일났다.. DP (Dynamic Programming)이란? 큰 쿤제를 작은문제로 나누어 푸는것 동적 기억하기 프로그래밍 이라고 이해하는편이 좋겠다. DP와 분할정복의 차이 작은문제가 중복이 일어나는가 안일어나는가 분할정복 : 큰 문제를 작은문제로 나누어 푸는것은 맞지만, 작은문제들에서 반복이 없다!! DP : 작은문문제들이 반복되는것 (답이 바뀌지 않는) DP 적용방법 모든 작은문제는 한.번.만 푼다. -> 한번 구한 답을 어딘가 저장해놓는다. 이후에 다시 반복되는 작은문제가 나타나면 이미 구한답을 그대로 이용한다. DP의 조건 아래와 같은 조건을 만족하는 경우에 다이나믹 프로그래밍 풀이를 적용할수 있다. DP문제는 이 문제가 DP로 푸..