알고리즘 문제 풀이/Programmers

각 단계에서 최선의 선택을 하여 문제를 풀 수 있는 그리디 문제이다. 그리디 문제라고 생각은 하였으나 각 단계에서 최선의 선택이 무엇인지, 어떻게 구현할 수 있을지 생각하지 못해 풀 지 못한 문제였다. [ 풀이 방법 ] 처음에 가지고 있는 카드와 현재 라운드까지 뽑았던 카드를 각각 저장하고,1. 동전을 사용하지 않고 다음 라운드로 진행할 수 있는 경우  - 처음에 가지고 있는 n/3 장의 카드 중 2장을 사용하여 카드에 적힌 수의 합이 n+1이 되도록 만들 수 있는 경우2. 동전을 1개만 사용하여 다음 라운드로 진행할 수 있는 경우  - 처음에 가지고 있는 n/3 장의 카드 중 1장과 현재 라운드까지 뽑았던 카드 중 1장을 사용하여 카드에 적힌 수의 합이 n+1이 되도록 만들 수 있는 경우3. 동전을 2..

A가 먼저 n / 2개의 주사위를 가져가고, B가 남은 n / 2개의 주사위를 가져가는 경우의 수는 최대 10C5=252이고, A와 B가 가져간 주사위를 모두 굴려서 나오는 결과의 합을 구하는 경우의 수는 최대 65, 약 7700이다. 따라서, 완전 탐색을 이용해 A와 B가 주사위를 n / 2개 씩 가져가는 모든 경우에 대해 A와 B가 각각 가져간 주사위를 굴려서 나오는 모든 결과의 합을 구한 뒤 서로 비교하여 A가 승리하는 횟수가 가장 많은 경우를 찾아 문제를 해결할 수 있다. (252 x 7700은 약 200000) [ 문제 풀이 ] 1. 가져갈 주사위를 고르는 기능 - 완전 탐색을 이용해 A가 먼저 n / 2개의 주사위를 가져가고, B가 남은 n / 2개의 주사위를 가져가는 경우를 모두 탐색한다. ..

edges의 size가 최대 1,000,000이므로 최대 O(n log n)의 시간복잡도를 갖도록 구현해야 한다. [ 풀이 방법 ] 1. 생성한 정점을 찾는 기능 - 들어오는 edge가 없고 나가는 edge만 존재하는 정점 - 나가는 edge가 2개 이상이어야 한다. 2. 막대 모양 그래프의 개수를 구하는 기능 - 들어오는 edge만 있거나 나가는 edge만 존재하는 정점 - 들어오는 edge만 있는 정점의 개수를 센다. - 들어오는 edge와 나가는 edge 둘 다 없는 정점도 포함되어야 한다. 3. 8자 모양 그래프의 개수를 구하는 기능 - 들어오는 edge와 나가는 edge가 모두 2개인 정점의 개수를 센다. 4. 도넛 모양 그래프의 개수를 구하는 기능 - 생성한 정점에서 나가는 edge의 개수는 ..

[ 풀이 방법 ] 우선순위 큐를 이용한 BFS로 문제를 해결하였다. board의 빈 칸을 INF, 벽이 있는 칸을 -1로 초기화하고, (0, 0)부터 시작하여 우선순위 큐를 이용해 board의 특정 칸까지의 도로 건설 비용이 최소가 되는 순서로 BFS를 수행하며 board에 특정 칸까지의 도로 건설 비용이 최소값이 되는 경로만을 탐색하고 최소 비용을 board에 저장하였다. 탐색이 종료된 후 (N-1, N-1)에 저장된 값을 출력하여 문제를 해결하려 하였다. 그러나 2개의 테스트 케이스가 틀렸고, 질문하기를 참고하여 원인을 찾을 수 있었다. board의 특정 칸에 나중에 도착한 도로(board의 특정 칸까지의 도로 건설 비용이 더 큰 도로)가 (N-1, N-1)까지의 도로 건설 비용은 더 작을 수 있기 ..

행의 길이와 열의 길이가 최대 50000, 행*열이 최대 1000000, operation의 개수가 최대 100000이므로 ShiftRow와 Rotate 연산을 수행하는데 걸리는 시간복잡도는 O(log n)이어야 한다. 따라서, vector를 사용할 수 없고(맨 뒤에 원소 삽입, 삭제: O(1), 맨 앞의 원소 삭제: O(n)) deque를 사용해 연산을 수행한 뒤(맨 앞, 뒤에 원소를 삽입, 삭제: O(1)) 마지막에 모든 연산을 수행한 결과를 2차원 vector로 옮겨 반환해야 한다. ShiftRow 연산의 경우, 모든 열을 deque에 옮겨 순서를 바꾸는 것은 비효율적이고, Rotation 연산을 수행할 때는 열이 아닌 맨 위와 아래의 행이 필요하기 때문에 ShiftRow 연산을 수행할 때마다 맨..