Level 2. 후보키 카카오 문제 답게 하나의 개념만 물어보지 않고, 조합과 중복 체크 등 여러 개념을 물어보는 문제였다. 그래서 카카오 문제를 풀고 나면 항상 함수가 많다.. 처음에 해시 값을 계산해 중복을 체크할 때, 각 속성 값의 해시 값을 더해 계산해서 오답 처리되었다. (2, 3)과 (3, 2)가 같은 것으로 처리되었기 때문이다. 각 속성들을 하나의 문자열로 합친 후 해시 값을 계산해 해결했다. 최소성의 경우 적은 수의 조합부터 후보키가 가능한지 검사하고, bitset과 교집합(&)을 이용해 확인했다. #include #include #include #include #include #include using namespace std; using bset = bitset; vector get_c..

Level 2. 마법의 엘리베이터 #include #include using namespace std; int solution(int storey) { if (storey < 10) return min(storey, 11 - storey); int left = storey % 10; return min(left + solution(storey / 10), 10 - left + solution(storey / 10 + 1)); }

Level 2. 배달 처음에 그냥 DFS로 해결하려다가 방문 여부를 관리하면서 최소 비용을 갱신하는 방법이 잘 떠오르지 않아 찾아봤다. 결국은 전형적인 다익스트라 알고리즘 문제였다.. [ 프로그래머스 배달 (Lv2) ] (C++) 프로그래머스의 배달(Lv2) 문제이다. [ 문제풀이 ] 1번마을에서 K시간내에 배달을 갈 수 있는 마을의 갯수를 구해야 하는 문제이다. #1. 구해야 하는 값 1번 마을에서 K시간내에 배달을 갈 수 있는 yabmoons.tistory.com vector를 활용한 인접 리스트로 그래프를 만들었다. 처음에 우선순위 큐에 시작점을 0의 비용으로 넣고, 매번 가장 비용이 적은 정점을 우선순위 큐에서 뽑는다. 뽑은 정점의 인접 정점들의 비용을 갱신한다. 인접 정점의 비용 > 나의 비용 ..

Level 2. 전력망을 둘로 나누기 2차원 vector를 활용한 인접 리스트로 그래프를 만들었고, 각 연결을 끊고 끊은 두 지점부터 DFS를 수행해 차이를 계산한 최솟값을 구하면 된다. #include #include #include #include using namespace std; int rDFS(vector& tree, int vertex) { int nConnected = 1; for (int j = 1; j < tree.size(); ++j) { if (tree[vertex][j]) { tree[vertex][j] = tree[j][vertex] = false, nConnected += rDFS(tree, j); } } return nConnected; } int calculate(vecto..

Level 2. 미로 탈출 최단 거리를 구해야 하는 전형적인 BFS 문제다. 출발지와 목적지의 거리를 구하는 함수를 만들어 재사용하면 편하고, 좌표에 unsigned 형을 사용하면 범위 검사가 간편해진다. #include #include #include using namespace std; struct Point { unsigned x; unsigned y; bool operator == (const Point& p) { return (x == p.x) && (y == p.y); } }; struct Entity { int level; Point point; }; int distance(vector& maps, Point from, Point to) { int X = maps.size(), Y = map..

Level 2. 메뉴 리뉴얼 코드가 다소 길긴 하지만 엄청 복잡하지는 않다. 모든 메뉴에서 가능한 n개 메뉴의 경우의 수를 구한다. 그 중 2번 이상 주문된 조합을 주문 수를 기준으로 메뉴 vector를 저장하는 set에 넣는다. 마지막에 가장 많게 주문된 조합들을 정답에 넣는다. 경우의 수 조합을 구할 때, 알파벳이 들어있는 map을 사용하므로 별도의 정렬은 필요하지 않다. 하지만, 모든 메뉴를 map에 넣어 가능한 경우의 수를 계산해서 그런지 시간 초과가 발생했다. // 이 풀이는 시간 초과가 발생한다. #include #include #include #include #include using namespace std; vector get_combinations(map& mp, int start, i..