코학다식

프로그래머스: 순위 문제 링크 플로이드 와샬로 모든 정점에서 모든 정점의 관계를 파악해서 풀 수 있는 문제였다. 구체적인 순위가 필요한 것이 아니라 "정확하게 순위를 매길 수 있는 선수의 수"를 구하는 것이 목적이므로, 플로이드 와샬을 이용해서 모든 정점(선수)에서 모든 정점(선수)까지의 경로를 찾는다. 경로가 존재한다면 승패가 가려진 상황이므로, 한 정점에서 다른 모든 정점까지의 경로가 존재하는 경우라면 순위를 정확하게 매길 수 있다. 처음에 배열을 int로 선언했을 때는 계속 오답이라고 나왔는데, 이유를 모르겠다. 어차피 0이냐, 아니냐만 따지면 되기 때문에 문제될 것이 없다고 생각했는데 왜일까? 풀이 #include #include #include #include #include using name..

프로그래머스: 가장 먼 노드 문제 링크 전형적인 BFS 문제였다. 1번 노드에서 BFS를 시작해서 단계가 진행될 때마다 거리를 1씩 늘려서 함께 저장하도록 한다. 풀이 #include #include #include #include #include using namespace std; using pii = pair; bool visited[20001]; vector graph[20001]; bool desc(int a, int b) { return a > b; } int solution(int n, vector edge) { int answer = 0, v, u, cnt; for(int i = 0; i < edge.size(); i++){ u = edge[i][0]; v = edge[i][1]; grap..

프로그래머스: 베스트앨범 문제 링크 위장과 마찬가지로 C++의 map을 활용해서 풀 수 있는 문제였다. 장르별로 노래를 보관하는 배열을 가지고 있고, 노래가 추가될 때마다 재생 횟수와 고유 번호에 따라 정렬해 주도록 한다. 이 작업이 완료되면 속한 노래가 많이 재생된 장르 순서대로 앨범에 노래를 넣어 주어야 하는데, 이를 위해서 속한 노래의 모든 재생 횟수를 키로 가지고 장르 이름을 값으로 가지는 맵을 하나 더 선언해 주었다. 맵은 키에 따라 자동으로 오름차순으로 정렬되는데, 내림차순이 필요하기 때문에 -1을 곱해 주었다. 맵을 사용할 수 있었던 건 모든 장르는 재생된 횟수가 다르다는 조건 때문이었다. 자동으로 장르별로 내림차순 정렬이 되었으므로, 이제 이 순서를 따라 장르별로 노래를 넣어 준다. 장르에..

프로그래머스: 위장 문제 링크 c++의 map 혹은 그와 유사한 다른 자료구조를 사용해서 쉽게 풀 수 있는 문제이다. 옷을 종류별로 구분해서 저장하기 위해 map으로 선언해 준 후 주어진 배열을 탐색하면서 종류별 배열에 옷을 넣어 주었다. 종류마다 옷을 하나씩 선택(n)하거나 선택하지 않는 경우(1)의 수가 있는데, 서로 다른 옷의 조합의 수를 구하기 위해 종류마다 가능한 경우(총 n+1)를 곱해 준 후 아무것도 선택하지 않는 경우를 빼 준다. 풀이 #include #include #include #include using namespace std; int solution(vector clothes) { int answer = 1; map m; // 옷의 종류, 실제 옷을 저장하는 배열 for(vecto..

문제 링크 그래프에서 최단 경로를 찾는 알고리즘 중 하나인 벨만-포드 알고리즘으로 풀 수 있는 문제였다. 주의해야 할 점은 오버플로우가 발생할 수 있기 때문에 거리 배열의 타입을 long long으로 선언해 주어야 한다는 점이다. Bellman-Ford&#39;s Algorithm 어떤 경로든 최대 ||V|| - 1개의 간선으로 이루어질 수 있으므로 모든 간선을 ||V|| - 1번 확인하면서 모든 정점의 최단 거리를 갱신하는 알고리즘이다. 한 개의 정점에서 시작해 모든 정점으로 가는 최단 경로를 찾는다. 간선이 E개, 정점이 V개일 때 각 간선을 ||V|| - 1번 확인하므로 시간복잡도는 O(||V|| ||E||)가 된다. 음수인 간선이 있어도 사용할 수 있다. 아래의 예시에서 시작하는 정점은 S이다. ..

프로그래머스: 섬 연결하기 문제 링크 처음에는 아주 단순하게 생각해서 비용을 오름차순으로 정렬한 후에 선택된 다리의 수가 n-1개 이상이 되면 모든 섬을 방문하는지 확인하도록 했다. 결과는 당연히 틀렸다. 아마 사이클을 고려하지 않았기 때문인 것 같다. 질문하기를 보니 크루스칼 알고리즘(Kruskal Algorithm)을 사용했다는 말이 보였고, 바로 사용해 보았더니 쉽게 통과했다. 알고리즘 수업 이후로 잊고 살았던 이 친구를 다시금 리마인드하는 계기가 되었다. Kruskal Algorithm 가장 적은 비용으로 모든 노드를 연결하는 알고리즘이다. 즉, 최소 비용 신장 트리를 만드는 알고리즘이라고 할 수 있다. 모든 노드를 가장 적은 비용으로 연결시키기 위해 모든 간선(비용) 정보를 오름차순으로 정렬 후..

문제 링크 Solution 처음에는 양수 배열과 음수 배열로 나누어서 이분 탐색을 실행하는 걸 고민해 봤는데, 번거로운 것 같고 다른 방법이 있을 것 같아 다른 방법을 찾다 절댓값으로 정렬해서 이웃한 두 수를 더하는 방법을 사용했다. 이 방법을 사용하면 모두 양수인 경우, 모두 음수인 경우도 쉽게 해결할 수 있다. 대충 봤을 때 값이 꽤 커 보이기에 모든 변수를 long long으로 선언해 줬다. +) C++의 sort 함수는 정말 자주 유용하게 쓰이는 것 같다. code #include #include #include #include using namespace std; vector ans; bool cmp (const long long a, const long long b) { if (abs(a) =..

문제 링크 Solution 정렬 함수인 sort()만 사용하면 쉽게 풀 수 있는 문제로 보이지만, 주의해야 할 것이 하나 있다. 나이가 같은 경우 먼저 가입한, 즉 먼저 입력받은 요소가 앞에 와야 한다는 것이다. 이를 위해 비교 함수(comp)를 바꿔 줄 수도 있지만, sort()와 같이 정렬 함수 중 하나인 stable_sort()를 사용하면 간편하게 풀 수 있다. stable_sort()는 sort()와 같이 정렬을 수행한다는 것은 같지만 값이 같은 경우에는 원래의 순서를 그대로 유지한다. sort()의 경우 입력받은 데이터의 크기가 작으면 값이 같은 경우에 따로 처리를 해 주지 않아도 순서가 유지되는 것처럼 보이나, 데이터가 커지면 랜덤하게 바뀔 수 있다. code #include #include ..