Hoon222y

문제를 간단하게 정리하자면 친구관계로 묶여 있는 그래프가 있는데 그 그래프에서 모든쌍의 최단거리를 구하는 문제이다그래프끼리의 간선의 가중치는 같다고 본다. 가중치가 다르다면 다익스트라 방식으로 접근해야 할 것이다.플로이드 머셜에 대한 내용은 다음시간에 정리하는것으로 보고 이번시간에는 이 문제를 접근하는 방식에 대해서 먼저 생각해보도록 하자 그래프 내에서 각 간선들의 가중치는 같고 그 그래프 내에서의 모든쌍의 최단경로를 구하는 문제의 경우에는 플로이드 머셜 알고리즘을 사용하는데 알고리즘의 중요부분은 다음과 같다. for(int k=1;k

문제가 길어서 .... 문제를 짧게 설명하자면 책의 번호가 저렇게 정렬되어 있는데 순서대로 정렬을 할 때 최소의 노동력으로 정렬할 때 그때의 최소 노동력을 구하는 것이다.이번 문제의 경우도 해매고, 해매고 ... 이 문제는 LIS알고리즘을 활용 한 것 이라는데 Longest increasing Subsequence 알고리즘으로 이 문제의 포인트는 최소한의 노동력 = 전체값 - 그대로 두는 노동력의 최대값이라고 볼 수 있다는 것이다.대략의 과정을 설명 하자면 앞에서 부터 시작을 한다. 813.8을 마지막으로 하는 정렬된 수열은 당연히 하나이므로 절약할 수 있는 노동력은 6이다.그 다음 812의 경우에는 812보다 작은 수가 없으므로 6 혹은 자기 자신의 노동력 20 중 그대로 두는 노동력이 큰 20이 저장..

그렇다 .. 처음 접근 했을때 ... 못풀었다 ㅋㅋㅋㅋㅋㅋㅋ 처음에 접근 방식을 완전 탐색? 뭐 이렇게 생각을 했었는데 전에 문해기 시간 때 했던 DP와 비슷한 접근이었다. 이 유형의 문제가 DP의 2가지중 하나의 대표적 유형이라고 한다.(힙색이었나? 배낭DP라고 했던듯 ...)일단 내 코드다. #include#include using namespace std; long long arr[100001];long int dp[100001]; int main(){ int num; int weight; memset(dp,0,sizeof(dp)); memset(arr,0,sizeof(arr)); cin >> num >> weight; for(int i=1;i> a >> b; arr[i] =a*1000000LL+b..

예전에도 한번 풀어봤던 문제이다. 방학때 공부하는 책 한권을 완성하기 위해 다시 풀어보는 과정중에 next_permutation을 사용하여 접근을 해보았다. #include//#include #include#include#include using namespace std; int arr[56];int answer;int stuNum;int setNum;bool gett[56];vector v;vector::iterator iter; int check(int a){ for(int i=0;i> testCase; //scanf("%d",&testCase); // next_permutation 쓸꺼임 while(testCase--){ answer =0; memset(gett,true,sizeof(gett)); ..

123456789#include #include using namespace std; int main(){ char a; scanf("%c", &a); printf("%d" ,a);}cs

vector를 공부하면서 iterator에 대해 정확히 정리를 하지 못해서 넘어 갔었는데 포인터 비슷한개념인것 같은데 딱히 차이점을 알지 못했다 . 그래서 검색을 해보았는데 역시나 .. 나같은 사람이 있었다 .ㅎㅎ 이렇다고 합니다 ㅎㅎ

next_perutaion 의 경우에는 vector 내에서 순열적인 결과를 얻기위해 사용하는 방법이다. 예를들어 vecotr내에 1 2 3 이라고 저장이 되있었다면 next_permutation을 통해 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1 이런 결과를 얻을 수 있는것이다. 그럼 간단한 소스코드를 보도록 하자. do while문 안에 하고싶은 연산을 넣어주고 while문에서 범위를 지정해주는 형식이다. 여기서 주의해야할 점은 바로바로 next_permutation 을 사용하기 위해서는 백터내에 숫자들이 정렬이 되어있어야 한다는 점이다. 그런데 사용하다보니 궁금한점이 있는데 해결이 안된다 .. 처음에 for 문안에 0을 안넣고 1을 넣으니까 오류가 생긴다 .. 왤까 .... xcode..

1. Vector의 자료구조와 특징 번호와 번호에 대응하는 데이터로 이루어진 자료구조로 배열과 유사하다, 배열의 크기는 고정이지만, vector의 크기는 동적으로 변한다는 차이점을 가진다. - 중간에 데이터 삽입, 삭제가 용이하지 않다. - 데이터를 순차적으로 저장한다. (검색 속도가 느리다, 랜덤 접근이 용이하다) 2. Vector를 사용해야 하는 경우 - 중간의 데이터 삽입이나 삭제가 없을 경우 - 순차적으로 저장된 데이터를 빈번하게 검색하지 않을 경우 - 특정 데이터가 저장된 위치를 파악하여 랜덤 접근 할 경우 - 순차접근은 list, vector 모두 유리하지 않고 (map, set이 유리) - 랜덤접근을 사용할 경우 list 보다 vector를 사용하는게 유리하다. - 데이터 중간에 삽입, 삭제..

문제해결기법 수업 동맹(Alliance)문제이다.주어진 문제를 풀기위해 진짜 .... 20시간정도를 투자하였는데 ..... 결국 못풀고 어쩌다보니 Union-Find 자료구조를 알게 되었다.자세한 참고는 이곳을 통하여 배우게 되엇다. (http://blog.secmem.org/521) 일단 나의 방식으로 설명하자면 트리의 구조이다.다른 트리와 다른점이 있다면 트리간의 연결성, 즉 같은 그룹안에 속해있는지 아닌지를 판별하는데 아주 좋은 자료구조라고 볼 수 있다.Union_Find 자료구조를 구성하기 위한 기본 3가지 함수이다.init 함수는 맨처음 자기자신을 head로 하는 n개의 트리를 각각 만드는 것이다.find함수는 각각의 그룹이 어떤 그룹에 속해 있는지 head를 반환해주는 함수이다.unite함수는..

소풍을 가는데 싸우지 않기위해 친구끼리만 짝지어줄 수 있는 방법의 수를 출력하는 문제였다 . 내가 고민했던 방법은 2 가지였다. 1) 각각의 짝들을 하나의 수로 바꾸어 배열에 저장한 후 재귀적으로 반복하면서 겹치는 숫자가 없게하는 방법 . - 설명이 애매하네 .. 나중에 파일 찾아볼 것. 그런데 구현하는 과정에 for문을 학생수 만큼 반복해야하는데 그걸 동적으로 구현하지 못하여 포기2) 책에나온것처럼 재귀적으로 확인 - 결국 이걸로 풀긴 했는데 문제가 애매하다 .... 내가 짠 코드에서는 예제가 하나 틀리게 나오는데 정답처리가 되버렸다 ... 일단 내가 작성한 코드를 분석해보도록 하자.재귀함수 부분만 보도록 하자. 나머지 부분은 그냥 횟수에 관한 코드이므로 .....일단 전역변수로 학생의 1차원배열, 학..