코학다식

프로그래머스: 순위 문제 링크 플로이드 와샬로 모든 정점에서 모든 정점의 관계를 파악해서 풀 수 있는 문제였다. 구체적인 순위가 필요한 것이 아니라 "정확하게 순위를 매길 수 있는 선수의 수"를 구하는 것이 목적이므로, 플로이드 와샬을 이용해서 모든 정점(선수)에서 모든 정점(선수)까지의 경로를 찾는다. 경로가 존재한다면 승패가 가려진 상황이므로, 한 정점에서 다른 모든 정점까지의 경로가 존재하는 경우라면 순위를 정확하게 매길 수 있다. 처음에 배열을 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 혹은 그와 유사한 다른 자료구조를 사용해서 쉽게 풀 수 있는 문제이다. 옷을 종류별로 구분해서 저장하기 위해 map으로 선언해 준 후 주어진 배열을 탐색하면서 종류별 배열에 옷을 넣어 주었다. 종류마다 옷을 하나씩 선택(n)하거나 선택하지 않는 경우(1)의 수가 있는데, 서로 다른 옷의 조합의 수를 구하기 위해 종류마다 가능한 경우(총 n+1)를 곱해 준 후 아무것도 선택하지 않는 경우를 빼 준다. 풀이 #include #include #include #include using namespace std; int solution(vector clothes) { int answer = 1; map m; // 옷의 종류, 실제 옷을 저장하는 배열 for(vecto..