2022.12.01 최초 작성
2023.1.17 파이썬 코드 추가
이전 글(제약을 통한 문제해결 응용력 키우기 훈련 1)에서 구구단 출력할 때 반복문에 제약사항을 주었다. 이번에는 두 변수에 저장된 데이터를 서로 교환하는 예제를 활용하려 한다.
두 변수에 담긴 값을 서로 교환하는 문제도 구구단처럼 거의 모든 프로그래밍 교재에 나온다고 생각된다. 보통 SWAP이라고 하며 프로그래밍을 학습하는 과정에서 거의 반드시 풀어보는 기본적인 문제이다.
변수는 수학적으로는 변하는 수를 말하며 컴퓨터에서는 데이터를 기억하는 공간으로 이야기한다. 변수에 저장된 값은 필요할 때 다른 값으로 변경될 수 있고 새로운 변수를 만들 수 있다.
두 변수의 값을 서로 교환하라고 하면 거의 99.9%의 교재에는 임시변수를 만들어서 활용하는 예제가 나와 있다. 이것은 구구단을 2단부터 9단까지 출력할 때 이중 반복 구조를 만드는 것처럼 가장 효율적이며 단순한 방식인 것은 누구도 부정하기 힘들 것이다.
#include<stdio.h>
void main() {
int a = 10;
int b = 20;
printf("[교환 전] a : %d, b : %d\n", a, b);
int temp = a;
a = b;
b = temp;
printf("[교환 후] a : %d, b : %d\n", a, b);
}a = 10
b = 20
print(f"[교환 전] a : {a}, b : {b}")
temp = a
a = b
b = temp
print(f"[교환 후] a : {a}, b : {b}")
위 코드가 바로 우리가 모범답안으로 생각하는 두 변수의 값을 서로 교환하는 코드이다.
너무 쉽고 단순하여 다른 방법을 고민할 필요성도 느끼기 힘들 정도이다. 하지만 그렇기에 더욱 고정관념이 생길 수 있다고 생각한다. 그래서 제약을 주어 새롭게 문제를 분석해보자.
제약사항은 임시변수를 쓰지 말고 기존에 있는 a와 b 변수만을 활용하는 것이다. 만약 이 프로그램이 일반 PC가 아닌 메모리의 크기가 부족한 가전제품에서 사용되는 것이라면 메모리의 크기가 한정되어있다. int 변수 1개를 줄이면 전자제품에 추가할 메모리 크기를 줄여 대량생산에서 큰 이익을 남길 수 있는 상황일 수도 있다.
[C언어 코드]
#include<stdio.h>
void main() {
int a = 10;
int b = 20;
printf("[교환 전] a : %d, b : %d\n", a, b);
a = a + b;
b = a - b;
a = a - b;
printf("[교환 후] a : %d, b : %d\n", a, b);
}
[파이썬 코드]
a = 10
b = 20
print(f"[교환 전] a : {a}, b : {b}")
a = a + b
b = a - b
a = a - b
print(f"[교환 후] a : {a}, b : {b}")
위 코드는 임시변수를 쓰지 않고 기존의 두 변수만 사용하여 데이터를 교환한 코드이다.
a와 b 변수는 정수 타입인 int 변수이다. 정수의 특징은 계산이 가능하다는 것이다. 두 수의 차이를 이용하는 것인데 사람들은 일상생활에서 이런 방법을 많이 사용한다.
예를 들면 이런 것이다.
내 키는 친구인 홍길동보다 5cm 크다.
내 키는 175cm이다.
홍길동의 키를 계산으로 알 수 있다.
내 키 – 5cm = 홍길동의 키
175cm – 5cm = 170cm
버스를 방금 아깝게 놓쳤다.
지금은 오전 7시이고 오전에 버스 배차간격은 15분이다.
다음 버스의 도착시간은 계산으로 알 수 있다.
오전 7시 + 15분 = 오전 7시 15분
이처럼 간단한 계산을 통해 데이터를 교환하는 것이 가능하다. 문제를 해결할 때 내가 알고 있는 간단한 수학적 계산을 활용할 수 있다면 아주 유용하게 사용할 수 있다. 그러므로 알고리즘에서 수학적 방식으로의 접근도 반드시 고려해보아야 한다.
추가로 임시변수를 만들지 않고 간단한 계산의 수학적 방식으로 두 변수의 값을 교환하는 문제를 해결하였다. 하지만 여기서 만족하지 말고 추가로 다른 방법을 고민해보자.
프로그래밍의 가장 매력적인 특징은 정답이 유일하지 않다는 것이다. 문제해결 능력이 뛰어난 사람을 “창의적이다”라고 이야기하는데 창의성의 한 종류로 유창성이 있다.
유창성은 특정 상황에서 가능한 많은 다양한 아이디어를 생각하는 능력이다. 유창성이 뛰어난 사람이 응용력이 좋다.
문제를 해결하려면 문제의 본질을 잘 이해해야 한다. 문제의 본질을 잘 이해하는 방법으로 “제1원칙 기반 사고”를 소개한다.
“제1원칙 기반 사고”는 일론 머스크가 쓰고 있는 방법으로도 유명하다. 아리스토텔레스가 형이상학이란 책에서 언급한 것으로 더 이상 추론될 수 없는 원칙에서부터 추론되어야 한다는 원칙이다. 어떤 문제에서 생각이나 사실을 덜어내고 본질에서부터 생각해야 한다는 것이다.
기존에 알고 있는 지식을 잘 연결하는 것도 중요하지만 “제1원칙 기반 사고”를 통해 본질에서부터 생각해야 하고, 필요하다고 생각되고 이해가 되지 않는 것이 있으면 해당 내용을 공부한 후 다시 고민해야 한다.
이 문제는 두 변수에 있는 데이터를 교환하는 것이니 여기서 본질은 “변수에 데이터를 어떻게 저장하는 것일까?”라고 접근할 수 있다. 프로그래밍을 공부할 때 변수라는 상자에 10이라는 숫자를 저장한다. 이해가 쉽기 위해 이렇게 설명한다. 조금만 더 깊이 공부하면 10이라는 숫자는 10진수이고 컴퓨터에는 10진수가 아닌 2진수로 관리가 되는 것을 알 수 있다. 그리고 변수는 크기가 있어서 해당 크기 이상의 데이터를 저장할 수 없고 만약 데이터의 크기가 작으면 비어있는 공간은 0으로 채운다는 것도 알 수 있다.
이런 방법으로 숫자가 int 변수에 저장되는 원리를 좀 더 자세히 알아야 할 필요성을 인지하고 스스로 그것을 찾아보아야 한다.
컴퓨터 환경에 따라 다를 수도 있지만 요즘 대부분은 int 변수가 4byte로 2,147,483,648 ~ 2,147,483,647 범위의 10진수를 저장할 수 있다. 당연히 다 외울 필요는 없다.
그러면 a와 b 변수에 10과 20이 저장될 때 2진수로 표현해보자. 편의상 1byte씩 한 칸을 띄운다.
| 변수명 | 10진수 | 2진수 |
| a | 10 | 00000000 00000000 00000000 00001010 |
| b | 20 | 00000000 00000000 00000000 00010100 |
int 변수는 약 21억까지의 숫자를 저장할 수 있는데 10과 20은 너무 작다. 그래서 왼쪽 부분은 거의 0으로 채워져 있다. 숫자는 오른쪽 끝을 기준으로 시작해서 숫자가 커질수록 왼쪽으로 자리를 차지한다.
그렇다면 만약 숫자가 아주 크지 않다면 2진수로 왼쪽 부분의 대부분은 계속 0만 있어서 사용되지 못하는 공간이 된다.
이 낭비되는 공간을 사용할 수는 없을까?
1원칙 기반 사고를 통해 본질인 변수의 데이터 저장 원리를 공부하다 보니 int 변수의 총 8byte 중 왼쪽에 있는 4byte를 사용할 방법을 찾게 되었다.
편한 계산을 위해 a와 b에서 최대 1byte(8bit)만 사용하는 것으로 하겠다. 그렇다면 왼쪽에 3byte(24bit)의 공간이 0으로 채워져 사용하지 않는 공간이 된다.
프로그래밍에서 비트를 이동시키거나 계산하는 것은 비트 연산자로 가능하다.
| 비트 연산자 | 표현 | 설명 |
| ~ | ~a | a값의 1의 보수 |
| & | a&b | a와 b의 비트 논리곱 |
| | | a|b | a와 b의 비트 논리합 |
| ^ | a^b | a와 b의 비트 베타적 논리곱 |
| << | a<<n | a값을 n비트 만큼 왼쪽으로 시프트 |
| >> | a>>n | a값을 n비트 만큼 오른쪽으로 시프트 |
위 비트 연산자를 활용하여 2진수의 10과 20을 비트 단위로 이동하고 논리곱과 논리합으로 계산하여 문제를 해결한 코드가 아래 코드이다.
[C언어 코드]
#include<stdio.h>
void main() {
int a = 10; // 주석1
int b = 20; // 주석2
printf("[교환 전] a : %d, b : %d\n", a, b);
b = a << 8 | b; // 주석3
a = b & 255; // 주석4
b = b >> 8; // 주석5
printf("[교환 후] a : %d, b : %d\n", a, b);
}a = 10 # 주석1
b = 20 # 주석2
print(f"[교환 전] a : {a}, b : {b}")
b = a << 8 | b # 주석3
a = b & 255 # 주석4
b = b >> 8 # 주석5
print(f"[교환 후] a : {a}, b : {b}")위 코드의 연산 과정에서 변수에 저장된 값을 10진수와 2진수로 정리한 표를 정리하였다.
| 주석 | 변수명 | 10진수 | 2진수 |
| 1 | a | 10 | 00000000 00000000 00000000 00001010 |
| 2 | b | 20 | 00000000 00000000 00000000 00010100 |
| 3 | a<<8 | 2560 | 00000000 00000000 00001010 00000000 |
| 3 | b = a << 8 | b | 2580 | 00000000 00000000 00001010 00010100 |
| 4 | a = b & 255 | 20 | 00000000 00000000 00000000 00010100 |
| 5 | b = b >> 8 | 10 | 00000000 00000000 00000000 00001010 |
10진수를 2진수로 저장할 때 숫자가 크지 않으면 일부 공간이 낭비되는 문제를 이용한 방식으로 문제를 풀어보았다. 이 방식에서의 단점은 큰 숫자의 경우 정상적으로 교환되지 않고 숫자가 변경될 가능성이 있다. int 자료형의 변수가 가지는 공간을 일부 빌려 쓰기 때문이다.
[결론]
임시변수를 사용하지 않는다는 제약을 통해 다른 관점으로 문제해결 방법을 고민해보았다.
특정 상황에서 가능한 많은 아이디어를 생각하려면 평소에 유창성을 잘 발휘할 수 있도록 연습이 필요하다. 제약을 통해 어쩔 수 없이 다른 관점으로 생각해보는 훈련이 유창성을 키워 응용력에 도움을 줄 것으로 믿는다.
세부 방법으로는 문제를 해결할 알고리즘을 고민할 때 반드시 수학적 접근을 해보길 추천한다. 어려운 수학이 아니라도 간단한 계산을 통해 많은 것을 알 수 있다.
그리고 문제의 본질에서부터 접근하는 것을 연습하기 위하여 제1원칙 기반 사고를 통해 접근하면 기존에 가지고 있던 고정관념이 없어지고 문제를 다른 관점으로 바라보게 될 것이다.
'알고리즘' 카테고리의 다른 글
| 제약을 통한 문제해결 응용력 키우기 훈련 2-1 (데이터 교환) (0) | 2022.12.10 |
|---|---|
| 제약을 통한 문제해결 응용력 키우기 훈련 1 (구구단) (1) | 2022.11.30 |