코영방

www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4

www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2

<추가 설명>

딱히 없네요.^^

그리디하게, 0,1 아니면 곱하기를 먼저 선택하면 되는 문제네용 ㅎㅎ

https://www.acmicpc.net/problem/15971

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/*
5 1 5
1 2 1
2 3 2
3 4 3
4 5 4
*/
int vi[100010],max1,tot;
vector <pair<int,int>> v[100010];

void dfs(int s, int e, int lmax, int l)
{
    if(s==e) {
        max1=lmax;
        tot=l;
    }
    else{
        vi[s]++;
        for(int i=0;i<v[s].size();i++)
        {
            if(vi[v[s][i].first]==0)
            {
                int last=lmax>v[s][i].second?lmax:v[s][i].second;
                dfs(v[s][i].first,e,last,l+v[s][i].second);
            }
        }
    }

}
int main()
{
    int r,r1,r2,i,s,e,d;

    scanf("%d %d %d",&r,&r1,&r2);
    for(i=1;i<r;i++)
    {
        scanf("%d %d %d",&s,&e,&d);
        v[s].push_back(make_pair(e,d));
        v[e].push_back(make_pair(s,d));
    }
    dfs(r1,r2,0,0);
    printf("%d",tot-max1);
    return 0;
}

https://www.acmicpc.net/problem/17618

#include<bits/stdc++.h>
using namespace std;

int sum; 
void Div_sum(int num)
{
    if(num == 0)
    {
        return;
    }

    sum+=(num%10);
    Div_sum(num/10);
}

int main(void)
{
    int n;
    int cnt=0;
    scanf("%d", &n);

    for(int i=1; i<=n; i++)
    {
        Div_sum(i);
        if((i%sum) == 0)
        {
            cnt++;
        }
        sum = 0;
    }

    printf("%d", cnt);

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
  int a;
  cin >> a;
  int cnt = 0;
  for(int i=1; i <=a; i ++)
  {
    int sum = 0;
    int temp = i;
    while(temp){
      sum = sum + temp%10;
      temp = temp / 10;
    }
    //cout << "== " << sum << "\n";
    if( i % sum == 0) cnt ++;
  }

  cout << cnt;
  
}

https://www.acmicpc.net/problem/17619

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//2019 정올 2차 2번 문제 (중등)
struct s{
    int a,b,pos;
};
bool compare(struct s x,struct s y)
{
    //return x.a<y.a;

    if(x.a<y.a)
        return true;
    return false;
}
int main()
{
    int m,n,i,j,y,r1[1000000]={0,},r2[1000000]={0,},max1,k=0,t=0,z=0,flag=0;
    int g2[1000000];
    struct s log[1000000];
    scanf("%d %d",&m,&n);
    for(i=0;i<m;i++){
        scanf("%d %d %d",&log[i].a,&log[i].b,&y);
        log[i].pos=i+1;
        g2[log[i].pos] = log[i].pos;
    }

    for(i=0;i<n;i++)
        scanf("%d %d",&r1[i],&r2[i]);
    sort(log,log+m,compare);
    while(1)
    {
        max1=log[t].b;
        
        int group = g2[log[t].pos];
        for(i=t;i<m-1;i++)
        {
            if(log[i+1].a<=max1)
            {
                
                g2[log[i+1].pos] = group;
                if(log[i+1].b>max1)
                    max1=log[i+1].b;
            }
            else
                break;
        }
        t=i+1;
        k++;
        z=0;
        if(t>=m)
            break;
    }


    for(t=0;t<n;t++)
    {
        if(g2[r1[t]] == g2[r2[t]]) puts("1");
        else puts("0");
    }
    return 0;
}

https://www.acmicpc.net/problem/1654

#include<stdio.h>

long long k;
long long Lan[20000];   //원소는 초기화 됨. 

long long div(long long len)   //len로 자르기. 
{
   long long sum = 0;
   
   for(int i=0; i<k; i++)
   {
      sum += (Lan[i]/len);
   }
   
   return sum;
}

int main(void)
{   
   long long n;
   long long max = 0;
   scanf("%lld %lld", &k, &n);
   
   for(int i=0; i<k; i++)
   {
      scanf("%lld", &Lan[i]);
      
      if(max<Lan[i])
      {
         max = Lan[i];   //최대 원소값 찾기 
      }
   }
   
   long long s = 1;
   long long e = max;   //mid의 범위를 1~최대 원소값까지로 고정. 
   long long mid;
   long long res; 
   long long res2 = -1; 

   
   while(s<=e)
   {
      mid = (s+e)/2;
      
      res = div(mid);   //res는 조각의 개수. 
      //
      if(res >= n)
      {
        if(res2 < mid) {
          res2 = mid;
        }
         s=mid+1;
      }
      
      else
      {
         e=mid-1;
      }
   }
   
   printf("%lld\n", res2);
   
   return 0;
}

https://www.acmicpc.net/problem/1463

#include <bits/stdc++.h>
using namespace std;

int main()
{
    long long int n,a[1000001]={0,},i;
    scanf("%lld",&n);

    for(i=2;i<=n;i++)
    {
        a[i]=a[i-1]+1;
        if(i%2==0 && a[i] > a[i/2] + 1)
            a[i] = a[i/2] + 1;
        if(i%3==0 && a[i] > a[i/3] + 1)
            a[i] = a[i/3] + 1;
    }

    /*
    for(i=1; i<=n; i++)
        printf("%lld : %lld  \n",i, a[i]);
        */
    printf("%d", a[n]);
    return 0;
}

https://www.acmicpc.net/problem/10819

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,a[1000000]={0,},max1=0,i,tmp=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    do
    {
        for(i=1;i<=n-1;i++)
        {
            tmp+=abs(a[i]-a[i+1]);
            if(max1<tmp)
            {
                max1=tmp;
            }
        }
        tmp=0;
    }while(next_permutation(a+1,a+n+1));
    printf("%d",max1);
    return 0;
}

https://www.acmicpc.net/problem/14002

아래 코드를 먼저 참고바랍니다.

https://coding-gongboo.tistory.com/38?category=829643

11053번 문제는 수열의 길이만 구하면 되지만, 14002문제는 수열을 표현해 주어야 한다.

#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
    int n,i,a[1000]={0,},l[1000]={0,},j,ma=-1,k[1000]={0,},m;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=1;i<=n;i++)
    {
        l[i]=1;
        k[i]=i;
        for(j=1;j<i;j++)
        {
            if(a[j]<a[i])
            {
                //l[i]=l[i]>l[j]+1 ? l[i] : l[j]+1;
                if(l[i] < l[j]+1)
                {
                    l[i] = l[j]+1;
                    k[i]=j;
                }
            }
        }
       // ma=ma>l[i]?ma:l[i];
        if(ma<l[i]){
            ma=l[i];
            m=i;
        }
    }
    printf("%d\n",ma);
    l[1] = a[m];
    for(i=2;i<=ma;i++)
    {
        l[i]=a[k[m]];
        m = k[m];
    }
    for(i=ma;i>0;i--)
        printf("%d ",l[i]);
    return 0;
}

https://www.acmicpc.net/problem/11053

이문제는 LIS(Longest Increasing Subsequence) 라는 유명한 문제입니다.

아래 코드는 다이내믹 방식으로 소스코드를 작성했습니다.

참고하시구요. 질문이나 수정할 부분있으면 알려주세요.^^

#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
    int n,i,a[100000]={0,},l[100000]={0,},j,ma=-1;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=1;i<=n;i++)
    {
        l[i]=1;
        for(j=1;j<i;j++)
        {
            if(a[j]<a[i])
                l[i]=l[i]>l[j]+1 ? l[i] : l[j]+1;
        }
        ma=ma>l[i]?ma:l[i];
    }
    printf("%d",ma);
    return 0;
}

https://www.acmicpc.net/problem/15652

이번문제는 N과 M (2)와 유사하다. 단, 중복 가능하다. 

아래 문제 조건과 같이 앞의 수가 다음수보다 작거나 같다은 조건을 만족하면 된다.

길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

따라서 N과 M (2)에서 재귀함수의 첫번째 인자만, i+1이 아니랑 i를 주면 된다.

즉, i값을 포함해서 다음 수를 정해나가는 형태이다. 왜냐? 중복을 허용하기 때문이다.

#include <bits/stdc++.h>
using namespace std;
vector <int> nm;
void NM4(int, int, int);

int main() {
    int n, m;
    cin >> n >> m;
    NM4(1, n, m);
    return 0;
}
void NM4(int s, int n, int m) {
    if (nm.size() == m) {
        for (int i = 0; i < m; i++) {
            cout << nm[i] << " ";
        }
        cout << '\n';
        return;
    }
    for (int i = s; i <= n; i++) {
        nm.push_back(i);
        NM4(i, n, m); //현재 nm vector에 넣은 수 이후 수를 확인 한다. (오름차순)
        nm.pop_back();
    }
}

https://www.acmicpc.net/problem/15651

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. (중복가능)

N = 4, M = 2인 경우 아래와 같이 16(4*4) 개의 경우가 발생한다.

1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4

내 생각에는 N과 M(1)보다 풀이에 접근하기 더 쉬운 문제라고 생각한다. 내기준으로는 "N과 M(0)" 이 맞을듯.^^

#include <bits/stdc++.h>
using namespace std;
vector <int> res;
void NM3(int n, int m) {
    if (res.size() == m) {
        for (int i = 0; i < m; i++) {
            cout << res[i] << " ";
        }
        cout << '\n';
        return;
    }
    for (int i = 1; i <= n; i++) {
        res.push_back(i);
        NM3(n, m);
        res.pop_back();
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    NM3(n, m);
    return 0;
}

https://www.acmicpc.net/problem/11724

연결 요소의 개수의 경우, DFS나 BFS를 공부를 공부한 후라면 간단하게 해결 가능하다.

모든 정점을 대상으로 방문한 적이 없는 정점이 있으면 그 정점을 기준으로 DFS 또는 BFS순회를 통해 방문했다는 체크를 해둔다. 그 후에도 아직 방문하지 않은 정점이 있다면 또 DFS나 BFS를 통해 순회하면서 방문했다는 체크를 하면 된다.

#include <bits/stdc++.h>
using namespace std;

int n, l;
vector <int> a[1005];
int visited[1005] = { 0, };

void dfs_l(int s) {
    int i;
    visited[s]++;
    for (i = 0; i < a[s].size(); i++){
        if (visited[a[s][i]] == 0){
            dfs_l(a[s][i]);
        }
    }

}

int main()
{
    int i, n1, n2, cnt = 0;
    scanf("%d %d", &n, &l);
    //간선 정보를 입력 받아 그래프 만들기
    for (i = 0; i < l; i++){
        scanf("%d %d", &n1, &n2);
        a[n1].push_back(n2);
        a[n2].push_back(n1);
    }
    
    //DFS 순회시에 인접 정점중에 정점번호가 작은 값부터 순회하기 위해 정렬
    //이번 문제에서는 굳이 없어도 됨.
    for (int i = 0; i < n; i++) {
        sort(a[i].begin(), a[i].end());
    }
    //방문하지 않은 정점을 발견하면 DFS순회함.
    //DFS가 호출되는 횟수가 연결요소의 개수가 됨.
    for (int i = 1; i <= n; i++){
        if (visited[i] == 0){
            dfs_l(i);
            cnt++;
        }
    }
    printf("%d", cnt);
    return 0;
}

https://www.acmicpc.net/problem/15650

N과 M(1)문제 풀이 참고바람. (https://coding-gongboo.tistory.com/9?category=829643)

N과 M(1) 과의 차이점은 "고른 수열은 오름차순이어야 한다"는 점이다.

이를 위해서 현재 선택된 수 보다 1개 높은 위치의 수를 부터 수열을 만들어 나가야 한다.

이를 위해서 NM2(재귀함수)에 start해야 할 위치를 인자로 넘겨주는 부분이 수정되었다.

그리고 항상 다음 수를 대상으로 수열을 만들어 나가기 때문에 중복체크를 위한 included배열은 필요없다.

#include <bits/stdc++.h>

using namespace std;
//bool included[10]; //중복 체크
vector <int> nm;
void NM2(int, int, int);

int main() {
    int n, m;
    cin >> n >> m;
    NM2(1, n, m);
    return 0;
}

void NM2(int s, int n, int m) {
    if (nm.size() == m) {
        for (int i = 0; i < m; i++) {
            cout << nm[i] << " ";
        }
        cout << '\n';
        return;
    }
   
    for (int i = s; i <= n; i++) {
        //if (!included[i]) {
            //included[i] = true;
            nm.push_back(i);
            NM2(i + 1, n, m); //현재 nm vector에 넣은 수 이후 수를 확인 한다. (오름차순)
            nm.pop_back();
            //included[i] = false;
        //}
    }
}

두번째 풀이

각 수들을 포함 하거나 또는 포함 하지않으면서 다음수로 넘어가는 형태

#include <bits/stdc++.h>
using namespace std;
vector <int> nm;
void NM2(int level, int n, int m);

int main() {
    int n, m;
    cin >> n >> m;
    NM2(1, n, m);
    return 0;
}

void NM2(int level, int n, int m) {
    if (nm.size() == m) {
        for (int i = 0; i < m; i++) {
            cout << nm[i] << " ";
        }
        cout << '\n';
        return;
    }
    if (level > n) return;
    nm.push_back(level);
    NM2(level + 1, n, m);
    nm.pop_back();
    NM2(level + 1, n, m);
}

세번째 풀이

배열을 사용해서 결과값을 저장한 위치에 해당하는 index 인자를 관리해주고,

오름차순을 위해 다음 수를 지정해주는 start를 관리해 주는 형태

#include <bits/stdc++.h>
using namespace std;
int res[10];
void go(int index, int start, int n, int m);

int main() {
    int n, m;
    cin >> n >> m;
    go(0, 1, n, m);
    return 0;
}

void go(int index, int start, int n, int m) {
    if (index == m) {
        for (int i = 0; i < m; i++) {
            cout << res[i];
            if (i != m - 1) cout << ' ';
        }
        cout << '\n';
        return;
    }
    for (int i = start; i <= n; i++) {
        res[index] = i;
        go(index + 1, i + 1, n, m);
    }
}

알고리즘을 공부하다보면, bits/stdc++.h 라는 생소한 헤더파일을 사용하는것을 자주 볼것이다.

표준 header file이 아니다보니, visiual studio에는 포함되어 있지 않다.

bits/stdc++.h를 visual studio에서 사용하는 법은 간단하다.

visual studio의 include 폴더에 bits라는 폴더를 만들고 아래 소스코드를 포함하는 stdc++.h파일을 만들어주면 끝이다.

내 PC의 경우, 

C:\Program Files (x86)\Microsoft Visual Studio\2019\Community\VC\Tools\MSVC\14.24.28314\include\ 에

bits라는 폴더를 만들고, stdc++.h 넣어주면 끝~!!!

//stdc++.h 헤더파일 소스코드
#pragma once
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

https://www.acmicpc.net/problem/15649

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

N=4, M=4가 주어지면, 아래와 같이 12(4*3)개의 경우가 발생한다.

아래 1 4 와 4 1과 같이 순서가 다른 경우는 다른 것으로 판단해야 함.

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

"중복 없이"라는 조건이 있음으로 한번 수열에 포함된 수는 수열을 완성할때까지 다시 포함되면 안됨으로 포함 여부를 판단하기 위해 included라는 배열을 사용한다.

n = 4, m = 2를 입력하면, 아래와 같은 순서로 실행된다.

"1. go(4,2)" : nm에 1추가 (nm = 1)

"2. go(4,2)" : nm에 2추가 (nm = 1,2)

"3. go(4,2)" : nm.size()가 m임으로 nm의 내용 1,2 출력 후 return

"2. go(4,2)" 로 돌아감. nm에서 2를 pop_bakc하고, for문을 통해 i 증가시킨 후 nm에 3을 추가함.

#include <bits/stdc++.h>

using namespace std;
bool included[10]; //중복 체크
vector <int> nm;
void NM1(int, int);

int main() {
    int n, m;
    cin >> n >> m;
    NM1(n, m);
    return 0;
}

void NM1(int n, int m) {
    if (nm.size() == m) {
        for (int i = 0; i < m; i++) {
            cout << nm[i] << " ";
        }
        cout << '\n';
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!included[i]) {
            included[i] = true;
            nm.push_back(i);
            NM1(n, m);
            nm.pop_back();
            included[i] = false;
        }
    }
}

지난 몇개월 동안 백준 문제풀이 사이트에서 딱 204개의 문제를 풀어봤다. 

2020년도 안에 300문제정도를 더 풀어서 백준사이트 랭킹 1000등안에는 들어가볼 계획이다.

내가 직접푼 소스코드는 물론이고, 학생들과 공부하는 과정에서 얻은 주옥같은 코드들도 공유하려한다.

대한민국이 SW강국이 되는 그날을 기대하며.......

https://www.acmicpc.net/