[Algorithm] Prim 과 Kruskal 그리고 Dijkstra 와 Floyd

이 4가지 알고리즘이 자꾸만 헷갈려서 심플하게 정리해 둔다.


- Prim과 Kruskal : MST (Minimumm Spanning Tree) 를 만드는 알고리즘

Prim 은 시작 정점부터 시작해서 가까이에 있는 정점으로 가는 패스 중 가장 최소값을 찾아서 연결해 나가는 방식이다. Greedy 적인 요소가 다분하다. 또한 Shortest Path를 찾는 알고리즘인 Dijkstra와 아주아주아주아주 유사하다.

반면 Kruskal은 Heap과 Union-Find 자료구조를 이용해서 MST를 만드는데 전체에서 가장 작은 Path들을 찾아서 서로서로 연결시켜 나가면서 MST를 만든다. Kruskal도 Greedy 적이다.



- Shortest Path 를 찾는 알고리즘 : Dijkstra 와 Floyd

Dijkstra는 시작점에서 가장 가까운 정점들 중 가장 최소값을 가진 Path를 따라간다. Prim과 매우 유사하다.

Floyd는 DP(Dynamic Programming) 방식으로 전체를 모두 스캔해 가면서 개선한다... 코드가 아주 짧은 것이 특징!

정리 종료!!

[Tizen] EFL을 위한 Vim 환경 설정

EDC Support 파일 다운로드를 다운로드 하자. 아래의 링크에서 Zip을 다운로드 받는다

https://git.enlightenment.org/editors/vim-configs.git/tree/syntax

다운로드 된 파일은 압축을 풀어서 ~/vim/bundle/ 에 넣어 놓는다.

끝!



# 참고 : https://github.com/vim-scripts/edc-support

# 참고 : http://storycompiler.tistory.com/57

[Tizen] EFL Relative

description { .. rel1 { relative: 0.0 0.0; offset: 0 0; to: [another part's name] } .. rel2 { relative: 1.0 1.0; offset: -1 -1; to: [another part's name] } .. }
The rel1 and rel2 blocks are used to define the position of each corner of the part's container. With rel1 being the left-up corner and rel2 being the right-down corner.

EFL에서 좌표는 왼쪽 상단을 기준(Origin)으로 한다. 즉, (0,0)은 왼쪽 상단을 의미하며 (1,1)은 오른쪽 하단을 의미한다.

relative 속성에서 rel1 은 왼쪽 위의 좌표를 의미하며, rel2는 오른쪽 아래의 좌표를 의미한다. 이 두 좌표로 하나의 Part의 위치를 지정한다. 즉, description이라는 상자의 위치를 정하는데 사용 하는 block 이다.


relative (in rel1 or rel2) : to 속성에 지정된 Part를 기준으로 상대적인 좌표를 지정하는 속성이다. relative [x axis] [y axis] 로 두개의 인자를 가진다. x axis가 0일 경우 to에 지정된 part의 왼쪽 x좌표를 가져오며 1일 경우 맨 오른쪽 x좌표를 가져온다. y axis도 마찬가지다.

relative	[X axis] [Y axis]
	Moves a corner to a relative position inside the container of the relative "to" part. Values from 0.0 (0%, beginning) to 1.0 (100%, end) of each axis.

offset (in rel1 or rel2) : to 에 지정된 Part와의 절대적인 거리를 둔다

offset	[X axis] [Y axis]
	Affects the corner position a fixed number of pixels along each axis.

to (in rel1 or rel2) : 어떤 대상을 기준으로 삼을 것인지 지정하는 속성이다. part name을 적어주면 된다.

to	[another part's name]
	Causes a corner to be positioned relatively to another part's container. Setting to "" will un-set this value for inherited parts.

to_x (in rel1 or rel2) : x 좌표만 기준으로 삼을 part의 name을 지정하는 속성이다. relative 에서 [x axis] 에 지정된 값이 to_x로 지정된 part의 x값을 결정하게 된다.

to_x	[another part's name]
	Causes a corner to be positioned relatively to the X axis of another part's container. Simply put affects the first parameter of "relative". Setting to "" will un-set this value for inherited parts.

to_y (in rel1 or rel2) : to_x와 마찬가지다. to_x 와 to_y가 겹치는 곳 사이가 결국 기준점이 된다.

to_y	[another part's name]
	Causes a corner to be positioned relatively to the Y axis of another part's container. Simply put, affects the second parameter of "relative". Setting to "" will un-set this value for inherited parts.

[Tizen] EFL Text

part {

description {

..

text {

text: "some string of text to display";

font: "font_name";

size: SIZE;

text_class: "class_name";

fit: horizontal vertical;

min: horizontal vertical;

max: horizontal vertical;

align: X-axis Y-axis;

source: "part_name";

text_source: "text_part_name";

ellipsis: -1.0 (since 1.8), 0.0-1.0;

style: "stylename";

}

..

}

}

 
min (in text block) : 만약 0이 아닌 어떤 값(보통 1)이 horizontal 이나 vertical 위치에 들어가게 되면 아무리 크기를 얼마로 잡아놨든 글자에 맞게 최소 크기를 확장된다. 본래 크기가 크다면 상관 없지만 글자영역보다 작다면 확장된다는 의미다.

max	[horizontal] [vertical]
	When any of the parameters is enabled (1) it forces the maximum size of the container to be equal to the maximum size of the text. The default value is "0 0".

max (in text block) : 만약 0이 아닌 어떤 값(보통 1)이 horizontal 이나 vertical 위치에 들어가게 되면 아무리 크기를 얼마로 잡아놨든 글자에 맞게 최대 크기가 확장된다. max 와 min의 차이가 뭘까.



max	[horizontal] [vertical]
	When any of the parameters is enabled (1) it forces the maximum size of the container to be equal to the maximum size of the text. The default value is "0 0".












ellipsis (in text block) : 글자 수가 많아서 본래 크기를 넘어버릴 때 생략 (...)을 한다. 0.0이면 글자의 앞을 살리고(끝을 생략한다는 의미) 1.0이면 글자의 뒤를 살린다(앞을 생략한다). 0.5라면? 중간을 살리고 양쪽을 생략해버린다.

ellipsis

[point of balance]

Used to balance the text in a relative point from 0.0 to 1.0, this point is the last section of the string to be cut out in case of a resize that is smaller than the text itself. The default value is 0.0.




아래는 EFL 문서에 있는 본문이다.
(https://docs.enlightenment.org/auto/edje/edcref.html)

[Cocos2d-x] 화면 사이즈

http://egloos.zum.com/icegeo/v/298307

[Android] Service

Service는 Thread와 마찬가지로 백그라운드 작업자다. 그러나 가장 큰 차이점은 명시적으로 Kill 하지 않으면 죽지 않는다는 점인데, 명시적 Kill 하지 않았는데 죽을 경우에는 다시 살아난다.

1. Unbound Service (or Started Service)
startService(); 로 호출

이러한 서비스는 작업 결과를 돌려주기 위해서는 BroadcastReceiver를 만들어서 결과를 받아야 한다.

그 Receiver는 Activity 와 상호 작용하여 UI를 업데이트 해야 한다.


2. Bound Service
bindService(); 로 호출

Unbound Service와 달리 Activity와 즉각 상호작용이 가능하다.



p.s 간단하게 썼지만 BroadcastReceiver 와 Activity간의 상호작용은 꽤나 어렵다. 다음의 예제에서 답을 찾을 수 있다.


package com.example.usecalcproject;

import android.app.Activity;
import android.content.BroadcastReceiver;
import android.content.ComponentName;
import android.content.Context;
import android.content.Intent;
import android.content.IntentFilter;
import android.content.ServiceConnection;
import android.os.Bundle;
import android.os.IBinder;
import android.os.RemoteException;
import android.view.View;
import android.widget.Button;
import android.widget.EditText;
import android.widget.TextView;

import com.example.calcproject.ICalc;

public class MainActivity extends Activity implements View.OnClickListener {

private EditText mEditExpr1;
private Button mBtnCalc1;
private TextView mtxtResult1;

private EditText mEditExpr2;
private Button mBtnCalc2;
private TextView mtxtResult2;

private BroadcastReceiver mBR;

/* 옵션 구현(1/5) */
ICalc mCalc;

@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);

mEditExpr1 = (EditText) findViewById(R.id.editExpr1);
mBtnCalc1 = (Button) findViewById(R.id.btnCalc1);
mBtnCalc1.setOnClickListener(this);
mtxtResult1 = (TextView) findViewById(R.id.txtResult1);

mEditExpr2 = (EditText) findViewById(R.id.editExpr2);
mBtnCalc2 = (Button) findViewById(R.id.btnCalc2);
mBtnCalc2.setOnClickListener(this);
mtxtResult2 = (TextView) findViewById(R.id.txtResult2);

if (savedInstanceState != null) {
String expr1 = savedInstanceState.getString("expr1", "");
mEditExpr1.setText(expr1);
String result1 = savedInstanceState.getString("result1", "");
mtxtResult1.setText(result1);
String expr2 = savedInstanceState.getString("expr2", "");
mEditExpr2.setText(expr2);
String result2 = savedInstanceState.getString("result2", "");
mtxtResult2.setText(result2);
}

mBR = new MyReceiver();
}

@Override
protected void onSaveInstanceState(Bundle outState) {
super.onSaveInstanceState(outState);
outState.putString("expr1", mEditExpr1.getText().toString());
outState.putString("result1", mtxtResult1.getText().toString());
outState.putString("expr2", mEditExpr2.getText().toString());
outState.putString("result2", mtxtResult2.getText().toString());
}

// Inner class
// Receiver가 Activity에 접근하는 하나의 방법
private class MyReceiver extends BroadcastReceiver {

@Override
public void onReceive(Context context, Intent intent) {
String result = intent.getStringExtra("result");
mtxtResult1.setText(result);
}
}

@Override
protected void onResume() {
super.onResume();
IntentFilter filter = new IntentFilter("example.mytest.CALCRESULT");
registerReceiver(mBR, filter);

/* 옵션 구현(2/5) */
Intent i = new Intent();
i.setClassName("com.example.calcproject", "com.example.calcproject.CalcService");
bindService(i, srvConn, BIND_AUTO_CREATE);
}

@Override
protected void onPause() {
super.onPause();
unregisterReceiver(mBR);

/* 옵션 구현(3/5) */
unbindService(srvConn);
}

/* 옵션 구현(4/5) */
ServiceConnection srvConn = new ServiceConnection() {

@Override
public void onServiceConnected(ComponentName className, IBinder binder) {
mCalc = ICalc.Stub.asInterface(binder);
}

@Override
public void onServiceDisconnected(ComponentName className) {
mCalc = null;
}
};

@Override
public void onClick(View v) {
switch (v.getId()) {
case R.id.btnCalc1:
if (mEditExpr1.getText().length() > 0) {
Intent i = new Intent();
i.setClassName("com.example.calcproject", "com.example.calcproject.CalcService");
i.putExtra("expr", mEditExpr1.getText().toString());
startService(i);
}
break;
case R.id.btnCalc2: /* 옵션 구현(5/5) */
if (mEditExpr2.getText().length() > 0) {
try {
String result = mCalc.calc(mEditExpr2.getText().toString());
mtxtResult2.setText(result);
}
catch (RemoteException e) {
e.printStackTrace(); // Security risk!
}
}
break;
}
}
}



해결 방법 중 하나인 AIDL 파일
package com.example.calcproject;

interface ICalc {
String calc(String expr);
}

[Android] Thread

DDMS 에서 원하는 앱을 선택하고 왼쪽고 상단에 화살표 세개 모양의 아이콘을 눌리고 오른쪽 창에서 같은 아이콘 모양의 Threads를 눌리면 현재 앱의 Thread 상태들을 볼 수 있다.

Android는 다음의 방식으로 Thread를 지원한다.

1. Looper
- 메시지 큐를 생성하고 초기화
- 메시지 큐에서 데이터를 꺼내서 Handler에게 전달

2. Handler
- Looper가 전달해 준 데이터를 처리
- 메시지 큐에 데이터를 삽입


UI Main Thread 도 Looper를 가지고 있으나 우리의 코드에 보이지는 않는다. 다만 Handler를 붙여서 Looper를 이용할 수는 있다.

보통 UI Thread와 다른 Thread (이하 Worker Thread) 간의 통신을 위해서 Handler를 사용하게 되는데 양방향 통신을 위해서는 Handler 또한 양 쪽 Thread 모두에게 붙여야 한다. Handler는 UI Thread와 Worker Thread에서 모두 접근 가능하도록 코드를 작성 해야 한다.

예제는 다음과 같다.

public class C16_Handler extends Activity {

int mMainValue = 0;
int mBackValue = 0;
TextView mMainText;
TextView mBackText;

@Override public void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.c16_thread);

mMainText = (TextView) findViewById(R.id.mainvalue);
mBackText = (TextView) findViewById(R.id.backvalue);

BackThread thread = new BackThread();
thread.setDaemon(true);
thread.start();
}

public void mOnClick(View v) {
mMainValue++;
mMainText.setText("MainValue : " + mMainValue);
}

class BackThread extends Thread {

@Override public void run() {
while (true) {
mBackValue++;
// mHandler.sendEmptyMessage(0);
Message msg = new Message();
msg.what = 0;
msg.arg1 = 0;
msg.arg2 = 0;
msg.obj = null;
mHandler.sendMessage(msg);

try {
Thread.sleep(1000);
}
catch (InterruptedException e) {
;
}
}
}
}

Handler mHandler = new Handler() {

@Override public void handleMessage(Message msg) {
if (msg.what == 0) {
mBackText.setText("BackValue : " + mBackValue);
}
}
};
}


Message를 다루는 방법도 여러가지가 있는데 여기서는 다루지 않겠다. 다만 다음과 같이 Pool 방식도 있음을 알아두자.

Message msg = Message.obtain();


다음은 명시적으로 Looper를 이용하는 방식의 예제다.


public class C16_Looper extends Activity {

int mMainValue = 0;

TextView mMainText;
TextView mBackText;
EditText mNumEdit;

CalcThread mThread;

@Override public void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.c16_looper);

mMainText = (TextView) findViewById(R.id.mainvalue);
mBackText = (TextView) findViewById(R.id.backvalue);
mNumEdit = (EditText) findViewById(R.id.number);

mThread = new CalcThread(mHandler);
mThread.setDaemon(true);
mThread.start();
}

public void mOnClick(View v) {
Message msg;

switch (v.getId()) {
case R.id.increase:
mMainValue++;
mMainText.setText("MainValue : " + mMainValue);
break;
case R.id.square:
msg = new Message();
msg.what = 0;
msg.arg1 = Integer.parseInt(mNumEdit.getText().toString());
mThread.mBackHandler.sendMessage(msg);
break;
case R.id.root:
msg = new Message();
msg.what = 1;
msg.arg1 = Integer.parseInt(mNumEdit.getText().toString());
mThread.mBackHandler.sendMessage(msg);
break;
}
}

Handler mHandler = new Handler() {

@Override public void handleMessage(Message msg) {
switch (msg.what) {
case 0:
mBackText.setText("Square Result : " + msg.arg1);
break;
case 1:
mBackText.setText("Root Result : " + ((Double) msg.obj).doubleValue());
break;
}
}
};
}

class CalcThread extends Thread {

Handler mMainHandler;
Handler mBackHandler;

CalcThread(Handler handler) {
mMainHandler = handler;
}

@Override public void run() {
Looper.prepare();

mBackHandler = new Handler() {

@Override public void handleMessage(Message msg) {
Message retmsg = new Message();
switch (msg.what) {
case 0:
try {
Thread.sleep(200);
}
catch (InterruptedException e) {
;
}
retmsg.what = 0;
retmsg.arg1 = msg.arg1 * msg.arg1;
break;
case 1:
try {
Thread.sleep(200);
}
catch (InterruptedException e) {
;
}
retmsg.what = 1;
retmsg.obj = new Double(Math.sqrt(msg.arg1));
break;
}
mMainHandler.sendMessage(retmsg);
}
};

Looper.loop();
}
}