'알고리즘' 카테고리의 글 목록 (2 Page)

1. 문제

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.

단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.

2. 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> nums;
string aeiou[5]={"A","E","I","O","U"};

void repeatPermutation(string s, int maxLength)
{
    if(maxLength==s.size()) //문자열의 크기 == 채울 문자열 크기
    {
        nums.push_back(s);
        return; //재귀함수 종료
    }
    
    for(int i=0;i<5;i++){
        repeatPermutation(s+aeiou[i],maxLength); //재귀함수 호출
    }
}

int solution(string word) {
    int answer = 0;
    
    for(int i=1;i<=5;i++){
        repeatPermutation("",i);
    }
    
    sort(nums.begin(), nums.end());  

    for(int i=0;i<nums.size();i++){
        if(word==nums[i]){
            answer=i;
            break;
        }
    }
       
    return answer+1;
}

3. 해설

vector<string> nums;
string aeiou[5]={"A","E","I","O","U"};

void repeatPermutation(string s, int maxLength)
{
    if(maxLength==s.size()) //문자열의 크기 == 채울 문자열 크기
    {
        nums.push_back(s);
        return; //재귀함수 종료
    }
    
    for(int i=0;i<5;i++){
        repeatPermutation(s+aeiou[i],maxLength); //재귀함수 호출
    }
}

int solution(string word) {
    int answer = 0;
    
    for(int i=1;i<=5;i++){
        repeatPermutation("",i);
    }

재귀 함수를 통해서 모든 경우의 수를 저장합니다.

경우의 수는 1자리일 때, 2자리일 때, 3자리일 때, 4자리일 때, 5자리일 때 모든 경우의 수를 구해야합니다.

따라서 1자리의 경우

for(int i=0;i<5;i++){
        repeatPermutation(s+aeiou[i],maxLength); //재귀함수 호출
}

이 부분이 aeiou[0] ~aeiou[4] 까지의 값이 한번씩 호출 되면서 끝납니다.

2자리의 경우 위의 for문이 aeiou[0]+aeiou[0]~aeiou[4] 에서부터 aeiou[4]+aeiou[0]~aeiou[4] 까지 계산함으로 총 25가지의 문자열이 저장됩니다.

이와 같은 방법으로 5자리의 경우까지 재귀함수를 통해 저장합니다.

sort(nums.begin(), nums.end());  

    for(int i=0;i<nums.size();i++){
        if(word==nums[i]){
            answer=i;
            break;
        }
    }
       
    return answer+1;
}

그 후, 사전적 배열로 나열해줘야합니다.

기존에 저장된 배열은 A,E,I,O,U,AA,AE,AI,AO,AU.... 등의 순서로 구성되어 있습니다.(함수 호출 순서에 따라 달라질 수 있으나 (1자리수...2자리수...3자리수.... 로 저장)

기본적으로 sort 함수는 string 변수에서 사전적 순서로 정렬해주기 때문에 별도의 판별 함수를 넣지 않아도 됩니다.

그 후 for문을 통해 받은 word 값과 nums[i]의 값이 같다면 해당 번호를 뽑아냅니다.

벡터는 0번부터 시작하기에 +1을 해주면 몇번째 수인지를 도출할 수 있습니다.

※ for문을 쓰지 않고 find() 함수를 통해서 한줄로 해결할 수도 있습니다.

저작자표시

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

[프로그래머스] 붕대 감기 (1)	2024.01.16
[프로그래머스] 체육복 (1)	2023.11.15
[프로그래머스] 전력망을 둘로 나누기 C++ (0)	2023.10.30
[프로그래머스] 피로도 C++ (0)	2023.10.26
[프로그래머스] 카펫 (1)	2023.10.26

1. 문제

출처:https://school.programmers.co.kr/learn/courses/30/lessons/86971

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

2. 코드

#include <string>
#include <vector>

using namespace std;

//dfs, visited 방법

int graph[101][101];
int visited[101];

int dfs(int cur, int n)
{
    if(visited[cur]) return 0;      //한번 방문한 곳은 재방문 X
    int child=1;      //하위 노드의 갯수
    visited[cur]=true;
    for(int i=1;i<=n;i++)
    {
        if(graph[cur][i])       //연결, 간적 없는 곳만
        {
            child+=dfs(i,n);
        }
    }
    return child;
}

void setGraph(int x,int y,int value)
{
    graph[x][y]=value;
    graph[y][x]=value;
}

int solution(int n, vector<vector<int>> wires) {
    int answer = 101;
    
    //연결되어 있는 모든 송전탑 1로 초기화
    for(int i=0;i<wires.size();i++){
        setGraph(wires[i][0],wires[i][1],1);
    }
    
    for(int i=0;i<wires.size();i++){
        //방문 배열 초기화
        fill_n(visited,101,false);
        
        //끊을 전선 0으로 만들어주기 -> 전선 끊기
        setGraph(wires[i][0],wires[i][1],0);

        vector<int> diff;
        for(int i=1;i<=n;i++)
        {
            int tmp=dfs(i,n);       //깊이 탐색
            if(!tmp)continue;       //방문한 경우 생략
            diff.push_back(tmp);
        }
        answer = min(answer, abs(diff[0]-diff[1]));
        if(answer==0)break;
        //원상태로 돌려놓기
        setGraph(wires[i][0],wires[i][1],1);
    }
    
    return answer;
}

3. 해설

//dfs, visited 방법

int solution(int n, vector<vector<int>> wires) {
    int answer = 101;
    
    //연결되어 있는 모든 송전탑 1로 초기화
    for(int i=0;i<wires.size();i++){
        setGraph(wires[i][0],wires[i][1],1);
    }
    
    for(int i=0;i<wires.size();i++){
        //방문 배열 초기화
        fill_n(visited,101,false);
        
        //끊을 전선 0으로 만들어주기 -> 전선 끊기
        setGraph(wires[i][0],wires[i][1],0);

        vector<int> diff;
        for(int i=1;i<=n;i++)
        {
            int tmp=dfs(i,n);       //깊이 탐색
            if(!tmp)continue;       //방문한 경우 생략
            diff.push_back(tmp);
        }
        answer = min(answer, abs(diff[0]-diff[1]));
        if(answer==0)break;
        //원상태로 돌려놓기
        setGraph(wires[i][0],wires[i][1],1);
    }
    
    return answer;
}

dfs를 이용해서 풀어야하는 문제이다. 처음에 문제를 접근할 때 dp로 접근하여서 노드의 하위 갯수를 누적하였었는데 해당 경우는 노드가 정렬되어 있지 않을 때 적합하지 않기 때문에 사용할 수 없었다.

푸는 순서는 다음과 같습니다.

1. 먼저 연결되어 있는 모든 송전탑들을 2차원 배열에 1로 표시해줍니다.

    //연결되어 있는 모든 송전탑 1로 초기화
    for(int i=0;i<wires.size();i++){
        setGraph(wires[i][0],wires[i][1],1);
    }

2. 0~n번째 송전탑을 각각 끊는 for 문을 이용하여 n번 돌려줍니다.

    for(int i=0;i<wires.size();i++){

3. 방문 배열을 초기화 해주고, 2차원 배열에서 끊을 송전탑을 0으로 만들어줍니다.

        //방문 배열 초기화
        fill_n(visited,101,false);
        
        //끊을 전선 0으로 만들어주기 -> 전선 끊기
        setGraph(wires[i][0],wires[i][1],0);

4. dfs 탐색을 통해 방문하지 않고 연결이 끊어지지 않은 곳까지 탐색을 하여 하위 노드의 갯수를 반환하고 그 값들의 차이를 반환합니다.

        vector<int> diff;
        for(int i=1;i<=n;i++)
        {
            int tmp=dfs(i,n);       //깊이 탐색
            if(!tmp)continue;       //방문한 경우 생략
            diff.push_back(tmp);
        }
        answer = min(answer, abs(diff[0]-diff[1]));
        if(answer==0)break;
        //원상태로 돌려놓기
        setGraph(wires[i][0],wires[i][1],1);

저작자표시

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

[프로그래머스] 체육복 (1)	2023.11.15
[프로그래머스] 모음사전 C++ (1)	2023.11.07
[프로그래머스] 피로도 C++ (0)	2023.10.26
[프로그래머스] 카펫 (1)	2023.10.26
[프로그래머스] 소수 찾기 (C++) (0)	2023.10.23

1. 문제

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/87946

유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

2. 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

//수열 next_permutation을 활용하여서 풀이
//경우의 수를 다 계산한 다음 차례로 검증함
int solution(int k, vector<vector<int>> dungeons) {
    int answer = 0;
    
    vector<int> v;
    // 0부터 던전 사이즈까지 벡터에 저장
	for(int i=0; i<dungeons.size(); i++){
		v.push_back(i);
	}
    
    do{
        int pirodo=k;
        int count=0;
		for(int i=0; i<v.size(); i++){
            if(pirodo>=dungeons[v[i]][0]){
                //피로도 차감 및 던전 갯수 올리기
                count++;
                pirodo-=dungeons[v[i]][1];
            }
		}
        answer=max(answer,count);
	}while(next_permutation(v.begin(),v.end()));
    
    return answer;
}

3. 해설

//수열 next_permutation을 활용하여서 풀이
//경우의 수를 다 계산한 다음 차례로 검증함
int solution(int k, vector<vector<int>> dungeons) {
    int answer = 0;
    
    vector<int> v;
    // 0부터 던전 사이즈까지 벡터에 저장
	for(int i=0; i<dungeons.size(); i++){
		v.push_back(i);
	}

경우의 수가 많지 않기에 완전 탐색을 통해 풀수 있는 문제이다.

정해진 배열에서 순서를 바꾸는 경우의 수를 구할 때는 수열을 사용해서 만들어준다.

먼저 0~ 던전의 갯수 까지의 배열을 만들어준다.

만약 던전의 갯수가 3이라면 [0,1,2] 가 만들어진다.

  do{
	int pirodo=k;
	int count=0;
	for(int i=0; i<v.size(); i++){
        	if(pirodo>=dungeons[v[i]][0]){
                //피로도 차감 및 던전 갯수 올리기
                count++;
                pirodo-=dungeons[v[i]][1];
            }
	}
    	answer=max(answer,count);
}while(next_permutation(v.begin(),v.end()));

만들어진 배열을 가지고 next_permutation() 함수를 통해서 수열의 경우의 수를 출력한다.

do while문을 통해 수열의 경우의 수를 받아올 때 피로도와 던전이 필요한 최소 피로도를 넘긴다면 던전을 클리어하도록 설계한다.

만약 최소 피로도를 넘기지 못하면 계산하지 않고 넘어간다.

계산이 끝난 후 만약 Count가 기존의 answer보다 클 경우 answer에 count 값을 삽입한다.

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

[프로그래머스] 체육복 (1)	2023.11.15
[프로그래머스] 모음사전 C++ (1)	2023.11.07
[프로그래머스] 전력망을 둘로 나누기 C++ (0)	2023.10.30
[프로그래머스] 카펫 (1)	2023.10.26
[프로그래머스] 소수 찾기 (C++) (0)	2023.10.23

1. 문제

원본 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42842

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

2. 코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    
    //완전 탐색
    int sum = brown+yellow;
    for(int i=2;i<sum;i++){
        if(sum%i!=0) continue;
        else
        {
            if((i-2)*(sum/i-2)==yellow)
            {
                answer.push_back(sum/i);
                answer.push_back(i);
                break;
            }
            else continue;
        }
    }
    
    return answer;
}

3. 해설

//완전 탐색
    int sum = brown+yellow;
    for(int i=2;i<sum;i++){
        if(sum%i!=0) continue;

먼저 brown+yellow를 더하면 모든 타일의 갯수를 구할 수 있습니다.

타일의 갯수는 가로x세로의 경우의 수를 구할 수 있기에 구해줍니다.

타일의 세로 길이는 1보다 커야하기에(0이나 1인 경우 노란색 구역이 생길 수 없음) i=2부터 for문을 돌려줍니다.

if(sum%i!=0) : 만약 나누어 질수 없는 경우라면 가로 세로를 구할수 없기 때문에 계산하지 않고 넘어갑니다.

        else
        {
            if((i-2)*(sum/i-2)==yellow)
            {
                answer.push_back(sum/i);
                answer.push_back(i);
                break;
            }
            else continue;
        }
    }

나누어지는 경우라면, 해당 가로 세로의 길이에서 2씩 빼서 yellow 영역의 갯수를 구합니다.

만약 yellow 갯수가 맞다면 해당 값들을 answer에 저장해줍니다.

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

[프로그래머스] 체육복 (1)	2023.11.15
[프로그래머스] 모음사전 C++ (1)	2023.11.07
[프로그래머스] 전력망을 둘로 나누기 C++ (0)	2023.10.30
[프로그래머스] 피로도 C++ (0)	2023.10.26
[프로그래머스] 소수 찾기 (C++) (0)	2023.10.23

1. 문제

한자리 숫자가 적힌 종이 조각이 흩어져있습니다.

흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

2. 코드

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

int solution(string numbers) {
    int answer=0;
    
    //next_permutation을 사용
    //순열 계산에서 1자리,2자리 ~ n자리만 사용하는 모든 경우의 수 구하기
    sort(numbers.begin(),numbers.end());
    vector<unsigned int> nums;
    string sub;
    do {
        for (int i = 1; i <=  numbers.size(); i++)
        {
            sub = numbers.substr(0, i);
            nums.push_back(stoi(sub));
        }
    } while (next_permutation(numbers.begin(), numbers.end()));
    
    //중복된 숫자 제거하기
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(),nums.end()), nums.end());
    
    //에라토스테네스체 구하기
    unsigned int nn=9999999;
    vector<bool> isPrimeNum(nn+1);
    isPrimeNum[1] = true; // 1은 소수가 아니므로 true
    for(unsigned int i = 2; i <= sqrt(nn); i++){
        if(isPrimeNum[i]) continue; // 이미 true면 계산 제외
        for(unsigned int j = i + i; j <= nn; j += i) // i를 제외한 i의 배수들은 소수가 아니다.
            isPrimeNum[j] = true;
    }

    for(int i=0;i<nums.size();i++){
	    if(!isPrimeNum[nums[i]]&nums[i]>0)      //0인 경우 제외
            answer++;
    }
    
    return answer;
}

3. 해설

    //next_permutation을 사용
    //순열 계산에서 1자리,2자리 ~ n자리만 사용하는 모든 경우의 수 구하기
    sort(numbers.begin(),numbers.end());
    vector<unsigned int> nums;
    string sub;
    do {
        for (int i = 1; i <=  numbers.size(); i++)
        {
            sub = numbers.substr(0, i);
            nums.push_back(stoi(sub));
        }
    } while (next_permutation(numbers.begin(), numbers.end()));

먼저 경우의 수를 구하기 위해서 string을 정렬해주고, next_permutation 함수를 통해 1~n자리의 모든 경우의 수를 구합니다.

    //중복된 숫자 제거하기
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(),nums.end()), nums.end());

그 후, 중복 경우의 수가 있을 수 있으므로, 중복된 숫자를 제거해줍니다.

    //에라토스테네스체 구하기
    unsigned int nn=9999999;
    vector<bool> isPrimeNum(nn+1);
    isPrimeNum[1] = true; // 1은 소수가 아니므로 true
    for(unsigned int i = 2; i <= sqrt(nn); i++){
        if(isPrimeNum[i]) continue; // 이미 true면 계산 제외
        for(unsigned int j = i + i; j <= nn; j += i) // i를 제외한 i의 배수들은 소수가 아니다.
            isPrimeNum[j] = true;
    }

에라토스테네스체의 해 알고리즘을 이용하여 주어진 범위 내에서 소수가 아닌 값들을 true로 표시해줍니다.

    for(int i=0;i<nums.size();i++){
	    if(!isPrimeNum[nums[i]]&nums[i]>0)      //0인 경우 제외
            answer++;
    }

소수 판별 vector isPrimeNum을 가지고 경우의 수들의 리스트 nums의 값과 비교하여 만약 소수가 아닌 경우(false) answer을 한개 늘려줍니다.

경우의 수가 0인경우는 소수가 아니기 떄문에 제외합니다.

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

[프로그래머스] 체육복 (1)	2023.11.15
[프로그래머스] 모음사전 C++ (1)	2023.11.07
[프로그래머스] 전력망을 둘로 나누기 C++ (0)	2023.10.30
[프로그래머스] 피로도 C++ (0)	2023.10.26
[프로그래머스] 카펫 (1)	2023.10.26

큐를 가장 쉽게 이해하는 방법은 줄을 서서 하는 싸인회를 생각하면 된다.
예를 들어서 유명 가수의 싸인회가 열린다고 가정해보자
나는 가수의 싸인회에 당첨이 되었고 현장에서 3번의 번호를 부여받았다.
다른 팬들은 1~20번의 번호를 부여받았다고 가정하였을 때, 진행자가 1번부터 싸인을 받으러 오라고 부를 것이다.
그리고 2~20번의 사람들에게 차례로 줄을 서라고 할 것이고 그 다음 차례는 2번부터 순서대로 싸인을 받으러 줄을 이탈할 것이다.
이게 바로 큐의 개념이다! FIFO(First In First Out) 선입선출 자료구조이다.
먼저 들어간 데이터는 먼저 빠져나온다. 즉 2번이 맨 앞에 있는데 3번이 먼저 빠져나갈 수 없다는 것이다.

큐가 쓰이는 구조는 어디에 있을 까? 미루어 짐작해보건데
명절날 내려가는 KTX 예매를 할 때, 내 앞의 대기자 00명이 있습니다. 라는 문구를 본 적 있는가?
아마도 그러한 곳에 쓰일 것 같다.
물론 이것 말고도 많은 곳에 쓰이겠지만 가장 가시적으로 볼 수 있는 느낌이 아닐까 싶다.

'알고리즘 > 자료구조' 카테고리의 다른 글

2. 스택 (0)	2023.09.07
1. 리스트 (0)	2023.09.05

KiTFOx's Notepad 📝

알고리즘

[프로그래머스] 모음사전 C++

1. 문제

2. 코드

3. 해설

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

[프로그래머스] 전력망을 둘로 나누기 C++

1. 문제

2. 코드

3. 해설

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

[프로그래머스] 피로도 C++

1. 문제

2. 코드

3. 해설

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

[프로그래머스] 카펫

1. 문제

2. 코드

3. 해설

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

[프로그래머스] 소수 찾기 (C++)

1. 문제

2. 코드

3. 해설

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

3. 큐

'알고리즘 > 자료구조' 카테고리의 다른 글

+ Recent posts

티스토리툴바