침대 밖은 위험해!

인터페이스나 스탯 스킬에 대해 알고 싶다면

참조 : 2017/12/22 - [일상다반사/게임] - [Exiled Kingdoms] 초반 공략 - 시작하면서

1. 시작 마을로 가기 전에

1) 시작과 함께 인터페이스에 대한 설명이 끝나면 'Adaon' 이라는 희대의 양아치 NPC를 만나게 됩니다.

   (나중에 대화 잘하면 반성하고 영원한 노예로 만들 수 있습니다.)

   (용병이 있는데 사실 어떻게 나눠야 할지 모르지만 돈주고 사는 용병과 NPC용병이 있습니다.

    돈주고 산 용병은 일회용입니다. 죽으면 ㅂ2

    NPC 용병은 플레이 하면서 3명 만났습니다.(각 직업별로) 죽어도 조금있으면 다시 되살아 나며 스킬도 쓰기 때문에 영원한 노예입니다.

    NPC 용병을 데리고 다니다가 나중에 다른 직업의 용병으로 바꿀 수도 있습니다.)

- 말걸기 싫지만 말을 걸어 봅니다.

- 이새퀴가 벌써부터 수작질을 부립니다. 별로 멀지도 않은 거리를 자꾸 자고 가자고 합니다.

  뭘 선택해도 자야합니다.

- 자고 일어나면 이렇게 빈 털털이가 됩니다.....

2. 시작마을, Lannegar(City)

- Lannegar Valley 맵에서 시작하고 첫 마을은 Lannegar 입니다.

1) 받을 수 있는 퀘스트 목록 및 설명

http://www.exiledkingdoms.com/wiki/index.php?title=Lannegar_(City)

ㄱ) 마을 내에서 받을 수 있는 퀘스트

- Goblin Hunt : 고블린 5마리 사냥

- Head Hunting : 고블린 왕 모가지 따기

- Gather ingredients : 꽃 모으기

- The Lost Explorer : 사라진 탐험가

- Flesh is Weak : 좀비가죽 3개 모으기

- The seed of trust : 보디가드

- Where is Giles : 이건 지금 받지도 못함....

ㄴ) 맵에서 받을 수 있는 퀘스트

- Forgatten Lore : 잃어버린 보물? 찾기

  (연계 퀘스트로 이거 깨면서 얻는 아이템들이 짭짤함)

2) 추천 퀘스트 순서 및 퀘스트 획득, 클리어 방법

ㄱ) Goblin Hunt

- 우선 마을입구의 'Captain Whitewater' 에게 가서 일자리를 달라고 떼쓰면 고블린 잡아오라고 합니다.

- 근처에서 고블린을 잡고 다시 가면 25골드와 hp 포션 하나를 받습니다.

- 퀘스트를 클리어 하면 다른 퀘스트(The Lost Explorer)를 받습니다.

- 받은 퀘스트는 상태창에서 'Journal' 에 보면 나옵니다.

ㄴ) The Lost Explorer

- The Lost Explorer 퀘스트를 보면 Lannegar의 서쪽 광산이 있답니다. 맵에서 보면 우측 그림처럼 왼쪽 위에 있는 던전입니다.

- 왼쪽 맵에서 좌측 중앙에 있는 방에 가면 오른쪽 그림처럼 감옥이 있습니다. 'Teram'에게 말을 걸면 열쇠는 모르겠고 레버가 있다고 합니다.

  레버는 왼쪽 맵에서 빨간색으로 표시된 곳에 있습니다. 당겨주고 다시 'Teram'에게 가서 따라오라고 하고 마을로 복귀하면 보상을 받습니다.

- 지금 굳이 맵을 다 돌지 않아도 조금만 있으면 지겹도록 돌테니 괜히 돌다가 임프한테 맞아 죽어서 저장 전으로 돌아가는 불상사가 발생하지 않았으면 좋겠습니다.

- 왼쪽은 레버 사진, 오른쪽은 레버를 당기고 다시 왔을 때 사진

- 'Teram'을 데려다 주고 'Captain' 에게 보상을 받으면서 처음에 물어봤던 도둑놈(Adaon)은 어디갔냐고 물어보니 킹스브릿지를 거쳐 뉴그랜드로 간다고 들었답니다.... 나중에 쫒아가야지요

ㄷ) Gather ingredients

- 마을에서 우측 상단에 있는 할아버지(Alchemist Markus) 한테 말을 걸면 'Blue Orched' 라는 꽃을 가져 오랍니다.

- 이렇게 생긴 꽃입니다.

- 지도에 표시된 위치에 파란색 꽃이 있으니 하나 가져다 주면 됩니다.

- 'Blue Orchid'를 가져다 주면 'Red Orchid'를 요구합니다. 그 이후에는 버섯 가져다 달라고 하는데 이건 다음 퀘스트를 깨면서 중간중간 줍도록합니다.

다음편

2017/12/25 - [분류 전체보기] - [Exiled Kingdoms] 공략 - Lannegar Valley, Lannegar(City) 2

- The seed of trust : 보디가드

- Head Hunting : 고블린 왕 모가지 따기

전사랑 도적은 키워봐서 이번에 성직자 키우면서 공략 글을 남겨볼까 합니다.

영어이긴 한데 그렇게 높은 장벽은 아니지만 누구한테 어떤 퀘스트를 받고 그에 따른 보상이 갈리기 때문에 위키를 참조해야 합니다.

초반 공략을 시작으로 차차 시간나면 올리겠습니다.

앞으로 쓰는 영어는 직접적인 번역이라기 보다 한국에서 rpg를 즐길때 가장 많이 접하는 단어로 표현하겠습니다.

0. 난이도

- 여러개 해본결과 초보이거나 너무 어려운 난이도는 싫다 하시면 easy나 normal이 정신건강에 매우 좋습니다.

  normal도 쉽지 않습니다.

1. 캐릭터 생성

1) 직업

- 캐릭터 생성시 전사, 도적, 성직자 세가지 직업이 있습니다.

  스탯(Traits)을 보면 마법사도 있는데 아직 개발이 안된듯 합니다.

2) 스탯

- 생성시 스탯(Traits)과 스킬(Skills)를 찍을 수 있는데

  스탯은 0 -> 1 : 1개

           1 -> 2 : 2개 이런식으로 필요 스탯포인트가 가중됩니다.

  스킬은 스킬에 따라서 다릅니다.

  전사라면 END(기본 HP 5 + 레벨당 HP 1 을 추가해줍니다.)를 추천합니다.

  이 게임은 일단 맞다이가 제일 중요하기 때문에 체력과 방어력, 저항력이 높으면 좋습니다.

  (물론 STR 올려도 2포인트당 1 hp인가... 올라갈겁니다....)

  도적이라면 AGI를 추천합니다.(로그 무기에 딜이 가장많이 올라가기 때문에...)

  성직자라면 END와 PER을 섞어서 올려줍니다.

  일단 기본 마나가 되야 스킬 사용이 가능하니까요

  INT도 있는데 일단 마나 상승률만 따지면 성직자는 PER에서 더 많이 올려줍니다.

  (INT 찍으면 포인트당 2%의 xp를 더 얻을 수 있는데 나중에 5, 7% 올려주는 스크롤 먹고 돌면 됩니다.)

3) 스킬

- 일단 기본 스킬과 2차 스킬이 있습니다.

- 기본 스킬은 시작하자마자 올릴 수 있지만 2차 스킬은 나중에 퀘스트를 깨야만 열립니다.

  (돈주고 배워야 합니다... 다른 직업 스킬도 배울 수 있지만 그닥 추천하진 않습니다.)

- 전사, 도적은 기억이 안나므로 패스

- 성직자라면 heal 무조건 찍습니다.

  이 게임은 포션이 그지같이 비싸기 때문에 피가 간당간당 하면 마을에 무조건 와야합니다.

  성직자는 heal로 안전한 파밍이 가능하기에 초반에 아주 좋더군요

- 나머지는 취향껏 active와 passive를 나눠 찍습니다.

- 스킬 포인트는 웬만하면 조금씩 모아두세요. 나중에 2차 스킬 찍을 때 필요합니다.

  1렙 올리기가 그지같이 힘들어서 스탯, 스킬 포인트 얻기가 정말 힘듭니다.

2. 기본 인터페이스

- 늘 그렇듯 좌측 하단은 방향키 입니다.

- 우측 하단은 공격버튼 그 위로 스킬입니다.

- 가운데 하단은 좌측 부터 미니맵, 설정, 저장 입니다.

- 좌측 중앙에 '+' 버튼은 누르면 피와 마나가 풀로 채워지지만, 전투 중(때리거나 맞고있을 경우, 피해도 몬스터가 쫒아오는 상황이라면 전투 중)에는 안눌리니 신중히 써야 합니다. 다쓰면 마을가서 충전을.... 그래서 성직자는 힐이 있어서 더 오래 파밍이 가능함.

- NPC나 물건, 박스 앞에 가면 우측 상단 처럼 누를 수 있는 화면이 나오는데 누르면 됩니다.

3. 최적화 문제

- 경우의 수 문제와 같이 답이 여러개인 문제에서 '어떤 기준'에 따라 '좋은' 답을 찾는 문제를 '최적화 문제(Optimization Problem)'

※ 최적화 문제를 해결하는 방법

- 완전 탐색

- 동적 계획법

- 조합 탐색

- 결정 문제로 치환

=> 완전 탐색은 최적화 문제를 풀기 위한 가장 직관적인 방법

예제. 문제 : CLOCKSYNC

https://algospot.com/judge/problem/read/CLOCKSYNC

1) 문제를 읽고 이해하기

- 시간 제한 10ms / 메모리 제한 2^16kb

- 테스트 케이스의 개수 <= 30

2) 문제 재정의

- 16개의 시계, 3, 6, 9 12 만 가리킬 수 있음

- 10개의 스위치로 시간 조작 가능

- 각각의 스위치는 3~5개의 시계와 연결되어 있어서 해당 스위치를 누르면 연결된 시계들이 +3 씩 움직임

- 모두 12시를 가리키기 위해 눌러야 할 최소 스위치의 횟수

- 불가능할 경우 -1 출력

3) 계획 세우기

계획1.

- 최소 스위치 횟수 이기에 bfs를 고민함.

- 스위치를 몇 번 눌러야 할지 정해지지 않았기에 모든 상태를 저장하고 하나의 상태를 방문할 때 마다 저장된 상태와 비교하려고 함.

- 시계 하나는 3, 6, 9, 12 4가지 상태를 나타낼 수 있으므로 2bit로 표현 가능.

  16개의 시계 이므로 32bit 즉, int 하나로 16개 시계의 한 가지 상태를 저장 할 수 있음

  하지만, 메모리가 너무 크고 시간 예측이 안됨.

  큐 0회 : 4byte

  큐 1회 : 0 ~ 9번 버튼을 각각 눌렀을 때 10가지의 상태 : 40byte

  큐 2회 : 큐 1회에서 각각 10가지 경우가 또 발생 하므로 : 400byte

  큐 3회 : 4,000byte

  ... 큐 1회를 돌 때마다 10배가 늘어나므로 65,536,000 byte < 4 * 10^N => N이 8이면 메모리 초과

계획2.

- 시계가 3, 6, 9, 12로 회전 하므로 하나의 시계가 4회 이상 돌아갈 필요가 없음.

- '0번 버튼 -> 1번 버튼' 이나 '1번 버튼 -> 0번 버튼' 이나 결과는 똑같음

   012012나 001122는 결과가 같음

- 즉, 각각의 버튼은 0 ~ 3회만 누르면 되고 순서에 상관없음.

- 버튼을 누르는 횟수의 경우의 수는 4, 총 버튼의 개수가 10이므로 모든 경우의 수는 4^10

4) 계획 검증하기

- '계획1'은 이미 메모리 초과

- '계획2'는 4^10 == 2^20 ≒ 1억번

5, 6) 계획 수행하기 및 회고하기

- 문제 풀이 원리 : 다시 되돌아 오는 특징과 버튼의 순서가 중요하지 않다는 점이 버튼을 누르는 횟수를 제한 시킴

- 사실 아직도 4번 이상 누를 필요가 없는지에 대해서는 확신이 없음

- 나중에 내가 다시 풀 수 있을까?

- 비슷한 문제를 찾아봐야 겠음. 전구인가 색칠하기 인가 한칸 누르면 인접 4칸 색이 바뀌는 문제가 있었던거 같은데

- 구현 시 배열이라면 길이를 확인 또 확인....

- "Run-Time Check Failure#2 - Stack around the variable was corrupted" 에러는 포인터로 지역변수를 넘겼을 때 실제로 선언된 사이즈를 넘어선 인덱스로 입력을 시도할 때 발생함.

소스코드

#include<iostream>
using namespace std;

#define INF 987654321

int b[10][5] = { { 0, 1, 2, 16, 16 },   // 0
				 { 3, 7, 9, 11, 16 },   // 1
				 { 4, 10, 14, 15, 16 }, // 2
				 { 0, 4, 5, 6, 7 },     // 3
				 { 6, 7, 8, 10, 12 },   // 4
			 	 { 0, 2, 14, 15, 16 },  // 5
				 { 3, 14, 15, 16, 16 }, // 6
				 { 4, 5, 7, 14, 15 },   // 7
				 { 1, 2, 3, 4, 5 },     // 8
				 { 3, 4, 5, 9, 13 } };  // 9
int ans;

void dfs(int *clock, int button, int cnt){	
	int i = 0;
	for (; i < 16; i++)
		if (clock[i] != 0)
			break;
	// 아 이거..... 15가 아니라 16이었군
	if (i == 16){
		ans = ans < cnt ? ans : cnt;
		return;
	}
	if (button == 10)
		return;

	for (int j = 0; j < 4; j++){
		dfs(clock, button + 1, cnt + j);
		// 4번 돌리니까 dfs를 호출 하기 전의 시계 상태로 돌아감
		// 4번 회전하면 호출 하기 전의 시계상태로 돌아가므로 이전 상태를 따로 저장할 필요가 없음
		for (int k = 0; k < 5; k++)
			if (b[button][k] < 16)
				clock[b[button][k]] = (clock[b[button][k]] + 3) % 12;
	}

	return;
}

int main(void){
	ios::sync_with_stdio(false);
	freopen("Text.txt", "r", stdin);
	int T;
	cin >> T;
	while (T--){
		// clock를 15로 선언함....이거때문에 "Run-Time Check Failure#2 - Stack around the variable was corrupted" 떠서 당황했네
		int clock[16];
		ans = INF;
		for (int i = 0; i < 16; i++){
			cin >> clock[i];
			clock[i] %= 12;
		}
		dfs(clock, 0, 0);
		cout << ((ans == INF) ? -1 : ans) << "\n";
	}
	return 0;
}

4. 많이 등장하는 완전 탐색 유형

1) 모든 순열 만들기

- 가능한 모든 경우 : N!

- 실제로 만드는 방법은 다른 블로그 많으니 참고

- C++ 은 next_permutation(), prev_permutation()이 있음

2) 모든 조합 만들기

- 재귀

- nCr => 1개를 뽑고 n-1Cr-1을 재귀

- 코드 6.2 참고

3) 2^n가지 경우 만들기

- 'Yes / No' 의 경우 => 재귀 2^N

- Bit Mask를 이용하면 for문 하나로 모든 경우를 다 돌 수 있음

- 알고리즘 문제 해결전략 1편 중 -

- 저작권 문제시 삭제하겠습니다 -

뜬금없이 궁금한 점이긴 한데

논리회로 공부를 하다가 보면 NAND gate를 배우기 마련

그럼 SSD에 들어가는 NAND Flash Memory에 NAND gate소자가 들어가서 NAND라는 이름이 붙은 걸까?

이유는 NAND flash memory 셀 어레이 회로 구조가 nMOS NAND gate의 회로 구조와 동일 하기 때문입니다.

                               <fig 1>                                                                         <fig 2>

위 그림에서 <fig1>의 왼쪽 그림이 NAND flash memory의 셀 구조 입니다. 

<fig1>에 나온 memory의 일부를 '스트링'이라고 하는데 NAND는 스트링이 Bit Line과 Source Line을 공유하는 구조 입니다.

<fig2>는 nMOS NAND gate의 회로 인데 NAND flash memory 스트링의 회로와 같이 소스와 드레인을 공유하고 있습니다.

이때문에 <fig1>의 어레이를 구조 하고 있는 flash memory를 NAND flash memory 라고 부르게 되었습니다.

부족하거나 틀린점은 피드백 바랍니다.

출처

fig1 : https://www.omicsonline.org/open-access/nand-flash-memory-organization-and-operations-2165-7866-1000139.php?aid=46500

fig2 : https://upload.wikimedia.org/wikipedia/commons/4/49/NMOS_NAND.svg

참고자료

- NAND flash memory

https://gigglehd.com/zbxe/5791789

http://gamma0burst.tistory.com/593

https://www.omicsonline.org/open-access/nand-flash-memory-organization-and-operations-2165-7866-1000139.php?aid=46500

- NAND vs NOR

https://gigglehd.com/zbxe/5709833

http://slidesplayer.org/slide/11162137/

- NAND gate

https://ko.wikipedia.org/wiki/NAND_%EA%B2%8C%EC%9D%B4%ED%8A%B8

- NOR gate

https://ko.wikipedia.org/wiki/NOR_%EA%B2%8C%EC%9D%B4%ED%8A%B8

문제출처 : https://www.acmicpc.net/problem/7568

1. 문제요약

- n명 몸무게, 키가 주어짐

- 1번 몸무게 > 2번 몸무게 && 1번 키 > 2번 키 이면 1번이 2번 보다 덩치가 크다

- 나의 덩치 순위는 나보다 덩치큰 사람 + 1

- 2 ≤ n ≤ 50, 10 ≤ 몸무게, 키 ≤ 200

2. 접근방법

- 브루트 포스

- 한명을 기준으로 나머지(n-1)명의 덩치를 비교

3. 시간복잡도

- 한명을 기준으로 나머지(n-1)명의 덩치를 비교 : n-1

- 총 n명 이므로 : n * (n - 1) ≒ 2500

4. 회고

- 할게 없음

소스코드

#include<iostream>
using namespace std;

int n, h[51][2];

int main(void){
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> h[i][0] >> h[i][1];

	for (int i = 0; i < n; i++){
		int cnt = 1;
		for (int j = 0; j < n; j++){
// i == j인 경우는 몸무게와 키가 같기 때문에 등수에 영향이 없음
			if (h[i][0] < h[j][0] && h[i][1] < h[j][1])
				cnt++;
		}
		cout << cnt << " ";
	}
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

문제출처 : https://www.acmicpc.net/problem/6603

1. 문제요약

- 원소 K개로 이루어진 집합 S (6 ≤ K ≤ 13)

- 집합 S에서 6개를 뽑는 경우의 수? (1 ≤ 원소 ≤ 49)

- 입력은 여러개 0 입력시 종료

- 사전 순 출력

2. 접근방법

- 조합 : 13C6

3. 시간복잡도

- 조합 : 1716

4. 회고

- 경우의 수 여서 브루트 포스

- 조합은 재귀나 다중 for문으로만 구현할 수 밖에 없나

소스코드 조합

#include<iostream>
using namespace std;

int K, S[14], P[6];

void dfs(int index, int in, int size){
	if (size == 6){
		for (int i = 0; i < 6; i++)
			cout << P[i] << " ";
		cout << "\n";
		return;
	}

	for (int i = index; i < K; i++){
		P[in] = S[i];
		dfs(i + 1, in + 1, size + 1);
	}
}

int main(void){
	freopen("Text.txt", "r", stdin);
	while ((cin >> K) && K != 0){
		for (int i = 0; i < K; i++)
			cin >> S[i];
		dfs(0, 0, 0);
		cout << "\n";
	}
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

예제. 문제 : BOARDCOVER

https://algospot.com/judge/problem/read/BOARDCOVER

1) 문제를 읽고 이해하기

- 시간제한 2ms / 메모리제한 2^16kb

- 1 <= h, w <= 20 / 흰칸의 수 <= 50

2) 문제 재정의

- 게임판의 흰칸( . )을 'ㄱ' 모양을 회전시킨 모양으로 전부 덮을 수 있는 경우의 수

3) 계획 세우기

- 경우의 수 문제이기에 일단 다해보는 '브루트 포스'

  : 블럭을 채워야 할 칸을 선택 후 적절한 블럭을 채움

  : 아직 채우지 않은 칸을 대상으로 위 과정을 반복함

  => '한 블럭'과 '나머지 칸'으로 문제를 분할 => 재귀

- 한 지점에서 시작하여 채우는 모양의 경우의 수가 16개

  최대 칸의 개수가 400개 이므로 중복되는 경우를 줄일 필요가 있음

- 재귀 호출 시 마다 젤 왼쪽 윗칸을 채우도록 순서를 강제함

  그럼 어떤 칸을 채우려고 할 때, 그 칸보다 왼쪽 윗칸은 다 차있다고 가정할 수 있음

            <fig 1>                                          <fig 2>                                           <fig 3>                                          <fig 4>

- 위 그림처럼 현재칸( * )을 채우는 경우의 수는 4가지

4) 계획 검증하기

- 시간복잡도 : 한 칸에서 선택할 수 있는 블럭 모양이 4가지 이므로

                   4 ^ 16(흰칸의 개수가 최대 50개라고 했으니 3개짜리 블럭은 최대 16개를 넣을 수 있음)

                   ≒ 4000 억

                   하지만, 재귀가 4000억을 다 돌지 않음. 그 이유는 한개의 블럭이 결정 되면 다음에 결정될 블럭의 경우의 수는 줄어듬

ex) 2*3 모두 하얀칸인 경우 

    <fig 1>을 선택하면 재귀 1 --- 경우의 수 0

    <fig 2>를 선택하면 재귀 2 --- 경우의 수 1

    <fig 3>을 선택하면 재귀 2 --- 경우의 수 1

    <fig 4>를 선택하면 재귀 0 --- 경우의 수 0

    즉, 실제로 재귀 5번 --- 모든 칸을 채울수 있는 경우의 수는 2

        2개의 블럭을 놓는 이론적인 경우의 수는 4^2 = 16가지

        2개의 블럭을 놓는 경우의 수에서 재귀가 도는 횟수가 많이 줄어듬

※ 실제로는 12칸일 경우 재귀는 23번

                 48칸일 경우 재귀는 68655번

※ 줄어드는건 알 수 있지만 그래도 어떻게 저 경우의 수가 시간 내에 들어오리라는 확신을 할 수가 있을까?

   확신을 해야만 브루트 포스로 풀텐데

- 공간복잡도 : global variable : int * 2 + int * 12 * 2 = 104byte

                   local variable : int * 400 = 1600byte(int나, bool 변수들은 무시)

                   즉, 1804byte < 2^16kb

5, 6) 계획 수행하기 및 회고하기

- 솔직히 아직도 재귀가 시간내에 들어오리란 확신을 가지지 못하겠음...

- 4가지 경우의 수를 줄일 때 처음에 '중심'을 가지고 줄였음

  하지만, 다음 중심을 찾기가 너무 어렵고, 중심이 들어가지 않는 경우가 발생한다면 그 부분에서 계속 무한루프를 돌게됨

  알고스팟 예제에서 첫 번째 흰칸을 중심이 들어갈 경우로 판단한다면 아무것도 넣을 수가 없음. 만약 건너뛰게 한다 하더라도

  다음번 시작점을 찾을 때도 (0, 0) 에서 시작하기에 저 부분을 계속 거치게 됨

  그래서 왼쪽 위를 무조건 채운다는 강제를 부여하게 되면 위 그림과 같은 4가지 경우가 생김

소스코드

#include<iostream>
using namespace std;

int h, w;
int dr[4][3] = { { 1, 0, 0 }, { 1, 1, 0 }, { 0, 1, 1 }, { 0, 0, 1 } };
int dc[4][3] = { { 0, 0, 1 }, { -1, 0, 0 }, { 0, 0, 1 }, { 0, 1, 1 } };

int dfs(char(*map)[21]){
	// 블럭을 채울 공간을 찾음
	int row, col, ret = 0;
	bool isWhiteBlock = false;

	for (int i = 0; i < h; i++){
		for (int j = 0; j < w; j++){
			if (map[i][j] == '.'){
				row = i; col = j;
				isWhiteBlock = true;
				break;
			}
		}

		if (isWhiteBlock)
			break;
	}

	// 하나의 경우의 수를 찾음
	if (!isWhiteBlock)
		return 1;

	// 4개의 경우를 찾음
	int i = 0;
	for (; i < 4; i++){
		bool isCover = true;
		for (int j = 0; j < 3; j++){
			int nrow = row + dr[i][j];
			int ncol = col + dc[i][j];

			if (nrow < 0 || nrow >= h || ncol < 0 || ncol >= w || map[nrow][ncol] != '.'){
				isCover = false;
				break;
			}
		}

		if (isCover){
			cnt += 1;
			map[row + dr[i][0]][col + dc[i][0]] = '#';
			map[row + dr[i][1]][col + dc[i][1]] = '#';
			map[row + dr[i][2]][col + dc[i][2]] = '#';
			ret += dfs(map);
			map[row + dr[i][0]][col + dc[i][0]] = '.';
			map[row + dr[i][1]][col + dc[i][1]] = '.';
			map[row + dr[i][2]][col + dc[i][2]] = '.';
		}
	}

	return ret;
}

int main(void){
	freopen("Text.txt", "r", stdin);
	int T;
	cin >> T;
	while (T--){
		cnt = 0;
		cin >> h >> w;
		char map[21][21];
		int white_block = 0;
		for (int i = 0; i < h; i++){
			for (int j = 0; j < w; j++){
				cin >> map[i][j];
				if (map[i][j] == '.') white_block++;
			}
		}

		if (white_block == 0)
			cout << '1' << "\n";
		else if (white_block % 3 == 0){
			cout << dfs(map) << "\n";
			cout << "cnt : " << cnt << "\n";
		}
		else
			cout << '0' << "\n";
	}
	return 0;
}

- 알고리즘 문제 해결전략 1편 중 -

- 저작권 문제시 삭제하겠습니다 -

문제출처 : https://www.acmicpc.net/problem/1182

1. 문제요약

- 집합, N개의 원소, 부분집합의 합이 S를 만족시키는 경우의 수

- N < 20, lSl < 1,000,000, l원소l < 100,000

- 공집합은 제외

2. 접근방법

- 부분집합의 개수는 2^N = 2^20 ≒ 1억번 ≒ 1초

- 모든 부분집합의 합을 다 구해보면 된다.

3. 시간복잡도

- 재귀 : 2^N => 테스트 결과 4ms

- Bit Mask : 2^N * N => 테스트 결과 52ms

4. 회고

- 재귀로 구현했을 때

  : 공집합인지 확인하는 과정이 필요함. S의 값이 0인 경우 공집합의 합은 0 이므로

  : 처음에는 선택한 원소의 개수도 재귀로 넘겼는데 S가 0이 아닌 경우는 공집합을 포함해도 경우의 수에 포함 되지 않으므로 

   마지막에 계산할 때, S가 0인 경우 1가지 경우의 수를 빼주면 됨.

- Bit Mask로 구현했을 때

  : 좀 더 구현에 연습이 필요함

재귀 소스코드

#include<iostream>
using namespace std;

int n, s, cnt = 0;
int v[21];

void dfs(int pos, int sum){
	if (pos == n){
		if(sum == s)
			cnt++;
		return;
	}
	dfs(pos + 1, sum + v[pos]);
	dfs(pos + 1, sum);
	return;
}

int main(void){
	cin >> n >> s;
	for (int i = 0; i < n; i++)
		cin >> v[i];
	dfs(0, 0);
    if(s == 0) cnt--;
	cout << cnt << "\n";
	return 0;
}

Bit Mask 소스코드

#include<iostream>
using namespace std;

int n, s, ans;
int v[21];

int main(void){
	freopen("Text.txt", "r", stdin);
	cin >> n >> s;
	for (int i = 0; i < n; i++)
		cin >> v[i];

	// 공집합을 제외한 모든 부분집합(000...001 ~ 111...111)
	for (int i = 1; i < (1 << n); i++){
		int sum = 0;
		// 하나의 부분집합에서 각 원소가 부분집합에 속하는지 확인
		for (int j = 0; j < n; j++)
			if ((1 << j) & i)
				sum += v[j];

		if (sum == s)
			ans++;
	}
	cout << ans << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

문제출처 : https://www.acmicpc.net/problem/2309

1. 문제요약

- 9명의 난쟁이 중 키의 합이 100이 되는 7명의 난쟁이를 뽑아 오름차순으로 출력

2. 접근방법

- 단순하게 9명 중 7명을 뽑아서 키의 합이 100이 되면 출력 후 종료 => 조합 9C7

- 9C7 = 9C2 이므로 9명의 총 합에서 100을 제외한 값을 만족하는 2명만 뽑아서 나머지를 출력

3. 시간복잡도

- 9C7 재귀 구현의 경우 O(2^N) = 2^9

- 9C2 for 구현의 경우 O(NC2) = 9C2 => for를 계산해보면 8 + 7 + 6 + 5 + ... + 2 + 1 = 36

4. 회고

- 9C7을 재귀로 구현했을 때

  재귀에서 '정답인 경우'와 '정답이 아닌 경우'를 잘못 선정해서 무한루프에...

  base case를 잘 생각해보자

- 조합을 재귀 말고 쉽게 구현할 수 있는 방법이 있을까? 아직 지하 밑바닥에 있어서 좀 더 경험이 필요할 듯

- 9C2를 for로 구현했을 때 sort에서 a+10을 해버렸....왜 0이 나오나 했네

소스코드 : 9C2

#include<iostream>
#include<algorithm>
using namespace std;

int a[9];

int main(void){
	int sum = 0;
	for (int i = 0; i < 9; i++){
		cin >> a[i];
		sum += a[i];
	}

	for (int i = 0; i < 8; i++){
		for (int j = i + 1; j < 9; j++){
			if (a[i] + a[j] == sum - 100){
				a[i] = 1000;
				a[j] = 1000;
			}
		}
	}

	sort(a, a + 9);
	for (int i = 0; i < 7; i++)
		cout << a[i] << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

오늘도 여전히 줍줍

std::ios::sync_with_stdio(false)

cout << ... << "\n";

http://gooddaytocode.blogspot.kr/2016/07/cin-scanf.html

https://algospot.com/forum/read/2496/

https://www.acmicpc.net/board/view/20309