1174 - 줄어드는 수

https://www.acmicpc.net/problem/1174

나올 수 있는 가장 큰 값은 9876543210 (10자리) 이다.
1자리 수(0~9)부터 10자리 수에 대해서 각각 감소하는 수를 모두 구하면 된다.
n자리로 이루어진 모든 감소하는 수는 재귀로 구현했다.

유사한 문제

- 1038번: 감소하는 수

2098 - 외판원 순회

https://www.acmicpc.net/problem/2098

문제 <외판원 순회 2>의 실행시간이 오래 걸리는 이유는 모든 정점을 방문했는 지 확인하는 반복문과 이미 방문한 경로의 불필요한 탐색때문이다.

비트마스킹을 통해 이러한 반복을 줄여보자. 정점의 개수는 최대 16이다. 0번째, 1번째, ... 15번째를 방문했는지를 비트마스킹을 통해 00.....0 과 같이 길이가 16인 2진수로 표현할 수 있다. 그럼 $O(1)$만에 종료 조건을 확인할 수 있다.

하지만 모든 경우를 탐색하는 것은 똑같아서 수행시간에 큰 차이는 없을 것이다. (N배 빠르니까 약 10배)

여러 정점을 방문하면서 남은 정점을 확인할 때 중복되는 경우가 많다. 예를 들면 1 2 5 3 4 순으로 방문한 경우와 2 1 5 3 4 순으로 방문한 경우는 둘 다 1, 2를 방문한 상태에서 5 3 4 를 다시 방문하고 있다. 5 3 4 순으로 방문했을 때의 최적값을 구해둔다면 다시 방문할 필요 없이 미리 구한 최적해를 사용하면 된다. (메모이제이션으로 구현함)

이전에 작성한 글에서 소스의 다른 부분은 모든 정점을 방문했는 지 확인하는 반복문을 없애고 O(1)의 비트로 확인한다는 점과, 메모이제이션을 적용했다는 점 밖에 다르지 않다.

1062 - 가르침

https://www.acmicpc.net/problem/1062

k개의 알파벳을 학습하여 N개의 남극언어 중 몇 개를 읽을 수 있는가인데, 시간 복잡도 계산 안하고 그냥 재귀로 돌려봤다 (패기..!)

매번 모든 알파벳을 검사하기는 힘들다. 그리고 어차피 알파벳은 한번만 배우면 계속 쓰일 수 있다. 그럼 각 단어마다 알파벳의 존재여부를 체크하여 저장할 수가 있는데, 한 단어에서 x번째 알파벳이 사용되었다/안되었다(0/1) 로 구분하면 26자리 2진수 (최대 $2^{26}-1$) 로 표현할 수 있다. 그럼 ACE 는 0 00000 00000 00000 00000 10101 로 표현된다.
소스는 1번째...26번째로 해서 비트가 왼쪽으로 하나씩 밀려있다.

A~Z 중에 k개를 선택했을 때 읽을 수 있는 최대 단어의 갯수를 반환하면서, 그 최대값을 갱신하도록 했다.

그리고 "K개의 글자"에 남극언어에 들어가는 ANTA,TICA 도 포함되어야 한다. (이것때문에 한참 틀렸다) 즉, 5개의 글자(ANTIC)를 반드시 배워야한다는 것이다.

1238 - 파티

처음에는 플로이드 와샬로 접근해봤다. 아니나다를까 N=1,000 이라서 $O(N^3)$ 은 시간초과였다.

처음으로 다익스트라를 구현해봤다.
잘 동작하는지는 모르겠고 흉내만 내는 것 같다.

#define INF 987654321

typedef pair<int,int> ii;

int dijkstra(vector<ii> adj[], int n, int s, int e){
    vector<int> cost(n, INF); /* s 로부터 i까지의 최소 비용 */
    priority_queue<ii /*(-weight, next)*/> q;
    q.push({0, s});
    cost[s] = 0;
    while(!q.empty()){
        int pos = q.top().second;
        int dist = -q.top().first;
        q.pop();
        
        for(int i=0; i<adj[pos].size(); ++i){
            ii& next = adj[pos][i]; /* (next, weight) */
            if(dist + next.second >= cost[next.first]) continue;
            q.push({-(dist+next.second), next.first});
            cost[next.first] = dist+next.second;
        }
    }
    return cost[e];
}

예제가 잘 나오길래 제출해봤는데 정답이 잘 나왔다. 시간이 좀 걸리는걸 보니 N이 좀 커지면 시간초과가 나올 듯 하다.

9009 - 피보나치

https://www.acmicpc.net/problem/9009

주어진 정수 X를 X와 같거나 가장 가까운 작은 수로 계속 빼면 된다.
마치 동전을 큰 단위부터 거슬러주면 제일 적은 개수로 거슬러 줄 수 있듯이,
가능한 큰 수로 계속 빼면 그것이 최소 개수로 표현할 수 있는 피보나치 수의 합이다.

ACM ICPC 2012 인터넷예선 D번 Fibonacci Numbers

10971 - 외판원 순회 2

https://www.acmicpc.net/problem/10971

어떤 지점 s에서 출발해서 모든 정점을 거치고 다시 s로 돌아오는 경우를 모두 탐색했다. $O(N!)$
매 번 "모든 정점을 방문했는가?" 를 확인하면서 모두 방문했다면 현재가 s인가(출발점 == 종료점)를 판별해서 그렇다면 그때의 값이 최소가 되게 했다.

이동할 때마다 가중치를 더한다. 모든 정점을 방문했을 때 자신으로 돌아온게 아니라면 답이 아니도록 했다.

어떤 지점 s는 어디건 상관없다. 출발점과 도착점이 같은 지점을 찾는다면, 그 지점이 어디건 정답인 경우의 경로는 똑같이 나온다.

1208 - 부분집합의 합 2

1182 - 부분집합의 합 에서 시간 제한이 N=20 에서 N=40 으로 확장된 문제이다.

$2^{20}$ 은 약 100만이라 시간이 충분했지만, $2^{40}$ 은 1조에 가깝다.

문제를 아무리 봐도 좋은 생각이 안 나다가, 주변에서 몇가지 힌트를 받고 해결할 수 있었다.

N개의 정수로 이루어진 배열 a에서 모든 부분집합을 살피려면 위에 말한것과 같이 $2^{40}$ 이라 굉장히 힘들다. 하지만 반으로 나눠서 부분 집합을 살핀다면 이 문제를 해결할 수 있다.

배열 a를 반으로 나눈다. 즉, $ a_0, a_1, \dots a_n $ 을 $ a_0, a_1, \dots a_{n/2} $ 와 $ a_{n/2 +1}, \dots a_n $ 으로 나눈다.

그리고 $ a_0, a_1, \dots a_n $ 에서 나올 수 있는 부분 집합의 합을 A 라 하고 나머지 $ a_{n/2 +1}, \dots a_n $ 나올 수 있는 부분 집합의 합을 B 라 하자.

그럼 문제의 정답은 (A의 원소로만 가능한 경우) + (A+B로 가능한 경우) + (B로만 가능한 경우) 로 나타낼 수 있다.
각각의 배열을 만드는 시간은 $2^{20}$ 을 두 번 하면 되고, "A+B로 가능한 경우"는 배열 B에 S-A[i]의 원소가 있는 지를 확인하면 된다.

S=0 이고 a = [ -7, -3, -2, 5, 8 ] 같은 경우는 A = { [-7, -3] 으로 나타낼 수 있는 부분 집합들 } 이고 B = { [-2, 5, 8] 으로 나타낼 수 있는 부분 집합들 } 이다. 이를 자세히 적는다면 A = [ -7, -3, -10 ], B = [ -2, 5, 8, 3, 6, 11 ] 이다.
여기서 답은 (A의 원소로만 가능한 경우 = 0) + (A+B로 가능한 경우는 -3+3=0 으로 1개) + (B로만 가능한 경우 = 0) 으로 1 이다.

주의해야 할 점은, 원소가 같은 것이 여러 개 있을 수 있다. 예를 들어 A = [0, 2, 2], B = [2, 2, 4] 라면 각 숫자는 서로 다르기 때문에 따로 세어야하고 A+B 로 만들어지는 2+2 의 경우들도 모두 서로 다르게 조합된 것들이기 때문에 모두 세어야 한다. 같은 2+2 이지만 $A_1 + B_0$ 은 2 + 2 인 것이고, $A_2 + B_0$ 은 (0+2) + 2 이기 때문이다.

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

1012 - 유기농 배추

DFS나 BFS와 같은 전탐색으로 문제를 해결할 수 있다.
필자는 DFS를 사용했는데, int dirt[4]={-1,0,1,0}; 과 같이 선언하고

08	int DFS(int y, int x, int H /*최대 높이*/, int W /*최대 너비*/)

09

{

10	if( /* Base Case; 기저 케이스 */ ) return 0;

15	for(int i=0; i < 4; ++i)

16	DFS( y+dirt[(i+3)%4], x+dirt[i], H, W );

17

return 1;

18

}


위와 같이 [상(-1,0), 우(0,-1), 하(+1,0), 좌(0,+1) ]의 조합을 배열 하나로 사용했다.

여기서 DFS가 return 1; 을 했다. 이건 한 덩어리(구간)의 출발점만 리턴될 것이다.
왜냐하면 기저 케이스에서 "방문한 노드"는 return 0; 으로  걸러질 것이기 때문이다.

1759 - 암호 만들기

재귀적인 탐색 문제이다.

문제에서 "최소 1개의 모음과 최소 2개의 자음" 이라는 부분을 놓쳐서 몇 번 틀렸다.

재귀함수는 아래와 같다.

void password( int cur, int k, int N, int C /*Consonant*/, int V /*Vowel*/ ){
    if( k >= N && C > 1 && V > 0 ){
        // 누적된 문자열 출력
        return;
    }
    // ....
}

글자수가 제한되어 있으니 재귀 호출의 깊이를 제한하면 된다.
깊이의 제한을 위해 k로 깊이를 인자로 넘기고, N은 문제에서 말한 암호의 길이이다.

cur은 알파벳이고, 처음에 입력받은 알파벳들은 정렬 후 사용했다. (사전순 출력을 위해)