[1. TCP : echo_client.c / echo_server.c]

<echo_client.c>

<echo_server.c>

<터미널 실행 결과 화면>

서버

클라이언트

tcp 통신의 한계 : 한개의 server는 multiple client와 동시에 통신할 수 없음.

첫번째 클라이언트와 서버가 통신하고 있고, quit 를 하지 않은 상태에서 두번째 클라이언트가 서버에 메세지를 보내면 다시 send back 되지 않는다. (아직 첫번째 클라이언트와 통신하고 있으므로)

> 첫번째 클라이언트가 q 를 눌러서 통신을 종료하면 즉시 두번째 클라이언트에 아까 보냈던 메세지가 send back 되어서 출력된다.

[2. UDP : uecho_client.c / uecho_server.c]

<uecho_server.c>

<uecho_client.c>

<UDP — multiple host 와 커넥션>

• 클라이언트와 서버 역할이 아니라 서로 Host이고 서로 interaction 한다.
• TCP 에서의 문제가 여기서는 발생하지 않는다. ( connectionless)

[3. TCP : op_server.c / op_client.c]

• Really network based application.
• Remote data processing where a client will be making use of the server

<op_client.c>

<op_server.c>

<터미널 결과>

• 클라이언트 자체 내에서 계산한 것이 아니라 클라이언트가 서버에 opeartion을 보낸 후 계산된 결과를 받는 network based application 이다.

• connect 한 다음에 서버쪽에서 ctrl+c로 종료한 다음, 클라이언트에서 opeartion을 수행하면 result 가 0이 나온다. 서버가 응답하지 않았기 때문이다. (trash value)

[4. UDP : bound_host1.c / bound_host2.c]

• Host2에서 Host1으로 msg1, msg2, msg 3를 보낸다.
• Host1에서는 메세지를 받을때마다 5초를 delay 시킨다.

<bound_host1.c>

<bound_host2.c>

• TCP 방식이었다면 delay 해도 host1에서 msg1,msg2,msg3가 한번에 출력되었을 것이다.(data stream)
• 그러나 UDP 방식은 Datagram 형식으로 메세지를 보내므로 5초마다 msg1, msg2, msg3 가 차례로 출력된다.

참고 : 유투브 — 센치한 개발자

목표 : Handler 와 Runnable 를 이용하여 카운트 다운을 만들어 보자.

• xml 파일에는 id 만 추가해주자.

• 1에서 5까지 1초마다 한 번씩 카운트가 증가한다.
• line 19 : count 가 int 형이므로 count 뒤에 [+ “” ] 를 덧붙여주었다.
• line 36에서 post() 를 하면 line17 이 실행된다. 처음 count 변수를 0으로 초기화했으므로 run() 이 실행되면 1이 되면서 count가 5가 될 때까지 1초에 1씩 증가한다.

빌드를 해 보면 1에서 5까지 증가하고 멈춘 것을 확인할 수 있다.

참고)

<Process>

: 실행중인 프로그램의 객체. Android에서 앱을 실행하면 하나의 Process가 실행되고 MainActivity의 코드와 데이터를 메모리에 올린다.

<Thread>

: Process 안에서 코드를 실행시키는 객체. 하나의 Process 안에 여러개의 Thread가 있을 수 있다. (Multi Thread => 효율성 향상)

Process가 처음 시작되고 Thread를 처음 가지게 되는데, 이를 MainThread(UI Thread) 라고 한다. 이 위에서 작업량이 많아지면 ANR(Application Not Responding) 에러가 발생한다. 이를 위해 Worker Thread를 사용해야 한다.(멀티 스레드)

<Runnable>
: Thread 가 실행(run)해야하는 코드

<Handler>

: Worker Thread 에서 Main Thread 로 메세지를 전달하는 역할. post 를 통해 전달된 runnable 객체는 해당 handler 가 연결된 Thread 에서 실행된다.

참고 — https://brunch.co.kr/@mystoryg/84 , https://developer88.tistory.com/72

참고 : 유투브 — 센치한 개발자

• Firebase : 클라우드. 웹과 모바일 개발에 필요한 기능을 제공해주는 BaaS(Backend as a Service).

[1. Firebase 셋팅하기]

• https://firebase.google.com/docs/ml-kit/detect-faces 에 접속하여 로그인을 한다.

• 콘솔로 이동 > 프로젝트 생성

• 안드로보이 클릭

• 패키지 이름은 아래 화면과 같이 AndroidManifest.xml에서 가져온다. (line 3)

• 다운 받은 파일을 지정된 위치에 복사+붙여넣기 한다.

• 앱 수준의 bundle gradle — 위 쪽 파일 / 프로젝트 수준의 bundle gradle — 아래 쪽 파일

• 참고 : https://console.firebase.google.com/project/ny-face/overview

classpath 'com.google.gms:google-services:4.3.3'

를 종속성에 추가한다. (line 12)

• line 47, 52,53 을 추가하고 Sync Now 를 클릭한다.

• 참고 : https://firebase.google.com/docs/ml-kit/android/detect-faces
• ML KIT : 인공 지능의 한 분야로, 컴퓨터가 학습할 수 있도록 하는 알고리즘과 기술을 개발하는 분야이다.

• line 49~52 추가

• line 26~28 추가
• Sync Now 클릭

• real time mode -> 셀카 촬영 모드에서 바로(실시간으로) 얼굴을 인식할 때 쓰면 좋을것이다.
• 우리는 사진으로 얼굴을 인식할 예정이므로 위의 ‘high accuracy’ 를 쓸것이다.

[2. Face Detector 구성]

액티비티 파일을 생성하고 이와 연결할 xml 파일도 생성한다.

• 예제 코드를 복사하여 사용할 클래스(액티비티) 를 새로 생성한다.

• 액티비티와 연결할 xml 파일도 하나 생성한다.

• scaleType : 이미지가 정해진 레이어보다 커서 넘쳤을 때 어떻게 해결할건지를 정의한다.
• adjustViewBounds : 이미지의 종횡비가 깨지는 것을 허용할 것인지 아닌지 정한다. 값이 true 이면 허용하지 않을 것이라는 의미이다. (비율을 유지할 것)
• 기본 이미지 위에 다른 이미지들을 겹쳐서 올리는 것이므로 RelativeLayout 을 사용한다.

• 코드를 긁어서 붙여넣기한 후 class 를 import 한다. (alt + enter)

[3. Face Detector 실행]

머신러닝을 실행하려면 fire base 에게 Image 를 던져줘야한다.

참고 : https://firebase.google.com/docs/ml-kit/android/detect-faces

• line 34 : FirebaseVisionImage 객체를 만든다.
• line 36,37 : FirebaseVisionFaceDetector의 인스턴스를 가져온다.
• line 39~56 : 이미지를 detectInImage 메소드에 전달한다.

[4. 감지된 얼굴에서 데이터 정보 얻기]

• line 51~81 : 에 복사한 코드를 추가해준다.

[5. 이미지 리소스 파일을 코드로 가져오기]

• line 31~36 : fire base 설정한 부분. 이 fire base 에게 bit map 사진을 던져주면 분석을 한다.
• bitmap 사진을 던져보자. => 어디에?

• src 로 받아 온 이미지(lien 19)를 bitmap 으로 옮겨오는 과정이 필요하다. (이미지 출처 — https://kplog.tistory.com/186?category=754033)

• res 아래에 drawable-xxhdpi 디렉토리를 새로 만들어서 다운받은 이미지 파일 네개를 넣어준다.
• Context : 앱의 기능들을 자유롭게 사용하기 위한 매개체. 전역 변수로 선언해준다.
• faces 인 이유 : 이미지에 얼굴이 여러개인 경우 For 문을 돌면서 찾기 위해 => 그 찾는 정보를 보기 위해 Log 를 찍어보자. => json 에 얼굴 정보들이 들어있다.
• Landmark — 얼굴의 눈,코,입,볼 등의 정보
• 이렇게 얻어온 Landmark 의 좌표에 멍 사진과 고양이 수염 사진을 넣으면 된다.

위치 정보 빼오기

• png 파일을 ImageView 로 직접 가져와서 써도 되지만 이러면 사진을 추가할 때마다 xml 파일을 변경해야하는 불편함이 있다. 또한 멍 사진과 고양이 수염 사진 뿐 아니라 추후에 더 많은 사진들을 추가할 것을 대비하여 이미지 뷰를 가상으로 만들어 이용하는 방법으로 코딩해보자.
• line 5 : 스티커(이미지)는 사진 위에 겹치게 보일 예정이므로 부모인 RelativeLayout에 이름을 지정하여 붙일 예정이다.

• line 13 : RelativeLayout 위에 스티커를 붙일 것이므로 findViewById로 가져온다. (final 로 선언 한 이유 : 본인은 오류가 final 을 안 붙여도 오류가 나지 않았으나 강의에서는 범위로 인해(중괄호 바깥에 선언을 해서) 오류가 발생했음. 이를 해결하기 위해 값이 변하지 않고 그대로라는 뜻의 final 을 써줘야함.)
• line 39 : 초기화
• line 81,85,89 : 가상이미지를 통해 스티커를 붙였다. (imageCL 은 imageLC로 고쳐야함. 오타임.) => 이제 붙인 스티커를 위에서 getPosition으로 받은 좌표 위로 옮기면 된다.
• 디스플레이 사이즈와 불러온 이미지 사이즈의 포인트 위치가 안드로이드 해상도 문제로 인해 조금씩 틀어진다. => 계산식이 필요하다.

• 위에서 말했다시피, 스크린상의 좌표 (실제 좌표) 와 getPosition() 으로 얻어온 좌표와 사진 위치(R.drawable.sentilab) 사이의 계산식이 필요하다.
• 필요한 계산 식 : point * 랜드마크 좌표 / 비트맵(얼굴 사진)

• line 98 : imageLE의 크기를 바꾸자 => imageLE 가 속해있는 부모를 써야하므로 RelativeLayout 을 쓴 것이다.
• -100 이유 : x,y에 face detector가 알려주는 점이랑 이미지랑 위치가 안 맞다.

최종 결과

참고 : 유투브 — 센치한 개발자

참고 : 아래 사이트

firebase.google.com/docs/database

• NoSQL 은 json 형태를 기반으로 한다.

[1. 기본 설정하기]

implementation 'com.google.firebase:firebase-database:19.1.0'

를 앱 수준의 build.gradle 에 종속성을 추가한다.

• 콘솔로 이동한 후 좌측의 Database 를 클릭한다.
• 베타 버전인 Cloud Firestore 대신 Realtime database 만들기를 클릭한다.

• read, write 를 모두 true 로 하고 사용설정을 클릭한다.

• 안드로이드에서 저 프로젝트에 접근해서 json 데이터를 쌓을 것이며 이 데이터가 채팅 내용이다.

[2. 액티비티, xml 파일 생성]

• Empty Activity 를 생성하면 xml 파일도 동시에 생성된다.

• xml 파일을 위와 같이 수정해준다.

• AndroidManifest.xml 파일도 수정해준다. (이전 액티비티 삭제)

[3. 데이터 베이스에 쓰기]

• https://firebase.google.com/docs/database/android/start 로 이동.

• line 18~20을 복사 붙여넣기 한다.
• 위 링크 하단의 다음 단계>데이터 읽기 및 쓰기를 클릭한다. (링크 — https://firebase.google.com/docs/database/android/read-and-write)
• line 18 : 데이터 베이스를 선언하고 할당(생성)했다.
• line 19 : ny-face 데이터 베이스 밑에 “message” 가 없으니 “message”를 만든다.
• line 21 : message 밑에 “Hello World” 라는 내용이 들어간다.

• message 가 올라간 것을 확인할 수 있다.

[4. DTO 생성]

채팅 데이터를 주고 받는 DTO(Data Transfer Object) 부터 만들어보자.

• ChatData 을 생성한다.

[5. 어댑터 생성]

이제 ChatData 를 가져다가 값을 셋팅하는 Recycler의 어댑터가 필요하다.

• 위와 같이 코드를 타이핑한다.

[6. xml 파일 생성]

• 루트 LinearLayout이 vertical이므로 그 아래 weight 를 1로 다 가져간 RecyclerView의 height 는 0dp 이고, 그 아래 LinearLayout은 horizontal 이므로 weight를 1로 다 가져간 EditText의 width는 0dp 이다.
• onBindViewHodler에서 받아온 닉네임을 비교하여 메세지를 정렬한다. (상대 방의 메세지는 왼쪽에 나의 메세지는 오른쪽에)

[7. add 함수 생성]

• line 104 : 뉴스 앱을 만들 때에는 매번 실행할 때마다 새로운 데이터로 갱신됐는데, 채팅 앱은 메세지가 1건씩 추가될 때마다 뒤에 덧붙여야 하므로 add 하는 로직이 필요하다.
• line 105 : 데이터가 삽입되는 것의 변화를 위해 notifyItemInserted를 사용해야 한다.
• line 105 : add 를 하면 채팅 데이터 배열의 크기가 늘어나므로 그 사이즈를 활용해야 한다.

[8. 채팅 정보 셋팅]

• setValue를 하여 데이터를 넣을 때 ChatData Class 자체를 넣을 예정이다.
• line 47~50 : 이렇게 클래스를 넣기 시작하면 주의해야할 점이 있다. 우리가 처음에 “Hello World” 라는 스트링형을 데이터 베이스에 넣었기 때문에 에러가 난다. 그러므로 클래스를 넣기 전에 이미 올라가 있는 스트링 데이터를 지워야한다.

이제 리사이클러뷰의 어댑터에 가져온 채팅 데이터를 셋팅해야한다.

• line 51 : dataSnapshot = 채팅 데이터를 담고 있는 변수
• line 52 : 우리는 두번째 getValue() 를 쓸 것이고 괄호 안에 들어갈 클래스는 ChatData 클래스 이다.
• getValue(ChatData.class) : 또 다른 형태의 클래스를 넣은 적이 있다면 이때 오류가 난다.

• line 57 : 클래스 형 변환 필수!

[9. 전송 버튼 눌렀을 때 전송되게 하기]

• 채팅 내용을 입력한 후 전송 버튼을 눌렀을 때에 서버로 채팅 내용을 보내야 한다.
• line 32,33 : 변수 선언
• line 43,44 : xml 컴포넌트와 매칭
• line 46 : 버튼을 눌렀을 때 Button_send, EditText_chat 의 정보를 읽어서 서버로 보내야하므로 클릭 리스너 생성
• line 51 : 빈 칸은 서버로 보내지 않도록 null check.

[10. 중간 점검 & 오류 해결]

• line60~63 : 리사이클러 뷰 셋팅
• line 64 : 리스트 선언
• line 66~67 : 어댑터 셋팅
• line 69,70 : 데이터 베이스 접속 후 데이터 정보 가져옴
• line 72~75 : 채팅 데이터에 최초 데이터를 넣음

• line 76~80 : 내가 보낸 메세지면 오른쪽에(END), 상대방이 보낸 메세지면 왼쪽에(START) 배치한다.

그러나 이렇게 실행을 하면 오류가 발생한다.

• 데이터는 들어갔으나 앱은 실행되지 않았다.

로그화면

• 이유 : 데이터가 정상처럼 보이지만 구조가 맞지 않았다.

에러를 해결해보자.

• 초기 데이터 문제일 수도 있으므로 line 72~75를 주석처리했다.

• 데이터도 삭제하고 다시 빌드해보았다.

그러나 앱은 실행되지 않았다.

로그를 살펴보자.

오브젝트를 변환할 수 없다고 뜬다.

• line 71의 path 를 지우고 line 84,85를 주석처리 한 다음 Line 82와 같이 로그를 찍어보자.

• 들어간 데이터가 한 묶음이 아닌 따로 들어가서 (두 줄로 나옴) 오류가 나는 것으로 예상한다.

다시 해결해보자.

• Serialzable 을 지우고, setValue() 전에 push()를 해준다.

• 값이 정상적으로 짝을 이루어 들어간 것을 확인할 수 있다.

• 로그 값도 짝이 지어져 있는 것을 볼 수 있다.

• 주석 처리한 것을 풀고 다시 확인해보자.
• 추가로 nick1 에 대해서 닉네임과 채팅 내용을 모두 오른쪽 정렬 해 주자.

• line 78,82 를 추가해준다.

결과

[11. 새로운 단말기 빌드]

두번째 채팅방 접속자를 만들기 위해 새로운 단말기로 빌드해보자.

성공

추가)

• 지금 만든 앱은 새로운 접속자가 있을 때 마다 nick1,nick2,,, 이런 식으로 직접 바꿔줘야한다.
• 그러나 랜덤 채팅 혹은 정해진 사용자만을 원할 때는 저번에 배운 로그인 화면을 이용한다던가 firebase의 authentication 의 로그인 기능을 이용할 수도 있다.
• 현재는 가장 처음에 read, write 를 true 로 해주어 아무나 접속이 가능하지만, 이를 false 로 바꾸면 그게 불가능하다.

문제 링크 : www.acmicpc.net/problem/1707

문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.

출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

접근 방법

연결 그래프와 비연결 그래프 두 경우를 생각해야한다.

1번노드부터 V번노드까지 BFS를 돌린다. 그래야 연결되지 않고 따로 떨여져 있는 노드도 처리할 수 있다.

처음 시작노드를 team1로 정했으면 그 노드와 연결된 노드들은 team2로, 그 다음은 다시 team1로 지정한다.

지정이 끝나면 이중포문을 돌면서 아래와 같이 검사한다. 

for(1번노드부터 V번 노드까지){

  for(해당 노드에 연결된 모든 노드들에 대해){   ...   } 

}

문제의 테스트케이스는 모두 연결 그래프로 나와있어서 비연결 그래프에 대해 생각해야한다는게 어려웠는데 백준 질의응답을 보고 해결했다.

예를 들어,

1-2

3-4

이렇게 연결되어 있는 그래프가 있다고 하자.

{1,4} ,{2,4} 또는 {1,3},{2,4} 로 집합을 나눌 수 있으므로 답은 YES이다.

주의할 점

테스트케이스가 반복되는 경우이므로 테스트케이스가 끝날 때마다 초기화를 해준다.

그리고 출력할 때도 줄바꿈을 해줘야한다.

#include <iostream>
#include <queue>
#include <vector>
#include <utility>
#include <cstring>    //memset

using namespace std;

vector<int> vecArr[20001];				//벡터1부터 벡터V까지에 대한 벡터배열이므로 +1
vector<pair<int,int>> eVec;

int visit[20001] = {0};
int group[20001] = {0};
int V,E;

void BFS(int start){
    queue<int> que;

    que.push(start); 
    visit[start] = 1;	//방문 체크
    group[start] = 1;	//집합 가르기
    
    int team = 1;
    
    while(!que.empty()){
   
        int sV = que.front();
        que.pop();

		
        //연결된 노드들을 현재벡터(sV)와 반대로 
        if(group[sV]==1) team = 2;
        else if(group[sV]==2) team = 1;
        
        for(int i = 0; i<vecArr[sV].size(); i++){
            
            int nV = vecArr[sV][i];
            
            if(visit[nV]==0){
                que.push(nV);
                visit[nV] = 1; 
                group[nV] = team;         
            }   
        }
    }

}


int main(){
    
    int T; cin >> T;
    
    for(int t=0; t<T; t++){
        
        cin >> V >> E;
        
        int e1,e2;
        for(int i = 0; i<E; i++){
            cin >> e1 >> e2;
           
            vecArr[e1].push_back(e2);
            vecArr[e2].push_back(e1);

        }

        for(int i = 1; i<=V; i++){
            if(visit[i]==0){			//모든 노드에 대해 돌려야 비연결 그래프도 통과
                BFS(i);
            }

        }
        
        
        bool chk = true;
        for(int i=1; i<=V; i++){
            for(int j = 0; j<vecArr[i].size(); j++){
                if(group[i]==group[vecArr[i][j]]){
                    chk=false;
                    break;
                }
            }
        }
       if(!chk) cout << "NO\n";
       else cout << "YES\n";
  
        for(int i = 0; i<=V; i++) vecArr[i].clear();
        memset(visit,0,sizeof(visit));
        memset(group,0,sizeof(group));
        
        
    }
    
    
    
    
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/14889

문제

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

i\j12341234

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S12 + S21 = 1 + 4 = 5
• 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S13 + S31 = 2 + 7 = 9
• 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

입력

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

접근 방법

sumFunc이 DFS이다. 

DFS 돌면서 각각 팀의 능력치를 더한다.

그 능력치의 차를 구해서 최소가 되는 경우를 찾는다.

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>

using namespace std;

int N;
int map[21][21];
int visited[21] = {0};
int num;

vector<int> start;
vector<int> link;

int chk[11] = {0};

vector<int> vec;
vector<int> sumVec;
int ans1 = 0;
int ans2= 0;
int ans = 100000000;


vector<int> sSum;

//DFS 돌면서 팀의 능력치 더함
void sumFunc(int toPick, vector<int> vec){
    
    if(toPick==0){
        
        int sum =  map[sumVec[0]][sumVec[1]] + map[sumVec[1]][sumVec[0]];
        sSum.push_back(sum);
        return;
    }
    
    for(int i = 0; i<vec.size(); i++){
        if(chk[i] ==0){
            chk[i] = 1;
            sumVec.push_back(vec[i]);
            sumFunc(toPick-1, vec);
            sumVec.pop_back();
            chk[i] = 0;
            
        }
    }
    
    
}


void choiceFunc(int toPick, int num){
    
    
    if(toPick==0){
        ans1 = 0; ans2 = 0;
        link.clear();
		
        //스타트와 링크 각각 start, link 벡터에 나눔
        for(int j = 1; j<=N; j++){
            if(visited[j]==0) {
                link.push_back(j);
            }
        }

        //스타트
        sumFunc(2, start);
        for(int i = 0; i<sSum.size(); i++){
            ans1+=sSum[i];
        }
        sSum.clear();
        
        //링크
        sumFunc(2, link);
        for(int i = 0; i<sSum.size(); i++){
            ans2+=sSum[i];
        }
        sSum.clear();


        if(ans1<ans2){		//더 큰게 ans1이 되게 바꿈
            int tmp=ans1;
            ans1=ans2;
            ans2=tmp;
        }
        
        if(ans1-ans2 < ans){ans = ans1-ans2;}	//능력치 차가 최소인 것 구함 
        memset(chk, 0, sizeof(chk));
        
        return;
        
    }
    
    for(int i = 1; i<=N; i++){
        
        if(visited[i]==0 && num<i){
            visited[i] = 1;
            start.push_back(i);
            choiceFunc(toPick-1, i);
            start.pop_back();
            visited[i] = 0;
            
        }
    }
    
}



int main(){
    
    cin >> N;
    for(int i = 1; i<=N; i++){
        for(int j = 1; j<=N; j++){
            cin >> map[i][j];
        }
    }

    num = (N*(N-1)) / 4;
    
    choiceFunc(N/2, 0);
    
    cout << ans/2 ;
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/14501

문제

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

 1일2일3일4일5일6일7일TiPi

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

접근 방법

파라미터 start를 바꿔가며 DFS를 돈다. 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N;
int T[15] = {0};
int P[15] = {0};

int ans = 0;

void dfs(int start, int sum){
    
    if(start>N) return;
    
    ans = max(ans, sum);
    
    for(int i = start; i<N; i++){
        dfs(i+T[i], sum+P[i]);		//시작일을 바꿔가며 최대 sum 체크
    }
        

}


int main(){
    
    cin >> N;
    for(int i = 0; i<N; i++){
        cin>> T[i] >> P[i];
    }
    
    dfs(0,0);
    cout << ans << "\n";
    return 0;
}

문제 링크 : www.acmicpc.net/problem/1759

문제

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

출력

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

접근 방법

DFS를 돌면서 ansVec벡터에 알파벳들을 push하고, toPick을 L부터 0까지 감소시켜나간다. 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<char> alpha;
vector<char> ansVec;
int visited[15] = {0};

//문제 조건 만족하는지 체크 : 모음 최소 1개 포함 and 암호 최소 길이 3
bool chk(){
    int cntV = 0;   //모음
    int cntC = 0;   //자음
    for(int i = 0; i<ansVec.size(); i++){
        if(ansVec[i]=='a' || ansVec[i]=='e' || ansVec[i]=='i' || ansVec[i]=='o' || ansVec[i]=='u') {cntV++;}
        else cntC++;
    }
    if(cntV>=1 && cntC>=2) return true;
    else return false;

}



void dfs(int toPick, char c){
    
    if(toPick==0){
        if(chk()){
            for(int i = 0; i<ansVec.size(); i++){
                cout << ansVec[i];
            }
            cout << "\n";
        }
        return;
    }
    
    
    for(int i = 0; i<alpha.size(); i++){
        
        if(visited[i]==0 && c<=alpha[i]){	//중복가능하니 등호 포함(c<=alpha[i])
            visited[i] = 1;
            ansVec.push_back(alpha[i]);
            dfs(toPick-1, alpha[i]);
            ansVec.pop_back();
            visited[i] = 0;
            
        }
        
    }
    
}
int main(){
    
    int L,C;
    cin >> L >> C;
    
    for(int i = 0; i<C; i++){
        char c; cin >> c;
        alpha.push_back(c);
    }
    
    sort(alpha.begin(), alpha.end());
    dfs(L, 'a');	//암호 알파벳 중복 가능하니까 초기값 'a'로 설정해도 상관 x
    
    
    return 0;
}