본문 바로가기

dp58

[쇼미더코드 3회] 백준 27212 - 미팅 (자바 java) 문제 : boj27212 필요 알고리즘 개념 DP (동적 계획법) 약간 생각이 필요한 DP 문제였다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 쇼미더코드 3회 당시 1, 2번 15분만에 풀어놓고 이것만 1시간정도 걸렸다. 생긴게 이분 그래프 형태라 그래프쪽으로 자꾸 생각해보다가 오래걸렸다. 확실히 난 DP에 약한 것 같다 ㅠ. DP로 풀면 되겠는데?! 라고 깨닿기까지 너무 오래걸렸다 ㅋㅋ 입력이 아래와 같다고 해보자. .. 2023. 1. 15.
[쇼미더코드 3회] 백준 27210 - 신을 모시는 사당 (자바 java) 문제 : boj27210 필요 알고리즘 개념 구현, DP 이전까지의 결과를 가지고 판단하는 DP 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 내 경우엔 좀 독특하게 푼 것 같다. 왼쪽과 오른쪽으로 기준을 나누어서 진행했다. 1. 왼쪽을 기준으로 생각하기 왼쪽인 돌상을 +1, 오른쪽인 돌상을 -1이라고 해보자. 그럼 예제 입력 1은 다음과 같다. '1 1 -1 1 -1' 그리고 왼쪽부터 차례대로 더하다가 음수가 나.. 2023. 1. 15.
[자바] 백준 13699 - 점화식 (java) 문제 : boj13699 필요 알고리즘 개념 다이나믹 프로그래밍 (동적 계획법, DP) DP 문제이긴한데, 그냥 memoization 문제라고 보면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 t(n)을 계산하기 위해서는 t(0)부터 t(n-1) 까지의 계산 결과가 모두 필요한데, 이걸 매번 점화식대로 구해주면 당연히 시간초과가 될 것이다. 그러니 매번 x = 1부터 35까지 t(x)를 순서대로 계산해주고, t(x).. 2023. 1. 14.
[자바] 백준 20303 - 할로윈의 양아치 (java) 문제 : boj20303 필요 알고리즘 개념 분리집합 또는 dfs 또는 bfs DP로 실제 답을 구하는 로직 이전에 아이들의 그룹을 만들기 위해 분리집합 알고리즘(union-find) 혹은 그래프 탐색이 필요하다. 이하 풀이는 분리집합으로 풀었다. DP (Knapsack) DP 활용법 중 유명한 냅색류의 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 결국 연결된 아이들의 그룹별로 선택할 수 밖에 없다. 따라서 만약.. 2023. 1. 11.
[자바] 백준 9465 - 스티커 (java) 문제 : boj9465 필요 알고리즘 개념 동적 계획법 (Dynamic Programming, DP) DP로 풀 수 있는 문제이다. DP는 알고리즘이라기 보단 문제 푸는 방식? 같은 거라 생각한다. 어쨌든 어떤건진 미리 알고 풀어야 생각해낼 수 있을 것 같다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 스티커 위치가 아래와 같다고 해보자. A C E B D F 이 때, 각 스티커의 가치 중 음수인 것은 없으므로 결국 우측.. 2022. 12. 21.
[자바] 백준 16395 - 파스칼의 삼각형 (java) 문제 : boj16395 필요 알고리즘 개념 다이나믹 프로그래밍 (DP, 동적계획법) 파스칼의 삼각형을 한쪽으로 전부 밀어보면 규칙이 보인다. DP로 미리 값을 구한 후, n과 k에 따라 해당하는 값을 출력해주면 된다. DP 문제긴한데 DP라기보다는 그냥 규칙찾는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문제에서 제시된 파스칼 삼각형을 코드로 어떻게 표현할지 생각해보자. 파스칼 삼각형을 좌측으로 쭉 밀어서 2.. 2022. 10. 25.
[자바] 백준 6220 - Making Change (java) 문제 : boj6220 필요 알고리즘 개념 동적 계획법 (DP; Dynamic Programming) DP로 효율적으로 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 얼핏 큰 동전부터 최대한 사용하면 가능할 것이라 생각할 수 있다. 예를들어 예시 1의 경우 25, 50, 10, 1, 5원 이므로 큰 동전부터로 정렬하면 50, 25, 10, 5, 1 이다. 차례대로 사용해서 93 - 50원, 43 - 2.. 2022. 10. 13.
[자바] 백준 15489 - 파스칼 삼각형 (java) 문제 : boj15489 필요 알고리즘 개념 동적계획법(DP) 사실 딱히 DP 개념은 필요없다. 풀고보니 파스칼 삼각형 데이터 마련하는게 DP 느낌인거지, 그냥 구현문제다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 최근에 어떤분의 질문으로 3차원 파스칼 삼각형에 대한 설명이 이해안된다고 해서 그려서 설명해줬었는데, 마침 백준에 파스칼 삼각형이 보이길래(이 문제는 2차원이긴 하다) 한번 풀어봤다. 아래 이미지는 설명해준다.. 2022. 9. 7.
[자바] 백준 25418 - 정수 a를 k로 만들기 (java) 문제 : boj25418 필요 알고리즘 개념 동적계획법(DP), 너비 우선 탐색(BFS), 탐욕법(greedy) DP, BFS, 그리디 정도가 풀이로 생각나는 문제이다. 셋 다 알아야 하는건 아니고, 셋 중 하나만 알면 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1 - DP 풀이 dp[x]를 x를 만들기 위한 최소 횟수로 정의하자. 그리고 dp[x]를 모두 무한대로(이 문제의 경우 나올 수 있는 최대수치가 .. 2022. 9. 4.
[자바] 백준 5557 - 1학년 (java) 문제 : boj5557 필요 알고리즘 개념 동적 계획법 (DP; Dynamic Programming) DP를 이용한 문제이다. DP 개념을 적용해서 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 약간 응용되었지만, 아무튼 기본형태의 DP문제이다. 참고로 '경우의 수' 어쩌구 하는 문제의 대부분은 DP로 해결된다. 우선 단순히 +, -를 넣어서 모든 경우를 보려면 O((N-2)^2)이 필요하므로 시간초과가 나게 .. 2022. 8. 27.

티스토리툴바