CHIPMAKER

1. 소스 코드

아래 블로그에 관련 내용은 잘 정리되어 있어서 따라 해 보았다.

메뉴를 만들어서 각 단계별로 동작을 확인하는 메뉴로 각 단계별 동작을 확인하였다.

좀 더 수식적으로 접근하는 블로그를 보았던 것 같은데, 수식적으로 각 단계별로 최소값을 노드로 선택해서 이동 시

출발 노드에서 각 노드간 길이가 최소가 되는지 의문이긴 하다. 수식으로 증명하는 부분을 봤으면 한다.

http://hsp1116.tistory.com/42

#include <iostream> #include <vector> #include <tuple> #include <limits> #include <iomanip> #include <bitset> #define INF 0x1FFFFFFF enum { G_EDGE = 0, G_WEIGHT } GRAPH_TUPLE_INDEX; enum { R_WEIGHT = 0, R_PREV_IDX, R_VISIT } RESULT_TUPLE_INDEX; int N = 5; int g_menu_choice; int getArraryIndex(int idx) { if(idx > N) { std::cout << "out of range" << std::endl; return -1; } return idx - 1; } void loadInitData(std::vector<std::vector<std::tuple<int,int>>> &G, std::vector<std::tuple<int,int,bool>> &R) { std::vector<std::tuple<int,int,int>> edgeInfo = { std::make_tuple(getArraryIndex(1), getArraryIndex(3), 6), std::make_tuple(getArraryIndex(1), getArraryIndex(4), 3), std::make_tuple(getArraryIndex(2), getArraryIndex(1), 3), std::make_tuple(getArraryIndex(3), getArraryIndex(4), 2), std::make_tuple(getArraryIndex(4), getArraryIndex(2), 1), std::make_tuple(getArraryIndex(4), getArraryIndex(3), 1), std::make_tuple(getArraryIndex(5), getArraryIndex(2), 4), std::make_tuple(getArraryIndex(5), getArraryIndex(4), 2), }; for(auto v : edgeInfo) { int vertex = std::get<0>(v); int edge = std::get<1>(v); int weight = std::get<2>(v); G[vertex].emplace_back(edge, weight); } for(int i = 0; i < N; i++) { // weight, previous idx, isvisited R.emplace_back(INF, -1, false); } } void printGraph(const std::vector<std::vector<std::tuple<int,int>>> &G) { for(int i = 0; i < N; i++) { std::printf("Vertex : [%d] ", i+1); for(auto e : G[i]) { int index = std::get<G_EDGE>(e); std::printf("-> %d", index+1); } std::cout << std::endl; } std::cout << std::endl; } int getMinIdx(const std::vector<std::tuple<int,int,bool>> &R) { int mIdx = -1; int min = INF; for(int i = 0; i < R.size(); i++) { if(std::get<R_VISIT>(R[i]) == false) { if(std::get<R_WEIGHT>(R[i]) < min) { min = std::get<R_WEIGHT>(R[i]); mIdx = i; } } } return mIdx; } void dijkstra(int sIdx, const std::vector<std::vector<std::tuple<int,int>>> &G, std::vector<std::tuple<int,int,bool>> &R, std::vector<std::vector<int>> &IRS) { int mIdx; std::get<0>(R[sIdx]) = 0; while( (mIdx = getMinIdx(R)) != -1) { std::vector<int> tv; std::get<2>(R[mIdx]) = true; for(auto &c : R) { tv.emplace_back(std::get<0>(c)); } IRS.emplace_back(tv); for(auto &t : G[mIdx]) { int edge = std::get<G_EDGE>(t); int weight = std::get<G_WEIGHT>(t); if( std::get<R_WEIGHT>(R[edge]) >= weight + std::get<R_WEIGHT>(R[mIdx]) ) { std::get<R_WEIGHT>(R[edge]) = weight + std::get<R_WEIGHT>(R[mIdx]); std::get<R_PREV_IDX>(R[edge]) = mIdx; } } } } void printResult(const std::vector<std::tuple<int,int,bool>> &R) { for(auto &c : R) { std::printf("%d ", std::get<R_WEIGHT>(c)); } std::cout << std::endl; } void printIntermediatResult(const std::vector<std::vector<int>> &IRS) { int idx = 1; for(auto &v : IRS) { std::printf("%2d] ", idx++); for(auto &c : v) { if(c == INF) std::printf("INF "); else std::printf("%3d ", c); } std::cout << std::endl; } std::cout << std::endl; } void printPaths(int sIdx, const std::vector<std::tuple<int,int,bool>> &R) { for(int i = 0; i < R.size(); i++) { int pIdx = i; std::printf("%d 까지 경로(distance = %d) : ", i+1, std::get<R_WEIGHT>(R[i])); while(1) { if(pIdx == sIdx) { std::printf("%d ", pIdx+1); break; } std::printf("%d <- ", pIdx+1); pIdx = std::get<R_PREV_IDX>(R[pIdx]); } std::cout << std::endl; } } bool select_menu() { std::cout << "=====================================================" << std::endl; std::cout << "1. Display Graph " << std::endl; std::cout << "2. Display Final Result " << std::endl; std::cout << "3. Display Intermediate Result " << std::endl; std::cout << "4. Display Paths " << std::endl; std::cout << "0. Exit " << std::endl; std::cout << "=====================================================" << std::endl; std::cout << " >> "; std::cin >> g_menu_choice; std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); std::cout << std::endl; if (std::cin.fail() == true) { std::cout << "invalid input .. " << std::endl; std::cin.clear(); std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); return false; } return true; } int main() { int sIdx; std::vector<std::vector<std::tuple<int,int>>> G(N); std::vector<std::tuple<int,int,bool>> R; std::vector<std::vector<int>> IRS; // intermediate results #if 0 std::cout << " number of vertex >> "; std::cin >> N; std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); std::cout << std::endl; sIdx = getArraryIndex(5); G.resize(N); #else sIdx = getArraryIndex(5); #endif loadInitData(G, R); dijkstra(sIdx, G, R, IRS); while (1) { if (select_menu() == false) { continue; } switch (g_menu_choice) { case 0: return 0; break; case 1: printGraph(G); break; case 2: printResult(R); break; case 3: printIntermediatResult(IRS); break; case 4: printPaths(sIdx, R); break; } } return 0; }

1. 소스 코드

아래 블로그의 설명과 그림을 참조하여 최소 신장 트리 알고리즘 중에 하나인 프림 알고리즘을 구현해 보았다.

우선 순위 큐를 기반으로 구현하였으며, 결과적으로 다른 블로그의 예제와 유사해 보인다.

전체적으로 이해한 바로는 그래프를 너비 우선 순위로 탐색하는 것과 유사하게 구현 뼈대를 가져가고,

단지 Queue에 넣을 때는 일반 Queue가 아닌 우선 순위 큐를 사용하다는 점에 착안하여 구현하는 방향으로

구현해야 한다.

http://swlock.blogspot.kr/2016/02/prim-mstminimum-spanning-tree.html

#include <iostream> #include <vector> #include <queue> #include <functional> struct edgeInfo_t { int from; int to; int weight; }; struct edge_t { int to; int weight; }; const int N = 7; char vtxStr[N] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; bool visited[N]; std::vector<edgeInfo_t> result; auto compare = [](edgeInfo_t a, edgeInfo_t b){ return (a.weight > b.weight); }; using priority_queue_t = std::priority_queue<edgeInfo_t, std::vector<edgeInfo_t>, decltype(compare) >; int getIndex(char ch) { for(int i = 0; i < N; i++) { if(ch == vtxStr[i]) { return i; } } return -1; } void buildGraph(std::vector<edge_t> (&g)[N]) { edgeInfo_t edgeInfo[] = { {getIndex('A'), getIndex('B'), 7}, {getIndex('A'), getIndex('D'), 5}, {getIndex('B'), getIndex('C'), 8}, {getIndex('B'), getIndex('E'), 7}, {getIndex('B'), getIndex('D'), 9}, {getIndex('B'), getIndex('A'), 7}, {getIndex('C'), getIndex('E'), 5}, {getIndex('C'), getIndex('B'), 8}, {getIndex('D'), getIndex('A'), 5}, {getIndex('D'), getIndex('B'), 9}, {getIndex('D'), getIndex('E'), 15}, {getIndex('D'), getIndex('F'), 6}, {getIndex('E'), getIndex('C'), 5}, {getIndex('E'), getIndex('G'), 9}, {getIndex('E'), getIndex('F'), 8}, {getIndex('E'), getIndex('D'), 15}, {getIndex('E'), getIndex('B'), 7}, {getIndex('F'), getIndex('E'), 8}, {getIndex('F'), getIndex('G'), 11}, {getIndex('F'), getIndex('D'), 6}, {getIndex('G'), getIndex('E'), 9}, {getIndex('G'), getIndex('F'), 11}, }; int sz = sizeof(edgeInfo)/sizeof(edgeInfo[0]); for(int i = 0; i < sz; i++) { edge_t edge; int v = edgeInfo[i].from; edge.to = edgeInfo[i].to; edge.weight = edgeInfo[i].weight; g[v].push_back(edge); } } void prim(int sIdx, const std::vector<edge_t> (&g)[N], priority_queue_t &q) { for(int i = 0; i < g[sIdx].size(); i++) { edgeInfo_t edgeInfo; edgeInfo.from = sIdx; edgeInfo.to = g[sIdx][i].to; edgeInfo.weight = g[sIdx][i].weight; q.push(edgeInfo); } visited[sIdx] = true; while(q.empty() == false) { edgeInfo_t edgeInfo = q.top(); int target = edgeInfo.to; q.pop(); if(visited[target] == true) { continue; } visited[target] = true; for(auto v : g[target]) { if(visited[v.to] == false) { edgeInfo_t edgeInfo; edgeInfo.from = target; edgeInfo.to = v.to; edgeInfo.weight = v.weight; q.push(edgeInfo); } } result.push_back(edgeInfo); } } void printGraph(const std::vector<edge_t> (&g)[N]) { for(int i = 0; i < N; i++) { std::printf("Vertex %c : ", vtxStr[i]); for(int j = 0; j < g[i].size(); j++) { std::printf("-> %c ", vtxStr[(g[i][j]).to]); } std::cout << std::endl; } } int main() { std::vector<edge_t> graph[N]; priority_queue_t priorityQ(compare); buildGraph(graph); prim(getIndex('D'), graph, priorityQ); //printGraph(graph); for(auto v : result) { std::printf("%c -> %c [%d]\n", vtxStr[v.from], vtxStr[v.to], v.weight); } return 0; }

2. 실행 결과

1. 소스 코드

http://www.playsw.or.kr/repo/cast/110 그림을 참조하여 위상정렬을 해 보았다.

상세 알고리즘 동작은 위 블로그를 참조함.

#include <iostream> #include <string> #include <vector> #include <queue> const std::string str[] = { "컴퓨터공학입문", "논리회로", "자료구조", "어셈블러", "데이터베이스", "시스템프로그램밍", "컴퓨터구조", "알고리즘", "네트워크", "운영체제" }; const int N = 10; int M; std::vector<int> G[N]; std::queue<int> Q; std::queue<int> R; int in[N]; struct edge_t { int from; int to; }; int getIndex(const std::string s) { int sz = sizeof(str)/sizeof(str[0]); for(int i = 0; i < sz; i++) { if(s == str[i]) { return i; } } return -1; } edge_t data[] = { {getIndex("컴퓨터공학입문"), getIndex("자료구조")}, {getIndex("논리회로"), getIndex("컴퓨터구조")}, {getIndex("자료구조"), getIndex("데이터베이스")}, {getIndex("자료구조"), getIndex("알고리즘")}, {getIndex("자료구조"), getIndex("시스템프로그램밍")}, {getIndex("어셈블러"), getIndex("시스템프로그램밍")}, {getIndex("어셈블러"), getIndex("컴퓨터구조")}, {getIndex("시스템프로그램밍"), getIndex("네트워크")}, {getIndex("시스템프로그램밍"), getIndex("운영체제")}, }; void insertData() { M = sizeof(data)/sizeof(data[0]); for(int i = 0; i < M; i++) { int from = data[i].from; int to = data[i].to; G[from].emplace_back(to); in[to]++; } } void printIndegree() { for(int i = 0; i < N; i++) { std::printf("%-25s : %d\n", str[i].c_str(), in[i]); } } void printGraph() { for(int i = 0; i < N; i++) { std::printf("%-25s ", str[i].c_str()); for(auto e : G[i]) { std::printf("-> %s", str[e].c_str()); } std::cout << std::endl; } } int main() { insertData(); //printGraph(); //printIndegree(); for(int i = 0; i < N; i++) { if(in[i] == 0) { Q.push(i); in[i] = -1; } } while(Q.empty() == false) { int qf = Q.front(); Q.pop(); R.push(qf); for(auto e : G[qf]) { in[e]--; } for(int i = 0; i < N; i++) { if(in[i] == 0) { Q.push(i); in[i] = -1; } } } while(R.empty() == false) { std::printf("%s ", str[R.front()].c_str()); R.pop(); } std::cout << std::endl; return 0; }

2. 실행 결과

1. 소스 코드

백준 https://www.acmicpc.net/problem/1463 문제 정리.

이 문제를 처음 접하는 순간 아무 생각이 들지 않았다. 나는 왜 이리 멍청할까 정도만 생각이 들지

모든 문제를 해결하기 위해서 먼저 완전탐색부터 고민하면서 속도 개선을 위해서 하나 하나 개선해 가는 식으로 여기에 정리한다. 참고로 여러 사람들이 해 놓은 코드를 참조하였다.

아래 코드는 완전 탐색으로 구현한 내용이다.

#include <iostream> unsigned int min = 0xFFFFFFFF; void f(int n, unsigned int d) { if(n == 1) { if(min > d) { min = d; } return; } f(n-1, d+1); if(n%2 == 0) { f(n/2, d+1); } if(n%3 == 0) { f(n/3, d+1); } } int main() { int n; std::cin >> n; f(n, 0); std::cout << min << std::endl; return 0; }

2. DP 코드

1. 소스 코드

백준 https://www.acmicpc.net/problem/2579 문제 정리. 

아래 코드는 완전 탐색으로 구현해 보았다. 완전 탐색도 조건이 계단 오르기 전과 오른 후에 연속해서 한 계단씩 오르는 조건이 달라서 코드가 지저분해졌다. 맞게 구현했는지도 솔직히 모르겠다. 두 가지 가능성에 대해서 TC로 돌려봤는데 생각하는데로 나오기는 했는데.

[완전 탐색]

#include <iostream> int max = -1; bool first = true; #ifdef TEST_BY_TC int N = 6; int data[302] = {0, 10, 20, 15, 25, 10, 20}; //int data[302] = {0, 5, 30, 30, 5, 20, 30}; #else int data[302]; int N; #endif void f(int d, int c, int v) { //std::printf("d = %d, c = %d v = %d, data = %d \n", d, c, v, data[d]); if(d == N+1) { if(max < v) { max = v; } std::cout << "arrived ." << std::endl; return; } if(d > N+1) { std::cout << "out of range" << std::endl; return; } // 계단을 오르기 전의 경우 대응 if(c == 3 && first == true) { std::cout << "continuous _1 ." << std::endl; first = false; return; } // 계단을 오른 후에 경우 대응 if(c == 2 && first == false) { std::cout << "continuous 1 ." << std::endl; return; } f(d+1, c+1, v + data[d]); f(d+2, 0, v + data[d]); } int main() { #ifndef TEST_BY_TC int n; std::cin >> n; N = n+1; for(int i = 1; i < N; i++) { std::cin >> data[i]; } #endif f(0, 0, 0); std::cout << "max : " << max << std::endl; return 0; }

2. DP 코드

처음에는 완전 탐색에서 더 탐색하지 않아도 되는 가지를 쳐 낼려고 했는데, 아무리 노력해도 되지 않아서 풀이를 찾기 시작했다. 풀이나 코드를 보고도 이해가 잘 안되었는데, 딱 이해를 할 수 있도록 정리하신 분이 있다.

따라서 아래 링크를 걸어 둔다.

[DP Code]

#include <iostream> int stair[301]; int dp[301]; int main() { int N; std::cin >> N; for(int i = 0; i < N; i++) { std::cin >> stair[i]; } dp[0] = stair[0]; dp[1] = std::max(stair[0] + stair[1], stair[1]); dp[2] = std::max(stair[0] + stair[2], stair[1] + stair[2]); for(int i = 3; i < N; i++) { dp[i] = std::max(dp[i-2] + stair[i], dp[i-3] + stair[i-1] + stair[i]); } std::cout << dp[N - 1] << std::endl; return 0; }

[출처] http://kwanghyuk.tistory.com/4

1. 소스 코드

백준 https://www.acmicpc.net/problem/1932 문제 정리. 

처음에는 Tree로 착각해서 Tree를 배열로 변환해서 처리하는 Heap 구조를 많이 생각했는데, 이상한 쪽으로 빠져서 해메다가 다른 분들이 푼 풀이를 보고 나름 정리했다.

입력을 받으면서 처리하도록 하여 메모리 사용을 최소화했다.

#include <iostream> int max = -1; int sum[501][501]; int main() { int N; int data; std::cin >> N; // get root value std::cin >> data; sum[0][0] = data; for(int y = 1; y < N; y++) { for(int x = 0; x <= y; x++) { std::cin >> data; if(x == 0) { sum[y][x] = sum[y-1][x] + data; } else if(x == y) { sum[y][x] = sum[y-1][x-1] + data; } else { sum[y][x] = std::max(sum[y-1][x-1], sum[y-1][x]) + data; } if(max < sum[y][x]) { max = sum[y][x]; } } } std::cout << max << std::endl; return 0; }

2. 동작

정상동작

1. 소스 코드

백준 https://www.acmicpc.net/problem/1149 문제 정리. 완전 탐색으로 풀었을 때, 비교하나 잘 못해서 3일동안 뻘짓.

다행히 고마우신 분이 힌트를 주어서 해결. DP 문제라고 구지 분류하니까 너무 복잡하게 생각했는데 단순하게

생각하면 이해하기 어렵진 않았다.

완전 탐색 시에는 O(N^2)의 복잡도와 메모리는 문제에서 데이터 입력량만큼 늘어난다. 하지만 완전 탐색이 아닌 접근법으로 구현 시에는 복잡도는 O(N)으로 보이고 메모리는 데이터 입력량에 Constant이다.

[완전탐색]

#include <iostream> unsigned int data[1001][3]; unsigned int min = 0xFFFFFFFF; int n; void f(int c, int d, unsigned int v) { if (d == n) { if (min > v) { min = v; } return; } for (int i = 0; i < 3; i++) { if (i != c) { f(i, d + 1, v + data[d][i]); } } } int main() { std::cin >> n; for (int i = 0; i < n; i++) { std::cin >> data[i][0] >> data[i][1] >> data[i][2]; } f(-1, 0, 0); std::cout << min << std::endl; return 0; }

[일반적인 내 수준에서 풀이 시]

#include <iostream> int main() { int n; int a, b, c; int minA, minB, minC; int prevMinA = 0, prevMinB = 0, prevMinC = 0; std::cin >> n; for (int i = 0; i < n; i++) { std::cin >> a >> b >> c; minA = std::min(prevMinB, prevMinC) + a; minB = std::min(prevMinA, prevMinC) + b; minC = std::min(prevMinA, prevMinB) + c; prevMinA = minA; prevMinB = minB; prevMinC = minC; } std::cout << std::min(std::min(minA, minB), minC) << std::endl; return 0; }

2. 실행결과

두 개 백준 사이트에서 돌렸을 때, 잘 동작하였다.

1. 소스 코드

백준 https://www.acmicpc.net/problem/1924 문제로 규칙 찾기 중에서 2007년도 특정 월/일에 대해서 요일을 출력하는 문제. 계속 틀려서 달력도 출력해 보았다. 구글 출제 문제에 외계 행성의 달력 찍기 문제가 있어서 여기에 정리하면 유사 문제 출제 시 다시 Remind할 수 있을 것 같다.

#include <iostream> #include <string> enum week { SUN, MON, TUE, WED, THU, FRI, SAT }; std::string weekString[] = {"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"}; int day[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; void displayWeeks() { int m = 1; int d = 1; int p = 1; while(m <= 12) { std::printf("\n\n ------ %d 월 -------\n", m); if(p != 1) { int r = p; for(int i = 0; i < r - 1; i++) { std::printf("%2s ", " "); } } while(d <= day[m]) { std::string s = std::to_string(d); std::printf("%2s ", s.c_str()); if(p % 7 == 0) { std::printf("\n"); p = 1; } else { p++; } d++; } d = 1; m++; } } int main() { int m; int d; int index; int days = 0; displayWeeks(); std::cout << std::endl; std::cin >> m >> d; for(int i = 1; i <= m; i++) { days += day[i-1]; } days += d; index = days % 7; std::cout << weekString[index] << std::endl; return 0; }

2. 실행결과

달력 찍고, 특정 월/일에 대한 요일 출력. 가장 왼쪽이 일요일이면 완벽한 달력인데, 아쉽게도 가장 왼쪽이 월요일이다.

이 정도에서 마무리한다.

 ------ 1 월 -------

 1  2  3  4  5  6  7

 8  9 10 11 12 13 14

15 16 17 18 19 20 21

22 23 24 25 26 27 28

29 30 31

 ------ 2 월 -------

          1  2  3  4

 5  6  7  8  9 10 11

12 13 14 15 16 17 18

19 20 21 22 23 24 25

26 27 28

~~ 중략

 ------ 12 월 -------

                1  2

 3  4  5  6  7  8  9

10 11 12 13 14 15 16

17 18 19 20 21 22 23

24 25 26 27 28 29 30

31

12 2

SUN

1. 소스 코드

ZigZag Scan은 MPEG에서 DCT 후에 수행되는 매우 중요한 동작 중에 하나이다. 대학원에 있을 때, 

교수님이 과제를 내 주었던 것 같은데, 남이 해 놓은 거 배껴서 냈는데 이제 해 보려니 잘 안되네.

해보게 된 동기는 https://www.acmicpc.net/problem/1193 <분수찾기> 문제를 풀다보니 의욕이 생겼다.

다음 블로그를 보니 잘 짜 놓은 신듯 http://kama1204.tistory.com/m/112

다만 위의 블로그의 대략적인 복자도는 O(N^2) 인 것으로 보인다. 아래 내가 짠 소스는 어찌하다 보니

O(N)으로 만들어진 것 같다.

#include <iostream> #define N 8 int array[N][N]; void display() { std::printf("\n"); for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { std::printf("%2d ", array[i][j]); } std::printf("\n\n"); } } void zig_zag_scan() { int n = 1; int x = 0; int y = 0; for(int idx = 0, d = 1; idx <= 2*(N-1); idx++, d *= (-1)) { if(idx <= N-1) { if(d == 1) { y = idx; x = idx - y; } else { x = idx; y = idx - x; } } else { if(d == 1) { x = idx - (N-1); y = idx - x; } else { y = idx - (N-1); x = idx - y; } } //std::printf("%d, %d, %d, %d, \n", idx, x, y, d); for(; x >= 0 && y >= 0 && x < N && y < N; x = x + d, y = y - d) { array[y][x] = n++; } } } int main() { zig_zag_scan(); display(); return 0; }

2. 실행결과

3X3 행렬에 대한 동작이다. 다른 값에 대해서도 잘 동작한다.

대만에서 쓴 논문을 보니 ZigZag Scan을 FPG로 속도 개선하기 위해서 쓴 논문도 있었던 것 같다.

 1  2  6 

 3  5  7 

 4  8  9 

3. 소스 코드

달팽이 Scan도 도전해 보았다.

void snail_scan() { int x = 0; int y = 0; for(int i = 0, idx = 0; i < N*N; idx++) { for(x = idx, y = idx; x < (N - idx) ; x++) { array[y][x] = ++i; //std::printf("1. %d, %d, %d \n", x, y, i); } for(x = x - 1, y = y + 1; y < (N - idx) ; y++) { //std::printf("2. %d, %d, %d \n", x, y, i); array[y][x] = ++i; } for(x = x - 1, y = y - 1; x >= idx ; x--) { //std::printf("3. %d, %d \n", x, y); array[y][x] = ++i; } for(x = x + 1, y = y - 1; y > idx ; y--) { array[y][x] = ++i; } } } int main() { //zig_zag_scan(); //vertical_scan(); snail_scan(); display(); return 0; }

4. 실행결과

 1  2  3  4  5 

16 17 18 19  6 

15 24 25 20  7 

14 23 22 21  8 

13 12 11 10  9 

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