분류 전체보기 검색 결과

해당 글 230건

[백준 15989] 1,2,3 더하기 4 -JAVA // le_effort//

이해하는데 정말 오래 걸렸다.... 한 시간 반은 걸린 거 같다.... 문제에서 주어진 것 처럼 중복을 없애야 한다. 일단 dp를 2차원 배열로 설정한다. - POINT A dp[n][1] 정수 n을 표현한 수 중 1로 끝나는 것 dp [n][2] 정수 n을 표현한 수 중 2로 끝나는 것 dp [n][3] 정수 n을 표현한 수 중 3으로 끝나는 것 중복을 제거하기 위해서는 어떻게 해야 할 까? 2+1+1 , 1+1+2 , 1+2+1 -> 이 3개는 중복이다. 애초에 설정할 때 저 3가지의 숫자 중 하나만 들어가게 하면 되는 게 우리의 목표다. 이걸 위해서는 생각해야 할 게 있다. 수는 오름차순으로만 있어야 한다 이런 중복의 제거 유형은 대체로 오름차순으로 두어야 한다고 한다. A- 2+1+1 오름차순이 ..
알고리즘 2020. 3. 9. 16:06

[백준 15988] 1,2,3 더하기 3 -JAVA// le_effort//

https://suhyeokeee.tistory.com/21 [백준 9095] 1,2,3 더하기 -JAVA //le_effort 전형적인 DP문제이다 일단 점화식은 dp [i] = dp[i-1]+dp[i-2]+dp[i-3] 인데 이걸 어떻게 도출하는지에 대해서 설명하겠다 모든 수를 1 , 2, 3 을 이용해서 만들어야 한다. dp[i] 는 i번째 수를 만들 수 있는 개.. suhyeokeee.tistory.com 이 문제에서 나누기만 해주면 된다. 주의 할 점: 1 2 3 4 5 6 for(int i=4; iColored by Color Scripter olor:white">cs
알고리즘 2020. 3. 9. 14:03

[백준 9095] 1,2,3 더하기 -JAVA //le_effort

전형적인 DP문제이다 일단 점화식은 dp [i] = dp[i-1]+dp[i-2]+dp[i-3] 인데 이걸 어떻게 도출하는지에 대해서 설명하겠다 모든 수를 1 , 2, 3 을 이용해서 만들어야 한다. dp[i] 는 i번째 수를 만들 수 있는 개수로 하겠다 dp [1] = 1 총 1개 dp[2] = 1+1 / 2 총 2개 dp[3] = 1+1+1 , 1+2, 2+1, 3 총 4개 이제 dp[4]이상을 구해보자 dp[4]는 위 문제에도 나와있다. (1+1+1+1) (1+2+1) (2+1+1) (3+1) (1+1+2) (2+2) (1+3) 자 이제 규칙을 찾기 위해 색을 칠하겠다. (1+1+1+1) (1+2+1) (2+1+1) (3+1) (1+1+2) (2+2) (1+3) 색칠된 부분을 보자. 초록색으로 색칠된..
알고리즘 2020. 3. 9. 11:45

[백준 10942] 펠린드롬? -JAVA // le_effort//

배울게 많았던 문제였다. DP는 다른 알고리즘에 비해 코드 길이가 짧지만 규칙을 찾기가 너무 힘든 것 같다. 펠 린드 롬이란 앞으로 읽던 거꾸로 읽던 숫자가 똑같은걸 의미한다 M의 최대 크기가 1,000,000으로 크니 DP로 메모제이션을 활용해야 한다. DP [i][j]는 i번째 수부터 j 번째가 펠린드롬인가? 를 의미한다. 예를 들면, DP [1][4]는 1번째 수부터 4번째 수 까지가 펠린드롬 인가의 여부를 구하는 것이다 펠린드롬을 구하는 방법은 크게 3가지로 나뉜다 1. 길이가 1인 펠린드롬을 구한다. 2. 길이가 2인 펠린드롬을 구한다. 3. 길이가 3 이상인 펠린드롬을 구한다 길이가 1인 펠린드롬 일단 길이가 1인 배열의 경우는 무조건 펠린드롬이다. 숫자가 하나밖에 없으니 앞에서 읽던 뒤에서 ..
알고리즘 2020. 3. 9. 11:05

[백준 15558] 점프게임 -JAVA //le_effort//

숨바꼭질 문제와 비슷한 유형이다 아마 bfs의 기본 개념이 있다면 쉽게 풀릴 거라 생각 하지만 나도 그렇고 사람들이 가장 자주 틀리는 것이 n초가 지나면 n번째 칸이 사라진다는 개념 일 것이다. 내가 첫 오답을 받았을 경우 한 칸 앞, 한칸 뒤, 반대 줄 점프 이 3개의 과정을 하고 나서 bfs 진행 중 큐에서 빠질 때 time을 증가시켜줬는데 오답 코드를 첨부하겠다. 이 코드에서 6번째 줄과 49,50 번째 줄 만 보길 바란다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 publi..
알고리즘 2020. 3. 5. 20:58

[백준 1890] 점프 -JAVA // le_effort//

알고리즘 DP 주의할 점 경로의 개수가 2^63 -1 이니 dp 배열을 long 형태로 받아야 한다. dp [i][j] = 이 칸 까지 올 수 있는 경우의 수들. 일단 첫 시작 지점 dp [0][0] = 1로 둔다. 그 이유는 아래에서 설명한 조건을 다 충족 할 시 개수를 늘려줘야 하는데 0으로 두면 계속 0 이 되기때문이다. 문제에서 오른쪽/ 아래쪽으로 정해진 칸만큼 갈 수 있다 했으니 dp [i][j] 기준으로 아래쪽으로 갈 때 i+정해진 칸
알고리즘 2020. 3. 5. 20:44

[백준 11048] 이동하기 -JAVA //le_effort//

알고리즘 : DP 반대로 생각해서 했다. 이동 가능한 방향이 r+1,c r,c+1 r+1 c+1 으로 가능 한 데 도착 칸 기준으로 동그라미 칸에서 올 수 있는 것은 저기 화살표 친 방향들 즉 r-1 c-1 / r-1 c / r c-1 이렇게 올 수 있다 이렇게 하면 반복문을 진행 할 때 인덱스 오류를 범하지 않을 수 있다 저기 빨간색 친 부분은 기존의 맵보다 1 크게 받았는데 반복문이 1,1 부터 시작해도 인덱스 오류가 나지 않고 빨간칸은 어차피 0 으로 되어있으므로 값에 오류가 없다 라는 것을 설명하기 위해 그린 것 dp[r-1][c-1] dp[r-1][c] dp[r][c-1] 중 가장 큰 값과 현재 칸의 값 map[r][c]를 더해주면 답이 나온다. 1 2 3 4 5 6 7 8 9 10 11 12 ..
알고리즘 2020. 3. 5. 19:44