본문 바로가기

분류 전체보기209

[프로그래머스 lv2] 행렬 테두리 회전하기 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 (x1, y1)를 왼쪽 꼭짓점, (x2, y2)를 오른쪽 꼭짓점으로 하는 직사각형을 회전했을 때 회전하는 라인에 있는 최솟값을 모아 리턴하는 문제이다. 문제에서 주어진 대로 그대로 구현하면 AC를 받을 수 있다. 회전 방향에 0, 1, 2, 3의 인덱스를 부여하고, 각각의 방향에서 다음 블럭을 당겨오자. 아래의 코드에서는 0번 방향과 2번 방향일 때 h-1 만큼 당기고, 1번과 3번 방향일 때 w-1 만큼 당기도록 구현하였다. 블럭을 회전하며 가장 작은 숫자를 기록하고 이를 모은 벡터를 리턴하면 정답이다. 코드 #include #include #include #include #include #include #include #include #includ.. 2022. 8. 21.
[프로그래머스 lv2] 2개 이하로 다른 비트 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 자연수 x에 대하여 x보다 큰 수 중 2진수 비트가 1~2개만 다른 가장 작은 수를 구하는 문제이다. 규칙을 찾아보면, 1) 000...1000 과 같이 가장 마지막 자리가 0인 경우 이를 1로 바꾸면 된다. 2) 000...0111 과 같이 마지막 자리가 아닌 자리가 0인 경우, 가장 뒷자리 부터 0을 찾아 이를 1로 바꾸고 해당 자리의 다음자리를 0으로 바꾼다. 예를 들어, 000...0111 을 바꾸면 1011이 되고, 10진수 7에 대한 정답은 11이 된다. 10진수를 2진수 문자열로 바꾸어 연산할 수도 있지만, 비트 연산을 이용하여 간단히 구현할 수 있다. 가장 끝 0번 인덱스부터 각 자리를 추출하여 해당 자리가 0이면 이를 1로 바꾸고, 0.. 2022. 8. 20.
[프로그래머스 lv2] 가장 큰 정사각형 찾기 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 가장 먼저, 완전 탐색 풀이를 적어보고 시간복잡도가 효율성을 통과할 수 있을지 확인해보자. 완전탐색으로 푼다면, 직사각형의 크기가 N x M 일 때 가능한 정사각형 한변의 길이 k에 대하여 모든 k*k를 확인해야 한다. 따라서 다음과 같이 5중 포문을 써야 하고 결국 TLE가 날 것임을 예상할 수 있다. for (int k = 1; k 2022. 8. 20.
[프로그래머스 lv2] n^2 배열 자르기 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 가장 먼저 해당 문제가 완전 탐색이나 단순 구현으로 해결되는지 확인해야한다. 최대 입력 범위가 10^7 이기 때문에 반복문으로 배열의 행과 열을 채우면 TLE가 발생한다. 따라서 배열을 일렬로 나열했을 때의 인덱스를 보고 바로 배열의 값을 알아낼 수 있는 방법을 찾아야 한다. 일단, 배열의 x, y 좌표와 배열 값 사이의 관계를 생각해보면, (x, y)의 값은 max(x, y) + 1 이 된다. 예를 들어, (2, 3)의 값은 max(2, 3)+1 = 4 가 되고, (2, 0)의 값은 max(2, 0)+1 = 3 이 된다. 해당 규칙을 이용하면 각 배열을 모두 순회하지 않고도 특정 좌표의 값을 바로 알 수 있다. 다음으로, 배열을 일렬로 나열했을 때의.. 2022. 8. 19.
[프로그래머스 lv2] 2xn 타일링 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 2 x n 타일을 채우는 방법은 크게 두가지로 나눌 수 있다. 첫째, 2 x (n-1) 을 채우고 2 x 1 을 채우는 방법 둘째, 2 x (n-2)를 채우고, 1 x 2 를 가로로 두개 채우는 방법 따라서, dp[i] 를 2 x i 를 채우는 방법의 수라고 정의할 때, 점화식은 다음과 같다. dp[i] = dp[i-1] + dp[i-2] 이때, 문제에서 1000000007로 나눈 나머지를 구하라고 했으므로, 최종 점화식은 다음과 같다. dp[i] = (dp[i-1] + dp[i-2]) % 1000000007 dp 값을 구한 뒤 dp[n]을 리턴하면 정답이다. 코드 #include #include #include #include #include #in.. 2022. 8. 18.
[프로그래머스 lv2] 점프와 순간이동 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 0에서 n까지 이동할 수 있는 방법은 두가지이다. 첫째, 현재 위치에서 2배 위치로 이동하는 것(순간이동, 건전지 소모 X) 둘째, K 만큼 점프하는 것(점프, K만큼의 건전지 소모 O) 방향을 뒤집어 n에서 0까지 이동한다고 생각해보자. 현재의 위치가 짝수이면 무조건 n/2 위치로 순간 이동을 하는 것이 유리하다. 순간이동은 건전지 소모가 없기 떄문이다. 반면, 현재 위치가 홀수이면 n/2 위치로 순간 이동을 할 수 없으므로 무조건 건전지를 1 소모해야 한다. 따라서, 반복문 내에서 n이 홀수이면 n을 1줄이면서 건전지 소모량을 1 늘리고, 짝수이면 n을 2로 나누어주자. n이 0이 되었을 때 총 건전지 소모량을 리턴하면 정답이다. 코드 #inclu.. 2022. 8. 17.
[프로그래머스 lv2] 괄호 회전하기 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 주어진 문자열을 0번~ s.size()-1번 회전했을 때 올바른 괄호의 개수를 세는 문제이다. s의 입력 길이가 최대 1000이므로, 회전한 문자열 모두을 구해 올바른 괄호인지 확인하여도 TLE가 발생하지 않는다. s를 i번 회전했을 때의 문자열은, s를 i번째 인덱스에서 끊고 앞 부분을 모두 문자열의 뒤로 이동시킨 것과 같다. i번 회전한 문자열을 구한 뒤, 해당 문자열이 올바른 괄호인지 확인하자. 문자열이 올바른 괄호인지 확인하는 방법은 다음과 같다. 먼저, 여는 괄호가 등장했을 때는 스택에 넣는다. 닫힌 괄호가 나왔을 때, 스택의 가장 최근 원소가 짝이 맞는 여는 괄호인지 확인하여 스택에서 삭제한다. 만약, 스택의 가장 최근 원소가 짝이 맞는 열.. 2022. 8. 17.
[프로그래머스 lv2] 하노이의 탑 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 n개의 원판들을 1번 기둥에서 3번 기둥으로 옮기는 하노이 문제이다. 처음 하노이 문제를 보는 사람이라면 규칙을 찾아서 절차적으로 해결하려고 노력하게 된다. 하지만 절차적으로 생각하면 할 수록 더욱 미궁 속으로 빠지게 되고... 이 문제는 재귀의 가장 대표적인 유형으로 재귀적 사고를 통해 해결해야 한다. func(int n, int f, int t)는 n개의 원판을 f 기둥에서 t 기둥으로 옮길 때 필요한 이동 방법을 리턴한다. 원판을 옮길 때 큰 원판은 절대 작은 원판보다 먼저 움직일 수 없다. 따라서, n개의 원판을 f에서 t로 옮기려면, n-1개까지의 원판을 f, t가 아닌 다른 기둥에 옮겨놓고 가장 마지막에 있는 n번째 원판을 f에서 t로 이동.. 2022. 8. 17.
[프로그래머스 lv2] 큰 수 만들기 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 숫자의 순서를 유지하면서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하는 문제이다. numbers 길이에서 k개를 선택하는 모든 경우의 수를 탐색하면 TLE가 발생할 것이 분명하므로 더 간단한 풀이를 찾아야 한다. 어떻게 해결하면 좋을까 하다가 이런 생각이 들었다. "만약, 앞에 있는 수가 현재 수보다 작으면 앞에 있는 수를 제거해서 한자리씩 앞으로 당기는 것이 더 큰 수를 구하는 방법이지 않을까?" 예를 들어, 17725.... 가 있다고 했을 때 7은 1보다 크고, 1을 제거해서 7을 앞당기는 것이 가장 큰 수를 만드는데 유리하다. 해서, 숫자의 각 자리를 순회하면서 스택에 넣되, 스택에 이미 들어있는 수 중에서 현재 스택에 넣으려고.. 2022. 8. 17.
[프로그래머스 lv2] 숫자의 표현 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 연속된 숫자들의 합이 n이 되는 경우의 수를 구하는 문제이다. 결론적으로, (n-i*(i-1)/2)%i == 0 && (n-i*(i-1)/2)/i > 0 이면 연속된 i개 수의 합이 n이 되는데, 해당 수식의 도출과정을 살펴보자. i개의 연속된 수의 합이 n이 된다는 것을 다음과 같이 표현할 수 있다. x + (x+1) + (x+2) ... (x+i-1) = n 이를 정리해보면, 다음과 같다. i*x + (1+2+3+...+i-1) = n i*x + (i-1)*i/2 = n (등차수열의 합 공식) i*x = n-i*(i-1)/2 이 때, x가 존재하려면 n-i*(i-1)/2 를 i로 나눈 나머지가 0이어야 하고, 몫이 0보다 커야 한다. 따라서, (n.. 2022. 8. 17.

티스토리툴바