MFC 미로 게임

Maze Generator

매번 만들어야지 생각만 하다가, 드디어 해봤다.
오랜만에 MFC를 잡아서인지 몇 시간 걸렸다.
이전에 선배 도와주면서 만들어본 "DFS와 BFS를 이용한 최단경로" 를 적용해서 [Find Path] 버튼을 추가할 예정.

역시 알고리즘은 이렇게 써먹으면 기분 좋음

한가지 재미있는 사실이라면, srand(time(NULL)) 같이 time함수를 잘 쓰지 않는 편이라 (온라인 저지 탓인ㄱ..) rand함수를 잘 사용하지 않았다.
그럼 어떻게 하느냐
srand((int)&val)); 과 같이 특정 변수의 주소를 정수로 변환해버린다.
그런데 이게 지역변수라 매번 할당을 다르게 할 줄 알았더니, Generate 버튼을 아무리 눌러도 항상 같은 미로를 만들었다. 주소값이 같은건가..!!
덕분에 좋은 난수 생성 알고리즘을 알았는데, 메르센 트위스터(MT) 고안자가 만든 WELL512 를 사용해봤다. 자세한 내용은 구글링 + 위키 참조

---

10-06 15:48 update. v1.2

- 셀 크기 설정 추가 (가로X세로에 대해 자동 계산)

- 정답 출력(Find Path) 추가

- 미로만 다시 그리기(Reset) 추가

여담:
- 셀 크기가 너무 작거나 크면 미로를 만들지 않도록 했는 데 먹히질 않는다 (!!)
- 셀 크기가 너무 작으면 튕긴다. 주의..
- BFS 과정 출력 버튼도 있었는데 너무 더러워서 제거 (....)

---

10-06 18:55 update. v1.3

- 랜덤하지 못하게 편향된 경로 결과 수정
- 셀 크기를 변경하고 Find Path를 누르면 잘못되던 버그 수정

---

10-06 20:37 update. v1.4.0

- 버튼 활성화/비활성화 추가
- 최소 셀 크기 제한
- 버튼 UI를 왼쪽으로 이동
- 숫자 입력 후 엔터 누르면 자동 Generate 반복문이 맞물려서 런타임 에러가 남. 일단 삭제
- 창 크기 및 출력 크기 변경 가능

---

10-10 20:02 update. v1.4.1

- 인쇄 기능 추가 (세로 모드로 출력)
- 왼쪽 상단에 미로의 크기 정보 표시
- 미로 난이도 상향 (...?)
- 길 찾기 결과 출력에 옵션 추가. (탈출로 / BFS 결과)
- 시작점과 출발점을 변경함 (윗쪽 중앙에서 아랫쪽 중앙으로 탈출)
- 그 외 기타 예외 처리.

Attached File
> Maze_Generator.v1.4.1.exe

1695 - 팰린드롬 만들기

처음에 그리디적으로 접근했는데, 이게 발상의 시초였다.

팰린드롬을 만들 때, 좌우 한쪽을 기준으로 잡고, 양쪽이 다르면 반대쪽에 "그 문자"를 추가한다고 생각해보았다. 예를 들면,

abaacd 라면 가장 왼쪽 a와 잡고 가장 오른쪽은 d를 비교한다. 이 때 문자가 서로 다르므로 오른쪽에 a를 추가하여 abaacda 를 만든다고 생각한다. a는 이제 추가했으므로 b를 잡고 다시 d를 비교한다. 다르므로 다시 추가하면 abaacdba 가 될 것이다.

이 행동을 반복하면

abaacdaba

abaacdaaba

abaacdcaaba

abaacdcaaba

하지만 위 방법은 너무 그리디적이여서 만약 번갈아서 추가해야하는 상황이 생기면 틀리게 된다.

생각을 살짝 바꾼다면, L번째와 R번째를 비교하는 함수를 p(L, R) 이라 하자.
p(L, R) 에서 나올 수 있는 경우는 3가지이다.

1. L과 R이 같은 경우

2-1. L과 R이 다를 때, p(L+1, R)에서 답이 나오는 경우 + 1 (여기서 1은 한쪽이 다르므로 문자를 추가한 비용)

2-2. L과 R이 다를 때, p(L, R-1)에서 답이 나오는 경우 + 1

우리는 이제 그리디적인 2-1 과 2-2 에 대해 유연하게 대처할 수 있게 되었다.

중복되는 연산이 굉장히 많으므로 [L][R]과 같이 저장해서 중복연산을 피하면 되겠다.

2004 - 조합

nCm 에 대해서 오른쪽부터 0의 개수를 출력하는 문제이다.

nCm = (n! / m!) / (n-m)! 이다. 여기서 m≤n≤2,000,000,000 인데 각각 팩토리얼을 계산한다면 절대 구할 수 없을 것이다. (오버플로우나 시간복잡도 등..)

이 문제 이전에 일반적인 nCm 을 구하는 문제부터 짚어보자.
오버플로우를 피해서 nCm을 구하는 것이라면 각 팩토리얼을 모두 계산 후에 나누는 게 아니라 분자(2 * 3 *... * n-m+1) 와 분모(2 * ... * m) 을 구성하는 각 숫자를 하나씩 계산하는건데

12C5 를 예로 들자면 12! 을 계산 후에 5! 7! 으로 나누는게 아니라 아래와 같이 진행한다.
12C5는 아래와 같이 나타낼 수 있다.
( 12 * 11 * 10 * 9 * 8 ) / ( 5 * 4 * 3 * 2 * 1 )
위 식은 다시말해 (12/5) * (11/4) * (10/3) * (9/2) * (8/3) 을 따로 한 것과 같은 결과이다.

그럼 0의 개수는 어떻게 구할까?
0의 개수를 구하는 문제는 보통 숫자를 소인수분해해서 2의 지수갯수와 5의 지수갯수 중 더 작은 만큼이 0의 갯수를 구성하는 게 일반적이다.
예를들면 120 = 2³ * 3¹ * 5¹ = 2¹ * 3¹ * 10¹ 이라서 가능하다.

서론이 길었는데, 다시 본문으로 돌아와서.
이 문제에서는 nCm을 구하는게 아니라 nCm의 0의 개수를 구하는 문제이니, [분자에서 나온 2^a * 5^b]와 [분모에서 나온 2^c * 5^d] 를 구해서 a-c 와 b-d 중에 더 작은 값이 곧 nCm의 0의 개수가 된다.

N=9 으로 생각해보자.
N! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 이 될 것이다.
여기서 2의 배수만 추려낸다면 2의 지수를 구할 수 있을 것이다.
2의 배수 = N/2 개만큼 있다. = 4개 ( 2, 4, 6, 8. )   --- 여기서 2의 배수만 구했는데, 그럼 2, 4, 6 이 각각 2¹ 을 가지고 있다는 뜻이된다.
4의 배수 = N/4 개만큼 있다. = 2개 ( 4, 8. )       ---- 2¹에 대해서 앞에서 더해줬기 때문에 지금 센 것이 중복일 지 몰라도 잘 생각해보면 "중복을 피했다"

마찬가지로 8의 배수, 16의 배수... 에 대해서 반복하면 된다.
5의 배수도 위와 같이 세면 된다.

수학적인 사고가 부족해서 위 개념을 이해하는 데 한참 걸렸다. 답답함을 안고 알려준 친구에게 고마움을 표한다.

1701 - 소녀시대 공식팬클럽 회장

2번 이상 나타나는 부분문자열을 찾고 그 최대 길이를 출력하는 문제이다.

Suffix Array 를 사용했는데,
길이가 n인 문자열 s에 대해 s[i...n]의 suffix (n개)를 나열한다. 예를들어, abbac 라면

abbac
bbac
bac
ac
c

와 같이 나오는데, 이걸 사전순으로 정렬하여 다음과 같이 만든다.

abbac
ac
bac
bbac
c

위 suffix array에 대해 서로 문자열을 비교한다.
i번 문자열과 i+1번 문자열에 대해 [0...j]를 비교. [i][j] 와 [i+1][j] 가 다를 때까지의 길이가 부분문자열의 길이가 된다.
이는 "모든 부분문자열은 모든 접미사의 접두사들"이기 때문이다.

Suffix Array는 간단한 구현으로 많은 문제에 영감을 줄 수 있지만, 위와 같이 N개에 대해 저장하거나 N²의 시간복잡도를 가지는 경우가 있어서 길이가 1만 정도만 넘어도 사용하기 힘들어진다고 한다.

길이가 10만을 넘는 문자열에 대해서 부분문자열은 어떻게 찾는지 고심해봐야겠다.

7579 - 앱

M 메모리를 확보하기 위해 활성화 중인 앱을 종료시켜야 하는데
다시 실행하는 데 드는 비용 C 를 최소화하는 문제이다.

생각을 바꿔서, 비용 C로 얼마만큼의 메모리를 확보할 수 있는가로 풀면 된다.

1244 - 스위치 켜고 끄기

남학생의 경우 주어진 수(k라 하자)의 배수마다 NOT 연산을 한다.
이부분은 인덱스 idx를 k-1부터 시작해서 idx += k 씩 증가시키면서 NOT을 하면 된다.

여학생의 경우 주어신 수 k를 기준으로 좌우대칭 구간만큼 NOT 연산을 한다.
left = k, right = k 로 설정하고 left--, right++ 을 하면서 배열의 [left]원소와 [right]원소가 다를 때 까지 NOT 연산을 반복하면 된다.

최대 학생 수=100, 스위치=100 이라 걱정없었지만, 더 큰 입력에 대해선 어떻게 해야할 지 모르겠다. 더 효율적인 좋은 방법이 있으리라 생각한다.

4493 - 가위 바위 보?

가위, 바위, 보는 서로를 향하는 상성을 가진다.
이기면 +2점, 비기면 +1점, 지면 0점이라고 했을 때
X(행)가 Y(열)과 붙었을 때 얻을 수 있는 점수는 아래와 같이 표현할 수 있다

	R	P	S
R	1	0	2
P	2	1	0
S	0	2	1

입력된 char형에 따라 R => 0, P => 1, S => 2 으로 변환하고, 테이블을 참조하여 플레이어 기준으로 점수를 더하게 했다.