24년 8월 24일 알고리즘 2일차

아아. 오늘 잠시 사회란 곳을 다녀와서 시간을 낭비했군. 하지만 내 마음 속은 항상 알고리즘이였다고, 

그러면 시간복잡도 계산 하는 방법을 알아볼까

 

==

하하 시간복잡도에 대해서 알아보려 했지만 이거이거 날 새겠는걸? 

문제 한 개 풀고 오늘은 자야겠다. 

 

 

문제: 배열의 회전

설명: 주어진 정수 배열을 오른쪽으로 k번 회전시키는 함수를 작성하세요. 배열의 회전은 배열의 마지막 요소를 배열의 첫 번째 위치로 이동시키고, 나머지 요소들을 한 칸씩 뒤로 밀어내는 방식으로 이루어집니다.

입력:

• 정수 배열 nums (예: [1, 2, 3, 4, 5, 6, 7])
• 정수 k (예: 3)

출력:

• 배열을 k번 회전시킨 후의 배열 (예: [5, 6, 7, 1, 2, 3, 4])

예시:

• 입력: nums = [1, 2, 3, 4, 5, 6, 7], k = 3
• 출력: [5, 6, 7, 1, 2, 3, 4]

조건:

• k는 음수가 아니며, 배열의 길이보다 클 수 있습니다.
• 추가적인 배열을 사용하지 않고 문제를 해결해보세요.

 

음

한 칸씩 뒤로 미는 함수를 만들고 정수값만큼 반복하게 하는 함수를 만들면 될 것 같은데, 

뒤로 밀게 어떻게 하지/.

 

 

private void 생략(int k)

{

for( k 만큼 반복)

{

int arryNextNum = nums[0];

int arryCurNum=  0;

 

for(배열크기만큼 반복)

{

if(i+1 > nums.length )

{

nums[0] = arryNextNum;

}

else

{

arryCurNum = arryNextNum;

arryNextNum  = nums[i+1]

nums[i+1] = arryCurNum;

}

}

}

}

 

어... 된 거 같은데 이렇게 하면 되나

일단 이렇게 하면 시간복잡도가 O(n제곱인가? ㅋㅋ) 

 

==

인덱스 계산 오류 if(i+1 > nums.length ) 이건 >= 이 되어야 한다. 0부터 시작 하기에 i+1을 하면 이 조건문은 실행을 안 한다. 

시간복잡도는 O(k*n)

 

개선 된 방법

 

public void Rotate(int[] nums, int k)
{
    int n = nums.Length;
    k = k % n;  // k가 배열 길이보다 클 경우를 대비해 모듈로 연산

    for (int i = 0; i < k; i++)
    {
        // 배열의 마지막 요소를 첫 번째 요소로 옮기기
        int last = nums[n - 1];

        // 배열의 요소들을 한 칸씩 뒤로 이동
        for (int j = n - 1; j > 0; j--)
        {
            nums[j] = nums[j - 1];
        }

        // 첫 번째 요소에 마지막 요소 삽입
        nums[0] = last;
    }
}

 

더하는 방식이 아니라 빼는 방식으로 반복을 돌게 했고 마지막건 처음에 빼서 반복문 끝나고 넣게 했다. 

이건 간단한 방법이지만 한 번에 K번 만큼 회전 시키는 방법이 좋은데 음.

 

이런 문제 굉장히 기초적인 문제인 것 같은데 나 재능 없나?,, 내일 일어나서 강의 알아봐야 겠다.

 

그리고 노래튜터님께서 선생GPT를 포기해야 한다고 말씀 해주셨다. 이거이거 GPT선생님 되게 친절하셨는데, 오늘까지인가.