저번 글에서는 landmark detection이라는 오픈소스를 활용하여 얼굴의 특징점들을 얻고 각 거리를 구하여 얼굴의 비대칭성을 구했었다. 사용자가 쉽게 사용할 수 있는 방법이 웹캡을 활용하는 방법이었다. 따라서 노트북으로 홈페이지를 접속하여 얼굴을 찍어 넘기게 하였다. 프론트엔드는 리액트라는 자바스크립트 api를 활용하여 구성하였다.
메인 화면
웹페이지는 총 3개의 큰 페이지로 구성되어 있다. 페이지 상단에는 여러 페이지를 탐색할 수 있는 Navigation Bar가 위치해 있고 중앙에는 현재 화면이 표시된다. 처음은 홈 화면으로, 누구든지 사용 방법을 쉽게 알아볼 수 있도록 프로그램 이름과 함께 검사를 바로 진행할 수 있는 사진 찍기 버튼으로 구성하였다.
검사 방법
사진 찍기 버튼을 누르게 되면 간단할 설명과 함께 예시 표정이 오른쪽에 주어진다. 검사 방법 밑에 위치한 사진 찍기 버튼을 다시 누르게 되면 다음 창으로 넘어가 웹 캠 또는 스마트폰 카메라를 통해 사진을 캡처한 후 검사를 위해 서버에 전송할 수 있다. 사진에서는 잘 보이지 않지만 검사 방법은 다음과 같다.
카메라가 바닥과 수평인지 확인 해주세요.
얼굴에 그림자가 지지 않도록 밝은 곳에서 진행해주세요.
오른쪽 사진과 같이 정면을 보고 웃어주세요.
카메라를 응시한 채 '캡쳐' 버튼을 눌러주세요.
결과가 나올 때까지 잠시 기다려주세요.
사진 찍기
사진 찍기 버튼을 누를 경우 위와 같이 사진을 찍을 수 있다. 웹캠이 화면에 표시되면 앞선 설명에 나와 있던 대로 사진을 찍으면 된다. 왼쪽의 캡처 버튼을 누르게 되면 사진은 서버로 전송되고 분석 과정을 거치게 된다.
결과 출력
사진을 전송한 뒤 잠시 후 인식된 얼굴의 사진과 함께 계산에 사용된 얼굴 부위의 좌표들을 사용자에게 보여준다. 그리고 왼쪽에는 뇌졸중 의심 여부에 대한 판단과 함께 분석한 결과의 세부 사항들을 사용자가 참고할 수 있도록 출력하였다. 위 결과에서 뇌졸중 의심 여부 : false이므로 뇌졸중이 의심되지 않는 것으로 나온다. 또한 눈, 입술, 코의 비대칭성을 수치로 보여주어 어느 부위가 비대칭적인지 알 수 있게 하였다. 사진은 위에서 찍을 때와 다른 사진이다.
네이버가 빅데이터를 활용한 헬스케어사업을 준비하고 있을 수 있다는 소식이다. 네이버는 국내 최대 포털사이트인 보유한 데이터만큼은 우리나라 최고일 것이다. 네이버가 인수하는 이지케어텍은 100여개의 대형 병원에 EMR시스템을 운용하고 있는 EMR전문 업체이다. 이런 데이터를 기반으로 네이버가 헬스케어를 할 경우 해외 기업에 버금가는 영향력을 행사할 것이라고 생각한다. 이 글에서도 아마존, 구글, 애플 등의 기업들은 이미 데이터 기반 헬스케어사업을 본격화하고 있다고한다. 요즘 굉장히 많이 팔리고 있는 애플워치도 그런 데이터를 쌓을 수 있는 수단일 수 있다는 생각도 든다.
이 기사를 보면서 역시 네이버가 트렌드에 맞춘 사업을 준비하다고 생각했다. 요즘 해외 기업들도 관심있는 헬스케어에 뛰어든다는 것은 트렌드를 잘 읽고 있다는 것이고 그에 뒤쳐지지 않고 성장한다고 생각이 들었다.
한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.
준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.
풀이
문제 설명에 나와 있듯이 유명한 냅색 문제이다. 무게가 정해져 있을 때 가치를 최대로 배낭을 채우는 문제이다. DP문제로 유명한 이 문제는 다음 점화식으로 풀 수 있다.
이 점화식에서 i는 i번째 물건을 뜻한다. j는 무게이다. 즉 dp[i][j]가 뜻하는 것은 i번째 물건을 무게가 j이하로 채울 때 최대 가치의 합을 나타낸다. 따라서 dp[i-1][j]은 i번째 물건을 넣지 않는다는 뜻이고 dp[i-1][j-weight[i]] + cost[i]는 i번째 물건을 넣는다는 것이다. 따라서 i번째 물건의 무게(weight[i])를 j에서 뺀 값에 i번째 물건의 가치(cost[i])를 더한 값을 뜻한다. 즉 위의 점화식이 나타내는 것은 i번째 물건을 넣었을 때와 넣지 않았을 때의 값중 더 큰 값을 저장한다는 것이다. 이 점화식을 이용하여 작성한 코드는 다음과 같다.
소스 코드
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
vector<pair<int,int>> arr;
int dp[101][100001]; //101은 물건의 개수, 100001은 무게의 최대값
int w[101]; //i번째 물건의 무게
int value[101]; //i번째 물건의 가치
int main() {
int N, K; cin >> N >> K;
for(int i = 1; i <= N; i++) {
cin >> w[i] >> value[i];
}
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= K; j++) {
if(j < w[i]) //j값보다 i번째 물건의 무게가 더 큰 경우 배낭에 넣을 수 없다.
dp[i][j] = dp[i-1][j]; //따라서 물건을 넣지 않는다.
else { //물건이 들어갈 경우
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + value[i]);
//물건을 넣는 경우와 넣지 않은 경우 중 더 큰 가치 선택
}
}
}
cout << dp[N][K];
}
이렇게 문제를 풀 경우 상당한 메모리가 소모도니다. 이 코드를 보면 i번째 dp배열은 i-1번째 dp배열로부터 계산되는 것을 알 수 있다. i값은 2가지만 사용한다. 또 j번 인덱스만 봤을 때 더 큰 값이거나 같은 값으로 유지된다. 그림으로 나타내면 다음과 같다.
그렇다면 1개의 배열로 사용할 수 있지 않을까? 만약 j를 큰 값부터 줄여간다면 작은 값들에 영향을 주지 않고 갱신할 수 있을 것이다 (큰 값부터 한다는 것은 만약 작은 값에서 j-w[i]와 같이 큰 값으로 갱신 된다면 이후에 큰 값을 갱신할 때 이미 영향을 받은 값을 다시 갱신할 수 있기 때문이다). 코드로 나타내면 다음과 같다.
소스 코드
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int MN = 101;
const int MK = 100101;
int w[MN], cost[MN];
int dp[MK]; //1차원 배열
int main() {
int N, K; cin >> N >> K;
for(int i = 1; i <= N; i++) {
cin >> w[i] >> cost[i];
}
for(int i = 1; i <= N; i++) {
for(int j = K; j >= 0; j--) { //큰 값부터 작은 값으로
if(j >= w[i]) //배낭에 넣을 수 있을 때만
dp[j] = max(dp[j], dp[j-w[i]] + cost[i]); //더 큰 값으로 갱신
}
}
cout << dp[K];
}
채점 결과
위의 결과가 1차원 배열을 사용한 경우가 아래 결과가 2차원 배열을 사용한 경우이다. 메모리가 거의 20배 차이 나는 것을 알 수 있다.
문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 LCS(Longest Common Subsequence)를 구하고 있었다. 어느 날 영식이는 조교들이 문자열 3개의 LCS를 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다.
이제 우리가 할 일은 다음과 같다. 영식이를 도와서 문자열 3개의 LCS를 구하는 프로그램을 작성하라.
풀이
우리가 문자열 2개의 LCS를 구할 때 2차원 dp배열을 이용했다. 이 문제는 정말 단순하게 dp배열을 3차원으로만 늘리면 쉽게 풀린다. 3개의 문자열 s1, s2, s3가 있을 때 각각 i, j, k번 문자가 같을 경우 i, j, k번 이전의 문자열까지 중에 가장 큰 공통 부분 문자열의 크기에 1을 더한다. 그렇지 않을 경우 각각 i-1, j-1, k-1번까지의 공통 부분 문자열의 최대 크기를 저장한다. 코드로 나타내면 다음과 같다.
소스 코드
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int MN = 101;
int dp[MN][MN][MN];
int max(int a, int b, int c) { //인자 3개짜리 최대값 함수
return max(max(a, b), c);
}
int main() {
string s1, s2, s3;
cin >> s1 >> s2 >> s3; //3개의 문자열 입력
s1 = ' ' + s1;
s2 = ' ' + s2;
s3 = ' ' + s3;
for(int i = 1; i < s1.size(); i++) {
for(int j = 1; j < s2.size(); j++) {
for(int k = 1; k < s3.size(); k++) {
if(s1[i] == s2[j] && s2[j] == s3[k]) { //3개 문자가 모두 같은 경우
dp[i][j][k] = dp[i-1][j-1][k-1] + 1; //이전 공통 부분 문자열 크기에 1을 더함
}
else { //같지 않은 경우
dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1]); //지금까지의 최대값 저장
}
}
}
}
cout << dp[s1.size()-1][s2.size()-1][s3.size()-1];
}
팰린드롬이란 대칭 문자열이다. 즉, 왼쪽에서 오른쪽으로 읽었을때와 오른쪽에서 왼쪽으로 읽었을때 같다는 얘기다. 당신은 문자열이 주어졌을때, 최소 개수의 문자를 삽입하여 팰린드롬이 되게 되는 문자의 개수를 구하는 프로그램을 작성하여라.
예제에서는, 2개의 문자를 삽입하여 팰린드롬이 된다. "Ab3bd"는 "dAb3bAd" 혹은 "Adb3bdA" 로 바뀔 수 있다. 하지만, 2개 미만의 문자를 삽입해서는 팰린드롬이 될 수 없다.
풀이
이 문제는 LCS문제를 변형한 문제이다. 한 문자열이 펠린드롬이 되기 위해서는 펠린드롬이 되는 부분 문자열에 부족한 부분을 추가하면 된다. 따라서 어떤 문자열과 그 문자열을 뒤집은 문자열의 공통 부분 문자열의 길이를 구하고 원래 문자열과의 차이를 구하면 된다. 예시는 다음과 같다.
ab3bd를 뒤집으면 db3ba가 된다. 그럼 ab3bd와 db3ba의 공통 부분 문자열은 b3b가 된다. 그렇다면 원래 문자에서 빠진 문자는 a와 d가 있다. 이 a와 d를 원래 문자열에 하나씩 추가하면 펠린드롬을 만들 수 있는 것이다. 코드로 나타내면 다음과 같다.
소스 코드
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int MN = 5001;
int dp[MN][MN]; //LCS를 위한 dp배열
int main() {
int answer = 0;
int N; cin >> N;
string s1, s2; //원래 문자열과 뒤집은 문자열
cin >> s1;
s2 = s1;
s1 = ' ' + s1;
reverse(s2.begin(), s2.end()); //문자열 뒤집기
s2 = ' ' + s2;
for(int i = 1; i < s1.size(); i++) { //공통 부분 문자열 길이 구하기
for(int j = 1; j < s2.size(); j++) {
if(s1[i] == s2[j]) {
dp[i][j] = dp[i-1][j-1] + 1;
answer = max(answer, dp[i][j]);
}
else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
cout << N - dp[N][N]; //공통 부분 문자열의 길이를 원래 문자열 길이에서 뺀다. 즉 부족한 문자 개수 출력
}
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
풀이
LCS문제는 DP를 이용한다. 2차원 배열 DP에서 dp[i][j]가 의미하는 것은 두 문자열 s1, s2에 대하여 s1의 i번째 문자와 s2의 j번째 문자까지 공통되는 부분 수열의 길이를 나타낸다. 배열은 다음과 같다.
만약 s1[i]와 s2[j]가 같다면 dp[i-1][j-1]에 1을 더한 값을 넣는다. 이전 길이에서 하나 더 늘어났기 때문이다. 그렇지 않고 만 약 s1[i]와 s2[j]가 같지 않다면 dp[i-1][j]와 dp[i][j-1] 중에 더 큰 값을 넣는다. 이전 문자까지 이루어진 공통 부분 수열 중 가장 큰 값을 넣어야하기 때문이다. 코드를 짜면 다음과 같다.
소스 코드
#include <iostream>
#include <string>
#include <vector>
#include <deque>
using namespace std;
const int MN = 1001;
int dp[MN][MN];
int main() {
string s1, s2; //두 문자열
cin >> s1 >> s2;
s1 = ' ' + s1; //1번 인덱스부터 사용하기 위해 앞에 공백을 추가
s2 = ' ' + s2;
for(int i = 1; i < s1.size(); i++) {
for(int j = 1; j < s2.size(); j++) {
if(s1[i] == s2[j]) //같은 경우
dp[i][j] = dp[i-1][j-1] + 1; //이전 문자까지 중에 가장 큰 값에 1을 추가
else //같지 않을 경우
dp[i][j] = max(dp[i-1][j], dp[i][j-1]); //이전 문자까지 중 가장 큰 값으로 설정
}
}
cout << dp[s1.size()-1][s2.size()-1];
}
앞에 공백을 추가하는 이유는 1번 인덱스부터 사용하기 위해서이다. 대각선 값을 가져오는데 만약 첫 문자가 같은 경우 -1이 되므로 (1, 1)부터 인덱스를 시작하기 위하여 앞에 공백을 넣었다.
이 문제에서 가장 까다로웠던 것은 주사위가 굴러가는 것이다. 좌, 우로만 움직이거나 상, 하로만 움직인다면 굉장히 쉬운 일이지만 만약 지금 상태에서 상하로 구르는 것과 좌로 한 칸 이동 후에 상하로 구르는 것은 완전 다른 패턴을 가지고 있으므로 표현하는 것이 어렵다. 따라서 주사위가 상,하,좌,우로 굴렀을 때 값의 위치가 어디로 가는 지를 알고 상, 하, 좌, 우로 이동하는 함수 4개를 만들었다. 예시로 다음과 같다. 만약 주사위가 위의 문제와 같이 있고 1이 위에 있다고 가정하자. 주사위를 위로 굴렸을 때 값은 이렇게 바뀐다.
1번 자리 : 5
2번 자리 : 1
3번 자리 : 3
4번 자리 : 4
5번 자리 : 6
6번 자리 : 2
그림 예시
이런 방식으로 상, 하, 좌, 우로 굴렀을 때의 주사위를 나타내는 함수를 만들었다. 그 다음은 어렵지 않다. 문제에서 준 대로 바닥이 0인 경우 주사위의 아래있는 값을 복사하고 0이 아닌 경우 주사위의 면을 갱신하고 바닥을 0으로 만들면 된다.
소스 코드
#include <iostream>
#include <cstring>
#include <vector>
#include <deque>
using namespace std;
int board[21][21];
int dice[6] = {0, 0, 0, 0, 0, 0}; //초기 주사위 전개도 순서로 초기화
void up() { //위로 굴렀을 때의 주사위 값 변화
int tmp[6];
tmp[0] = dice[4];
tmp[1] = dice[0];
tmp[2] = dice[2];
tmp[3] = dice[3];
tmp[4] = dice[5];
tmp[5] = dice[1];
memcpy(dice, tmp, sizeof(dice));
}
void down() { //아래로 굴렀을 때의 주사위 값 변화
int tmp[6];
tmp[0] = dice[1];
tmp[1] = dice[5];
tmp[2] = dice[2];
tmp[3] = dice[3];
tmp[4] = dice[0];
tmp[5] = dice[4];
memcpy(dice, tmp, sizeof(dice));
}
void left() { //왼쪽으로 굴렀을 때의 주사위 값 변화
int tmp[6];
tmp[0] = dice[2];
tmp[1] = dice[1];
tmp[2] = dice[5];
tmp[3] = dice[0];
tmp[4] = dice[4];
tmp[5] = dice[3];
memcpy(dice, tmp, sizeof(dice));
}
void right() { //오른쪽으로 굴렀을 때의 주사위 값 변화
int tmp[6];
tmp[0] = dice[3];
tmp[1] = dice[1];
tmp[2] = dice[0];
tmp[3] = dice[5];
tmp[4] = dice[4];
tmp[5] = dice[2];
memcpy(dice, tmp, sizeof(dice));
}
int main() {
int N, M, x, y, K; cin >> N >> M >> x >> y >> K;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
cin >> board[i][j];
}
}
if(board[x][y] == 0) { //바닥이 0인 경우
board[x][y] = dice[5]; //주사위값 복사
}
else { //바닥이 0이 아닌 경우
dice[5] = board[x][y]; //주사위에 바닥값 복사
board[x][y] = 0; //바닥은 0으로
}
for(int i = 0; i < K; i++) {
int a; cin >> a;
switch(a) {
case 1: //동쪽으로 가는 경우
if(y + 1 < M) { //벗어나지 않을 때 동작
y++;
right();
}
else continue;
break;
case 2: //서쪽으로 가는 경우
if(y-1 >= 0) {
y--;
left();
}
else continue;
break;
case 3: //북쪽으로 가는 경우
if(x-1 >= 0) {
x--;
up();
}
else continue;
break;
case 4: //남쪽으로 가는 경우
if(x+1 < N) {
x++;
down();
}
else continue;
break;
}
if(board[x][y] == 0) { //바닥이 0인 경우
board[x][y] = dice[5]; //바닥에 주사위 아래값 복사
}
else { //바닥이 1인 경우
dice[5] = board[x][y]; //주사위 아래에 바닥값 복사
board[x][y] = 0; //바닥은 0으로
}
cout << dice[0] << '\n'; //주사위 위에 있는 값 출력
}
}
