지뢰찾기 게임에서 지뢰의 최대 개수를 찾는 알고리즘

9082번: 지뢰찾기 2*n 배열이 주어진다. 첫번째 행은 숫자들이 쓰여있는데 그 블록 주위에 지뢰가 몇개 있는지를 나타낸다. 두번째 행은 지뢰가 숨겨져 있는 행인데, *, #으로만 주어진다. *은 지뢰이다. 예를 들어 11122####*로 주어진다면 첫번째 #은 바로 위에 1이 쓰여있고, 우측 대각선 상단에 1이 쓰여있으므로 지뢰가 있을 수 있다. 11122*###* 그리고 4번째 #에는 왼쪽 대각선 상단에 1, 바로 위 2, 우측 대각선 상단에 2가 쓰여있는 것으로 보아 지뢰가 있을 수 있다 11122*##** 이때 *을 포함해서 숨겨진 지뢰의 최대 개수를 구한다. ---------------------------------------------------------------------------..

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

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

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