침대 밖은 위험해!

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

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

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

앞으로 쓰는 영어는 직접적인 번역이라기 보다 한국에서 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