2016.10.03 12:02


Menifest 상에 설정하는 User-permission


 

<uses-permission android:name="android.permission.ACCESS_FINE_LOCATION"/>

//위치정보 확인함
<uses-permission android:name="android.permission.ACCESS_MOCK_LOCATION"/>

//위치정보 확인함

<uses-permission android:name="android.permission.ACCESS_WIFI_STATE"/>

//wifi 연결을 확인함
<uses-permission android:name="android.permission.CHANGE_WIFI_STATE"/>

//wifi 체인지를 확인함

<uses-permission android:name="android.permission.ACCESS_NETWORK_STATE" />

//네트웍이 연결된것을 확인할수 있게함

<uses-permission android:name="android.permission.RECEIVE_BOOT_COMPLETED" />

//부팅완료를 확인할수있게함

<uses-permission android:name="android.permission.INTERNET"/>

// 인터넷을 사용함

<uses-permission android:name="android.permission.WRITE_EXTERNAL_STORAGE"/>

// 외장메모리 사용

<uses-permission android:name="android.permission.RECODER_AUDIO"/>

//녹음이 가능하게 함

 

ACCESS_CHECKIN_PROPERTIES      체크인데이터베이스의_속성테이블로_액세스
ACCESS_COARSE_LOCATION         코스_로케이션_액세스_(Cell-ID/WiFi)
ACCESS_FINE_LOCATION           파인로케이션_액세스(GPS)          
ACCESS_LOCATION_EXTRA_COMMANDS 로케이션_옵션_커맨드_액세스       
ACCESS_MOCK_LOCATION           목_로케이션_프로바이더_생성_(테스트용)
ACCESS_NETWORK_STATE           네트워크_상태_접근                
ACCESS_SURFACE_FLINGER         서피스_플링거_접근                
ACCESS_WIFI_STATE              WiFi상태_접근                     
ADD_SYSTEM_SERVICE             시스템서비스_추가                 
BATTERY_STATS                  배터리_상태                       
BLUETOOTH                      블루투스                          
BLUETOOTH_ADMIN                블루투스_어드민                   
BRICK                          디바이스_실효성_지정              
BROADCAST_PACKAGE_REMOVED      제거된_패키지에_대한_notification_브로드캐스트
BROADCAST_SMS                  SMS에_대한_브로드캐스트           
BROADCAST_STICKY               인텐트_브로드캐스트               
CALL_PHONE                     통화                              
CALL_PRIVILEGED                통화(긴급전화_포함)               
CAMERA                         카메라                            
CHANGE_COMPONENT_ENABLED_STATE 컴포넌트의_실효성_변경            
CHANGE_CONFIGURATION           컨피그_변경                       
CHANGE_NETWORK_STATE           통신상태_변경                     
CHANGE_WIFI_STATE              WiFi상태_변경                     
CLEAR_APP_CACHE                어플리케이션_캐시_클리어          
CLEAR_APP_USER_DATA            어플리케이션의_유저데이터_클리어  
CONTROL_LOCATION_UPDATES       위치정보_갱신                     
DELETE_CACHE_FILES             캐시파일_제거                     
DELETE_PACKAGES                패키지_제거                       
DEVICE_POWER                   전원상태에_대한_로우레벨_접근     
DIAGNOSTIC                     진단리소스_읽고쓰기               
DISABLE_KEYGUARD               키_가드_끄기_DUMP_덤?            
EXPAND_STATUS_BAR              상태표시줄_확장                   
FACTORY_TEST                   팩토리_테스트                     
FLASHLIGHT                     플래시라이트                      
FORCE_BACK                     포스백                            
GET_ACCOUNTS                   어카운트_획득                     
GET_PACKAGE_SIZE               패키지_획득                       
GET_TASKS                      태스크_획득                       
HARDWARE_TEST                  하드웨어테스트                    
INJECT_EVENTS                  유저이벤트_키/트랙볼              
INSTALL_PACKAGES               패키지_인스톨                     
INTERNAL_SYSTEM_WINDOW         내부_시스템윈도_활용              
INTERNET                       인터넷                            
MANAGE_APP_TOKENS              어플리케이션_토큰관리             
MASTER_CLEAR                   마스터_클리어                     
MODIFY_AUDIO_SETTINGS          오디오설정_편집                   
MODIFY_PHONE_STATE             전화상태_편집                     
MOUNT_UNMOUNT_FILESYSTEMS      파일시스템_편집                   
PERSISTENT_ACTIVITY            액티비티_지속                     
PROCESS_OUTGOING_CALLS         전화_발신처리_접근                
READ_CALENDAR                  캘린더_읽어오기                   
READ_CONTACTS                  주소록_읽어오기                   
READ_FRAME_BUFFER              프레임버퍼_읽어오기               
READ_INPUT_STATE               입력상태_읽어오기                 
READ_LOGS                      로그_읽어오기                     
READ_OWNER_DATA                owner_data읽어오기                
READ_PHONE_STATE               통화상태_읽어오기_READ_SMS_SMS읽어오기
READ_SYNC_SETTINGS             동기설정_읽어오기                 
READ_SYNC_STATS                동기상태_읽어오기                 
REBOOT                         reboot                            
RECEIVE_BOOT_COMPLETED         boot완료                          
RECEIVE_MMS                    MMS수신                           
RECEIVE_SMS                    SMS수신                           
RECEIVE_WAP_PUSH               WAP수신                           
RECORD_AUDIO                   오디오_수신                       
REORDER_TASKS                  태스크_Z오더                      
RESTART_PACKAGES               패키지_리스타트                   
SEND_SMS                       SMS송신                           
SET_ACTIVITY_WATCHER           액티비티_왓쳐지정                 
SET_ALWAYS_FINISH              액티비티_전체_종료                
SET_ANIMATION_SCALE            스케일_애니메이션_지정            
SET_DEBUG_APP                  디버그어플리케이션_지정           
SET_ORIENTATION                스크린_로테이션지정               
SET_PREFERRED_APPLICATIONS     자주_사용하는_어플리케이션_지정   
SET_PROCESS_FOREGROUND         포어그라운드_처리지정             
SET_PROCESS_LIMIT              제한처리_지정                     
SET_TIME_ZONE                  타임존_지정                       
SET_WALLPAPER                  배경화면_지정                     
SET_WALLPAPER_HINTS            배경화면_힌트_지정                
SIGNAL_PERSISTENT_PROCESSES    지속처리_시그널_지정              
STATUS_BAR                     상태표시줄_지정                   
SUBSCRIBED_FEEDS_READ          서브스트립드_피즈_읽어오기        
SUBSCRIBED_FEEDS_WRITE         서브스트립드_피즈_쓰기            
SYSTEM_ALERT_WINDOW            알림_윈도우                       
VIBRATE                        진동                              
WAKE_LOCK                      알람                              
WRITE_APN_SETTINGS             APN설정_쓰기                      
WRITE_CALENDAR                 캘린더_쓰기                       
WRITE_CONTACTS                 주소록_쓰기                       
WRITE_GSERVICES                G서비스_쓰기                      
WRITE_OWNER_DATA               owner_data쓰기                    
WRITE_SETTINGS                 설정_쓰기
WRITE_SMS                      SMS쓰기 
WRITE_SYNC_SETTINGS            동기설정_쓰기

신고


Posted by injunech
2016.10.01 21:13


[Android] 알람 링톤 (Alarm Ringtone) 선택하기



알람의 벨소리(링톤) 을 선택하고 싶을 때 참고하세요.


DialogPicker를 startActivityForResult()로 호출 하고

해당 Dialog 에서 선택된 Ringtone 의 Uri 를 onActivityResult() 콜백 함수에서 받아온다.


onActivityResult() 콜백 함수 내에서 999 호출 되었을때 

선택된 Ringtone 의 URI 를 저장하거나 해당 링톤을 재생하거나 원하는 대로 코딩하면 됩니다.


private void showRingtonePickerDialog() {
    Intent intent = new Intent(RingtoneManager.ACTION_RINGTONE_PICKER);
    intent.putExtra(RingtoneManager.EXTRA_RINGTONE_TITLE, "Select ringtone for notifications:");
    intent.putExtra(RingtoneManager.EXTRA_RINGTONE_SHOW_SILENT, false);
    intent.putExtra(RingtoneManager.EXTRA_RINGTONE_SHOW_DEFAULT, true);
    intent.putExtra(RingtoneManager.EXTRA_RINGTONE_TYPE,RingtoneManager.TYPE_NOTIFICATION);
    startActivityForResult(intent, 777);
}



@Override
protected void onActivityResult(int requestCode, int resultCode, Intent data) {
    super.onActivityResult(requestCode, resultCode, data);
    if (resultCode == RESULT_OK) {
        switch (requestCode) {
           case 999:
                    Uri uri = data.getParcelableExtra(RingtoneManager.EXTRA_RINGTONE_PICKED_URI);
                    if (uri != null) {
                        String ringtonePath = uri.toString();
                        Toast.makeText(getApplicationContext(), "ringtone="+ringtonePath, Toast.LENGTH_LONG).show();
                    }
           break;
 
        default:
           break;
        }
    }
}



# intent 에서 아래의 옵션을 설정 하여 보여주고싶은 Alarm Ringtone 의 목록 설정


Intent intent = new Intent(RingtoneManager.ACTION_RINGTONE_PICKER);
intent.putExtra(RingtoneManager.EXTRA_RINGTONE_TITLE, "Select ringtone");
intent.putExtra(RingtoneManager.EXTRA_RINGTONE_SHOW_SILENT, false);
intent.putExtra(RingtoneManager.EXTRA_RINGTONE_SHOW_DEFAULT, true);

// 아래 4가지중 선택
// intent.putExtra(RingtoneManager.EXTRA_RINGTONE_TYPE, RingtoneManager.TYPE_ALL);
// intent.putExtra(RingtoneManager.EXTRA_RINGTONE_TYPE, RingtoneManager.TYPE_ALARM);
// intent.putExtra(RingtoneManager.EXTRA_RINGTONE_TYPE, RingtoneManager.TYPE_NOTIFICATION);
intent.putExtra(RingtoneManager.EXTRA_RINGTONE_TYPE,  RingtoneManager.TYPE_RINGTONE);





신고


Posted by injunech
2016.09.23 01:26


ListView를 보시면 화면을 터치한 후 드래그하는 속도에 따라 ListView의 스크롤링 속도가 변하는 것을 볼 수 있습니다. 천천히 하면 스크롤도 천천히 되고 빠르게 드래그하면 바퀴 돌 듯이 ListView가 스크롤 되지요. 이런 효과는 어떻게 구현될 수 있을까요? 안드로이드에서 제공하는 클래스를 통해 쉽게 구현할 수 있습니다. 다음의 코드를 보시죠.


public class MyOnTouchListener implements OnTouchListener {

    private VelocityTracker mVelocityTracker;

    public boolean onTouch(View v, MotionEvent event) {

        if (mVelocityTracker == null) {

            mVelocityTracker = VelocityTracker.obtain();

        }

        mVelocityTracker.addMovement(event);


        switch (event.getAction()) { 

        case MotionEvent.ACTION_DOWN:

            Log.v(TAG"ACTION_DOWN");

            break



        case MotionEvent.ACTION_MOVE:

            Log.v(TAG"ACTION_MOVE");

            mVelocityTracker.computeCurrentVelocity(1);

            float velocity = mVelocityTracker.getXVelocity();

            break


        case MotionEvent.ACTION_UP:

            Log.v(TAG"ACTION_UP");

            if (mVelocityTracker != null) {

                mVelocityTracker.recycle();

                mVelocityTracker = null;

            }

            break

        } 

        return true;

    }

}


요점은 VelocityTracker가 드래그의 속도를 측정해준다는 것입니다. 위의 예제에서는 VelocityTracker의 5가지 메소드가 사용되었습니다.

1. obtain()
   이것은 정적 메소드입니다. VelocityTracker의 인스턴스를 구하기 위한 팩토리 메소드입니다.
2. addMovement(MotionEvent e)
   속도를 측정하기 위해서 VelocityTracker 인스턴스에 MotionEvent를 입력합니다.
3. computeCurrentVelocity(int unit)
   입력된 데이타를 기반으로 속도를 측정합니다. unit은 측정 시간 단위이며 1은 1밀리초를, 1000은 1초를 의미합니다. 다시 말해 unit이 1이라면 1밀리초동안의 픽셀단위의 이동 거리를 측정합니다.
4. getXVelocity()
   X축으로의 속도를 구합니다. Y축으로의 속도는 getYVelocity()를 사용하면 됩니다. 
5. recycle()
   객체를 재사용할 수 있도록 초기화 합니다.
   드래깅 속도 측정은 빈번하게 일어나는 연산입니다. 하지만 이를 위해서 각각의 OnTouchListener가 VelocityTracker의 인스턴스를 하나씩 점유하는 것은 분명 낭비입니다.(안드로이드는 임베디드 시스템을 위한 운영체제임!) 따라서 VelocityTracker 객체의 생성은 팩토리 메소드에 위임하고 객체는 사용 후 반환합니다. 그러면 결과적으로 VelocityTracker 객체 하나가 모든 드래깅 동작에 공유되어 사용될 수 있습니다. 




출처 : http://anddev.tistory.com/16


신고


Posted by injunech
2016.09.14 01:20



# String to Int



 int numInt = Integer.parseInt(numStr);


 


# Int to String



 String numStr2 = String.valueOf(numInt);
 

신고


Posted by injunech
2016.04.09 00:14


[초급] 문자열 입력받고 하나씩 자르기

입력값이 12345 와같은 값으로 들어올때 int 배열의 하나의 공간에 각 한자리 숫자 값을 입력 받는 방법이다.
#include <stdio.h>

int main() {
	char str[50];
	int val[10];

	scanf("%s", &str);
	for (int i = 0; str[i] != '\0'; i++){
		val[i] = str[i] - '0';
		printf("%d ", val[i]);
	}
	return 0;
}
input 값이 12345 인 경우 char str 배열에 들어가는 입력 값은 str[0] 부터 str[4] 까지 차례로 1,2,3,4,5 가 되며 코드 수행시 아래와 같이 출력 된다. 1 2 3 4 5 끝.


신고


Posted by injunech
2016.03.25 00:56


android TextView setTextSize 할 때, default 설정은 sp 이며
px로 입력하려면 아래와 같이 설정한다.

<?xml version="1.0" encoding="utf-8"?>
<resources>
    <dimen name="typo14">9sp</dimen>
</resources>


setTextSize(TypedValue.COMPLEX_UNIT_SP, 9);
setTextSize(TypedValue.COMPLEX_UNIT_PX, getResources().getDimensionPixelSize(R.dimen.typo14));
textview_msg.setTextSize(TypedValue.COMPLEX_UNIT_SP, 20);

출처:

http://stackoverflow.com/questions/6784353/inconsistency-when-setting-textview-font-size-in-code-and-in-resources

신고


Posted by injunech
2016.01.14 22:33


[Android] EditText 키보드 엔터(Enter)키 기능 변경


안드로이드에서 EditText에 텍스트를 입력할 때 소프트 키보드의 엔터키가 상황에 따라 다르게 나타나는 것을 종종 볼 수 있습니다. 예를 들어 아래의 그림처럼 인터넷 브라우져 주소창이면 '이동' 또는 '검색' 으로, 검색창이면 '검색'으로, 정보 입력창이면 '완료' 등을 볼 수 있죠. 이렇게 소프트 키보드의 엔터키를 상황에 맞게 바꿔주는 방법에 대해서 알아보도록 하겠습니다.





엔터키를 변경하기 위해서는 우선 EditText가 존재하는 xml에서 imeOptions와 inputType 어트리뷰트를 설정해줍니다. 예시는 엔터키를 '검색'으로 바꾼 예입니다.


xml 코드 예시


<EditText

...

android:imeOptions="actionSearch"

android:inputType="text"

/>


Java 코드 예시


editText.setImeOptions(EditorInfo.IME_ACTION_SEARCH);

editText.setInputType(InputType.TYPE_CLASS_TEXT);


imeOptions 에 적용될 수 있는 어트리뷰트는 다음과 같습니다.


xml 코드


android:imeOptions="normal"     // 특별한 의미 없음

android:imeOptions="actionUnspecified"     // 특별한 의미 없음

android:imeOptions="actionNone"     // 특별한 의미 없음

android:imeOptions="actionGo"     // '이동'의 의미 (예 : 웹 브라우져에서 사용)

android:imeOptions="actionSearch"     // '검색'의 의미 (예 : 네이버 검색창)

android:imeOptions="actionSend"     // '보내기'의 의미 (예 : 메세지 작성시 사용)

android:imeOptions="actionNext"     // '다음'의 의미 (예 : 회원가입시 다음 필드로 이동시)

android:imeOptions="actionDone"     // '완료'의 의미 (예 : 정보 입력창)

android:imeOptions="actionPrevious"     // '이전'의 의미 (예 : 회원가입시 이전 필드로 이동시) - API11부터 가능


Java 코드


EditorInfo.IME_ACTION_NONE    // 특별한 의미 없음

EditorInfo.IME_ACTION_UNSPECIFIED    // 특별한 의미 없음

EditorInfo.IME_ACTION_GO     // '이동'의 의미 (예 : 웹 브라우져에서 사용)

EditorInfo.IME_ACTION_SEARCH     // '검색'의 의미 (예 : 네이버 검색창)

EditorInfo.IME_ACTION_SEND     // '보내기'의 의미 (예 : 메세지 작성시 사용)

EditorInfo.IME_ACTION_NEXT     // '다음'의 의미 (예 : 회원가입시 다음 필드로 이동시)

EditorInfo.IME_ACTION_DONE     // '완료'의 의미 (예 : 정보 입력창)

EditorInfo.IME_ACTION_PREVIOUS     // '이전'의 의미 (예 : 회원가입시 이전 필드로 이동시) - API11부터 가능


위와 같이 작성해주고 Java 코드 에서 EditText에 OnEditorActionListener 인터페이스를 연결해줘야합니다.


editText.setOnEditorActionListener(new OnEditorActionListener() { 

@Override

public boolean onEditorAction(TextView v, int actionId, KeyEvent event) {

switch (actionId) {

case EditorInfo.IME_ACTION_SEARCH:

Toast.makeText(getApplicationContext(), "검색", Toast.LENGTH_LONG).show();

break;

default:

Toast.makeText(getApplicationContext(), "기본", Toast.LENGTH_LONG).show();

return false;

}

return true;

}

});


여기까지 다 완료 해주면 소프트 키보드의 엔터키가 검색으로 바뀌고 클릭 되었을 때 이벤트를 받아 올 수 있습니다.





신고


Posted by injunech
2015.12.12 10:03


간단한 큐(Queue)의 구현


순환 큐가 가장 좋은 것으로 알고 있지만 

빠른 알고리즘의 구현을 할 경우에는 전체 큐의 범위를 넉넉하게 잡고 아래와 같은 방식으로 구현하였다.

큐는 BFS 알고리즘을 쓸때 주로 이용된다.


여기서 사용된 Front 와 Rear 의 용도는 다음과 같다.

값의 존재 기준으로 보면
Front 는 값이 존재하는 제일 앞에서 index 값이 -1 만큼인 값
Rear 는 값이 존재하는 제일 마지막에서 index 값이 +1 만큼인 값

값을 넣어야 하는 기준으로 보면
값을 꺼낼 때 Front 의 현재 index 에서 +1의 위치 값을 꺼내온다.
값을 넣을 때 Rear 의 index 위치에 값을 넣는다.

Queue에 Push 할때는 Rear 가 가리키는 Index 에 넣고 Rear 의 값을 +1 한다.
Queue에 있는 값을 Pop으로 꺼낼때는 Front 의 +1한 다음 Index 값이 Rear 와 같은 경우 Null 을 알려주고 그렇지 않은 경우 Front 값을 +1 하고 해당 위치에 값을 Return 한다.


#include <stdio.h>

#define SIZE 100

struct vertex{
	int x;
	int y;
}typedef vertext;

vertext queue[SIZE];
int front=-1;
int rear=0;

void push_rear(vertext a){
	queue[rear++] = a;
}

vertext pop_rear(){
	if (rear == front+1){
		// QUEUE NULL
		printf("QUEUE is NULL\n");
	}
	else{
		return queue[++front];
	}
}

void printQueue(){
	int i=front+1;
	printf("QUEUE : ");
	if (i < rear){
		do{
			printf("(%d, %d) ", queue[i].x, queue[i].y);
			i++;
		} while (i< rear);
	}
	printf("\n");

}

int main(){
	int i=0;
	int T=0;
	vertext value;
	int b,c,d,e,f,g;

	int a[10];
	
	while (1){
		printf("----------------\n");
		printf("1. Push 2.Pop\n");
		scanf("%d", &T);

		if (T == 1){
			scanf("%d %d", &value.x, &value.y);
			printf("%d %d", value.x, value.y);
			push_rear(value);

		}
		else if (T == 2){
			pop_rear();
		}

		printf("----------------\n");
		printQueue();
	}

	return 0;
}
 



신고


Posted by injunech
2015.12.06 19:23


Syntax Highlighter이 뭐냐면... 그냥 소스코드 예쁘게 뿌려주는거다. 이 글에서도 자주 쓰이니 알아서 판단하시고.

일단 티스토리는 Syntax Highlighter를 제공하지 않는다. 플러그인을 마음대로 설치할 수도 없으니 물건너간 줄 알았으나...
찾아보니까 된다 카더라 'ㅅ' 그러니까 스킨 뜯어고치면 된다.

소스 홈페이지 : http://alexgorbatchev.com/SyntaxHighlighter/ (오픈소스로 공개중이다. 감사하도록.)



1. 설치방법

설정 - 스킨 - HTML/CSS 편집 들어간 후, </body>와 </html> 사이에 다음 내용을 추가해 준다.


<link rel='stylesheet' type='text/css' href='http://alexgorbatchev.com/pub/sh/current/styles/shCore.css' />
<link rel='stylesheet' type='text/css' href='http://alexgorbatchev.com/pub/sh/current/styles/shThemeDefault.css' />
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shCore.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushXml.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushCpp.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushPhp.js' type='text/javascript'></script>
<script type="text/javascript">
SyntaxHighlighter.all();
</script>


2. 사용방법

우선 편집기에서 소스를 쭉 작성한다. < 를 &lt; 로 작성해야 하는데, 이건 티스토리 편집기에서 자동으로 치환해 준다.
그리고 HTML 모드에서 위아래를 <pre> - </pre> 태그로 묶어주는데, 코드 종류에 따라 태그 클래스를 미묘하게 바꿔줘야 한다.


CPP 코드 : <pre class="brush: cpp"> - </pre>
HTML : <pre class="brush: html"> - </pre>
PHP : <pre class="brush: php"> - </pre>



정확하게는 위에서 추가해 준 브러시 타입만 사용할 수 있다. 저 위 소스 잘 보면 shBrush___.js 를 삽입하는걸 볼 수 있는데 이 부분.
다른쪽(Ruby라거나...) 쓰는 블로그라면 알아서 홈페이지 뒤져서 바꿔주면 되겠다.
(설마 코드 다루는 블로그 주인장이 저 정도 응용력도 없진 않겠지...)


파이어폭스 사용시, 코드 뒤에 <br /> 붙는건 지워줘야 한다. 아니면 아래처럼 소스에 한 줄 추가해주면 알아서 삭제하고 파싱해 준다.

<script type="text/javascript">
SyntaxHighlighter.config.stripBrs = true;
SyntaxHighlighter.all();
</script>


3. Include 부분은 아래와 같이 입력 해준다.

#include &lt;stdio.h&gt;



끝!

신고

'Programming > HTML,PHP,Javascript' 카테고리의 다른 글

티스토리 Syntax Highlighter 설치  (0) 2015.12.06


Posted by injunech
2015.12.06 19:16


[BackTracking] 체스 여왕말 놓기 (N-Queen Problem)



되추적(Backtracking) 방법을 얘기 할 때 가장 많이 거론 되는 듯한 N-여왕말(N-Queen) 문제이다. 어떤 문제인가하면 서양 장기(Chess:이후 체스)의 여왕말(Queen:이후 퀸)을 서로가 서로의 이동경로가 아닌 위치에 있도록 최대한 많은 퀸을 체스판 위에 놓는 문제이다.


 원래 체스판은 8ⅹ8이지만 간단히 4ⅹ4일 경우에 좌측의 결과와 같이 되는 경우를 찾는 것이 바로 N-Queen 문제 이다.

 4ⅹ4일 경우에는 좌측과 같은 2가지의 경우만 나오지만 체스판이 커지면 커질수록 다양한 경우의 수가 나온다. 우선 정해진 것은 NⅹN의 체스판에 올라갈 수 있는 퀸의 최대 갯수는 언제나 N이 된다는 점이다.


 그렇다면 어째서 이것이 되추적(Backtracking) 방법이 되느냐 하는 것은

① 첫번째 퀸이 (1, 1) 위치에 오게 될 경우

② 두번째 퀸은 (2, 3) 과 (2, 4) 위치에 올 수 있다. 우선 (2, 3) 위치에 퀸을 놓는다면

③ 세번째 퀸을 놓을 수 있는 자리는 없어진다. 그러면 다시 ②로 돌아가서 두번째 퀸을 (2, 4) 위치에 놓게 되면

④ 세번째 퀸을 (3, 2) 위치에 놓을 수 있지만 이렇게 되면 네번째 퀸을 놓을 수가 없어진다. 그렇게 되면 이번엔 다시 ①로 돌아가서 첫번째 퀸을 (1, 2)에 놓고 다시 시작한다.


 위의 과정과 같이 결과값을 찾아가다가 그 방법이 아니라는 것을 알았을 때 이전 단계로 돌아가는 것이 바로 되추적 방법이다.


 N-Queen의 문제의 경우 참고 자료에 있는 책을 본다면 좀 더 쉽게 알 수 있을 것이다. 언제나와 같이 나는 참고자료에 있는 'Foundations of Algorithms.....' 책을 참고로 해서 프로그램을 작성하였다.

 N값을 입력 받아서 결과를 보여주는 N-여왕말 문제 알고리즘


참고자료 

알고리즘(Foundatations of Algorithms Using C++ Pseudocode) - Neapolitan, Naimipour 저 / 도경구 역

누워서 읽는 알고리즘 - 임백준 저



#include <stdio.h>
#include <malloc.h>
#include <math.h>

void queens(int i, int n, int col[]);   // n개 여왕말 알고리즘
void printqueen(int n, int col[]);      // n개 여왕말의 위치 출력
int promising(int i, int col[]);    // 유망한지 검사하는 함수

int main()
{
	int i;
	int n;
	int* col;

	printf("How many Columns or Rows?\n> ");
	scanf("%d", &n);
	getchar();

	// 여왕말이 해당행의 몇번째 열에 있는지 저장
	col = (int*)malloc(sizeof(int)*n);

	// 뿌리 노드(0)부터 탐색을 시작
	queens(0, n, col);

	free(col);

	return 0;
}

void queens(int i, int n, int col[])
{
	int j;

	if (promising(i, col)) // 유망한가?
	if (i == n) // n개의 여왕말 위치를 찾았나?
		printqueen(n, col); // 여왕말 위치 출력
	else
	for (j = 1; j <= n; j++) {    // (i+1)번째 행에 있는 여왕말을
		col[i + 1] = j;           // n개의 열에 놓을 수 있는지 각각
		queens(i + 1, n, col);    // 검사한다.
	}
}

void printqueen(int n, int col[])   // 보기 편하게 결과값을 출력
{
	int j, k;
	printf("    |");           // 상단 열의 갯수 출력 부분
	for (j = 1; j <= n; j++)
		printf("%3d |", j);
	printf("\n");

	for (j = 0; j <= n; j++)    // 행을 나누는 선 출력
		printf("----+");
	printf("\n");

	for (j = 1; j <= n; j++) {
		printf("%3d |", j);   // 행의 번호
		for (k = 1; k < col[j]; k++) {
			if (((k + j) % 2))
				printf("▩▩|");    // 여왕말이 없는 칸
			else
				printf("    |");    // 여왕말이 없는 칸
		}
		printf("QUEE|");      // 여왕말
		for (k = col[j]; k < n; k++){
			if (!((k + j) % 2))
				printf("▩▩|");    // 여왕말이 없는 칸
			else
				printf("    |");    // 여왕말이 없는 칸
		}
		printf("\n");

		for (k = 0; k <= n; k++)   // 행을 나누는 선 출력
			printf("----+");
		printf("\n");
	}
	printf("\n");

	printf("Press ENTER to continue");
	getchar();  // 결과 값이 많으므로 하나의 결과값마다 멈추도록
}

int promising(int i, int col[]) // 유망한지 판단하는 함수
{
	int k;
	int bSwitch;

	k = 1;
	bSwitch = 1;
	while (k < i && bSwitch) {
		/* col[i] == col[k] 는 같은 열에 있는지 판별한다
		* abs(col[i] - col[k]) == i - k의 경우는
		* 2개의 여왕말간의  행의 차와 열의 차의 절대값이 같으면
		* 같은 대각선상에 있다는 의미이다. */
		if (col[i] == col[k] || abs(col[i] - col[k]) == i - k)
			bSwitch = 0;
		k++;
	}
	return bSwitch;
}



출처 : http://egloos.zum.com/sakuragis/v/3468837 

신고


Posted by injunech