인접한 두 수를 분해하여 적절하게 바꿔서 정렬하는 방법

33708번: 인수분해 정렬 두 수 A[i]와 A[i+1]을 a*b = A[i]*A[i+1], a+b != A[i]+A[i+1]을 만족하는 a,b로 바꿀 때  원하는 만큼 이 연산을 시행해서 주어진 수열 A를 비내림차순으로 바꿀 수 있는가? ------------------------------------------------------------------------------------------------------------------------------------------- a = 1, b = A[i]*A[i+1]이라고 하면, A[i],A[i+1]을 반드시 1,A[i]*A[i+1] 반대로 a = A[i]*A[i+1], b = 1이라고 하면 A[i],A[i+1]을 반드시 A[i]*A[i+1],..

• format_list_bulleted 애드 혹 알고리즘
• · 2025. 4. 10.
• textsms

이전에 점프한 양에 의존하는 다이나믹 프로그래밍

2253번: 점프 1번에서 n번으로 이동할건데 처음에는 1칸만 점프할 수 있다 그 이후에는 이전에 x칸 점프했으면 이번에는 x-1,x,x+1칸 중 하나를 선택하여 점프할 수 있다 물론 1칸 이상 점프해야한다 그리고 어떤 돌에는 점프할 수 없다 이때 필요한 최소 점프 횟수는? -------------------------------------------------------------------------------------------------------------------------------- dp[i][j]를 i칸에 왔을때 점프한 칸의 수가 j칸일때 최소 점프 횟수라고 정의해야할텐데 문제가 n이 최대 10000인데 점프할 수 있는 칸 수 j도 10000으로 잡으면 메모리 초과당할 것 같다 그래도..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 4. 9.
• textsms

구간 내 가장 큰 해밍거리를 가지는 두 정수를 구하는 방법

33692번: 해밍 거리 두 정수 a,b의 해밍거리는 a,b를 각각 이진수로 나타내서, 동일한 위치의 비트를 비교하여 서로 다른 비트의 수를 말한다. 예를 들어 9 = 1001 12 = 1100이므로, 2번째 비트와 4번째 비트가 서로 달라 9,12의 해밍거리는 2이다. 두 정수 A,B가 주어질때 A이상 B이하에서 해밍거리가 가장 큰 두 정수 a,b를 아무거나 구한다. -------------------------------------------------------------------------------------------------------------------------------------------------------- A,B를 각각 이진수로 나타내고 이진수의 길이가 서로 다르다면, 앞..

• format_list_bulleted 애드 혹 알고리즘
• · 2025. 4. 8.
• textsms

스위치를 누른 효과가 j초 남아있는 지속시간 다이나믹 프로그래밍

30460번: 스위치  i초에 A[i] 점수를 얻는 게임 n초간 진행하는데 t초에 스위치를 눌렀을 때 t, t+1, t+2초에는 얻는 점수를 2배로 할 수 있다 t초에 스위치를 누르면 t+3초부터 다시 스위치를 누를 수 있다 가능한 점수의 최댓값은 ---------------------------------------------------------------------------------------------------------------------------------------- 그냥 평소대로 i초간 봤을때 스위치를 눌렀냐 안눌렀냐? dp[i][j]로 j = 0,1 했더니 안풀리더라 i초에 눌렀을때 i,i+1,i+2초 점수 2배로 먹는다 쳐도  i초에 안누르고 점수 그대로 가져가도.. i초에 눌..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 4. 7.
• textsms

일직선 상에서 특정 위치에서 거리 합이 최소가 되도록 집을 짓는 문제

18513번: 샘터 N개의 샘터가 주어질때 K채의 집을 지을려고 한다 각 집에서 가장 가까운 샘터까지의 거리를 불행도라고 정의할때 K채의 집의 모든 불행도의 합이 최소가 되도록 집을 짓는다 그 불행도의 합의 최소를 구하는 문제 ------------------------------------------------------------------------------------------------------------------- BFS로 풀 수 있다는데 생각해봐도 감이 잘 안오더라고... 평소 BFS문제랑 조금 달라서 그런지 샘터 위치 x에서 왼쪽 오른쪽으로 -1,1만큼 봐서 비어있으면 x-1, x+1에 집을 짓고 다시 x-1에서 왼쪽 오른쪽으로 -1,1만큼 x-1,x에서 비어있으면 집을 짓고 x+1에..

• format_list_bulleted DFS BFS 정복기
• · 2025. 4. 5.
• textsms

양팔저울을 이용해서 무게를 알아낼 수 있는 추를 찾는 방법

2629번: 양팔저울 양팔저울에 1g과 4g의 추를 이용해서, 어떤 구슬이 3g인지 확인할려면 한쪽에 1g의 추, 3g의 구슬을 놓고 다른 한쪽에는 4g의 추를 올려놓은 다음 양쪽이 균형을 이루는지 확인하면 된다 가지고 있는 추와 무게를 확인하려는 구슬이 주어질때 무게를 확인이 가능한 구슬을 모두 찾는다 ----------------------------------------------------------------------------------------------------------------------------------------------------------- 핵심은 한쪽에 추를 올리는 것이 +라고 한다면 반대쪽에 올리는 것은 -라고 생각하는 것이다 한쪽에 +4g을 올리면 다른 한쪽에 ..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 4. 4.
• textsms