[알고리즘] ㄹ자 채우기

ㄹ자 채우기

2차원 배열에 ㄹ자 방향으로 데이터가 들어가는 방식입니다.

 

행이 고정된 상태에서 열이 변화하면서 데이터가 들어간 형태로 방향은 아래와 같습니다.

 

첫 행은 1열부터 5열까지 1씩 증가하는 형태,

다음 행은 5열 부터 1열까지 1씩 감소하는 형태가 반복됩니다.

 

이 때 열의 시작값, 끝값, 증가값이 바뀌기 때문에 상수 처리를 할 수 없어

변수로 처리를 해야 합니다.

 

변화하는 값을 확인해보니 일정한 패턴이 보이는데요.

 

첫 행의 시작값은 다음 행의 끝값으로,

첫 행의 끝값은 다음 행의 시작값으로,

첫 행의 증가값에서 -1을 곱한 값이

다음 행의 증가값으로 반복되는 걸 알 수 있습니다.

 

---

 

교환로직

일반적으로 A, B라는 두 저장공간이 있을 때

A값과 B값을 서로 바꿀 때

A값을 B값으로 옮기면 기존의 B값은 지워지고 A값이 덮어씌워지게 됩니다.

 

교환로직은 이 때 임의의 변수(주로 Temp로 명명)를 만들어

임시로 데이터를 놔둘 공간을 마련합니다.

옮길 A값을 Temp로 옮겨 두고

B값을 A로 옮긴 뒤

Temp에 있던 값을 B로 옮깁니다.

 

순서를 식으로 표현하면

 

Temp = A

A = B

B = Temp

 

가 됩니다.

 

---

 

이를 응용한 문제의 순서도를 살펴보겠습니다.

 

5행 5열의 2차원 배열에 다음과 같은 값을 저장할 때의 순서도입니다.

 

위에서 살펴봤던 교환로직인

 

Temp = A

A = B

B = Temp

 

가 예시에서는

 

TEMP = BEGIN

BEGIN = END

END = TEMP

 

이 부분이 되겠죠.

 

증가값에 -1씩 곱해야 할 부분은

 

SW = SW * (-1)

 

로 처리되었습니다.