종만북에 나오는 명언이 하나 있습니다.
'코드와 데이터를 분리하라.'
저는 코드와 데이터를 분리하는 기준을 다음과 같이 두고 있습니다.
코드 : 무언가를 하는 반복적인 행위.
데이터 : 반복적인 행위를 하기 위한 데이터의 집합. 반복적인 행위가 이 데이터에 따라서 다른 결과를 도출함.
종만북에서도 데이터를 배열로 선언(테이블로 만듦)해서 배열을 순회하며 처리하라고 되어있습니다!
많은 분들이 쓰고 계신 예가 하나 있습니다.
바로 BFS에서 이동을 처리하는 경우이죠.
저는 2015년에 (x,y)를 이동하는 방법을 다음과 같이 만들었습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | int x,y; void move(int d){ switch(d){ case 0: x -= 1; break; case 1: x += 1; break; case 2: y -= 1; break; case 3: y += 1; break; } } | cs |
하지만 대부분의 사람은 이렇게 코드를 작성하지 않습니다!
아래와 같이 작성하죠!
1 2 3 4 5 6 7 8 | const int dr[] = {-1,1,0,0}; const int dc[] = {0,0,-1,1}; int r,c; void move(int d){ r += dr[d], c += dc[d]; } | cs |
다시 한번 위의 기준으로 볼까요!?
코드 : 무언가를 하는 반복적인 행위.
데이터 : 반복적인 행위를 하기 위한 데이터의 집합. 반복적인 행위가 이 데이터에 따라서 다른 결과를 도출함.
여기에서 반복적인 행위는 다음으로 이동하는 것을 의미합니다.
그리고 데이터는 바로 이동하고자 하는 방향과 x와 y에 더해지는 값이죠.
위의 코드는 데이터가 달라질 때 마다의 행위를 모두 다 if와 else로 표현한 것일 뿐입니다.
비슷하게 반복적인 코드를 4번이나 작성한 것이에요!
코드와 데이터를 분리하면, 아래처럼 딱 한줄로 4가지의 함축된 표현을 다 할 수 있습니다.
만약 유사한 if와 else가 반복적으로 나타난다면, 배열로 테이블을 만들어서 간단하게 표현하는 방법을 찾아보시기 바랍니다!
생각보다 많은 부분에서 찾을 수 있을 겁니다!
기억 나는 몇가지 방법을 적어보겠습니다.
1. 어떤 문자열이 들어왔을 때, int 형으로 바꿔야 하는 경우!
대표적으로, 'A'가 들어오면 더하기, 'M'이 들어오면 곱하기 이런 경우가 있을 수 있습니다.
문자열은 0~255의 데이터형을 가지고 있습니다.
enum TYPE{MUL, ADD}와 같은 enum을 이용하면
int conv[256]을 선언해 놓은 다음에 conv['M'] = MUL; 이런식으로 전처리를 해놓으면 굉장히 쉽게 int로 변환할 수 있습니다.
=> 심화된 방법으로, conv를 함수 포인터로 바로 만들어서 conv['M'] = mul 이런식으로 만들 수 있습니다.
2. 이동
맨 처음 알려드린 방법과 유사합니다.
다만, 4 방향뿐만 아니라 8 방향도 가능하고, 체스에서 나이트의 움직임 등으로 확장할 수도 있습니다.
3. 시작 인덱스와 이동 방향
가끔씩 2차원 배열에서 왼쪽 위에서 시작해서 오른쪽 방향으로 간다거나, 오른쪽 아래에서 시작해서 위 방향으로 움직여야 하는 경우가 있습니다.
이런 경우에도 시작 인덱스를 int sx[4] = {0,n,0,n}; int sy[4] = {0,n,n,0} 등으로 하면, 인덱스 값에 따라 (0,0), (n,n), (0,n), (n,0)중 어디서 시작할지 정할 수 있습니다.
또한, 다음으로 이동하는 것도 int dr[4] = {1, -1, 0, 0} int dc[4] = {0, 0, -1, 1} 으로 초기화 해 놓으면,
(0,0) : 아래쪽으로 이동
(n,n) : 위로 이동
(0,n) : 왼쪽으로 이동
(n,0) : 오른쪽으로 이동
이렇게 이동을 만들 수 있습니다.
4. 특정 패턴을 다른 쪽으로 밀기
대표적인 방법이 시계 방향으로 90도 돌리기 입니다!
시계 방향으로 돌리는건 이동과도 상관이 있죠.
자! 이동에는 상하좌우가 있죠!
일단 대표적으로 위의 방향을 시계 방향으로 뺑뺑 돌려볼까요!?
네! 보시는 바와 같이, 상 -> 우 -> 하 -> 좌 -> 상 -> ... 으로 돌아갑니다!
즉, 시계 방향으로 돌아간다는 반복 행위는
상 = 0, 우 = 1, 하 = 2, 좌 = 3이라고 했을 때, 한 칸 오른쪽으로 밀면 된다는 것 입니다!
앗! 그렇다면 우 에서 오른쪽으로 하나 돌리면 4가 되는데 어떻게 합니까!? 라고 물어보실 수 있습니다.
이 방법을 처리하기 아주 좋은 것이 바로 모듈러 연산입니다.
오른쪽처럼, 모듈러 연산을 하면 배열이 밖으로 나가지 않고 다시 처음으로 돌아오게 해주거든요!
즉, 3에서 오른쪽으로 한 칸 돌리면 0이 된다는 것이죠.
이는, 환형 큐를 만들때에도 많이 쓰이니 잘 기억해 두시면 좋습니다.
참고로 반시계 방향은 시계 방향을 3번 돌리면 나오는 연산입니다.
따라서, 반시계 방향으로 돌릴 때에는 (현재 방향 + 3) % 4 를 해주면 됩니다.
그리고 패턴을 찾는 일반 적인 경우에서 반대로 돌리는 것의 경우, +1의 반대인 -1을 해줍니다. C 언어에서 음수에 대한 모듈러 연산은 안되므로, 이와 동치인 (현재 방향 + 사이즈 - 1)% 사이즈 의 방법을 사용합니다.
반시계 방향 돌리기 경우에는 (현재 방향 + 4 -1) % 4 = (현재 방향 + 3) % 4 가 된거죠!
일반적인 경우에는 특정 패턴을 배열에 담아두고, 환형 큐를 이용해서 배열을 쭈욱 밀어서 다시 담아주면 됩니다!
삼성 기출 문제인 큐빙이 바로 이런 문제이죠.
풀이는 여기에 있습니다!
오늘도 쓰다보니 꺠알은 아니군요! 그럼 이제 팁을 끝냅니다.
'공부 > 알고리즘 깨알팁' 카테고리의 다른 글
| [알고리즘 깨알팁] heapify 시간복잡도 계산 (2) | 2020.10.05 |
|---|---|
| [알고리즘 깨알 팁] BFS 짜는 법 (4) | 2019.03.12 |
| [알고리즘 깨알 팁] 비트로 연산하는 방법 (0) | 2019.03.11 |
| [알고리즘 깨알팁] 재귀로 1, 2차원 구간 처리하기 (0) | 2019.03.11 |
