Ros package 만들어보기
1. manifest 파일 만들기
recommended format
<package format="2">
<name>foo_core</name>
<version>1.2.4</version>
<description>
This package provides foo capability.
</description>
<maintainer email="ivana@osrf.org">Ivana Bildbotz</maintainer>
<license>BSD</license>
</package>
여러개의 패키지를 하나로 묶는 태그
<export>
<metapackage />
</export>
2. CMakeList.txt 만들기
structure
1.version => cmake_minimum_required(VERSION 2.8.3)
2. package name => project(robot_brain)
3. 필요한 패키지 => find_package(catkin REQUIRED)
4. catkin_package(
INCLUDE_DIRS include
=> The exported include paths (i.e. cflags) for the package
LIBRARIES ${PROJECT_NAME}
=> The exported libraries from the project
CATKIN_DEPENDS roscpp nodelet
=> Other catkin projects that this project depends on
DEPENDS eigen opencv)
=> Non-catkin CMake projects that this project depends on
5. set_target_properties(
rviz_image_view
PROPERTIES OUTPUT_NAME image_view
PREFIX "")
6. path
include_directories(include ${Boost_INCLUDE_DIRS}${catkin_INCLUDE_DIRS})
link_directories(~/my_libs)
7. executable target을 정해준다.
add_executable(myProgram src/main.cpp src/some_file.cpp src/another_file.cpp)
8.
add_library(${PROJECT_NAME} ${${PROJECT_NAME}_SRCS})
9.
target_link_libraries(<executableTargetName>, <lib1>, <lib2>, ... <libN>)
System dependency 관리
Ros package가 운영체제에 있는 라이브러리를 쓰고자 할 때 System Dependency를 추가해줘야한다.
How? rosdep install package
2015년 8월 12일 수요일
2015년 8월 11일 화요일
ROS 나만의 정리(1)
ROS의 설치
필요조건: 우분투(영어 버전으로 설치)
http://wiki.ros.org/indigo/Installation/Ubuntu(Indigo)따라하기
설치하기 전에 버전 확인하기 (ROS 버전과 Ubuntu 버전)
Ros 위키에 있는 내용을 나에게 맞게 정리
rospack find package_name : 패키지의 경로 반환
roscd package_name : 폴더 이동
roscd log : Ros의 로그파일이 저장되있는 폴더로 이동
rosls package_name : package 안의 list를 보여줌
catkin에서 작업공간 만들기
1. mkdir -p ~/catkin_ws/src
2. cd ~/catkin_ws/src
3. catkin_init_workspace
4. cd ~/catkin_ws/
5. catkin_make
catkin_make : Ros package build
roscore : Ros를 사용할 때 가장 먼저 하는 일
rosnode 명령어 : node에 대한 정보를 알고 싶을 때
rosrun package_name node : node를 직접 실행
publish : 주는 것 subscribe : 받는 것
rqt_graph 사용
$ sudo apt-get install ros-<distro>-rqt $ sudo apt-get install ros-<distro>-rqt-common-plugins
<distro>는 자기 버전에 맞게 바꾸기 ex) indigo, hydro
rostopic 명령어 : topic을 다룰 때 사용
rostopic -h 를 통해 자세한 기능을 알아볼 것
rostopic pup topic msg_type args : 현재의 topic에 publish data
ex)
rostopic pup
-1 : 하나의 메시지만 publish
/turtle/cmd_vel : publish 하고 싶은 topic의 이름
geometry_msgs/twist : publish 할 내용이 담겨있는 메시지
-- : option
rosrun rqt_plot rqt_plot : topic에 publish된 data를 시간에 따라 plot에 표현
rosservice : Ros의 client나 service에 쉽게 attach 가능
rosservice -h로 커맨드에 대해 알아볼 것
rosparam : Ros parameter server에 있는 data를 저장하고 조작하는 데 쓰인다.
rosparam -h로 커맨드에 대해 알아볼 것
rosed package_name filename : package_name으로 파일 수정
필요조건: 우분투(영어 버전으로 설치)
software & updates 화면이 이와 같아야 한다.
확인점: main, universe, restricted, multiverse checked
Download from: Main server
설치하기 전에 버전 확인하기 (ROS 버전과 Ubuntu 버전)
Ros 위키에 있는 내용을 나에게 맞게 정리
rospack find package_name : 패키지의 경로 반환
roscd package_name : 폴더 이동
roscd log : Ros의 로그파일이 저장되있는 폴더로 이동
rosls package_name : package 안의 list를 보여줌
catkin에서 작업공간 만들기
1. mkdir -p ~/catkin_ws/src
2. cd ~/catkin_ws/src
3. catkin_init_workspace
4. cd ~/catkin_ws/
5. catkin_make
catkin_make : Ros package build
roscore : Ros를 사용할 때 가장 먼저 하는 일
rosnode 명령어 : node에 대한 정보를 알고 싶을 때
rosrun package_name node : node를 직접 실행
publish : 주는 것 subscribe : 받는 것
rqt_graph 사용
$ sudo apt-get install ros-<distro>-rqt $ sudo apt-get install ros-<distro>-rqt-common-plugins
<distro>는 자기 버전에 맞게 바꾸기 ex) indigo, hydro
rostopic 명령어 : topic을 다룰 때 사용
rostopic -h 를 통해 자세한 기능을 알아볼 것
rostopic pup topic msg_type args : 현재의 topic에 publish data
ex)
rostopic pup
-1 : 하나의 메시지만 publish
/turtle/cmd_vel : publish 하고 싶은 topic의 이름
geometry_msgs/twist : publish 할 내용이 담겨있는 메시지
-- : option
rosrun rqt_plot rqt_plot : topic에 publish된 data를 시간에 따라 plot에 표현
rosservice : Ros의 client나 service에 쉽게 attach 가능
rosservice -h로 커맨드에 대해 알아볼 것
rosparam : Ros parameter server에 있는 data를 저장하고 조작하는 데 쓰인다.
rosparam -h로 커맨드에 대해 알아볼 것
rosed package_name filename : package_name으로 파일 수정
2015년 8월 9일 일요일
Ontology (1)
Ontology의 주요 구성 요소
1. 논리적 추론
2. 추상적 사고
3. 개념과 언어를 이해
4. 유사한 개념이나 사물을 분류
개념화
1. 인식한 것들을 구분하고 구분된 영역을 무엇이라고 부르는 지 배운다.
2. 영역안에서 객체들을 분리한다.
3. 다른 구성원들이 영역을 어떻게 분류하고 부르는 지 안다.
4. 영역안에서 분류된 각 객체들간의 관계와 고유의 속성을 정의합니다.
1. 논리적 추론
2. 추상적 사고
3. 개념과 언어를 이해
4. 유사한 개념이나 사물을 분류
개념화
1. 인식한 것들을 구분하고 구분된 영역을 무엇이라고 부르는 지 배운다.
2. 영역안에서 객체들을 분리한다.
3. 다른 구성원들이 영역을 어떻게 분류하고 부르는 지 안다.
4. 영역안에서 분류된 각 객체들간의 관계와 고유의 속성을 정의합니다.
2015년 8월 7일 금요일
알고리즘 문제 해결 전략(4)
분할 정복
주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부문 문제의 답으로부터 전체 문제의 답을 계산한다.
세 가지 구성 요소
문제를 더 작은 문제로 분할하는 과정(divide)
각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge)
더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)
수열의 빠른 합과 행렬의 빠른 제곱
fastSum(n) = 2*fastSum(n/2)+(n^2/4)
//필수 조건: n은 자연수
//1 + 2 + ... + n을 반환한다.
int fastSum(int n) {
//기저 사례
if(n == 1) return 1;
if(n % 2 == 1) return fastSum(n-1) + n;
return 2*fastSum(n/2) + (n/2)*(n/2);
}
행렬의 거듭제곱
A^m = (A^(m/2))*(A^(m/2))
//정방행렬을 표현하는 SqureMatrix 클래스가 있다고 가정하자.
class SquareMatrix;
// n*n 크기의 항등 행렬(identity matrix)을 반환하는 함수
SquareMatrix identity(int n);
//A^m을 반환한다.
SquareMatrix pow(const SqureMatrix& A, int m) {
//기저 사례: A^0 = 1
if(m == 0) return identity(A.size());
if( m % 2 > 0) return pow(A, m-1) * A;
SquareMatrix half = pow(A, m /2);
//A^m = (A^(m/2))*(A^(m/2))
return half * half;
}
나누어 떨어지지 않을 때의 분할과 시간 복잡도
같은 문제라도 어떻게 분할하느냐에 따라 시간 복잡도 차이가 커진다.
Why? 여러 번 중복되어 계산되면서 시간을 소모하는 부분 문제들이 있다.
병합 정렬과 퀵 정렬
병합 정렬 알고리즘
1. 주어진 수열을 가운데에서 쪼개 비슷한 크기의 수열 두개로 만든 뒤 이들을 재귀 호출을 이용해 각각 정렬한다.
2. 그 후 정렬된 배열을 하나로 합침으로써 정렬된 전체 수열을 얻습니다.
퀵 정렬 알고리즘
1. 병합 과정이 필요 없도록 한쪽의 배열에 포함된 수가 다른 쪽 배열의 수보다 항상 작도록 배열을 분할
=> 퀵 정렬은 파티션이라고 부르는 단계를 도입하는데, 배열에 있는 수 중 임의의 '기준 수(pivot)'를 지정한 후 기준보다 작거나 같은 숫자를 왼쪽, 더 큰 숫자를 오른쪽으로 보낸다.
일반적인 곱셈 알고리즘
//num[]의 자릿수 올림을 처리한다.
void nomalize(vector<int>& num) {
num.push_back(0);
//자릿수 올림을 처리한다.
for (int i = 0; i < num.size(); ++i) {
if (num[i] < 0) {
int borrow = (abs(num[i]) + 9) / 10;
num[i + 1] -= borrow;
num[i] += borrow * 10;
}
else {
num[i + 1] += num[i] / 10;
num[i] %= 10;
}
}while (num.size() > 1 && num.back() == 0) num.pop_back();
}
// 두 긴 자연수의 곱을 반환한다.
// 각 배열에는 각 수의 자릿수가 1의 자리에서부터 시작해 저장되어 있다.
vector<int> multiply(const vector<int>& a, const vector<int>& b) {
vector<int> c(a.size() + b.size() + 1, 0);
for (int i = 0; i < a.size(); ++i)
for (int j = 0; j < b.size(); ++j)
c[i + j] += a[i] * b[j];
nomalize(c);
return c;
}
예제: 카라츠바의 빠른 곱셈 알고리즘
카라츠바의 빠른 곱셈 알고리즘은 두 수를 각각 절반으로 쪼갠다. a와 b가 각각 256자리 수라면 a1 과 b1은 첫 128자리, a0 과 b0은 그 다음 128자리를 저장하도록 하는 것이다.
a = a1 * 10^128 + a0
b = b1 * 10^128 + b0
a*b = (a1 * 10^128 + a0)*(b1 * 10^128 + b0)
= a1 * b1 * 10^256 + (a1 * b0 + a0 * b1) * 10^256 + a0 * b0
z2 z1 z0
z2 = a1 * b1;
z0 = a0 * b0;
z1 = (a0 + a1) * (b0 + b1) - z0 - z2;
=> 곱셈을 세 번밖에 쓰지 않는다.
// a += b * (10 ^ k)
void addTo(vector<int>& a, const vector<int>& b, int k);
// a -= b; a>=b를 가정
void subFrom(vector<int>& a, const vector<int>& b);
// 두 긴 정수의 곱을 반환한다.
vector<int> karatsuba(const vector<int>& a, const vector<int>& b) {
int an = a.size(), bn = b.size();
// a가 b보다 짧을 경우 둘을 바꾼다.
if (an < bn) return karatsuba(b, a);
// 기저 사례: a나 b가 비어 있는 경우
if (an == 0 || bn == 0) return vector<int>();
// 기저 사례: a가 비교적 짧은 경우 O(n^2) 곱셈으로 변경한다.
if (an <= 50) return multiply(a, b);
int half = an / 2;
// a 와 b를 밑에서 half 자리와 나머지로 분리한다.
vector<int> a0(a.begin(), a.begin() + half);
vector<int> a1(a.begin() + half, a.end());
vector<int> b0(b.begin(), b.begin() + min<int>(b.size(), half));
vector<int> b1(b.begin() + min<int>(b.size(), half), b.end());
//z2 = a1 * b1
vector<int> z2 = karatsuba(a1, b1);
//z0 = a0 * b0
vector<int> z0 = karatsuba(a0, b0);
//a0 = a0 + a1; b0 = b0 + b1
addTo(a0, a1, 0); addTo(b0, b1, 0);
//z1 = (a0*b0) - z0 - z2
vector<int> z1 = karatsuba(a0, b0);
subFrom(z1, z0);
subFrom(z1, z2);
//ret = z0 + z1 * 10^half + z2 * 10^(half*2)
vector<int> ret;
addTo(ret, z0, 0);
addTo(ret, z1, half);
addTo(ret, z2, half + half);
return ret;
}
쿼드 트리 뒤집기
대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 하나
주어진 공간을 항상 4개로 분할해 재귀적으로 표현함
검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현
1. 이 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림과 관계없이 b가 된다.
2. 이 그림의 모든 픽셀이 흰 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 w가 됩니다.
3. 모든 픽셀이 같은 색이 아니라면, 쿼드 트리는 이 그림을 가로 세로로 각각 2등분해 4개의 조각으로 쪼갠 뒤 각각을 쿼드 트리 압축합니다. 이때 전체 그림의 압축 결과는 x(왼쪽 위 부분의 압축 결과)(오른쪽 위 부분의 압축 결과)(왼쪽 아래 부분의 압축 결과)(오른쪽 아래 부분의 압축 결과)가 된다.
쿼드 트리 압축 풀기
char decompressed[MAX_SIZE][MAX_SIZE];
// s를 압축 해제해서 decompressed[y..y+size-1][x..x+size-1] 구간에 쓴다.
void decompress(const string& s. int y , int x, int size);
압축 문자열 분할하기
s의 나머지 부분을 넷으로 쪼개기가 어렵다
why? 각 부분의 길이가 일정하지 않다.
solution
1. 주어진 위치에서 시작하는 압축 결과의 길이를 반환하는 함수를 만든다.
ex) s[0]이 x라고 할 때, 왼쪽위==s[1]이면 getChunkLength(s,1)이 해당 부분의 길이를 반환
getChunkLength(s, 1)이 4를 반환한다고 할 때, 다음 조각은 s[5]부터 시작
2. s를 미리 쪼개는 것이 아닌 decompress()함수에서 '필요한 만큼 가져다 쓰도록' 한다.
decompress() 함수에 s를 통째로 전달하는 것이 아닌, s의 한 글자를 가리키는 포인터를 전달한 후 함수 내에서 한 글자를 검사할 때마다 이 포인터를 앞으로 한 칸씩 옮긴다.
char decompressed[MAX_SIZE][MAX_SIZE];
void decompressed(string::iterator& it, int y, int x, int size) {
// 한 글자를 검사할 때마다 반복자를 한 칸 앞으로 옮긴다.
char head = *(it++);
// 기저 사례: 첫 글자가 b 또른 w인 경우
if (head == 'b' || head = 'w') {
for (int dy = 0; dy < size; ++dy)
for (int dx = 0; dx < size; ++dx)
decompressed[y + dy][x + dx] = head;
}
else {
// 네 부분을 순서대로 압축 해제
int half = size / 2;
decompressed(it, y, x, half);
decompressed(it, y, x + half, half);
decompressed(it, y + half, x, half);
decompressed(it, y + half, x + half, half);
}
}
압축 다 풀지 않고 뒤집기
string reverse(string::iterator& it) {
char head = *it;
++it;
if (head == 'b' || head == 'w')
return string(1, head);
string upperLeft = reverse(it);
string upperRight = reverse(it);
string lowerLeft = reverse(it);
string lowerRight = reverse(it);
// 각각 위와 아래 조각들의 위치를 바꾼다.
return string("x") + lowerLeft + lowerRight + upperLeft + upperRight;
}
울타리 잘라내기
분할 정복 알고리즘의 설계
가장 큰 직사각형을 왼쪽 부분 문제에서만 잘라낼 수 있다.
가장 큰 직사각형을 오른쪽 부분 문제에서만 잘라낼 수 있다.
가장 큰 직사각형은 왼쪽 부분 문제와 오른쪽 부분 문제에 걸쳐 있다.
//각 판자의 높이를 저장하는 배열
vector<int> h;
// h[left..right] 구간에서 찾아낼 수 있는 가장 큰 사각형의 넓이를 반환한다.
int solve(int left, int right) {
//기저 사례:판자가 하나밖에 없는 경우
if (left == right) return h[left];
// [left, mid], [mid + 1, right]의 두 구간으로 문제를 분할한다.
int mid = (left + right) / 2;
// 분할한 문제를 각개격파
int ret = max(solve(left, mid), solve(mid + 1, right));
// 부분 문제 3: 두 부분에 모두 걸치는 사각형 중 가장 큰 것을 찾는다.
int lo = mid, hi = mid + 1;
int height = min(h[lo], h[hi]);
// [mid, mid+1]만 포함하는 너비 2인 사각형을 고려
ret = max(ret, height * 2);
// 사각형이 입력 전체를 덮을 때까지 확장해 나간다.
while (left < lo || hi < right) {
//항상 높이가 더 높은 쪽으로 확장
if (hi < right && (lo == left || h[lo - 1] < h[hi + 1])) {
++hi;
height = min(height, h[hi]);
}
else {
--lo;
height = min(height, h[lo]);
}
// 확장한 후 사각형의 넓이
ret = max(ret, height * (hi - lo + 1));
}
return ret;
}
정당성
양쪽 부분 문제에 걸쳐있는 직사각형을 찾을 때, 각 단계마다 더 높은 판자를 택하는 것이 항상 옳다.
알고리즘에서는 너비가 2인 사각형에서 시작해서 한 칸씩 사각형의 너비를 늘려가므로,
우리가 고려한 사각형들 중 R과 너비가 같은 사각형(R')이 반드시 하나 있다.
너비가 같으면 높이가 높은 쪽이 크기가 크다.
팬미팅
int hugs(const string& members, const string& fans) {
int N = members.size(), M = fans.size();
vector<int> A(N), B(M);
for (int i = 0; i < N; i++) A[i] = (members[i] == 'M');
for (int i = 0; i < M; i++) B[M - 1 - i] = (fans[i] == 'M');
//karatsuba 알고리즘에서 자리 올림은 생략한다.
vector<int> C = karatsuba(A, B);
int allHugs = 0;
for (int i = N - 1; i < M; i++)
if (C[i] == 0)
++allHugs;
return allHugs;
}
주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부문 문제의 답으로부터 전체 문제의 답을 계산한다.
세 가지 구성 요소
문제를 더 작은 문제로 분할하는 과정(divide)
각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge)
더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)
수열의 빠른 합과 행렬의 빠른 제곱
fastSum(n) = 2*fastSum(n/2)+(n^2/4)
//필수 조건: n은 자연수
//1 + 2 + ... + n을 반환한다.
int fastSum(int n) {
//기저 사례
if(n == 1) return 1;
if(n % 2 == 1) return fastSum(n-1) + n;
return 2*fastSum(n/2) + (n/2)*(n/2);
}
행렬의 거듭제곱
A^m = (A^(m/2))*(A^(m/2))
//정방행렬을 표현하는 SqureMatrix 클래스가 있다고 가정하자.
class SquareMatrix;
// n*n 크기의 항등 행렬(identity matrix)을 반환하는 함수
SquareMatrix identity(int n);
//A^m을 반환한다.
SquareMatrix pow(const SqureMatrix& A, int m) {
//기저 사례: A^0 = 1
if(m == 0) return identity(A.size());
if( m % 2 > 0) return pow(A, m-1) * A;
SquareMatrix half = pow(A, m /2);
//A^m = (A^(m/2))*(A^(m/2))
return half * half;
}
나누어 떨어지지 않을 때의 분할과 시간 복잡도
같은 문제라도 어떻게 분할하느냐에 따라 시간 복잡도 차이가 커진다.
Why? 여러 번 중복되어 계산되면서 시간을 소모하는 부분 문제들이 있다.
병합 정렬과 퀵 정렬
1. 주어진 수열을 가운데에서 쪼개 비슷한 크기의 수열 두개로 만든 뒤 이들을 재귀 호출을 이용해 각각 정렬한다.
2. 그 후 정렬된 배열을 하나로 합침으로써 정렬된 전체 수열을 얻습니다.
1. 병합 과정이 필요 없도록 한쪽의 배열에 포함된 수가 다른 쪽 배열의 수보다 항상 작도록 배열을 분할
=> 퀵 정렬은 파티션이라고 부르는 단계를 도입하는데, 배열에 있는 수 중 임의의 '기준 수(pivot)'를 지정한 후 기준보다 작거나 같은 숫자를 왼쪽, 더 큰 숫자를 오른쪽으로 보낸다.
일반적인 곱셈 알고리즘
//num[]의 자릿수 올림을 처리한다.
void nomalize(vector<int>& num) {
num.push_back(0);
//자릿수 올림을 처리한다.
for (int i = 0; i < num.size(); ++i) {
if (num[i] < 0) {
int borrow = (abs(num[i]) + 9) / 10;
num[i + 1] -= borrow;
num[i] += borrow * 10;
}
else {
num[i + 1] += num[i] / 10;
num[i] %= 10;
}
}while (num.size() > 1 && num.back() == 0) num.pop_back();
}
// 두 긴 자연수의 곱을 반환한다.
// 각 배열에는 각 수의 자릿수가 1의 자리에서부터 시작해 저장되어 있다.
vector<int> multiply(const vector<int>& a, const vector<int>& b) {
vector<int> c(a.size() + b.size() + 1, 0);
for (int i = 0; i < a.size(); ++i)
for (int j = 0; j < b.size(); ++j)
c[i + j] += a[i] * b[j];
nomalize(c);
return c;
}
예제: 카라츠바의 빠른 곱셈 알고리즘
카라츠바의 빠른 곱셈 알고리즘은 두 수를 각각 절반으로 쪼갠다. a와 b가 각각 256자리 수라면 a1 과 b1은 첫 128자리, a0 과 b0은 그 다음 128자리를 저장하도록 하는 것이다.
a = a1 * 10^128 + a0
b = b1 * 10^128 + b0
a*b = (a1 * 10^128 + a0)*(b1 * 10^128 + b0)
= a1 * b1 * 10^256 + (a1 * b0 + a0 * b1) * 10^256 + a0 * b0
z2 z1 z0
z2 = a1 * b1;
z0 = a0 * b0;
z1 = (a0 + a1) * (b0 + b1) - z0 - z2;
=> 곱셈을 세 번밖에 쓰지 않는다.
// a += b * (10 ^ k)
void addTo(vector<int>& a, const vector<int>& b, int k);
// a -= b; a>=b를 가정
void subFrom(vector<int>& a, const vector<int>& b);
// 두 긴 정수의 곱을 반환한다.
vector<int> karatsuba(const vector<int>& a, const vector<int>& b) {
int an = a.size(), bn = b.size();
// a가 b보다 짧을 경우 둘을 바꾼다.
if (an < bn) return karatsuba(b, a);
// 기저 사례: a나 b가 비어 있는 경우
if (an == 0 || bn == 0) return vector<int>();
// 기저 사례: a가 비교적 짧은 경우 O(n^2) 곱셈으로 변경한다.
if (an <= 50) return multiply(a, b);
int half = an / 2;
// a 와 b를 밑에서 half 자리와 나머지로 분리한다.
vector<int> a0(a.begin(), a.begin() + half);
vector<int> a1(a.begin() + half, a.end());
vector<int> b0(b.begin(), b.begin() + min<int>(b.size(), half));
vector<int> b1(b.begin() + min<int>(b.size(), half), b.end());
//z2 = a1 * b1
vector<int> z2 = karatsuba(a1, b1);
//z0 = a0 * b0
vector<int> z0 = karatsuba(a0, b0);
//a0 = a0 + a1; b0 = b0 + b1
addTo(a0, a1, 0); addTo(b0, b1, 0);
//z1 = (a0*b0) - z0 - z2
vector<int> z1 = karatsuba(a0, b0);
subFrom(z1, z0);
subFrom(z1, z2);
//ret = z0 + z1 * 10^half + z2 * 10^(half*2)
vector<int> ret;
addTo(ret, z0, 0);
addTo(ret, z1, half);
addTo(ret, z2, half + half);
return ret;
}
쿼드 트리 뒤집기
대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 하나
주어진 공간을 항상 4개로 분할해 재귀적으로 표현함
검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현
1. 이 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림과 관계없이 b가 된다.
2. 이 그림의 모든 픽셀이 흰 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 w가 됩니다.
3. 모든 픽셀이 같은 색이 아니라면, 쿼드 트리는 이 그림을 가로 세로로 각각 2등분해 4개의 조각으로 쪼갠 뒤 각각을 쿼드 트리 압축합니다. 이때 전체 그림의 압축 결과는 x(왼쪽 위 부분의 압축 결과)(오른쪽 위 부분의 압축 결과)(왼쪽 아래 부분의 압축 결과)(오른쪽 아래 부분의 압축 결과)가 된다.
쿼드 트리 압축 풀기
char decompressed[MAX_SIZE][MAX_SIZE];
// s를 압축 해제해서 decompressed[y..y+size-1][x..x+size-1] 구간에 쓴다.
void decompress(const string& s. int y , int x, int size);
압축 문자열 분할하기
s의 나머지 부분을 넷으로 쪼개기가 어렵다
why? 각 부분의 길이가 일정하지 않다.
solution
1. 주어진 위치에서 시작하는 압축 결과의 길이를 반환하는 함수를 만든다.
ex) s[0]이 x라고 할 때, 왼쪽위==s[1]이면 getChunkLength(s,1)이 해당 부분의 길이를 반환
getChunkLength(s, 1)이 4를 반환한다고 할 때, 다음 조각은 s[5]부터 시작
2. s를 미리 쪼개는 것이 아닌 decompress()함수에서 '필요한 만큼 가져다 쓰도록' 한다.
decompress() 함수에 s를 통째로 전달하는 것이 아닌, s의 한 글자를 가리키는 포인터를 전달한 후 함수 내에서 한 글자를 검사할 때마다 이 포인터를 앞으로 한 칸씩 옮긴다.
char decompressed[MAX_SIZE][MAX_SIZE];
void decompressed(string::iterator& it, int y, int x, int size) {
// 한 글자를 검사할 때마다 반복자를 한 칸 앞으로 옮긴다.
char head = *(it++);
// 기저 사례: 첫 글자가 b 또른 w인 경우
if (head == 'b' || head = 'w') {
for (int dy = 0; dy < size; ++dy)
for (int dx = 0; dx < size; ++dx)
decompressed[y + dy][x + dx] = head;
}
else {
// 네 부분을 순서대로 압축 해제
int half = size / 2;
decompressed(it, y, x, half);
decompressed(it, y, x + half, half);
decompressed(it, y + half, x, half);
decompressed(it, y + half, x + half, half);
}
}
압축 다 풀지 않고 뒤집기
string reverse(string::iterator& it) {
char head = *it;
++it;
if (head == 'b' || head == 'w')
return string(1, head);
string upperLeft = reverse(it);
string upperRight = reverse(it);
string lowerLeft = reverse(it);
string lowerRight = reverse(it);
// 각각 위와 아래 조각들의 위치를 바꾼다.
return string("x") + lowerLeft + lowerRight + upperLeft + upperRight;
}
울타리 잘라내기
분할 정복 알고리즘의 설계
가장 큰 직사각형을 왼쪽 부분 문제에서만 잘라낼 수 있다.
가장 큰 직사각형을 오른쪽 부분 문제에서만 잘라낼 수 있다.
가장 큰 직사각형은 왼쪽 부분 문제와 오른쪽 부분 문제에 걸쳐 있다.
//각 판자의 높이를 저장하는 배열
vector<int> h;
// h[left..right] 구간에서 찾아낼 수 있는 가장 큰 사각형의 넓이를 반환한다.
int solve(int left, int right) {
//기저 사례:판자가 하나밖에 없는 경우
if (left == right) return h[left];
// [left, mid], [mid + 1, right]의 두 구간으로 문제를 분할한다.
int mid = (left + right) / 2;
// 분할한 문제를 각개격파
int ret = max(solve(left, mid), solve(mid + 1, right));
// 부분 문제 3: 두 부분에 모두 걸치는 사각형 중 가장 큰 것을 찾는다.
int lo = mid, hi = mid + 1;
int height = min(h[lo], h[hi]);
// [mid, mid+1]만 포함하는 너비 2인 사각형을 고려
ret = max(ret, height * 2);
// 사각형이 입력 전체를 덮을 때까지 확장해 나간다.
while (left < lo || hi < right) {
//항상 높이가 더 높은 쪽으로 확장
if (hi < right && (lo == left || h[lo - 1] < h[hi + 1])) {
++hi;
height = min(height, h[hi]);
}
else {
--lo;
height = min(height, h[lo]);
}
// 확장한 후 사각형의 넓이
ret = max(ret, height * (hi - lo + 1));
}
return ret;
}
정당성
양쪽 부분 문제에 걸쳐있는 직사각형을 찾을 때, 각 단계마다 더 높은 판자를 택하는 것이 항상 옳다.
알고리즘에서는 너비가 2인 사각형에서 시작해서 한 칸씩 사각형의 너비를 늘려가므로,
우리가 고려한 사각형들 중 R과 너비가 같은 사각형(R')이 반드시 하나 있다.
너비가 같으면 높이가 높은 쪽이 크기가 크다.
팬미팅
int hugs(const string& members, const string& fans) {
int N = members.size(), M = fans.size();
vector<int> A(N), B(M);
for (int i = 0; i < N; i++) A[i] = (members[i] == 'M');
for (int i = 0; i < M; i++) B[M - 1 - i] = (fans[i] == 'M');
//karatsuba 알고리즘에서 자리 올림은 생략한다.
vector<int> C = karatsuba(A, B);
int allHugs = 0;
for (int i = N - 1; i < M; i++)
if (C[i] == 0)
++allHugs;
return allHugs;
}
2015년 8월 4일 화요일
알고리즘 문제 해결 전략(3)
무식하게 풀기 - 완전 탐색
재귀 호출과 완전 탐색
재귀 함수
자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고,
나머지를 자기 자신을 호출해 실행하는 함수
모든 재귀함수는 '더이상 쪼개지지 않는' 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야 한다.
쪼개지지 않는 가장 작은 작업 == 기저 사례
for(int i = 0; i < n; ++i)
for(int j = i+1; j < n; ++j)
for(int k = j+1; k < n; ++k)
for(int l = k+1; l < n; ++l)
cout << i << " " << j << " " << k << " " << l << endl;
n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘
// n: 전체 원소의 수
// picked: 지금까지 고른 원소들의 번호
// toPick: 더 고를 원소의 수일때, 앞으로 toPick개의 원소를 고르는 모든 방법을 출력한다.
void pick(int n, vector<int>& picked, int toPick) {
//기저 사례: 더 고를 원소가 없을 때 고른 원소들을 출력한다.
if(toPick == 0) {printPicked(picked); return;}
//고를 수 있는 가장 작은 번호를 계산한다.
int smallest = picked.empty() ? 0 : picked.back() + 1;
//이 단계에서 원소하나를 고른다.
for(int next = smallest; next < n; ++next) {
picked.push_back(next);
pick(n, picked, toPick - 1);
picked.pop_back();
}
}
ex) 보글게임
상하좌우 / 대각선으로 인접한 칸들의 글자들을 이어서 단어를 찾아내는 것
hasWord(y, x, word) = 보들 게임판의 (y, x)에서 시작하는 단어 word의 존재 여부를 반환
문제의 분할
hasWord()가 하는 일을 가장 자연스럽게 조각내는 방법은 각 글자를 하나의 조각으로 만드는 것이다. 함수 호출시에 단어의 시작 위치를 정해 주기 때문에, 문제의 조각들 중 첫 번째 글자에 해당하는 조각을 간단하게 해결할 수 있다. 그 이후에는 시작위치와 인접한 여덟 칸을 모두 시도하면서 답을 찾으면 된다.
기저 사례의 선택
1. 위치 (y, x)에 잇는 글자가 원하는 단어의 첫 글자가 아닌 경우 항상 실패
2. (1번 경우에 해당하지 않을 경우)원하는 단어가 한글자인 경우 항상 성공
Tip: 입력이 잘못되거난 범위에서 벗어난 경우도 기저 사례로 택해서 맨 처음에 처리
const int dx[8] = {-1, -1, -1, 1, 1, 1, 0, 0};
const int dy[8] = {-1, 0, 1, -1, 0, 1, -1, 1};
//5X5의 보글 게임 판의 해당 위치에서 주어진 단어가 시작하는 지를 반환
bool hasWord(int y, int x, const string& word) {
// 기저 사례 1: 시작 위치가 범위 밖이면 무조건 실패
if(!inRange(y,x)) return false;
// 기저 사례 2: 첫 글자가 일치하지 않으면 실패
if(board[y][x] != word[0]) return false;
// 기저 사례 3: 단어 길이가 1이면 성공
if(word.size() == 1) return true;
// 인접한 여덟 칸을 검사한다.
for(int direction = 0; direction < 8; ++direction) {
int nextY = y + dy[direction], next = x + dx[direction];
//다음 칸이 범위 안에 있는지, 첫 글자는 일치하는지 확인할 필요가 없다.
if(hasWord(nextY, nextX, word.substr(1)))
return true;
}
return false;
}
완전 탐색 레시피
1. 완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에
정확히 비례한다. 그러므로 최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 이들을 모두 제한 시간 안에 생성할 수 있을지를 가늠한다.
2. 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눈다.
3. 그중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성
4. 조각이 하나밖에 남지 않으 경우, 혹은 하나도 남지 않은 경우에는 답을 생성했으므로, 그섯을 기저 사례로 선택해 처리한다.
이론적 배경 : 재귀 호출과 부분 문제
문제 : 소풍 (문제 ID: PICNIC, 난이도: 하)
int n;
bool areFriends[10][10];
// 아직 짝을 찾지 못한 학생들의 명단이 주어질 때 친구끼리 둘씩 짝짓는 경우의 수를 // 계산하라.
int countPairings(bool taken[10]) {
//기저 사례: i번째 학생이 짝을 이미 찾았으면 true, 아니면 false
bool finished = true;
for (int i = 0; i < n; i++) if (!taken[i]) finished = false;
if (finished) return 1;
int ret = 0;
// 서로 친구인 두 학생을 찾아 짝을 지어준다.
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (!taken[i] && !taken[j] && areFriends[i][j]) {
taken[i] = taken[j] = true;
ret += countPairings(taken);
taken[i] = taken[j] = false;
}
return ret;
}
int n;
bool areFriends[10][10];
// Wrong의 해결 방안: 각 단계에서 남아 있는 학생들 중 가장 번호가 빠른 학생의 짝을 찾아 주도록 하면 된다.
// 아직 짝을 찾지 못한 학생들의 명단이 주어질 때 친구끼리 둘씩 짝짓는 경우의 수를 계산하라.
int countPairings(bool taken[10]) {
// 남은 학생들 중 가장 번호가 빠른 학생을 찾는다.
int firstFree = -1;
for (int i = 0; i < n; ++i) {
if (!taken[i]) {
firstFree = i;
break;
}
}
//기저사례: 모든 학생이 짝을 찾았으면 한 가지 방법을 찾았으니 종료한다.
int ret = 0;
// 서로 친구인 두 학생을 찾아 짝을 지어준다.
for (int pairWith = firstFree + 1; pairWith < n; ++pairWith) {
if (!taken[pairWith] && areFriends[firstFree][pairWith]) {
taken[firstFree] = taken[pairWith] = true;
ret += countPairings(taken);
taken[firstFree] = taken[pairWith] = false;
}
}
return ret;
}
#include <vector>
//주어진 칸을 덮을 수 있는 네가지 방법
//블록을 구성하는 세칸의 상대적 위치
const int coverType[4][3][2] = {
{{0,0},{1,0},{0,1}},
{{0,0},{0,1},{1,1}},
{{0,0},{1,0},{1,1}},
{{0,0},{1,0},{1,-1}}
};
//게임판 밖으로 나가거나, 겹치거나, 검은 칸을 덮을 때 false를 반환
bool set(vector<vector<int>>& board , int y, int x, int type, int delta) {
bool ok = true;
for (int i = 0; i < 3; ++i) {
const ny = y + coverType[type][i][0];
const nx = x + coverType[type][i][1];
if (x < 0 || ny > board.size() || y < 0 || nx > board[0].size())
ok = false;
}
return ok;
}
//board의 모든 빈 칸을 덮을 수 있는 방법의 수를 반환한다.
//board[i][j] = 1 이미 덮인 칸 혹은 검은 칸
//board[i][j] = 0 아직 덮이지 않은 칸
int cover(vector<vector<int>>& board) {
//아직 채우지 못한 칸 중 가장 윗줄 왼쪽에 있는 칸을 찾는다.
int y = -1, x = -1;
for (int i = 0; i < board.size; ++i) {
for (int j = 0; j < board[i].size(); ++j) {
if (board[i][j] == 0)
y = i;
x = j;
break;
}
if (y != -1) break;
}
}
//기저 사례: 모든 칸을 채웠으면 1을 반환한다.
if (y == -1) return 1;
int ret = 0;
for (int type = 0; type < 4; ++type) {
//만약 board[i][j]를 type형태로 덮을 수 있으면 재귀 호출한다.
if (set(board, y, x, type, 1))
ret += cover(board);
//덮었던 블록을 치운다.
set(board, y, x, type, -1);
}
return ret;
}
최적화 문제
문제의 답이 하나가 아니라 여러 개이고, 그 중에서 어떤 기준에 따라 가장 '좋은' 답을 찾아내는 문제 -- n개의 사과 중에서 r개를 골라서 무게의 합을 최대화하는 문제
최적화 문제를 해결하는 방법:
동적계획법, 조합 탐색, 최적화 문제를 결정 문제로 바꿔 해결하는 기법
int n; // 도시의 수
double dist[MAX][MAX]; // 두 도시 간의 거리를 저장하는 배열
//path: 지금까지 만든 경로
//visited: 각 도시의 방문 여부
//currentLength: 지금까지 경로의 길이
//나머지 도시들을 모두 방문하는 경로들 중 가장 짧은 것의 길이를 반환한다.
double shortestPath(vector<int>& path, vector<bool>& visited, double currentLength) {
//기저 사례: 모든 도시를 다 방문했을 때는 시작 도시로 돌아가고 종료한다.
if (path.size() == n)
return currentLength + dist[path[0]][path.back()];
double ret = INF; // 매우 큰 값으로 초기화
// 다음 방문할 도시를 전부 시도해 본다.
for (int next = 0; next < n; ++next) {
if (visited[next]) continue;
int here = path.next();
path.push_back();
path.push_back(next);
visited[next] = true;
//나머지 경로를 재귀 호출을 통해 완성하고 가장 짧은 경로의 길이를 얻는다.
double cand = shortestPath(path, visited, currentLength + dist[here][next]);
ret = min(ret, cand);
visited[next] = false;
path.pop_back();
}
return ret;
}
const int INF = 9999, SWITCHES = 10, CLOCKS = 16;
//linked[i][j] = 'x': i번 스위치와 j번 시계가 연결되어 있다.
//linked[i][j] = '.': i번 스위치와 j번 시계가 연결되어 있지 않다.
const char linked[SWITCHES][CLOCKS + 1] = {
"xxx............",
"...x...x.x.x...",
"....x.....x...xx",
"x...xxxx........",
"......xxx.x.x...",
"x.x...........xx",
"...x..........xx",
".xxxxx..........",
"...xxx...x...x.."
};
//모든 시계가 12시를 가리키고 있는지 확인한다.
bool areAligned(const vector<int>& clocks);
//swtch번 스위치를 누른다.
void push(vector<int>& clocks, int swtch) {
for (int clock = 0; clock < CLOCKS; ++clock)
if (linked[swtch][clock] == 'x') {
clocks[clock] += 3;
if (clocks[clock] == 15) clocks[clock] = 3;
}
}
//clocks: 현재 시계들의 상태
//swtch: 이번에 누를 스위치의 번호가 주어질 때, 남은 스위치들을 눌러서 clocks를 12시로 맞출 수 있는 최소 횟수를 반환한다.
//만약 불가능하다면 INF 이상의 큰 수를 반환한다.
int solve(vector<int>& clocks, int swtch) {
if (swtch == SWITCHES) return areAligned(clocks) ? 0 : INF;
//이 스위치를 0번 누르는 경우부터 세 번 누르는 경우까지를 모두 시도한다.
int ret = INF;
for (int cnt = 0; cnt < 4; ++cnt) {
ret = min(ret, cnt + solve(clocks, swtch + 1));
push(clocks, swtch);
}
//push(clocks, swtch)가 네 번 호출되었으니 clocks는 원래와 같은 상태가 된다.
return ret;
}
재귀 호출과 완전 탐색
재귀 함수
자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고,
나머지를 자기 자신을 호출해 실행하는 함수
모든 재귀함수는 '더이상 쪼개지지 않는' 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야 한다.
쪼개지지 않는 가장 작은 작업 == 기저 사례
for(int i = 0; i < n; ++i)
for(int j = i+1; j < n; ++j)
for(int k = j+1; k < n; ++k)
for(int l = k+1; l < n; ++l)
cout << i << " " << j << " " << k << " " << l << endl;
n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘
// n: 전체 원소의 수
// picked: 지금까지 고른 원소들의 번호
// toPick: 더 고를 원소의 수일때, 앞으로 toPick개의 원소를 고르는 모든 방법을 출력한다.
void pick(int n, vector<int>& picked, int toPick) {
//기저 사례: 더 고를 원소가 없을 때 고른 원소들을 출력한다.
if(toPick == 0) {printPicked(picked); return;}
//고를 수 있는 가장 작은 번호를 계산한다.
int smallest = picked.empty() ? 0 : picked.back() + 1;
//이 단계에서 원소하나를 고른다.
for(int next = smallest; next < n; ++next) {
picked.push_back(next);
pick(n, picked, toPick - 1);
picked.pop_back();
}
}
ex) 보글게임
상하좌우 / 대각선으로 인접한 칸들의 글자들을 이어서 단어를 찾아내는 것
hasWord(y, x, word) = 보들 게임판의 (y, x)에서 시작하는 단어 word의 존재 여부를 반환
문제의 분할
hasWord()가 하는 일을 가장 자연스럽게 조각내는 방법은 각 글자를 하나의 조각으로 만드는 것이다. 함수 호출시에 단어의 시작 위치를 정해 주기 때문에, 문제의 조각들 중 첫 번째 글자에 해당하는 조각을 간단하게 해결할 수 있다. 그 이후에는 시작위치와 인접한 여덟 칸을 모두 시도하면서 답을 찾으면 된다.
기저 사례의 선택
1. 위치 (y, x)에 잇는 글자가 원하는 단어의 첫 글자가 아닌 경우 항상 실패
2. (1번 경우에 해당하지 않을 경우)원하는 단어가 한글자인 경우 항상 성공
Tip: 입력이 잘못되거난 범위에서 벗어난 경우도 기저 사례로 택해서 맨 처음에 처리
const int dx[8] = {-1, -1, -1, 1, 1, 1, 0, 0};
const int dy[8] = {-1, 0, 1, -1, 0, 1, -1, 1};
//5X5의 보글 게임 판의 해당 위치에서 주어진 단어가 시작하는 지를 반환
bool hasWord(int y, int x, const string& word) {
// 기저 사례 1: 시작 위치가 범위 밖이면 무조건 실패
if(!inRange(y,x)) return false;
// 기저 사례 2: 첫 글자가 일치하지 않으면 실패
if(board[y][x] != word[0]) return false;
// 기저 사례 3: 단어 길이가 1이면 성공
if(word.size() == 1) return true;
// 인접한 여덟 칸을 검사한다.
for(int direction = 0; direction < 8; ++direction) {
int nextY = y + dy[direction], next = x + dx[direction];
//다음 칸이 범위 안에 있는지, 첫 글자는 일치하는지 확인할 필요가 없다.
if(hasWord(nextY, nextX, word.substr(1)))
return true;
}
return false;
}
완전 탐색 레시피
1. 완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에
정확히 비례한다. 그러므로 최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 이들을 모두 제한 시간 안에 생성할 수 있을지를 가늠한다.
2. 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눈다.
3. 그중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성
4. 조각이 하나밖에 남지 않으 경우, 혹은 하나도 남지 않은 경우에는 답을 생성했으므로, 그섯을 기저 사례로 선택해 처리한다.
이론적 배경 : 재귀 호출과 부분 문제
문제 : 소풍 (문제 ID: PICNIC, 난이도: 하)
int n;
bool areFriends[10][10];
// 아직 짝을 찾지 못한 학생들의 명단이 주어질 때 친구끼리 둘씩 짝짓는 경우의 수를 // 계산하라.
int countPairings(bool taken[10]) {
//기저 사례: i번째 학생이 짝을 이미 찾았으면 true, 아니면 false
bool finished = true;
for (int i = 0; i < n; i++) if (!taken[i]) finished = false;
if (finished) return 1;
int ret = 0;
// 서로 친구인 두 학생을 찾아 짝을 지어준다.
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (!taken[i] && !taken[j] && areFriends[i][j]) {
taken[i] = taken[j] = true;
ret += countPairings(taken);
taken[i] = taken[j] = false;
}
return ret;
}
int n;
bool areFriends[10][10];
// Wrong의 해결 방안: 각 단계에서 남아 있는 학생들 중 가장 번호가 빠른 학생의 짝을 찾아 주도록 하면 된다.
// 아직 짝을 찾지 못한 학생들의 명단이 주어질 때 친구끼리 둘씩 짝짓는 경우의 수를 계산하라.
int countPairings(bool taken[10]) {
// 남은 학생들 중 가장 번호가 빠른 학생을 찾는다.
int firstFree = -1;
for (int i = 0; i < n; ++i) {
if (!taken[i]) {
firstFree = i;
break;
}
}
//기저사례: 모든 학생이 짝을 찾았으면 한 가지 방법을 찾았으니 종료한다.
int ret = 0;
// 서로 친구인 두 학생을 찾아 짝을 지어준다.
for (int pairWith = firstFree + 1; pairWith < n; ++pairWith) {
if (!taken[pairWith] && areFriends[firstFree][pairWith]) {
taken[firstFree] = taken[pairWith] = true;
ret += countPairings(taken);
taken[firstFree] = taken[pairWith] = false;
}
}
return ret;
}
#include <vector>
//주어진 칸을 덮을 수 있는 네가지 방법
//블록을 구성하는 세칸의 상대적 위치
const int coverType[4][3][2] = {
{{0,0},{1,0},{0,1}},
{{0,0},{0,1},{1,1}},
{{0,0},{1,0},{1,1}},
{{0,0},{1,0},{1,-1}}
};
//게임판 밖으로 나가거나, 겹치거나, 검은 칸을 덮을 때 false를 반환
bool set(vector<vector<int>>& board , int y, int x, int type, int delta) {
bool ok = true;
for (int i = 0; i < 3; ++i) {
const ny = y + coverType[type][i][0];
const nx = x + coverType[type][i][1];
if (x < 0 || ny > board.size() || y < 0 || nx > board[0].size())
ok = false;
}
return ok;
}
//board의 모든 빈 칸을 덮을 수 있는 방법의 수를 반환한다.
//board[i][j] = 1 이미 덮인 칸 혹은 검은 칸
//board[i][j] = 0 아직 덮이지 않은 칸
int cover(vector<vector<int>>& board) {
//아직 채우지 못한 칸 중 가장 윗줄 왼쪽에 있는 칸을 찾는다.
int y = -1, x = -1;
for (int i = 0; i < board.size; ++i) {
for (int j = 0; j < board[i].size(); ++j) {
if (board[i][j] == 0)
y = i;
x = j;
break;
}
if (y != -1) break;
}
}
//기저 사례: 모든 칸을 채웠으면 1을 반환한다.
if (y == -1) return 1;
int ret = 0;
for (int type = 0; type < 4; ++type) {
//만약 board[i][j]를 type형태로 덮을 수 있으면 재귀 호출한다.
if (set(board, y, x, type, 1))
ret += cover(board);
//덮었던 블록을 치운다.
set(board, y, x, type, -1);
}
return ret;
}
최적화 문제
문제의 답이 하나가 아니라 여러 개이고, 그 중에서 어떤 기준에 따라 가장 '좋은' 답을 찾아내는 문제 -- n개의 사과 중에서 r개를 골라서 무게의 합을 최대화하는 문제
최적화 문제를 해결하는 방법:
동적계획법, 조합 탐색, 최적화 문제를 결정 문제로 바꿔 해결하는 기법
int n; // 도시의 수
double dist[MAX][MAX]; // 두 도시 간의 거리를 저장하는 배열
//path: 지금까지 만든 경로
//visited: 각 도시의 방문 여부
//currentLength: 지금까지 경로의 길이
//나머지 도시들을 모두 방문하는 경로들 중 가장 짧은 것의 길이를 반환한다.
double shortestPath(vector<int>& path, vector<bool>& visited, double currentLength) {
//기저 사례: 모든 도시를 다 방문했을 때는 시작 도시로 돌아가고 종료한다.
if (path.size() == n)
return currentLength + dist[path[0]][path.back()];
double ret = INF; // 매우 큰 값으로 초기화
// 다음 방문할 도시를 전부 시도해 본다.
for (int next = 0; next < n; ++next) {
if (visited[next]) continue;
int here = path.next();
path.push_back();
path.push_back(next);
visited[next] = true;
//나머지 경로를 재귀 호출을 통해 완성하고 가장 짧은 경로의 길이를 얻는다.
double cand = shortestPath(path, visited, currentLength + dist[here][next]);
ret = min(ret, cand);
visited[next] = false;
path.pop_back();
}
return ret;
}
const int INF = 9999, SWITCHES = 10, CLOCKS = 16;
//linked[i][j] = 'x': i번 스위치와 j번 시계가 연결되어 있다.
//linked[i][j] = '.': i번 스위치와 j번 시계가 연결되어 있지 않다.
const char linked[SWITCHES][CLOCKS + 1] = {
"xxx............",
"...x...x.x.x...",
"....x.....x...xx",
"x...xxxx........",
"......xxx.x.x...",
"x.x...........xx",
"...x..........xx",
".xxxxx..........",
"...xxx...x...x.."
};
//모든 시계가 12시를 가리키고 있는지 확인한다.
bool areAligned(const vector<int>& clocks);
//swtch번 스위치를 누른다.
void push(vector<int>& clocks, int swtch) {
for (int clock = 0; clock < CLOCKS; ++clock)
if (linked[swtch][clock] == 'x') {
clocks[clock] += 3;
if (clocks[clock] == 15) clocks[clock] = 3;
}
}
//clocks: 현재 시계들의 상태
//swtch: 이번에 누를 스위치의 번호가 주어질 때, 남은 스위치들을 눌러서 clocks를 12시로 맞출 수 있는 최소 횟수를 반환한다.
//만약 불가능하다면 INF 이상의 큰 수를 반환한다.
int solve(vector<int>& clocks, int swtch) {
if (swtch == SWITCHES) return areAligned(clocks) ? 0 : INF;
//이 스위치를 0번 누르는 경우부터 세 번 누르는 경우까지를 모두 시도한다.
int ret = INF;
for (int cnt = 0; cnt < 4; ++cnt) {
ret = min(ret, cnt + solve(clocks, swtch + 1));
push(clocks, swtch);
}
//push(clocks, swtch)가 네 번 호출되었으니 clocks는 원래와 같은 상태가 된다.
return ret;
}
2015년 8월 1일 토요일
알고리즘 문제 해결 전략(2)
선형 시간 알고리즘
다이어트 현황 파악: 이동 평균 계산하기
//실수 배열 A가 주어질 때, 각 위치에서의 M-이동 평균 값을 구한다.
vector<double> movingAverage1(const vector<double>& A, int M) {
vector<double> ret;
int N = A.size();
for(int i = M-1; i < N; ++i) {
//A[i]까지의 이동 평균값을 구하자.
double partialSum = 0;
for(int j = 0; j < M; ++j)
partialSum += A[i-j];
ret.push_back(partialSum / M);
//push_back: vector의 메소드로 마지막에 원소 추가
}
return ret;
}
//길이가 N인 실수 배열 A가 주어질 때, 각 위치에서의 M-이동 평균값을 구한다.
vector<double> movingAverage2(const vector<double>& A, int M) {
vector<double> ret;
int N = A.size();
double partialSum = 0;
for(int i = 0; i < M - 1; ++i)
partialSum += A[i];
for(int i = M-1; i < N; ++i) {
partialSum += A[i];
ret.push_back(partialSum / M);
partialSum -= A[i-M+1];
}
return ret;
}
선형 이하 시간 알고리즘 - 이진 탐색
입력의 크기가 커지는 것보다 수행 시간이 느리게 증가하는 알고리즘들을 선형 이하 시간 알고리즘이라 부른다.
지수 시간 알고리즘 - 다항 시간 알고리즘 - 재귀 함수
음식 메뉴 정하기
const int INF = 987654321;
// 이 메뉴로 모두가 식사할 수 있는지 여부를 반환한다.
bool canEverybodyEat(const vector<int>& menu);
// 요리할 수 있는 음식의 종류 수
int M;
//food번째 음식을 만들지 여부를 결정한다.
int selectMenu(vector<int>& menu, int food) {
//기저 사례:모든 음식에 대해 만들지 여부를 결정했을 때
if(food == M) {
if(canEverybodyEat(menu)) return menu.size();
//아무것도 못 먹는 사람이 있으면 아주 큰 값을 반환한다.
return INF;
}
//이 음식을 만들지 않는 경우의 값을 계산한다.
int ret = selectMenu(menu, food+1);
//이 음식을 만드는 경우의 답을 계산해서 더 작은 것을 취한다.
menu.push_back(food);
ret = min(ret, selctMenu(menu, food+1));
menu.pop_back();
return ret;
}
지수 시간 알고리즘
소인수 분해의 수행 시간
//자연수 n의 소인수 분해 결과를 담은 정수 배열을 반환한다.
vector<int> factor(int n) {
if(n == 1) return vector<int>(1, 1); // n = 1인 경우는 예외로 한다.
vector<int> ret;
for(int div = 2; n > 1; ++div)
while(n % div == 0) {
n /= div;
ret.push_back(div);
}
return ret;
}
void selectionSort(vector<int>& A) {
for(int i = 0; i < A.size(); ++i) {
int minIndex = i;
for(int j = i+1; j < A.size(); ++j)
if(A[minIndex] > A[j])
minIndex = j;
swap(A[i], A[minIndex]);
}
}
void insertionSort(vector<int> A) {
for(int i = 0; i < A.size(); ++i) {
// A[0..i-1]에 A[i]를 끼워넣는다.
int j = i;
while(j > 0 && A[j-1] > A[j]) {
swap(A[j-1], A[j]);
--j;
}
}
}
const int MIN = numeric_limits<int>::min();
//A[]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도: O(N^3)
int inefficientMaxSum(const vector<int>& A) {
int N = A.size(), ret = MIN;
for(int i = 0; i < N; i++)
for(int j = i; j < N; ++j) {
//구간 A[i, j]의 합을 구한다.
int sum = 0;
for(int k = i; k <= j; ++k)
sum += A[k];
ret = max(ret, sum);
}
return ret;
}
//A[]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도: O(N^2)
int betterMaxSum(const vector<int>& A) {
int N = A.size(), ret = MIN;
for(int i = 0; i < N; ++i) {
int sum = 0;
for(int j = i; j < N; ++j) {
//구간 A[i, j]의 합을 구한다.
sum += A[j];
ret = max(ret, sum);
}
}
return ret;
}
//A[lo, hi]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도: O(nlogn)
int fastMaxSum(const vector<int>& A, int lo, int hi) {
//기저 사례: 구간의 길이가 1일 경우
if(lo == hi) return A[lo];
//배열을 A[lo, mid], A[mid+1, hi]의 두 조각으로 나눈다.
int mid = (lo, hi) / 2;
//두 부분에 모두 걸쳐있는 최대 합 구간을 찾는다.
//이 구간은 A[i, mid], A[mid+1, j] 형태를 갖는 구간의 합으로 이루어진다.
//A[i, mid] 형태를 갖는 최대 구간을 찾는다.
int left = MIN, right = MIN, sum = 0;
for(int i = mid, i >= lo; --i){
sum += A[i];
left = max(left, sum);
}
//A[mid+1, j] 형태를 갖는 최대 구간을 찾는다.
sum = 0;
for(int j = mid+1; j <= hi; ++j) {
sum += A[j];
right = max(right, sum);
}
//최대 구간이 두 조각 중 하나에만 속해 있는 경우의 답을 재귀 호출로 찾는다.
int single = max(fastMaxSum(A, lo, mid), fastMaxSum(A, mid+1, hi));
//두 경우 중 최대치를 반환한다.
return max(left + right, single);
}
//A[]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도: O(N)
int fastestMaxSum(const vector<int>& A) {
int N = A.size(), ret = MIN, psum = 0;
for(int i = 0; i < N; ++i) {
psum = max(psum, 0) + A[i];
ret = max(psum, ret);
}
return ret;
}
계산 복잡도 클래스: P, NP, NP-완비
P : 다항 시간 내에 풀 수 있는 문제
NP : 다한 시간 내에 풀 수 없는 문제
알고리즘의 정당성 증명 - 수학적으로 증명
수학적 귀납법
단계 나누기 : 증명하고 싶은 사실을 여러 단계로 나눈다.
첫 단계 증명 : 첫 단계에서 증명하고 싶은 내용이 성립한다.
귀납 증명 : 한 단계에서 증명하고 싶은 내용이 성립한다면 다음 단계에서도 성립함을 보임
반복문 불변식
//(*) 불변식은 여기에서 성립해야 한다.
while(condition) {
//반복문 내용의 시작
..
//반복문 내용의 끝
//(**) 불변식은 여기에서도 성립해야 한다.
}
이진 탐색과 반복문 불변식
// 필수 조건: A는 오름차순으로 정렬되어 있다.
// 결과: A[i-1] < x <= A[i]인 i를 반환한다.
// 이때 A[-1] = 음의 무한대, A[n] = 양의 무한대라고 가정한다.
int binsearch(const vector<int>& A, int x) {
int n = A.size();
int lo = -1, hi = n;
//반복문 불변식 1: lo < hidden
//반복문 불변식 2: A[lo] < x < A[hi]
//(*) 불변식은 여기서 성립해야 한다.
while(lo + 1 < hi) {
int mid = (lo + hi) / 2;
if(A[mid] < x)
lo = mid;
else
hi = mid;
//(**) 불변식은 여기서 성립해야 한다.
}
}
삽입 정렬과 반복문 불변식
void insertionSort(vector<int> A) {
for(int i = 0; i < A.size(); ++i) {
// 불변식 a:A[0..i-1]은 이미 정렬되어 있다.
// A[0..i-1]에 A[i]를 끼워넣는다.
int j = i;
while(j > 0 && A[j-1] > A[j]) {
// 불변식 b: A[j + 1 .. i]의 모든 원소는 A[j]보다 크다.
// 불변식 c: A[0 .. i] 구간은 A[j]를 제외하면 정렬되어 있다.
swap(A[j-1], A[j]);
--j;
}
}
}
귀류법
내가 원하는 바와 반대되는 상황을 가정하고 논리를 전개해서 결론이 잘못됐음을 찾아내는 증명 기법
비둘기집의 원리
동전 뒤집기
순환 소수 찾기
구성적 증명
안정적 결혼 문제
다이어트 현황 파악: 이동 평균 계산하기
//실수 배열 A가 주어질 때, 각 위치에서의 M-이동 평균 값을 구한다.
vector<double> movingAverage1(const vector<double>& A, int M) {
vector<double> ret;
int N = A.size();
for(int i = M-1; i < N; ++i) {
//A[i]까지의 이동 평균값을 구하자.
double partialSum = 0;
for(int j = 0; j < M; ++j)
partialSum += A[i-j];
ret.push_back(partialSum / M);
//push_back: vector의 메소드로 마지막에 원소 추가
}
return ret;
}
//길이가 N인 실수 배열 A가 주어질 때, 각 위치에서의 M-이동 평균값을 구한다.
vector<double> movingAverage2(const vector<double>& A, int M) {
vector<double> ret;
int N = A.size();
double partialSum = 0;
for(int i = 0; i < M - 1; ++i)
partialSum += A[i];
for(int i = M-1; i < N; ++i) {
partialSum += A[i];
ret.push_back(partialSum / M);
partialSum -= A[i-M+1];
}
return ret;
}
선형 이하 시간 알고리즘 - 이진 탐색
입력의 크기가 커지는 것보다 수행 시간이 느리게 증가하는 알고리즘들을 선형 이하 시간 알고리즘이라 부른다.
지수 시간 알고리즘 - 다항 시간 알고리즘 - 재귀 함수
음식 메뉴 정하기
const int INF = 987654321;
// 이 메뉴로 모두가 식사할 수 있는지 여부를 반환한다.
bool canEverybodyEat(const vector<int>& menu);
// 요리할 수 있는 음식의 종류 수
int M;
//food번째 음식을 만들지 여부를 결정한다.
int selectMenu(vector<int>& menu, int food) {
//기저 사례:모든 음식에 대해 만들지 여부를 결정했을 때
if(food == M) {
if(canEverybodyEat(menu)) return menu.size();
//아무것도 못 먹는 사람이 있으면 아주 큰 값을 반환한다.
return INF;
}
//이 음식을 만들지 않는 경우의 값을 계산한다.
int ret = selectMenu(menu, food+1);
//이 음식을 만드는 경우의 답을 계산해서 더 작은 것을 취한다.
menu.push_back(food);
ret = min(ret, selctMenu(menu, food+1));
menu.pop_back();
return ret;
}
지수 시간 알고리즘
소인수 분해의 수행 시간
//자연수 n의 소인수 분해 결과를 담은 정수 배열을 반환한다.
vector<int> factor(int n) {
if(n == 1) return vector<int>(1, 1); // n = 1인 경우는 예외로 한다.
vector<int> ret;
for(int div = 2; n > 1; ++div)
while(n % div == 0) {
n /= div;
ret.push_back(div);
}
return ret;
}
void selectionSort(vector<int>& A) {
for(int i = 0; i < A.size(); ++i) {
int minIndex = i;
for(int j = i+1; j < A.size(); ++j)
if(A[minIndex] > A[j])
minIndex = j;
swap(A[i], A[minIndex]);
}
}
void insertionSort(vector<int> A) {
for(int i = 0; i < A.size(); ++i) {
// A[0..i-1]에 A[i]를 끼워넣는다.
int j = i;
while(j > 0 && A[j-1] > A[j]) {
swap(A[j-1], A[j]);
--j;
}
}
}
const int MIN = numeric_limits<int>::min();
//A[]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도: O(N^3)
int inefficientMaxSum(const vector<int>& A) {
int N = A.size(), ret = MIN;
for(int i = 0; i < N; i++)
for(int j = i; j < N; ++j) {
//구간 A[i, j]의 합을 구한다.
int sum = 0;
for(int k = i; k <= j; ++k)
sum += A[k];
ret = max(ret, sum);
}
return ret;
}
//A[]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도: O(N^2)
int betterMaxSum(const vector<int>& A) {
int N = A.size(), ret = MIN;
for(int i = 0; i < N; ++i) {
int sum = 0;
for(int j = i; j < N; ++j) {
//구간 A[i, j]의 합을 구한다.
sum += A[j];
ret = max(ret, sum);
}
}
return ret;
}
//A[lo, hi]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도: O(nlogn)
int fastMaxSum(const vector<int>& A, int lo, int hi) {
//기저 사례: 구간의 길이가 1일 경우
if(lo == hi) return A[lo];
//배열을 A[lo, mid], A[mid+1, hi]의 두 조각으로 나눈다.
int mid = (lo, hi) / 2;
//두 부분에 모두 걸쳐있는 최대 합 구간을 찾는다.
//이 구간은 A[i, mid], A[mid+1, j] 형태를 갖는 구간의 합으로 이루어진다.
//A[i, mid] 형태를 갖는 최대 구간을 찾는다.
int left = MIN, right = MIN, sum = 0;
for(int i = mid, i >= lo; --i){
sum += A[i];
left = max(left, sum);
}
//A[mid+1, j] 형태를 갖는 최대 구간을 찾는다.
sum = 0;
for(int j = mid+1; j <= hi; ++j) {
sum += A[j];
right = max(right, sum);
}
//최대 구간이 두 조각 중 하나에만 속해 있는 경우의 답을 재귀 호출로 찾는다.
int single = max(fastMaxSum(A, lo, mid), fastMaxSum(A, mid+1, hi));
//두 경우 중 최대치를 반환한다.
return max(left + right, single);
}
//A[]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도: O(N)
int fastestMaxSum(const vector<int>& A) {
int N = A.size(), ret = MIN, psum = 0;
for(int i = 0; i < N; ++i) {
psum = max(psum, 0) + A[i];
ret = max(psum, ret);
}
return ret;
}
P : 다항 시간 내에 풀 수 있는 문제
NP : 다한 시간 내에 풀 수 없는 문제
알고리즘의 정당성 증명 - 수학적으로 증명
수학적 귀납법
단계 나누기 : 증명하고 싶은 사실을 여러 단계로 나눈다.
첫 단계 증명 : 첫 단계에서 증명하고 싶은 내용이 성립한다.
귀납 증명 : 한 단계에서 증명하고 싶은 내용이 성립한다면 다음 단계에서도 성립함을 보임
반복문 불변식
//(*) 불변식은 여기에서 성립해야 한다.
while(condition) {
//반복문 내용의 시작
..
//반복문 내용의 끝
//(**) 불변식은 여기에서도 성립해야 한다.
}
이진 탐색과 반복문 불변식
// 필수 조건: A는 오름차순으로 정렬되어 있다.
// 결과: A[i-1] < x <= A[i]인 i를 반환한다.
// 이때 A[-1] = 음의 무한대, A[n] = 양의 무한대라고 가정한다.
int binsearch(const vector<int>& A, int x) {
int n = A.size();
int lo = -1, hi = n;
//반복문 불변식 1: lo < hidden
//반복문 불변식 2: A[lo] < x < A[hi]
//(*) 불변식은 여기서 성립해야 한다.
while(lo + 1 < hi) {
int mid = (lo + hi) / 2;
if(A[mid] < x)
lo = mid;
else
hi = mid;
//(**) 불변식은 여기서 성립해야 한다.
}
}
삽입 정렬과 반복문 불변식
void insertionSort(vector<int> A) {
for(int i = 0; i < A.size(); ++i) {
// 불변식 a:A[0..i-1]은 이미 정렬되어 있다.
// A[0..i-1]에 A[i]를 끼워넣는다.
int j = i;
while(j > 0 && A[j-1] > A[j]) {
// 불변식 b: A[j + 1 .. i]의 모든 원소는 A[j]보다 크다.
// 불변식 c: A[0 .. i] 구간은 A[j]를 제외하면 정렬되어 있다.
swap(A[j-1], A[j]);
--j;
}
}
}
귀류법
내가 원하는 바와 반대되는 상황을 가정하고 논리를 전개해서 결론이 잘못됐음을 찾아내는 증명 기법
비둘기집의 원리
동전 뒤집기
순환 소수 찾기
구성적 증명
안정적 결혼 문제
2015년 7월 31일 금요일
알고리즘 문제 해결 전략(1)
문제 해결 과정
1. 문제를 읽고 이해한다.
2. 문제를 익숙한 용어로 재정의한다.
3. 어떻게 해결할지 계획을 세운다.
4. 계획을 검증한다.
5. 프로그램으로 구현한다.
6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.
체계적인 접근을 위한 질문들
1. 비슷한 문제를 풀어본 적이 있던가?
2. 단순한 방법에서 시작할 수 있을까? == 무식하게 풀 수 있을까?
3. 내가 문제를 푸는 과정을 수식화할 수 있을까?
4. 문제를 단순화할 수 없을까? == 문제를 좀 더 쉽게 만들어 볼 순 없을까?
5. 그림으로 그려볼 수 있을까?
6. 수식으로 표현할 수 있을까?
7. 문제를 분해할 수 있을까?
8. 뒤에서부터 생각해서 문제를 풀 수 있을까?
9. 순서를 강제할 수 있을까?
10. 특정 형태의 답만을 고려할 수 있을까? == 답 후보의 유한한 갯수만을 고려
코딩과 디버깅에 관하여
1. 간결한 코드를 작성하기
2. 적극적으로 코드 재사용하기 == 코드 모듈화
3. 표준 라이브러리 공부하기
4. 항상 같은 형태로 프로그램을 작성하기 == 반복문의 일관된 사용, 배열의 전달 방법
5. 일관적이고 명료한 명명법 사용하기
6. 모든 자료를 정규화해서 저장하기 == 모든 분수는 기약분수로, 각도를 양수로만 표현
7. 코드와 데이터를 분리하기 == 데이터는 배열로 만들어서 정리
자주 하는 실수
1. 산술 오버플로
2. 배열 범위 밖 원소에 접근 == array[n]이면 0~n-1
3. 일관되지 않은 범위 표현 방식 사용하기
4. 계산의 큰 줄기는 맞지만 하나가 모자라거나 하나가 많아서 틀리는 코드의 오류
5. 컴파일러가 잡아주지 못하는 상수 오타
6. 스택 오버플로
7. 다차원 배열 인덱스 순서 바꿔 쓰기
8. 잘못된 비교 함수 작성 == <, >
9. 최소, 최대 예외 잘못 다루기
10. 연산자 우선순위 잘못 쓰기
11. 너무 느린 입출력 방식 선택
12. 변수 초기화 문제 == 이전 입력에서 사용한 전역 변수 값을 초기화하지 않고 사용
스캐폴딩 코드
//우리가 테스트하고 싶은 정렬 함수
void mySort(vector<int>& array);
//주어진 배열을 문자열로 바꾼다
string toString(const vector<int>& array);
int main() {
//무한히 반복한다.
while(true) {
//임의의 입력을 만든다.
int n = rand() % 100 + 1;
vector<int> input(n);
for(int i = 0; i < n; ++i)
input[i] = rand();
//두 개의 복제를 만들어서 하나는 우리의 정렬 함수로, 하나의 표준 라이브러리로
//정렬한다.
vector<int> mySorted = input;
mySort(mySorted);
vector<int> reference = input;
sort(reference.begin(), reference.end());
if(mySorted != reference) {
cout << "Mismatch!" << endl;
cout << "Input: " << toString(input) << endl;
cout << "Expected: " << toString(reference) << endl;
cout << "Got: " << toString(mySorted) << endl;
break;
}
}
}
산술 오버플로
어떤 식의 계산 값이 반환되는 자료형의 표현 가능한 범위를 벗어나는 경우
너무 큰 결과
프로그램이 출력해야 할 결과가 우리가 흔히 사용하는 32비트 자료형의 범위를 넘어가면 64비트 정수를 사용하거나 큰 정수 구현을 이용해야 한다.
너무 큰 중간 값
프로그램의 출력값의 범위는 작지만 중간과정에서 큰 값을 일시적으로 계산해야 하는 경우
너무 큰 '무한대' 값
무한대의 값을 어떤 큰 유한한 값으로 대체할 때 너무 큰 값으로 잡으면 안 됨
오버플로 피해가기
1. 캐스팅을 이용
2. 연산의 순서를 바꾼다. - 먼저 빼거나 나눈다.
3. 계산의 순서를 바꾼다.
실수 자료형의 이해
실수 == 근사값
=> 두 개의 실수값을 비교할 때에는 어느 정도의 오차는 염두해두어야 한다.
1. 오차의 한도를 상황에 맞게 설정한다.
2. 상대 오차를 이용한다.
relativeError(a, b) = |a-b| / max( |a|, |b| ) <= 큰 수를 비교할 때 유용
//절대 오차와 상대 오차를 모두 이용해서 두 수가 같은지 판정한다.
bool doubleEqual(double a , double b) {
double diff = fabs(a - b);
//절대 오차가 허용 범위 안일 경우 무조건 true를 반환한다.
if(diff < 1e-10) return true;
//이 외의 경우레는 상대 오차를 사용한다.
return diff <= 1e-8 * max(fabs(a), fabs(b));
}
대소 비교
연산 오차에 의해서 거짓이 될 값이 참이 될 수 있다.
코드의 수치적 안정성 파악하기
프로그램의 실행 과정에서 발생하는 오차가 더 커지지 않는다.
1. 문제를 읽고 이해한다.
2. 문제를 익숙한 용어로 재정의한다.
3. 어떻게 해결할지 계획을 세운다.
4. 계획을 검증한다.
5. 프로그램으로 구현한다.
6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.
체계적인 접근을 위한 질문들
1. 비슷한 문제를 풀어본 적이 있던가?
2. 단순한 방법에서 시작할 수 있을까? == 무식하게 풀 수 있을까?
3. 내가 문제를 푸는 과정을 수식화할 수 있을까?
4. 문제를 단순화할 수 없을까? == 문제를 좀 더 쉽게 만들어 볼 순 없을까?
5. 그림으로 그려볼 수 있을까?
6. 수식으로 표현할 수 있을까?
7. 문제를 분해할 수 있을까?
8. 뒤에서부터 생각해서 문제를 풀 수 있을까?
9. 순서를 강제할 수 있을까?
10. 특정 형태의 답만을 고려할 수 있을까? == 답 후보의 유한한 갯수만을 고려
코딩과 디버깅에 관하여
1. 간결한 코드를 작성하기
2. 적극적으로 코드 재사용하기 == 코드 모듈화
3. 표준 라이브러리 공부하기
4. 항상 같은 형태로 프로그램을 작성하기 == 반복문의 일관된 사용, 배열의 전달 방법
5. 일관적이고 명료한 명명법 사용하기
6. 모든 자료를 정규화해서 저장하기 == 모든 분수는 기약분수로, 각도를 양수로만 표현
7. 코드와 데이터를 분리하기 == 데이터는 배열로 만들어서 정리
자주 하는 실수
1. 산술 오버플로
2. 배열 범위 밖 원소에 접근 == array[n]이면 0~n-1
3. 일관되지 않은 범위 표현 방식 사용하기
4. 계산의 큰 줄기는 맞지만 하나가 모자라거나 하나가 많아서 틀리는 코드의 오류
5. 컴파일러가 잡아주지 못하는 상수 오타
6. 스택 오버플로
7. 다차원 배열 인덱스 순서 바꿔 쓰기
8. 잘못된 비교 함수 작성 == <, >
9. 최소, 최대 예외 잘못 다루기
10. 연산자 우선순위 잘못 쓰기
11. 너무 느린 입출력 방식 선택
12. 변수 초기화 문제 == 이전 입력에서 사용한 전역 변수 값을 초기화하지 않고 사용
스캐폴딩 코드
//우리가 테스트하고 싶은 정렬 함수
void mySort(vector<int>& array);
//주어진 배열을 문자열로 바꾼다
string toString(const vector<int>& array);
int main() {
//무한히 반복한다.
while(true) {
//임의의 입력을 만든다.
int n = rand() % 100 + 1;
vector<int> input(n);
for(int i = 0; i < n; ++i)
input[i] = rand();
//두 개의 복제를 만들어서 하나는 우리의 정렬 함수로, 하나의 표준 라이브러리로
//정렬한다.
vector<int> mySorted = input;
mySort(mySorted);
vector<int> reference = input;
sort(reference.begin(), reference.end());
if(mySorted != reference) {
cout << "Mismatch!" << endl;
cout << "Input: " << toString(input) << endl;
cout << "Expected: " << toString(reference) << endl;
cout << "Got: " << toString(mySorted) << endl;
break;
}
}
}
산술 오버플로
어떤 식의 계산 값이 반환되는 자료형의 표현 가능한 범위를 벗어나는 경우
너무 큰 결과
프로그램이 출력해야 할 결과가 우리가 흔히 사용하는 32비트 자료형의 범위를 넘어가면 64비트 정수를 사용하거나 큰 정수 구현을 이용해야 한다.
너무 큰 중간 값
프로그램의 출력값의 범위는 작지만 중간과정에서 큰 값을 일시적으로 계산해야 하는 경우
너무 큰 '무한대' 값
무한대의 값을 어떤 큰 유한한 값으로 대체할 때 너무 큰 값으로 잡으면 안 됨
오버플로 피해가기
1. 캐스팅을 이용
2. 연산의 순서를 바꾼다. - 먼저 빼거나 나눈다.
3. 계산의 순서를 바꾼다.
실수 자료형의 이해
실수 == 근사값
=> 두 개의 실수값을 비교할 때에는 어느 정도의 오차는 염두해두어야 한다.
1. 오차의 한도를 상황에 맞게 설정한다.
2. 상대 오차를 이용한다.
relativeError(a, b) = |a-b| / max( |a|, |b| ) <= 큰 수를 비교할 때 유용
//절대 오차와 상대 오차를 모두 이용해서 두 수가 같은지 판정한다.
bool doubleEqual(double a , double b) {
double diff = fabs(a - b);
//절대 오차가 허용 범위 안일 경우 무조건 true를 반환한다.
if(diff < 1e-10) return true;
//이 외의 경우레는 상대 오차를 사용한다.
return diff <= 1e-8 * max(fabs(a), fabs(b));
}
대소 비교
연산 오차에 의해서 거짓이 될 값이 참이 될 수 있다.
코드의 수치적 안정성 파악하기
프로그램의 실행 과정에서 발생하는 오차가 더 커지지 않는다.
피드 구독하기:
글 (Atom)