Algorithm

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 32 33 #include <iostream> #pragma warning(disable:4996) using namespace std; int main(void) { int num, tmp, cnt = 0; cin.tie(NULL); ios_base::sync_with_stdio(false); #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif cin >> num; tmp = num; do { tmp = ((tmp % 10) * 10) + (tmp%10 + tmp/10)%10; cnt++; } while (tmp != num); cout << cnt; #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; }

제목 재밌네 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 #include <iostream> #include <vector> #include <algorithm> #include <iomanip> #pragma warning(disable:4996) using namespace std; int main(void) { int num, casenum, score, cnt; double sum, avg; vector<int> arr; vector<int>::iterator it; cin.tie(NULL); ios_base::sync_with_stdio(false); #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif cin >> num; for (int i = 0; i < num; i++) { cin >> casenum; sum = 0; arr.clear(); avg = 0; cnt = 0; for (int j = 0; j < casenum; j++) { cin >> score; arr.push_back(score); sum += score; } avg = sum / casenum; for (it = arr.begin(); it != arr.end(); it++) { if ((*it) > avg) cnt++; } cout << fixed << setprecision(3); cout << (double)cnt/casenum*100 << "%\n"; } #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; }

요즘 다시 시작한 알고리즘 공부.. 쉬운거 부터 풀어 봅시다 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 32 33 34 35 36 37 38 39 40 41 42 43 #include <iostream> #include <vector> #include <algorithm> #include <iomanip> #pragma warning(disable:4996) using namespace std; int main(void) { int num, max, score; double sum = 0; vector<int> arr; vector<int>::iterator it; cin.tie(NULL); ios_base::sync_with_stdio(false); #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif cin >> num; for (int i = 0; i < num; i++) { cin >> score; arr.push_back(score); } max = *max_element(arr.begin(), arr.end()); for (it = arr.begin(); it != arr.end(); it++) { sum += (*it) / (double)max * 100; } cout << fixed << setprecision(2); cout << sum / num; #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; }

중요한 간선을 찾는 코드에서 prev2[next2.to] 가 되어있어야 하는데 prev2[curr2]로 되어 있는 것을 발견하지 못해 푸는데 오래 걸린 문제이다. 중요한 간선의 여부는 최대유량은 찾은 후에 입력 간선들 중에 u->v로 유량을 흘릴수 없는 경우 중요한 간선이라고 판단하였다. ...

시간초과가 계속해서 나는 것은 최적화 하면서 근근이 풀긴했는데, 속도가 많이 느리다. 자바로 풀 사람들 중에서 꼴등임 ㅎ 다른 정답자들의 풀이를 보니, 나는 에드몬드 카프 알고리즘을 이용해 풀었지만 빠르게 푼 사람들은 “디닉 알고리즘"이라는 것을 이용해서 풀었다. ...

어제 못 풀고 오늘에서야 푼 문제 정점을 1번만 지나는 조건을 만족하기 위해 정점을 분할하고 분할된 정점사이에 용량의 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 /** * */ import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.StringTokenizer; /** * @author jaeji * */ class edge{ int to; int flow; int cap; edge rever; edge(){ this(0,0,0,null); } edge(int ar_to, int ar_flow, int ar_cap, edge ar_rever){ to = ar_to; flow = ar_flow; cap = ar_cap; rever = ar_rever; } int residu() { return cap-flow; } void addflow(int ar_flow) { flow+=ar_flow; rever.flow -=ar_flow; } } public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) ); //BufferedReader br = new BufferedReader( new FileReader("input.txt" ) ); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int[] prev = new int[402]; ArrayList[] adj = new ArrayList[402]; Queue<Integer> q = new LinkedList<Integer>(); int total = 0; for(int i=0;i<402;i++) { adj[i] = new ArrayList<edge>(); } for(int i=0;i<n;i++) { edge temp_edge = new edge(i,0,1,null); edge temp_rever_edge = new edge(400,0,0,temp_edge); temp_edge.rever = temp_rever_edge; adj[400].add(temp_edge); adj[i].add(temp_rever_edge); } for(int i=200;i<200+m;i++) { edge temp = new edge(401,0,1,null); edge temp_rever_edge = new edge(i,0,0,temp); temp.rever = temp_rever_edge; adj[i].add(temp); adj[401].add(temp_rever_edge); } int no = 0; int temp = 0; for(int i=0;i<n;i++) { st = new StringTokenizer(br.readLine()); no = Integer.parseInt(st.nextToken()); for(int j=0;j<no;j++) { temp = Integer.parseInt(st.nextToken())+199; edge temp_edge = new edge(temp,0,1,null); edge temp_rever_edge = new edge(i,0,0,temp_edge); temp_edge.rever = temp_rever_edge; adj[i].add(temp_edge); adj[temp].add(temp_rever_edge); } } int curr = 0; edge next = null; int S = 400; int E = 401; while(true) { edge[] path = new edge[402]; Arrays.fill(prev, -1); q.clear(); q.add(S); curr = 0; next = null; while(!q.isEmpty()) { // 소스에서 흐를수 있는 유량찾기 curr = q.poll(); for(int i=0;i<adj[curr].size();i++) { next = (edge) adj[curr].get(i); if(next.residu() > 0 && prev[next.to] == -1) { q.add(next.to); prev[next.to] = curr; path[next.to] = next; if(next.to == E) break; } } } if(prev[E] == -1) break; // 경로를 탐색 한 후 싱크로 가는 경로가 없는 경우 for(int i=E;i!=S;i=prev[i]) { path[i].addflow(1); } total += 1; } System.out.println(total); } }

주어진 두 정수 범위내의 소수를 구하는 문제입니다. 에라토스테네스의 체 라는 것을 사용해 구합니다. 개념적으로 주의해야 할 것은 소수 판별하는 것과 다릅니다. 에라토스테네스의 체 는 특점 범위의 소수를 구할때 쓰는 알고리즘입니다. ...

주어지는 수들 중에서 소수의 개수를 출력하는 문제입니다. 소수를 판별하는 가장 기초적인 방법인 2~n-1 까지 나눠지는지 확인해서 판별하면 됩니다. 또한 $$\sqrt{n}$$ 까지 나눠지는 약수가 없으면 소수 라는 성질을 이용해 계산량을 줄일 수 있습니다. ...

두 자연수의 최대 공약수와, 최소 공배수를 출력하는 문제입니다. 유클리드 호제법을 이용해 최대공약수를 구하고 최대공야수를 이용해 최소 공배수를 구하면 됩니다. 최소 공배수만 구하라고 하는 경우에도 최대공약수를 구하여 최소공배수를 구하는 것이 쉽습니다. ...