#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
string solution(vector<string> participant, vector<string> completion) 
{
    string answer = "";
    
    sort(participant.begin(), participant.end());
    sort(completion.begin(), completion.end());
    
    for(int i = 0; i < completion.size(); i++)
    {
        if(participant[i] != completion[i])
        {
            answer = participant[i];
            return answer;
        }
    }
    
    // 끝까지 했는데 못찾은 경우, participant의 맨 마지막이 정답
    answer = participant[participant.size()-1];
    return answer;
}
cs
저작자표시

'Programmers > Level 1' 카테고리의 다른 글

[프로그래머스 1] 가운데 글자 가져오기 (C/C++)  (0) 2019.10.17
[프로그래머스 1] 2016년 (C/C++)  (0) 2019.10.17
[프로그래머스 1] K번째수 (C/C++)  (0) 2019.10.17
[프로그래머스 1] 체육복 (C/C++)  (0) 2019.10.16
[프로그래머스 1] 모의고사 (C/C++)  (0) 2019.10.16
#include <string>
#include <vector>
#include <stack>
using namespace std;
 
int isRight(string p)
{
    stack<char> st;
    
    for(int i = 0; i < p.size(); i++)
    {
        if(p[i] == '(')
        {
            st.push(p[i]);
        }
        else
        {
            if(st.empty())
            {
                return 0;
            }
            
            st.pop();
        }
    }
    
    if(st.empty())
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
string solution(string p) 
{
    // 이미 올바른 문자열이면 출력
    if(isRight(p) == 1)
    {
        return p;
    }
    
    string answer = "";
    string u = "";
    string v = "";
    
    int leftCnt = 0;
    int rightCnt = 0;
    
    // 1
    if(p == "")
    {
        return "";
    }
    
    // 2
    for(int i = 0; i < p.size(); i++)
    {
        if(p[i] == '(')
        {
            leftCnt++;
        }
        else
        {
            rightCnt++;
        }
        
        if(leftCnt == rightCnt)
        {
            u = p.substr(0, leftCnt+rightCnt);
            v = p.substr(leftCnt+rightCnt, p.size()-(leftCnt+rightCnt));    
            break;
        }
    }
    
    // 3
    if(isRight(u) == 1)
    {
        answer += u;
        string temp = solution(v);
        answer += temp;
    }
    // 4
    else
    {
        // 4-1 ~ 4-3
        string temp1 = "(";
        string temp2 = solution(v);
        temp1 += temp2;
        temp1 += ")";
        
        // 4-4, remove 
        string temp3 = u.substr(1, u.size()-2);
        
        // 4-4, reverse
        temp2 = "";
        for(int i = 0; i < temp3.size(); i++)
        {
            if(temp3[i] == '(')
            {
                temp2 += ')';
            }
            else
            {
                temp2 += '(';
            }
        }
        
        temp1 += temp2;
        answer = temp1;
    }
    
    return answer;
}
cs
저작자표시

'Programmers > Level 2' 카테고리의 다른 글

[프로그래머스 2] 탑 (C/C++)  (1) 2019.10.21
[프로그래머스 2] 124 나라의 숫자 (C/C++) (★)  (0) 2019.10.21
[프로그래머스 2] 주식가격 (C/C++)  (0) 2019.10.20
[프로그래머스 2] 기능개발 (C/C++)  (0) 2019.10.20
[프로그래머스 2] 스킬트리 (C/C++)  (0) 2019.10.20

#include<algorithm> sort

https://blockdmask.tistory.com/178

 

[C++] sort algorithm 정리 및 예시

안녕하세요 BlockDMask 입니다. 오늘은 C++ STL 에서 제공하는 알고리즘 중에 sort 알고리즘에 대해 알아보겠습니다. 0. sort algorithm sort 알고리즘은 헤더파일에 속해있습니다. sort(start, end)..

blockdmask.tistory.com

https://hongku.tistory.com/153

 

C++ :: STL sort() 함수 다루기, 오름차순 내림차순, 학생 점수 순서대로 나열하기

STL sort() 함수 정렬을 만들어서 사용할 수 는 있지만, 매번 만들어서 사용하기는 번거롭다. 이럴때, 'alforithm' 을 include해서 그안에 있는 sort() 함수를 사용하면 된다. 1. sort() 함수를 이용한 오름차순과..

hongku.tistory.com

 

#include<queue> sort (priority_queue)

https://koosaga.com/9

 

STL priority queue 활용법

모든 nlgn들의 영웅(?) 같은 priority_queue 존재 그 자체로 멋지지만 정말 멋지게 쓰기 위해서는 제대로 활용할 줄 알아야 할 것이다. 1. Colored By Color Scripter™ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1..

koosaga.com

 

차이점

1.

  • #include <algorithm> : sort에서는 greater가 내림차순
  • #include <queue> : priority_queue의 sort에서는 greater가 오름차순

2.

  • #include <algorithm> : sort에서는 1번의 greater를 사용시에 greater<int>()와 같이 사용
  • #include <queue> : priority_queue의 sort에서는 1번의 greater를 사용시에 gerater<int>와 같이 사용

3. 

  • #include <algorithm> : sort에서는 cmp 함수를 만들때 인자의 왼쪽이 기준
  • #include <queue> : priority_queue의 sort에서는 cmp 함수를 만들때 인자의 오른쪽이 기준

 

추천방법

1. #include <algorithm> : 비교함수 cmp를 만들어서 사용

2. #include <algorithm> : greater<type>() 사용 -> 구조체는 1번, 어떤 원소를 비교할지 몰라 에러 발생

 

bool cmp(pair<int, string> v1, pair<int, string> v2)
{
    if(v1.first == v2.first)
    {
         sort는 왼쪽이 기준이기 때문에 second 오름차순 정렬 
        return v1.second < v2.second;
    }
    else
    {
         sort는 왼쪽이 기준이기 때문에 first 오름차순 정렬     
        return v1.first < v2.first;    
    }
}
vector<pair<int, string>> v;
sort(v.begin(), v.end(), cmp); 
 
 
sort(v.begin(), v.end()); // 오름차순
sort(v.begin(), v.end(), greater<int>()); // 내림차순
 cs

 

3. #include <queue> : 클래스 cmp에 oeprator()를 만들어서 사용

4. #include <queue> : less<type>, greater<type> 사용

 

//struct cmp 
class cmp
{
    public:
        bool operator()(pair<int, int> pq1, pair<int, int> pq2)
        {
            if(pq1.first == pq2.first)
            {
                // priority_queue는 오른쪽이 기준이기 때문에 second 오름차순 정렬 
                return pq1.second > pq2.second;
            }
            else
            {
                // priority_queue는 오른쪽이 기준이기 때문에 first 오름차순 정렬     
                return pq1.first > pq2.first;   
            }
        }
};    
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
 
 
// 일반적인 사용법도 추천
priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> pq;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
 cs

 

 

 

저작자표시

#include <map>

1. 기본형

  • map<key,value> : key와 value를 pair 형태로 선언, 각 key와 value에 사용할 type 선언

2. 반복자(iterator)

  • begin() : beginning iterator를 반환
  • end() : end iterator를 반환

3. 추가 / 삭제

  • insert(make_pair(key,value)) : 맵에 원소를 pair 형태로 추가
  • erase(key) : 맵에서 key(키값)에 해당하는 원소 삭제
  • clear() : 맵의 원소들 모두 삭제

4. 조회

  • find(key) : key(키값)에 해당하는 iterator 반환, iterator의 first, second 통해 key, value에 접근 -> 없으면 end() 반환
  • count(key) : key(키값)에 해당하는 원소들(value들)의 개수를 반환

5. 기타

  • empty() : 맵이 비어있으면 true 아니면 false를 반환
  • size() : 맵 원소들의 수를 반환

 

#include <iostream>
#include <map>
#include <string>
using namespace std;
 
int main()
{
    // 기본형 선언 
    map<string, int> m;
    
    // iterator 선언 
    map<string, int>::iterator it;
 
 
 
    // insert(key,value)
    m.insert(make_pair("a", 1));
    m.insert(make_pair("b", 2));
    m.insert(make_pair("c", 3));
    m.insert({"d", 4});
    m.insert({"e", 5});
 
    // 주로 사용하는 형태
    m["f"] = 6;
 
 
 
    // erase(key)
    m.erase("d");
    m.erase("e");
    m.erase(m.find("f")); 
 
 
 
    // empty(), size()
    if(!m.empty()) cout << "m size : " << m.size() << "\n";
 
 
 
    // find(key)
    cout << "a : " << m.find("a")->second << "\n";
    cout << "b : " << m.find("b")->second << "\n";
    // it = m.find("a");
    // cout << "a : " << (*it).second << "\n";
    // if(m.find("a") != m.end())을 통해 키값 유무 확인
 
 
    // count(key)
    cout << "a count : " << m.count("a") << "\n";
    cout << "b count : " << m.count("b") << "\n";
    // if(m.count("a") != 0)을 통해 키값 유무 확인
 
 
 
    // begin(), end()
    cout << "traverse" << "\n";
    
    // for(auto it = m.begin(); it != m.end(); it++)
    for(it = m.begin(); it != m.end(); it++)
    {
        cout << "key : " << it->first << " " << "value : " << it->second << "\n";
    }
 
    return 0;
}
   cs

 

출처 :

https://twpower.github.io/91-how-to-use-map-in-cpp

 

저작자표시

'STL > map' 카테고리의 다른 글

<map> vs <unordered_map> 차이  (0) 2020.03.31

알고리즘 문제를 풀다가 main 함수에 int arr[5000][5000]을 선언했는데 바로 종료가 되어서... 검색해봤다.

 

함수 내에서 선언되어 사용되는 배열의 경우 배열 자체가 스택 영역에 생성되고, 함수가 호출될 때 마다 해당 배열을 위한 메모리를 새로 생성하고 초기화 하는 작업을 하기 때문에 배열의 크기가 큰 경우에는 다른 방법을 사용해야 한다.

함수 내에서 크기가 큰 배열을 생성하는 경우 다음과 같은 문제점을 일으킬 수 있다

  • 배열을 초기화 하는 경우 함수가 호출될 때 마다 값을 채워넣어야 하기 때문에 프로그램의 수행 속도가 느려질 수 있다. 특히나 자주 호출되는 함수인 경우에는 프로그램의 속도를 치명적으로 느리게 만들 수 도 있다.
  • 이론적으로 스택 -- 지역 자동변수가 저장되는 영역의 크기는 제한되지 않지만, 시스템에 따라 하드웨어적인 제한이나 스택 운영의 효율을 높이기 위해 스택의 크기를 제한하기도 한다. 그렇기 때문에 함수 내에서 선언되는 배열의 크기가 과도하게 큰 경우 스택 오버플로우 에러가 발생하고 프로그램이 강제 종료 될 수 도 있다.
  • 컴파일러의 종류나 옵션에 따라서는 컴파일된 프로그램의 크기가 커질 수 도 있다.

그래서 배열의 크기가 조금이라도 크다는 느낌이 든다면 다른 메모리 영역을 사용하는 것을 고려해 볼 필요가 있다

  • 전역 변수나 스태틱 변수를 사용한다.
  • alloc() 계열의 함수를 이용하여 힙영역을 할당하여 사용한다.

출처 :

https://ko.wikibooks.org/wiki/C_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D_%EC%9E%85%EB%AC%B8/%EB%8D%B0%EC%9D%B4%ED%84%B0_%EB%B0%B0%EC%97%B4

 

저작자표시

'Algorithm' 카테고리의 다른 글

완전탐색  (0) 2020.01.27
Prim vs Dijkstra (프림 다익스트라 비교)  (4) 2019.09.23
Dijkstra vs Floyd-Warshall (다익스트라 플로이드 비교)  (0) 2019.09.23

우선순위 큐는 priority_queue<자료형, 구현체, 비교연산자>로 정의한다.

 

구현체는 기본적으로 vector<자료형> 형태로 정의한다.

비교연산자는 functional 라이브러리 추가를 통해 greater<int> 오름차순으로 정렬 가능하다.

 

#include <stdio.h>
#include <queue>
#include <functional>
using namespace std;
 
int main()
{
    priority_queue<int, vector<int>, less<int>> pq;
    
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(1);
    pq.push(5);
    pq.push(9);
    
    while (!pq.empty()) 
    {
        printf("%d",pq.top());
        pq.pop();
    }
}
 cs

 

추가 참고자료 :

https://koosaga.com/9

 

저작자표시

scanf와 cin은 다음과 같이 속도면에서 큰 차이가 난다.

따라서 이를 해결하기 위해 사용할 수 있는 방법이 있다.

 

1
2
3
ios_base :: sync_with_stdio(false); 
cin.tie(NULL); 
cout.tie(NULL);
 cs

 

+ endl 보다 "\n" 사용하는 것이 더 빠르다.

 

하지만 이는 일종의 편법이므로, 다음과 같은 주의사항이 있다.

 

1. scanf, printf와 함께 사용하면 안된다.

2. 싱글 쓰레드 환경에서만 사용 가능하다. (알고리즘 문제풀이시에 사용, 실무에서는 사용 X)

 

저작자표시

'C++' 카테고리의 다른 글

C/C++ 소수점 출력하는 방법  (0) 2020.07.21

프림 알고리즘 (최소스패닝트리)

  • 그래프상에 존재하는 모든 노드들을 최소비용으로 연결시키는 알고리즘

 

프림 알고리즘을 적용한 모습

#include <stdio.h>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
 
int visited[10001];
int V, E;
int ans;
 
vector<pair<int, int>> map[10001];
 
void prim(int start)
{
    visited[start] = 1;
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    for(int i = 0; i < map[start].size(); i++)
    {
        int next = map[start][i].first;
        int nextCost = map[start][i].second;
        
        pq.push(make_pair(nextCost, next));
    }
    
    while(!pq.empty())
    {
        int now = pq.top().second;
        int nowCost = pq.top().first;
        pq.pop();
        
        if(visited[now] == 1)
        {
            continue;
        }
        
        visited[now] = 1;
        
        ans += nowCost;
        
        for(int i = 0; i < map[now].size(); i++)
        {
            int next = map[now][i].first;
            int nextCost = map[now][i].second;
            
            pq.push(make_pair(nextCost, next));
        }
    }
}
 
int main(void)
{
    freopen("B1197_input.txt", "r", stdin);
    
    scanf("%d %d", &V, &E);
    
    for(int i = 0; i < E; i++)
    {
        int from, to, weight;
        scanf("%d %d %d", &from, &to, &weight);
        
// 무향
        map[from].push_back(make_pair(to, weight));
        map[to].push_back({from, weight});
    }
    
    prim(1);
    
    printf("%d", ans);
    
    return 0;
}
 
 cs
 

 

 

다익스트라 알고리즘 (최단경로트리)

  • 시작 노드(1)로부터 그래프 상에 존재하는 모든 노드, 즉 두 노드 사이의 최단거리를 구하는 알고리즘

 

다익스트라 알고리즘을 적용한 모습

#include <stdio.h>
#include <vector>
#include <queue>
#include <functional> // 우선순위큐의 greater
using namespace std;
 
int d[20001];
int V, E;
int start;
 
vector<pair<int, int>> v[20001];
 
void solve(int start)
{
    d[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});
    
    while(!pq.empty())
    {
        int now = pq.top().second;
        int nowCost = pq.top().first;
        pq.pop();
        
        if(d[now] != nowCost)
        {
            continue;
        }
        
        for(int i = 0; i < (int)v[now].size(); i++)
        {
            int next = v[now][i].first;
            int nextCost = d[now]+v[now][i].second;
            
            if(nextCost < d[next])
            {
                d[next] = nextCost;
                pq.push({nextCost, next});
            }
        }
    }
}
 
int main(void)
{
    freopen("B1753_input.txt", "r", stdin);
    
    scanf("%d %d %d", &V, &E, &start);
    
    for(int i = 1; i <= V; i++)
    {
        d[i] = 9999999;
    }
 
    for(int i = 1; i <= E; i++)
    {
        int from, to, weight;
        scanf("%d %d %d", &from, &to, &weight);    
        
 // 유향
        v[from].push_back({to, weight});
    }
    
    solve(start);
    
    for(int i = 1; i <= V; i++)
    {
        if(d[i] == 9999999)
        {
            printf("INF\n");
        }
        else
        {
            printf("%d\n", d[i]);    
        }
    }
    
    return 0;
}
 
 cs

 

차이점

1. 프림은 다익스트라와 달리 두 노드 사이가 최단거리가 아닐 수도 있다.

   ※ 프림은 1->3의 비용이 3인 반면에, 다익스트라는 1->3의 비용이 2이다.

2. 프림은 무향 그래프에서만 작동하고, 다익스트라는 무향, 유향 그래프에서 모두 작동한다.

3. 프림이 다익스트라를, 다익스트라가 프림을 보장해주지 않는다.

   -> 최소스패닝트리가 최단경로트리를, 최단경로트리가 최소스패닝트리를 보장하지 않는다.

 

저작자표시

'Algorithm' 카테고리의 다른 글

완전탐색  (0) 2020.01.27
지역변수로 크기가 큰 배열 선언 시 문제점  (0) 2019.09.27
Dijkstra vs Floyd-Warshall (다익스트라 플로이드 비교)  (0) 2019.09.23

+ Recent posts

티스토리툴바