Dolphins의 HelloWorld

문제링크 : https://www.acmicpc.net/problem/9466 생각보다 푸는데 어려움을 느꼈던 문제이다. 원래 DFS를 푸는 방식을 조금 변형할 필요가 있다. 예를들어 1 -> 3 , 3 -> 5, 5 -> 3 이라고 가정할 때 기존의 방법대로 탐색을 하면 1 -> 3 -> 5 에서 5의 다음 노드가 3이고 3은 이미 지나간 노드이기 때문에 이제 처리를 해야한다. 여기서 이 문제만의 독특한 점은 이 탐색 안에서 따로 cycle을 찾아야한다는 것이다. 그러니까 위의 예시로 치면 3 -> 5 -> 3을 발견해야하며 숫자가 많아질 수록 복잡해질 것이다. cycle을 어떻게 찾을까에 대해 생각해보면 명확한 점은 한번씩 탐색을 한 다음 이미 지나간 노드라고 처음 인식한 지점이 실제 cycle의 첫..

문제 링크 : https://www.acmicpc.net/problem/2331 수열중에서 만약 새로 나온수가 이전에 나온수와 하나라도 같게되면 무조건 반복될 것이기 때문에 나는 일단 map함수를 사용하여 새로 나오는 수를 key, 누적 갯수를 value로 해서 수열의 숫자가 누적 갯수를 함께 가지고 있도록 하였다 그래서 만약 같은 숫자가 나온다면 그 숫자가 가지고있는 value에서 -1한 값을 결과값으로 내놓도록 하였다 #include #include using namespace std; int pow(int x, int p) { //각 자릿수를 p만큼 곱하도록 하는 함수 int ans = 1; for (int i = 0; i < p; i++) { ans = ans * x; } return ans; }..

문제링크 : https://www.acmicpc.net/problem/10451 #include #include using namespace std; int arr[1001]; bool check[1001]; int point; //맨 처음 cycle이 시작한 시작점 저장 bool DFS(int start) { check[start] = true; int next = arr[start]; if (check[next] == false) return DFS(next); //다음 노드가 탐색된 노드가 아니라면 탐색 else { //다음 노드가 이미 탐색된 노드일 때 if (next == point) return true; //시작 노드와 다음 노드가 같다면 cycle이 맞음 else return false; ..

Bipartite Graph 다음과 같은 성질을 가질 때 그 그래프는 Bipartite하다고 할 수 있다. 전체 vertex를 v1과 v2로 나누었을 때 -> v1노드끼리는 edge가 없음 -> v2노드끼리는 edge가 없음 -> v1과 v2와의 edge는 존재한다. v ∈ v1 , w ∈ v2 , (v,w) ∉ E 위의 그림에서 같은 집합의 노드끼리는 edge가 없는것을 쉽게 확인할 수 있다. 예를들어 다음과 같은 ring 형식의 그래프는 vertex가 홀수일 때는 Bipartite가 아니지만 , 짝수일 때는 Bipartite임을 알 수 있다. 이렇게 그래프가 Bipartite한지 아닌지는 DFS를 통해서도 판별할 수 있다. 다음의 문제를 통해 확인해보자. 확인을 위해 int check[]라는 배열을 ..

#include #include using namespace std; vector arr[1001]; bool check[1001]; void DFS(int start) { check[start] = true; for (int i = 0; i < arr[start].size(); i++) { int next = arr[start][i]; if (check[next] == false) DFS(next); } } int main() { int N, M; int u, v; scanf("%d %d", &N, &M); while (M--) { scanf("%d %d", &u, &v); arr[u].push_back(v); arr[v].push_back(u); } int count = 0; for (int i = ..

문제링크 : https://www.acmicpc.net/problem/1377 먼저 이 문제에서 출력하고자하는 i가 무엇인지에 대해 분석을 하면 버블소트를 하면서 정렬이 된 시점을 말한다는 것을 알 수 있다. 즉 버블소트로 1번 돌렸더니 정렬이 다 된다면 i = 1, 2번 돌렸더니 정렬이 다 된다면 i = 2가 되는것이다. 어떻게 하면 버블소트를 돌리지 않고 i를 구할 수 있을까를 알아보기 위해 버블소트가 작동하는 과정을 한번 주목해서 보자 문제의 예제대로 한다면 10 1 5 2 3 i = 1 1 5 2 3 10 i = 2 1 2 3 5 10 이런식으로 최종 정렬이 되는데 우리가 알 수 있는것은 큰 숫자는 한번에 끝까지도 이동할 수 있지만 작은 숫자는 한번 버블소트가 돌 때 한칸씩밖에 움직이지 못한다는 ..

문제 링크 : https://www.acmicpc.net/problem/11004 sort함수를 쓰는 방법에 대해서만 알고 있다면 크게 어렵지 않은 문제이다. sort함수 사용법 : http://dolphins-it.tistory.com/108 #include #include #define SIZE 5000000 using namespace std; long long tmp[SIZE]; int main() { long long N, K; scanf("%lld %lld", &N, &K); for (int i = 0; i < N; i++) scanf("%lld", &tmp[i]); sort(tmp, tmp + N); printf("%lld\n", tmp[K - 1]); }

문제링크 : https://www.acmicpc.net/problem/11652 처음에 이 문제를 봤을 때는 받는 숫자와 그 수가 나온 횟수를 함께 저장한 후 계속 검사를 하면서 만약 새로운 수가 들어왔을 때 vector안에 그 숫자가 이미 있는지를 확인하고 만약 있다면 횟수를 늘리고 없다면 새로 vector안에 추가시켜주는 식으로 코드를 짜 보았다. #include #include #include using namespace std; struct Card { long long number; long long count; }; bool cmp(const Card &a, const Card &b) { if (a.count > b.count) return true; else if (a.count == b.c..

문제링크 : https://www.acmicpc.net/problem/10989 문제의 의도에 맞게 접근하지 않으면 메모리 에러로 틀리기 쉬운 문제이다. 이 문제의 핵심은 10000000개의 수를 sorting해도 제한된 메모리 안에서 처리를 하게 하는것이다. 고로 수를 받는대로 vector나 배열에 모두 집어넣고 sort를 시키면 안된다. 문제의 조건을 만족시키기 위해 가장 중요한점은 sorting할 숫자가 10000을 넘지 않는다는 것이다 그래서 나는 배열의 공간을 10000개를 주고 배열값을 0으로 설정한 후 들어오는 숫자에 해당하는 배열 값을 증가시키는 방법을 택하였다.(예를들어 num이라는 숫자가 들어오면 arr[num]++을 해준것이다.) #include #include using namesp..

문제링크 : https://www.acmicpc.net/problem/10814 #include #include #include #include using namespace std; struct Person { int age; //나이 string name; //이름 int number; //순서 }; bool cmp(const Person &x, const Person &y) { if (x.age < y.age) return true; //나이순으로 정렬 else if (x.age == y.age)//나이가 같다면 번호순으로 정렬 return x.number < y.number; else return false; } int main() { int number = 1; Person p; vector v;..