CHIPMAKER

1. 문제

[설명]

0 살 이상 99살 이하의 사람들의 나이가 주어질 때, 이를 오름차순으로 정렬하는 프로그램을 작성하라.

[입력]

입력의 첫 줄에는 테스트 케이스의 개수 T가 입력된다.

각 테스트 케이스는 한줄로 이뤄지며, 자연수  자연수 N(1 ≤ N ≤ 2, 000, 000), X1(0 ≤ X1 ≤ 99), P(1 ≤ P ≤ N)가 차례대로 입력된다.

i(i>1) 번째 사람의 나이는 xi = (xi-1*11 + 97) mod 100 이다.

[출력]

각 테스트 케이스에 대해 한줄에 오름차순으로 P번째인 사람의 나이를 출력한다.

원소스 : http://judge.lavida.us/problem.php?id=2103

2. 설명

단순하게 생각했는데 내부적으로 고려해야 할 사항이 많다. 나머지 연산자의 특성을 모르면 함정에 빠질 수 있다.

처음에는 P번째 값을 구하라고 해서 단순히 P번째 값만 구했는데 나머지 연산 결과에 대한 특성을 파악하지 못했다. 

3. 코드

일단 재귀 호출로 성능 무시하고 구현하면 아래와 같다. STL을 사용하여 구현을 하였다.

#include <iostream> #include <vector> #include <algorithm> int calc(int i, int p) { if(p == 1) { // return inital value return i; } else { return (calc(i, p-1) * 11 + 97) % 100; } } int calc_age(int n, int i, int p) { std::vector<int> v; for(int j = 1; j <= n; j++) { v.push_back(calc(i, j)); } std::sort(v.begin(), v.end(), std::less<int>()); return v[p-1]; } int main() { int r = calc_age(5, 1, 5); std::cout << r << std::endl; r = calc_age(7, 9, 3); std::cout << r << std::endl; return 0; }

4. 실행 결과

Start

85
53

Finish

1. 설명

그래프에 대해서 깊이 우선 순위 구현 및 차 후에 다시 보기 위해서 여기에 남김.

깊이 우선 순위 구현은 재귀호출 기반과 스택 자료 구조를 이용해서 각각 구현해 보았다. C++ STL 버전은 아직 올리지 않았지만 STL기반으로 구현하면 정말 깔끔하다.

2. 소스 코드

Gist에서 관리한다.

3. 실행결과

1. 현재 그래프 출력

2. 재귀호출에 의한 깊이 우선 탐색

3. 스택에 의한 깊이 우선 탐색

0. 종료

========================================

 >> 1

고속도로 망의 인접 리스트

정점 서울의 인접 리스트 -> 대전 -> 춘천

정점 대전의 인접 리스트 -> 서울 -> 대구 -> 전주

정점 춘천의 인접 리스트 -> 서울 -> 대구

정점 대구의 인접 리스트 -> 대전 -> 춘천 -> 부산

정점 전주의 인접 리스트 -> 대전 -> 광주

정점 부산의 인접 리스트 -> 대구 -> 광주

정점 광주의 인접 리스트 -> 전주 -> 부산

========================================

1. 현재 그래프 출력

2. 재귀호출에 의한 깊이 우선 탐색

3. 스택에 의한 깊이 우선 탐색

0. 종료

========================================

 >> 2

깊이 우선 탐색 결과 : 서울 대전 대구 춘천 부산 광주 전주

========================================

1. 현재 그래프 출력

2. 재귀호출에 의한 깊이 우선 탐색

3. 스택에 의한 깊이 우선 탐색

0. 종료

========================================

 >> 3

깊이 우선 탐색 결과 : 서울 대전 대구 춘천 부산 광주 전주

========================================

1. 현재 그래프 출력

2. 재귀호출에 의한 깊이 우선 탐색

3. 스택에 의한 깊이 우선 탐색

0. 종료

========================================

 >> 0

1. 소스 코드

문제해결을 위한 창의적 알고리즘(중급) 예제 문제, 복습 목적

하위 트리 전개는 사건을 기준으로 한다. 경찰차 위치가 하나의 처리된 사건으로 가정하고 다음 사건을 정의하는 부분을 주의 깊게 보자

#include <iostream> #include <tuple> #include <array> const int N = 3; int min = 0x7FFFFFFF; std::array< std::tuple<int, int>, N+2> accident = {{ {1, 1}, {6, 6}, {3, 5}, {5, 5}, {2, 3} }}; int distance(int a, int b) { int dx = std::abs( std::get<0>(accident[a]) - std::get<0>(accident[b]) ); int dy = std::abs( std::get<1>(accident[a]) - std::get<1>(accident[b]) ); return dx+dy; } void f(int a, int b, int s) { int next = ((a > b) ? a : b) + 1; //std::printf("a = %d b = %d next = %d s = %d\n", a, b, next, s); if(next >= N+2) { if(min > s) { min = s; } return; } f(next, b, s+distance(a, next)); f(a, next, s+distance(b, next)); } int main() { f(0, 1, 0); std::printf("min = %d \n", min); return 0; }

1. 소스 코드

문제해결을 위한 창의적 알고리즘(중급), 100페이지 4문제로 미로가 주워지고 'S'에서 출발해서 'G'로 끝나점까지의 최단 거리를 찾는 문제이다. 기존에 두더지 문제를 잘 풀었다면 어렵지 않게 해결할 수 있다.

문제 해결은 깊이 우선 또는 너비 우선 순위로 해결할 수 있지만 너비 우선 순위로 풀어 보았다.

#include <iostream> #include <array> #include <algorithm> #include <queue> const int N = 5; std::array<int, 4> dx = {-1, 0, 1, 0}; std::array<int, 4> dy = {0, -1, 0, 1}; std::array<std::array<char, N>, N> map = {{ {'#', 'S', '#', '#', '#'}, {'#', '.', '.', '.', '#'}, {'#', '.', '#', '.', '#'}, {'#', '.', '.', '.', '.'}, {'#', '#', '#', 'G', '#'} }}; using coordinate = struct _coordinate { int x; int y; int l; }; bool isOutOfRange(int y, int x) { if( (x < 0) || (x > N-1) ) { return true; } if( (y < 0) || (y > N-1) ) { return true; } return false; } int bfs(int y, int x, int dist) { std::queue<coordinate> q; q.push(coordinate{x, y, dist}); while(!q.empty()) { coordinate pos = q.front(); q.pop(); if(map[pos.y][pos.x] == 'G') { std::printf("find road : %d \n", pos.l); return pos.l; } for(int i = 0; i < 4; i++) { int nx = pos.x + dx[i]; int ny = pos.y + dy[i]; int nl = pos.l + 1; if( (isOutOfRange(ny, nx) == false) && ((map[ny][nx] == '.') || (map[ny][nx] == 'G')) ) { if(map[ny][nx] == '.') map[ny][nx] = '-'; q.push(coordinate{nx, ny, nl}); } } } return -1; } int main() { int min = -1; for(int y = 0; y < N; y++) { for(int x = 0; x < N; x++) { if(map[y][x] == 'S') { min = bfs(y, x, 0); } } } std::printf("\n"); for(int y = 0; y < N; y++) { for(int x = 0; x < N; x++) { std::printf("%c ", map[y][x]); } std::printf("\n"); } std::printf("\n"); std::printf("최단 거리 : %d \n", min); return 0; }

2. 실행 결과

find road : 6 

# S # # # 
# - - - # 
# - # - # 
# - - - - 
# # # G # 

최단 거리 : 6 

1. 소스 코드

문제해결을 위한 창의적 알고리즘(중급), 77페이지 문제에 있는 문제로 두더지 굴이 몇 개 있으며, 각 두더지 굴의 깊이를 출력하는 문제이다.

#include <iostream> #include <array> #include <queue> const int N = 7; int cnt = 1; std::array<int, 4> dx = {-1, 0, 1, 0}; std::array<int, 4> dy = {0, -1, 0, 1}; std::array<std::array<int, N>, N> map = {{ {0, 1, 1, 0, 1, 0, 0}, {0, 1, 1, 0, 1, 0, 1}, {1, 1, 1, 0, 1, 0, 1}, {0, 0, 0, 0, 1, 1, 1}, {0, 1, 0, 0, 0, 0, 0}, {0, 1, 1, 1, 1, 1, 0}, {0, 1, 1, 1, 0, 0, 0} }}; using coordinate = struct { int x; int y; }; std::vector<unsigned int> vc; bool isOutOfRange(int y, int x) { if( (x < 0) || (x > N-1) ) { return true; } if( (y < 0) || (y > N-1) ) { return true; } return false; } void bfs(int y, int x, unsigned int &dist) { std::queue<coordinate> q; q.push(coordinate{x, y}); map[y][x] = cnt; while(!q.empty()) { dist++; coordinate pos = q.front(); q.pop(); for(int i = 0; i < 4; i++) { int nx = pos.x + dx[i]; int ny = pos.y + dy[i]; if( (map[ny][nx] == 1) && (isOutOfRange(nx, ny) == false) ) { map[ny][nx] = cnt; q.push(coordinate{nx, ny}); } } } } int main() { for(int y = 0; y < N; y++) { for(int x = 0; x < N; x++) { if(map[y][x] == 1) { unsigned int dist = 0; cnt++; bfs(y, x, dist); vc.push_back(dist); } } } for(int y = 0; y < N; y++) { for(int x = 0; x < N; x++) { std::printf("%2d ", map[y][x]); } std::printf("\n"); } std::printf("\n"); std::cout << "두더지 굴 개수 : " << vc.size() << std::endl; for(auto iter : vc) { std::printf("%d ", iter); } std::printf("\n"); return 0; }

2. 실행 결과

 0  2  2  0  3  0  0 
 0  2  2  0  3  0  3 
 2  2  2  0  3  0  3 
 0  0  0  0  3  3  3 
 0  4  0  0  0  0  0 
 0  4  4  4  4  4  0 
 0  4  4  4  0  0  0 

두더지 굴 개수 : 3
7 8 9 

1. 목적

공부한 내용 다음에 다시 복습하기 위해서 여기에 정리. 알고리즘 동작 원리는 설명은 생략.

여기 (http://blog.eairship.kr/268) 블로그에 정리된 내용 중에 최단 거리 탐색 문제를 내 나름되로 짜 봤다.

2. 코드 설명

너비 우선 탐색 기반은 비선형 탐색의 한 종류로 Queue 기반으로 Stack 기반의 깊이기반 탐색에서 10만번 이상을 수행 시에 Stack Overflow에 대한 제약 사항을 해결할 수 있는 하나의 방식이다.

#include <iostream> #include <array> #include <queue> const int N = 5; unsigned int min = 0xFFFFFFFF; std::array<int, 4> dx = {-1, 0, 1, 0}; std::array<int, 4> dy = {0, -1, 0, 1}; std::array<std::array<int, N>, N> map = {{ {1, 1, 1, 1, 1}, {0, 0, 0, 0, 1}, {1, 1, 1, 1, 1}, {1, 0, 1, 0, 0}, {1, 1, 1, 1, 1} }}; using coordinate = struct { int x; int y; unsigned int l; }; bool isOutOfRange(int x, int y) { if( (x < 0) || (x > N-1) ) { //std::printf("out of range x \n"); return true; } if( (y < 0) || (y > N-1) ) { //std::printf("out of range y \n"); return true; } return false; } void bfs(int x, int y) { std::queue<coordinate> q; q.push(coordinate{x, y, 0}); // 기존에 방문한 좌표를 재 방문하는 것을 막기 위해서 처리, 보통 visited라는 새로운 배열을 쓰곤한다. map[y][x] = -1; while(!q.empty()) { coordinate pos = q.front(); q.pop(); if( (pos.x == N-1) && (pos.y == N-1) ) { if(min > pos.l) { min = pos.l; std::printf("end of map : min = %u \n", min); } } for(int i = 0; i < 4; i++) { int nx = pos.x + dx[i]; int ny = pos.y + dy[i]; unsigned int nl = pos.l; if( (isOutOfRange(nx, ny) == false) && (map[ny][nx] == 1) ) { // 기존에 방문한 좌표를 재 방문하는 것을 막기 위해서 처리, 보통 visited라는 새로운 배열을 쓰곤한다. map[ny][nx] = -1; q.push(coordinate{nx, ny, nl+1}); } } } } int main() { bfs(0, 0); for(int y = 0; y < N; y++) { for(int x = 0; x < N; x++) { std::printf("%2d ", map[y][x]); } std::printf("\n"); } std::printf("\n최단거리 : %u \n", min); return 0; }

3. 실행 결과

end of map : min = 12 
-1 -1 -1 -1 -1 
 0  0  0  0 -1 
-1 -1 -1 -1 -1 
-1  0 -1  0  0 
-1 -1 -1 -1 -1 

최단거리 : 12 

1. 목적

공부한 내용 다음에 다시 복습하기 위해서 여기에 정리. 알고리즘 동작 원리는 설명은 생략.

여기 (http://blog.eairship.kr/268) 블로그에 정리된 내용 중에 최단 거리 탐색 문제를 내 나름되로 짜 봤다.

2. 코드 설명

깊이 우선 탐색 기반은 Stack 기반이고, 기존에 방문한 Node에 대해서 원하는 답을 얻지 못할 경우 다시 현재 Node 전의 Node로 이동해야 하는데 이 때 현재 Node 탐색에 사용된 중간 결과는 모두 원래되로 돌려줘야 한다. Back Tracking 기반이라는 의미로 해석된다. 흔히 운영체제나 이런 곳에서 Stack 되감기 이런 말을 들을 수 있는데 이 문제에서 많은 영감을 얻을 수 있다.

#include <iostream> #include <array> const int N = 5; unsigned int min = 0xFFFFFFFF; std::array<int, 4> dx = {-1, 0, 1, 0}; std::array<int, 4> dy = {0, -1, 0, 1}; std::array<std::array<bool, N>, N> visited; std::array<std::array<int, N>, N> map = {{ {1, 1, 1, 1, 1}, {0, 0, 0, 0, 1}, {1, 1, 1, 1, 1}, {1, 0, 1, 0, 0}, {1, 1, 1, 1, 1} }}; bool isOutOfRange(int y, int x) { if( (x < 0) || (x > N-1) ) { return true; } if( (y < 0) || (y > N-1) ) { return true; } return false; } void dfs(int x, int y, unsigned int distance) { if(isOutOfRange(y, x) == true) { return; } if( map[y][x] == 0) { //std::printf("no road \n"); return; } if( visited[y][x] == true) { //std::printf("already visited \n"); return; } if( (x == N-1) && (y == N-1) ) { if(min > distance) { min = distance; std::printf("end of loop .. distance : %d \n", distance); return; } } for(int i = 0; i < 4; i++) { visited[y][x] = true; // for backtracking of depth first search dfs(x + dx[i], y + dy[i], distance+1); visited[y][x] = false; // for backtracking of depth first search } } int main() { dfs(0, 0, 0); std::printf("\n최단거리 : %u \n", min); return 0; }

3. 실행 결과

end of loop .. distance : 16 
end of loop .. distance : 12 

최단거리 : 12 

1. 소스 코드

문제해결을 위한 창의적 알고리즘(중급), 77페이지 문제에 있는 문제로 두더지 굴이 몇 개 있으며, 각 두더지 굴의 깊이를 출력하는 문제이다.

#include <cstdlib> #include <iostream> #include <ctime> #include <array> #include <vector> #include <algorithm> const unsigned int N = 7; unsigned int cnt = 1; std::array<int, 4> dx = {-1, 0, 1, 0}; std::array<int, 4> dy = {0, -1, 0, 1}; std::array<std::array<unsigned int, N>, N> map = {{ {0, 1, 1, 0, 1, 0, 0}, {0, 1, 1, 0, 1, 0, 1}, {1, 1, 1, 0, 1, 0, 1}, {0, 0, 0, 0, 1, 1, 1}, {0, 1, 0, 0, 0, 0, 0}, {0, 1, 1, 1, 1, 1, 0}, {0, 1, 1, 1, 0, 0, 0} }}; std::vector<int> vc; bool isOutOfRange(int y, int x) { if( (x < 0) || (x > N-1) ) { return true; } if( (y < 0) || (y > N-1) ) { return true; } return false; } void dfs(int y, int x, unsigned int &dist) { map[y][x] = cnt; for(int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if( (map[ny][nx] == 1) && (isOutOfRange(ny, nx) == false) ) { dist++; dfs(ny, nx, dist); } } } int main() { for(int y = 0; y < N; y++) { for(int x = 0; x < N; x++) { if(map[y][x] == 1) { cnt++; unsigned int dist = 1; dfs(y, x, dist); vc.push_back(dist); } } } std::cout << "After Scan Tunnel ... "<< std::endl; for(int y = 0; y < N; y++) { for(int x = 0; x < N; x++) { std::printf("%d ", map[y][x]); } std::printf("\n"); } std::printf("\n"); std::cout << "number of tunnel : " << vc.size() << std::endl; std::sort(vc.begin(), vc.end(), std::greater<int>()); for(auto iter : vc) { std::printf("%d ", iter); } std::printf("\n"); return 0; }

2. 실행 결과