boj 23326 번 문제를 통해 접하게된 원형 배열에서의 인덱스 표시에 관하여. curr=(curr+tmp-1)% N +1; 형태의 코드에 대해

boj 23326번 문제의 경우, 원형으로 되어있는 상황에서 이동할 수 있는 경우가 1<<9 까지 제시되는 상태인데, 이때에 이렇게 이동을 할 수 있는 경우에 원형으로 이루어진 명소들에서 현재의 위치를 기반으로 그만큼 이동했을때의 위치를 나타낼 수 있어야 하는 상황이었다. 

이때에 생각해본 바로는 %을 이용해서 다시 원래의 위치를 기반으로 되돌리면 되겠다 싶었는데, 이 연산을 어떤식으로 구현해야 할지에 대해서는 잘 생각이 나지 않았다. 

 

이런 상황에서 참고 코드를 확인해보니 

일단은 curr=(curr+tmp-1)% N + 1;

형태로 코드가 작성되어 있는것을 확인할 수 있었다. 

근데 이때에, curr+tmp-1 에서 -1의 의미와, 마지막에 (curr+tmp-1)% N +1; 에서 +1의 의미에 대해서 잘 모르겠어서 이와 관련하여서 gpt에 검색해보고, 구글에서 블로그들에 검색해보면서 관련 정보들을 공부해보았다. 

 

https://2jinishappy.tistory.com/149

% 연산을 이용한 Circular Array 구현 및 응용

 

위와 같은 검색 결과들과 블로그 내에 있는 정보들을 확인해볼때, 

 

curr=(curr+tmp -1 ) % N +1 ; 형태로 코드를 작성하는 이유는, 

만약 이 문제가 현재의 위치가 0이고, 각각의 위치들을 0 , 1 , 2, 3, ... 형태로 작성하는 문제였다면, 

tmp 만큼 이동하라는 형태의 query가 주어졌을때 

curr=(curr+tmp)%N; 형태로 작성되었을 것이다. 이렇게 되면, 예를들어서

현재의 위치가 0이고, 각각의 섬이 5개이면서, 9만큼 이동하라고 하였다면,  curr= (0+ 9)% 5 =4 가 될것이고, 이때에 4라는 값은, 

0 ,1 , 2, 3, 4 에서 4번 *인덱스* 값이고, 그렇기 때문에 가장 끝에 위치하게 되는 형태이다. 

그리고 만약 현재 위치가 1이고, 각각의 섬이 5개이면서, 9만큼 이동하라고 하였다면, curr=(1+9)%5=0가 될것이고, 이때에 0라는 값은, 

0, 1, 2, 3, 4 에서 0번 *인덱스* 값이고, 그렇기 떄문에 가장 처음에 위치하게 되는 형태이다

 

위와 같이 설명한 모든 형태는 현재의 상황이 모두 시작이 0번부터 존재하는 0-indexed의 상황에서의 연산이고, 이게 만약 처음 시작이, 

배열의 위치를 1, 2, 3, 4, 5 처럼 1-indexed 형태로 작성된 문제라면, 그걸 다시 0-indexed 형태로 고쳐서 연산을 진행한뒤, 

결과를 다시 1-indexed 형태로 수정하는 형태로 연산을 진행해주면 원하는 curr의 index 위치를 구할 수 있을 것이고, 

그렇기 때문에, 이 문제에서

 

1-indexed 형태의 상황이기 떄문에(가장 처음의 curr 위치의 시작이 1 이다!) 이걸 처음엔 0-indexed 형태로 수정해서 연산하기 위해서 -1을 ((curr-1) + tmp)%N 처럼 curr에 해줘서 고쳐주고, 이렇게 연산결과를 구하고 난뒤 나오는 curr 값에

+1을 해주어서 ( curr= (curr-1+tmp)% N + 1(바로 이부분)) 다시 curr의 시작 위치가 1-indexed 형태로 고쳐주는 것이다. 

 

만약 이런 형태의 원형 배열 문제를 만나고 위치를 이동시키면서 각각의 이동된 뒤의 위치를 나타낼때는, 0-indexed의 경우 

바로 curr=(curr+이동할 거리 T) % N( 원소의 갯수) 형태로 구하면 되고, 만약 시작 값이 1, 2, 3, ... 등등처럼 다르게 표시되어 있다면, 

curr=(curr-a+T)%N +a 형태로 작성해서 연산해주면 될 것이다. 

이때에 시작 값이라는 것은 curr 위치의 현재 위치를 말한다기 보다는, 첫번째 원소가 놓인 위치를 몇이라고 보는지가 더 정확한 표현일 것이다. 

그래서 이 문제는 curr이 놓일 수 있는 첫번째 위치를 1이라고 보는 문제이기 때문에 curr=(curr-1 +t)%N+1; 형태로 작성해주었다. 

가장 기본인 curr=(curr+t)%N; 형태의 코드를 잘 이해하고 사용하도록 하고, 이때에 0-indexed인 경우 그대로, 1-indexed인 경우 수식에 -1과 +1을 해주는걸 잊지말고, 

만약 a-indexed 형태라면 수식에 -a와 +a를 해주는걸 잊지 말도록 하자. 

충분히 이해하고 잘 응용해보도록 하자.