문제

이항 계수1 백준 11050번

리뷰

N개중에 K개를 고르는 이항계수를 작성하는 문제다.

파스칼의 삼각형도 이항계수를 기반으로 풀 수 있다.

"재귀로 푼 이항계수"포스팅의 도움을 받았다. 

맞은 코드

#include <iostream>
#include <algorithm> 
using namespace std;

int N, K;

int bi(int n, int k){

    if(n == k || k == 0) return 1;
    else return bi(n-1, k) + bi(n-1, k-1);

}

int main(void){

    cin >> N >> K;
    cout << bi(N, K);

    return 0;
} 
728x90

'알고리즘 > 백준' 카테고리의 다른 글

카드2 백준 2164번  (0) 2020.09.30
ACM 호텔 백준 10250번 c++  (0) 2020.09.28
단어정렬 백준 1181번  (0) 2020.09.28
듣보잡 백준 1764번 c++  (0) 2020.09.22
숨바꼭질6 백준 17087번 c++  (0) 2020.09.19

문제

단어 정렬 백준 1181번


리뷰

단순히 sort 하면 되는 줄 알고 풀었는데, 아니었다.

단어 길이가 짧을 수록 앞에 와야 한다.

단어 길이가 다르다면, 길이가 짧은 것이 앞으로 와야 한다.

길이가 같으면, 사전순으로 정렬 한다.

sort 의 기준이 되는 compare 함수를 작성했다.

bool compare(string a, string b){
    if(a.size() == b.size() ) return a < b;  // 사전순 정렬 
    else return a.size() < b.size(); // 길이 긴 것이 뒤로 
}

sort(v.begin(), v.end(), compare);

맞은 코드

#include <iostream>
#include <vector>
#include <string> 
#include <algorithm> 
using namespace std;

vector<string> v;

bool compare(string a, string b){
    if(a.size() == b.size() ) return a < b;
    else return a.size() < b.size();
}

int main(void){

     int cnt = 0;
    cin >> cnt;

    while(cnt--){
        string input;
        cin >> input;

        // 중복 없으면 푸시  
        if(find(v.begin(), v.end(), input) == v.end())    v.push_back(input);     
    } 

    sort(v.begin(), v.end(), compare);

    for(int i = 0; i < v.size(); i++){
        cout << v[i] << '\n';
    }

    return 0;
} 

728x90

'알고리즘 > 백준' 카테고리의 다른 글

ACM 호텔 백준 10250번 c++  (0) 2020.09.28
이항계수1 백준 11050번 c++  (0) 2020.09.28
듣보잡 백준 1764번 c++  (0) 2020.09.22
숨바꼭질6 백준 17087번 c++  (0) 2020.09.19
링크와 스타트 백준 15661번 c++  (0) 2020.09.17

문제

듣보잡 백준 1764번

리뷰

문제 이름이 특이해서 도전해봤다. ㅋㅋ

두개의 string 명단을 비교해서 중복되는 string들을 출력하는 프로그램을 만들어야 한다.

N개를 저장한 벡터를 만든 후, 입력받은 string을 찾으려고 했는데 시간초과 났다.

혼자 헤매다가 결국 질문 게시판을 찾아보니 정렬을 하세요 라는 글이 있었다.

정렬을 하면 같은 이름끼리 붙어있을테니까!! 덕분에 풀 수 있었다.

맞은 코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> 
using namespace std;

int N, M, cnt; // 듣. 보
int max_len, min_len;
vector<string> v, answer;
string st;

int main(void){

    cin >> N >> M;

    for(int i = 0; i < N+M; i++){ // N+M개 모두 입력받기 
        cin >> st;
        v.push_back(st);
    }

    sort(v.begin(), v.end()); // 정렬 

     for(int i = 0; i < N+M-1; i++){
        if(v[i] == v[i+1]){   // 정렬하면 같은 단어는 붙어있다.  
            answer.push_back(v[i]);
            cnt++;
        }
    }

    cout << cnt << '\n';
    for(int i = 0; i < answer.size(); i++){
        cout << answer[i] << '\n';
    }
    return 0;
} 
728x90

'알고리즘 > 백준' 카테고리의 다른 글

이항계수1 백준 11050번 c++  (0) 2020.09.28
단어정렬 백준 1181번  (0) 2020.09.28
숨바꼭질6 백준 17087번 c++  (0) 2020.09.19
링크와 스타트 백준 15661번 c++  (0) 2020.09.17
8진수 2진수 백준 1212번  (0) 2020.09.16

문제

숨바꼭질6 백준 17087번

리뷰

수빈이의 위치와 1명 이상의 동생들의 위치가 주어진다.

수빈이가 어떤 간격 D로 움직여야 동생들을 전부 만날 수 있냐는 문제다.

수빈이의 위치와 동생들의 위치를 빼서 '거리'를 구한 배열을 만든다.

배열을 전부 순회하면서 '최대공약수'를 구한다.

int gcd(int a, int b){ //  유클리드 호제법으로 구하는 a, b의 최대공약수 
    if(b == 0) return a;
    else return gcd(b, a%b);
}  

동생이 1명이 올수도 있고, 2명일 수도 있으니까 동생 숫자를 유의해야 한다.

맞은 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, S, D; // 동생 수, 수빈 위치  
int A[100001]; // 동생들 위치  

int gcd(int a, int b){ // 최대공약수 

    if(b == 0) return a;
    else return gcd(b, a%b);
}  

int main(void){

    scanf("%d %d", &N, &S);

    for(int i = 0; i < N; i++){
        scanf("%d", &A[i]); // 동생의 위치 입력받음  
        A[i] = abs(A[i] - S); // 수빈의 위치와 동생의 위치의 '차이'로 갱신   
    }

    if(N == 1){ // 동생 수 N 1명  

        D = A[0];
    }else if(N == 2){ //동생 2명  

        D = gcd(A[0], A[1]); 
    }else{ 

        D = gcd(A[0], A[1]);

        for(int i = 2; i < N; i++){
            D = gcd(D, A[i]);
        }    
    }

    printf("%d", D);

    return 0;
}
728x90

'알고리즘 > 백준' 카테고리의 다른 글

단어정렬 백준 1181번  (0) 2020.09.28
듣보잡 백준 1764번 c++  (0) 2020.09.22
링크와 스타트 백준 15661번 c++  (0) 2020.09.17
8진수 2진수 백준 1212번  (0) 2020.09.16
2진수 8진수 백준 1373번  (0) 2020.09.15

문제

링크와 스타트 백준 15661번

리뷰

14889번 스타트와 링크 문제와 비슷했다.

스타트와 링크는 두 팀이 반드시 N/2 명씩 나뉘어야 했다.

이 문제는 두 팀이 1명 이상이면 된다는 조건이다. 하지만 팀 인원수가 1명이면, 능력치 계산을 못한다.

그래서 S팀이 2명일 때, S팀이 3명일 때, .... S팀이 N-2 명일 때의 경우를 모두 검사했다. DFS로 탐색했다.

    for(int i = 2; i < N-1; i++){  // 2명 부터 n-2명 까지의 범위 전부 검사 
        divideTeam(0, 0, i); 
    }

스타트와 링크 문제 풀이 포스팅

맞은 코드

#include <iostream> 
#include <vector>
#include <algorithm>  
using namespace std;

int N;
int answer = 2e9;
bool check[21];
int S[21][21]; 

void countPower(){ // 팀별 능력치 비교  

    vector<int> Steam, Lteam; 
    int Spower=0, Lpower=0; 

    for(int i = 0; i < N; i++){  // 1. vector에 팀별 멤버번호 나눠담기 
        if(!check[i]) {
            Steam.push_back(i);
        }
        else Lteam.push_back(i);
    }    

    for(int i = 0; i < Steam.size(); i++){ // 2. 팀별 능력치 계산  
         for(int j = i+1; j < Steam.size(); j++){
             Spower = Spower + ( S[ Steam[i] ][ Steam[j] ] ) + ( S[ Steam[j] ][ Steam[i] ] );
        }
    }

    for(int i = 0; i < Lteam.size(); i++){  // Steam과 Lteam은 인원수가 다를 수 있다 
         for(int j = i+1; j < Lteam.size(); j++){
            Lpower = Lpower + ( S[ Lteam[i] ][ Lteam[j] ] ) + ( S[ Lteam[j] ][ Lteam[i] ] );
        }
    }

    // 3. 최소값 갱신 
    answer = min(abs(Spower-Lpower),  answer);

    return;
}

void divideTeam(int idx, int cnt, int target){ // N명중에 target 명 고르기  

    if(cnt == target) { // 팀 선택 완료 
        countPower();
        return;
    }

    for(int i = idx; i < N; i++){ // DFS로 완전탐색 

        if(check[i]) continue;

        check[i] = true;
        divideTeam(i+1, cnt+1, target);
        check[i] = false;
    }

}


int main(void){

     cin >> N;

     for(int i = 0; i < N; i++){
         for(int j = 0; j < N; j++){
             scanf("%d", &S[i][j]);
        }
    }

    for(int i = 2; i < N-1; i++){ // 2명 부터 n-2명 까지의 범위 전부 검사 
        divideTeam(0, 0, i); 
    }

    cout << answer;

    return 0;
} 
728x90

'알고리즘 > 백준' 카테고리의 다른 글

듣보잡 백준 1764번 c++  (0) 2020.09.22
숨바꼭질6 백준 17087번 c++  (0) 2020.09.19
8진수 2진수 백준 1212번  (0) 2020.09.16
2진수 8진수 백준 1373번  (0) 2020.09.15
진법변환 백준 2745번  (0) 2020.09.15

문제

8진수 2진수 백준 1212번


리뷰

8진수 한 자리는 2진수 세 자리로 표현할 수 있다.

예를 들어, 8진수 7은 2진수로 111 이다. 111은 곧 4+2+1 == 7 이기 때문이다.

8진수 1 자리가 들어왔을 때, 2진수 3자리로 바꿔서 스택에 넣어줬다.

가장 작은 자리수 부터 계산하니까. 스택에 넣은다음에 출력할 때는 올바른 순서로 나오기 때문에 스택을 선택했다.

8진수를 2로 나눈 나머지를 스택에 저장한다. 이 때, 나눗셈을 3번 한다.


처음에는 틀렸는데, 질문게시판을 보니까 0을 넣으면 0이 나와야 한다는 댓글을 봤다.

내코드에서는 0넣으면 아무것도 출력이 안됬었다.

이유는 스택에 001100 가 들어가 있다면, 1100 으로 출력하기 위해서였다. 0으로 시작하는 이진수는 없기 때문이다.

처음에는 스택의 top이 0이고, flag 가 false 라면 pop만 하고, 출력하지 않았다.

처음 1이 나올때 부터, flag를 true로 바꿔줘서, top 출력과 pop 둘 다 하도록 했다.

    bool flag= false;

    while(!answer.empty()){ // 스택 출력 

        if(answer.top() == 0 && flag == false){
            answer.pop();
            continue;
        }else{
            flag = true;
        }

        cout << answer.top();
        answer.pop();
    }

입력이 8진수 0이라면, 이진수도 답이 0이 나와야 하니까

while문의 첫번째 if문 조건을 수정했다.

    bool flag= false;

    while(!answer.empty()){ // 스택 출력 

        if(answer.top() == 0 && flag == false && answer.size() != 1){
            answer.pop();
            continue;
        }else{
            flag = true;
        }

        cout << answer.top();
        answer.pop();
    }

맞은 코드 1 (내가 짠 코드)

#include <iostream> 
#include <string>
#include <cstring> // strcpy()
#include <stack>
using namespace std;

string st;
char N[333335];
stack<int> answer;

int main(void){

     cin >> st;

     strcpy(N, st.c_str()); // string을 char 배열로 복사 

     int len = st.length(); // 8진수의 길이 

     for(int i = len-1; i >= 0 ; i--){

        int temp = N[i]-48;

        if(temp == 0){
            answer.push(0); answer.push(0); answer.push(0);
            continue;
        }

        for(int j = 0; j < 3; j++){ // 0이 아니라면,  2로 나눈 나머지를 stack에 push  
             answer.push(temp % 2);
             temp /= 2; 
        }
    }

    bool flag= false;

    while(!answer.empty()){ // 스택 출력 

        if(answer.top() == 0 && flag == false && answer.size() != 1){
            answer.pop();
            continue;
        }else{
            flag = true;
        }

        cout << answer.top();
        answer.pop();
    }

    return 0;
} 



내 코드가 어수선 하다는 느낌이 들었다. 다른 분들 코드를 찾아 보고 배웠다.

8진수를 2진수로 나타낼 수 있는 8가지 문자열을 미리 배열에 저장해두고 활용하는 방식이다.

first는 첫 숫자가 0이 나오면 안되니까 만들어 둔 배열이다. 0으로 시작하는 이진수는 없기 때문이다.

string first[8] = {"0", "1", "10", "11", "100", "101", "110", "111"};
string other[8] = {"000", "001", "010", "011", "100", "101", "110", "111"};

string st;
cin >> st;

cout << first[st[0] - '0'] ; // 문자로 된 숫자 하나에서 '0' 을 빼주면 숫자가 나온다  

first [ st[0] - '0' ] 이게 뭐지 싶었는데.

예를 들어, st[0] 이 문자 '3' 이라면, 문자 3에서 문자 0을 뺴야 숫자 3을 얻을 수 있다.

// st [0] == '3'

 first  [ '3' - '0' ] = first [3] 
 과 같다. 

 other[st[i] - '0']; 도 같은 구조다. 
 // st[0] 이 문자 5라면  (8진수로 5를 받았다면,) 
 other[ '5'-'0' ] == other [5] 가 된다. 이렇게 8진수를 2진수로 변환한다.  

가독성도 좋고 아주 배우고 싶은 코드여서 정리한다.


맞은 코드 2

#include <iostream> 
#include <string>
using namespace std;

string first[8] = {"0", "1", "10", "11", "100", "101", "110", "111"};
string other[8] = {"000", "001", "010", "011", "100", "101", "110", "111"};

int main(void){

    string st;
    cin >> st;

    cout << first[st[0] - '0'] ; // 문자로 된 숫자 하나에서 '0' 을 빼주면 숫자가 나온다  

    for(int i = 1; i < st.size(); i++){
        cout << other[st[i] - '0'];
    }

    return 0;
} 
728x90

'알고리즘 > 백준' 카테고리의 다른 글

숨바꼭질6 백준 17087번 c++  (0) 2020.09.19
링크와 스타트 백준 15661번 c++  (0) 2020.09.17
2진수 8진수 백준 1373번  (0) 2020.09.15
진법변환 백준 2745번  (0) 2020.09.15
진법변환2 백준 11005번 c++  (0) 2020.09.15

문제

2진수 8진수 백준 1373번


리뷰

2진수의 3 자리를 8진수의 1 자리로 만들 수 있다.

예를 들어 2진수 11001100 이 있다.

맨 오른쪽 부터 2의 0승, 2의 1승, 2의 2승이 곱해진 수다. ( 4, 2, 1)

3의 배수의 길이일때 이것이 성립한다.

11001100은 길이가 8이다. 8진수로 계산할 때는 11 001 100 으로 나눠질 수 있다.

첫번째 1과 두번째 1은 따로 처리해줘야 한다.

11 001 100 

11 을 8진수로 바꾼다. 
(2^1)x 1  + (2^0)x 1   // 2자리 일때는 2의 1승부터 시작!
    = 2 + 1 
    = 3 

001 을 8진수로 바꾼다. 
(2^2)x 0  + (2^1)x 0  +  (2^0)x 1   // 3자리 일때는 2의 2승부터 시작!
    = 0 + 0 + 1
    = 1    

100 을 8진수로 바꾼다. 
(2^2)x 1  + (2^1)x 0  +  (2^0)x 0 
    = 4 + 0 + 0
    = 4

이진수 문자열 길이가 4, 5, 6인 세 가지 경우가 있다.

이진수 문자열 길이가 4인 경우, (길이 % 3 == 1)

맨 앞의 수를 (2^0)x ? 으로 계산해주고,

나머지 3개의 수를 (2^2)x ? + (2^1)x ? + (2^0)x ? 식으로 계산하면 된다.


맞은 코드

#include <iostream> 
#include <cstring> //strlen() 
using namespace std;

char ch[1000001];

int main(void){

    scanf("%s", &ch); 

    int len = strlen(ch);

    if(len % 3 == 1){
        printf("%d", ch[0]-48 );

    }else if(len % 3 == 2){
        printf("%d",  2*( ch[0]-48 ) + ch[1]-48 );
    }    

    // 나머지 3의 배수로 떨어지는 길이만큼. len%3으로 시작해야 한다.
    for(int i = len%3; i < len; i += 3 ){
        printf("%d", 4 * ( ch[i]-48 ) +   2 * ( ch[i+1]-48 ) +  ch[i+2]-48 );
    }

    return 0;    
} 

728x90

'알고리즘 > 백준' 카테고리의 다른 글

링크와 스타트 백준 15661번 c++  (0) 2020.09.17
8진수 2진수 백준 1212번  (0) 2020.09.16
진법변환 백준 2745번  (0) 2020.09.15
진법변환2 백준 11005번 c++  (0) 2020.09.15
GCD합 백준 9613번  (0) 2020.09.15

+ Recent posts