what ryan do

코드만 궁금한 분은 깃허브 링크 눌러주세요! :) GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제는 여기 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 문제 설명을 간략하게 하자면 행렬의 경우 분배 법칙..이라고 해야하나? 아무렇게나 막 곱해도 값이 똑같은 그런 규칙이 적용되지 않아서 곱셈 순서에 따라 값이 상당히 달라진다...

풀이 코드만 궁금한 분은 깃허브링크 눌러주세요..!! GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제 해설 간단히, 숫자들이 입력된 리스트가 있는데 거기에서 s칸씩 연결된 부분리스트들을 3개 만들어야 한다. 이 때 3개의 부분리스트들은 서로 겹치면 안되고, 이 때 부분리스트들의 합이 최대가 되는 3쌍의 부분리스트들을 찾아서 그 합을 리턴하면 된다. 문제 해결 논리 1. 우선 전체 n개의 칸 중 s칸씩만 합할 수 있으므로, 입력된 숫자리스트에서 s칸만큼의 부분합을 저장하는 리스트를 만들고 s부터~n까지 각각 부분합을 저장해둔다. s-..

문제 해결 코드만 궁금한 분은 깃허브링크 눌러주세요. 풀이가 2개니까 잘 보고 둘 다 실행 해보세요~ GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제 설명 다이나믹 프로그래밍이란걸 배운다면 가장 처음 배우게되는 배낭 문제. 나도 사실 이 문제는 파이썬 알고리즘 인터뷰에서 봣던 문제라 크게 어렵지 않게 풀었다. 문제 해설이 총 2개인데, 나는 파이썬 알고리즘 인터뷰에서 나온 방식대로 우선 한번 풀어봤다. 문제 해결 논리 1 1. N개의 행, K+1개의 열로 구성된 행렬을 하나 만든다. 2. 1행은 첫번째 물건만 넣었을 때를 의미하고,..

문제 해설 코드만 궁금한 분은 깃허브링크 눌러주세요..!! GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제 설명 문제 해결 논리 얼핏 보면 bfs문제같은데 시간초과로 bfs는 안된다. 생각해보면 계속 갯수가 2씩 곱해지고 최대 100번 반복해야하니까 최악으로는 가장 마지막 경우에 2^N개의 값을 계산해야될 수도 있다(O(2^(N^2))). 따라서 매 곡 순서마다 가능한 음량을 체크하는 리스트를 만들어서 가능한 음량을 체크하는 형식으로 계산하면 반복문을 활용, O(NM)으로 문제를 풀 수 있다. 1. 음량은 0부터 입력된 값 M까지 ..

풀이 코드만 궁금한 분은 깃허브링크 눌러주세요..! GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제 설명 결국 1, 2, 3을 적당히 잘 섞어서 어떤 수를 만드는데 그게 가능한 경우의 수를 모두 찾아야 한다. 문제 해결 논리 : 1. N이라는 값이 있을 때 그 값의 가능한 경우의 갯수를 dp[N]이라고 하자. 2. 이 때 dp[N]은 dp[N-1] + dp[N-2] + dp[N-3]이다. 그 이유는 N-1째에서 1을 더하고, N-2째에서 2를 더하고, N-3째에서 3을 더하는 것 모두 N을 만족하기 때문에 세 경우의 수를 모두 더해..

문제 풀이 코드만 궁금한 분은 깃허브링크 눌러주세요,,!! GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제 설명 문제 해결 논리 어차피 값들은 아랫쪽, 오른쪽으로만 진행할 수 있다. 따라서 맨 윗 행은 왼쪽 값들에만 영향을 받고 맨 왼쪽 열은 윗쪽 값들에만 영향을 받는다. 따라서 0행부터 N행까지, 왼쪽부터 오른쪽으로 차근차근 계산해나가면 우리가 원하는 답을 얻을 수 있다. 1. 문제에서 주어진 게임판과 똑같은 크기의 0으로만 구성된 리스트 dp를 만들고 시작부분 (0,0)을 1로 표시한다. 이건 해당 요소로 갈 수 있는 경우의 수..

코드만 궁금한 분은 깃허브링크 사실 내가 dp를 잘 하는 편은 아닌데 2293번 어제 푼거를 머릿속에 생각해보면서 푸니까 그래도 다소 어렵지 않게 풀 수 있었다. 문제를 대충 알려주자면, 1, 2, 5 이런식으로 무작위의 숫자들과 다른 숫자 임의의 숫자 하나가(예시를 들기 위해 10으로 한다.) 주어진다. 이 때 앞쪽에 주어진 숫자 1, 2, 5들을 이용해 10을 구성하는데 그 때 가장 적은 수로 숫자들을 이용하는 경우를 반환하면 된다. 말이 좀 이상한데, 간단히 얘기해서 10은 1을 10번 써도 되지만 5를 2번 써도 된다. 그럼 2가 더 작으니까 답은 2가 된다. 문제 풀기 1. 구성해야 하는 숫자 N의 길이만큼의 리스트를 미리 만든다. 2. 앞에 무작위로 주어졌던 숫자들 중 작은 수부터 활용해서, ..

코드만 궁금한 분은 깃허브링크 GitHub - Rhyankwon/algorithms Contribute to Rhyankwon/algorithms development by creating an account on GitHub. github.com 문제 이해는 쉽다. 10이 있고, 1원 2원 5원짜리 동전이 있으면 그 동전들을 막 조합해서 10을 만들면 되는데, 그렇게 10이 되는 주어진 동전들의 조합의 총 갯수를 반환하면 된다. 간단한 다이나믹 프로그래밍이다. 1부터 10까지 가능한 동전의 조합 수를 dp라고 하자. 우선 위에 내가 서술한 문제로 보면, dp[10]은 dp[9] + dp[8] + dp[5]이다. 왜냐면, 9까지 만든 다음 거기에 1원짜리 동전 하나를 더하고, 8까지 만든다음 거기에 2원..