이어서 랭킹이라는 문제다. 역시 문제를 열람할 수 없고 기억나는대로 문제를 서술해보면 다음과 같다. n명의 플레이어와 각 플레이어의 번호, 업적 점수 p, ??점수 g가 주어진다. 최종 점수는 p + 2 * g로 계산하며 플레이어들을 최종 점수를 기준으로 랭킹을 매겼을 때(점수가 같으면 p가 큰 플레이어가 더 상위 랭킹에 배치된다.), k 번째 랭킹에 해당하는 플레이어의 번호를 출력한다. 첫번째 문제가 난이도 1로 되어있고 두번째 문제가 난이도 2로 되어있었는데 나는 두번째 문제가 더 쉬운 느낌이였다. 단순히 어떤 컨테이너에 플레이어의 점수를 기준으로 내림차순 정렬을 한 뒤, k번째 값을 출력하면 되겠다 싶었다. 전체 플레이어 숫자 m_nPlayer, 찾고 싶은 랭킹 숫자 m_nTargetPlayer를 ..

어느새 코딩테스트 대비 수강이 끝나고 사후 모의고사를 보게되었고, 첫번째는 원카드라는 문제였다. 문제 내용을 다시 열람할 수 없어 정확히는 작성할 수 없지만 기억나는대로 작성하면 다음과 같다. 입력으로 확인해야하는 카드 수 n과 n만큼의 1 ~ 13 사이의 숫자가 입력으로 들어온다. n개의 입력에서 이전 숫자와 현재 숫자의 차이가 1만큼 나면 계단이라 정의한다. 연속적으로 계단을 이루는 최대 연속 수와 1 ~ 13의 각 숫자가 계단에 포함된 횟수를 출력한다. 나는 문제에서 n의 최대 수가 그렇게 많지 않고 일일히 보고 판단해도 문제가 되지 않는다고 생각해 다음과 같이 제출했다. 1 ~ 13 숫자가 계단에 포함된 횟수를 저장할 ans[13], 입력으로 들어올 카드 수 m_nCards, 계단의 개수 m_nS..

3주차 9강은 포격훈련이라는 문제였다. 문제 내용은 다음과 같다. 격자판에 점수가 있으며, 일정 범위 안의 격자판의 점수를 합산해 출력하면 되는 문제로 생각하고 그대로 코딩해보았다. 역시나 테스트 케이스만 통과되고 나머지는 TimeOut으로 통과되지 못했다. 그렇다면 일일히 계산하는 것이 아닌 더 빠른 방법으로 해야한다는 것인데, 동적계획법이 그 대안이 될 수 있을 것 같아 시도해보았다. nGrid에는 이제 각 보드의 점수가 들어가는 것이 아니라 1, 1을 기준으로 해당 칸까지의 점수를 합산한 값이 들어가게 한 뒤, 출력할 때는 이를 이용해 계산식으로 답을 출력하는 방식이다. 이렇게 하니 더 빠르게 계산이 가능했고 TimeOut이 나왔던 케이스들도 통과했다. 그래도 동적계획법에 점점 익숙해져가는 것 같아..

3주차 7강은 중앙값 구하기라는 문제이다. 문제 세부 내용은 다음과 같다. 즉, 매번 들어오는 값을 비교값으로 추가하면서 매번 중앙 값을 출력하면 되는 것이다. 이 문제를 봤을 때, Binary Tree가 제일 먼저 생각났다. 하지만 std::set은 중앙값을 가져오는 함수가 따로 존재하지 않기 때문에 비슷한 동작을 하는 시스템을 만들어 매번 중앙값을 출력하게 하면 되겠다 싶었다. 나는 다음과 같이 구현했다. 먼저, 작은 쪽의 원소들을 담을 m_pqLeft라는 priority_queue와 큰 쪽 원소들을 담을 m_pqRight라는 priority_queue를 선언한 다. 그리고 첫번째로 들어오는 값의 경우 무조건 중앙값이기 때문에 그대로 출력하고 m_pqLeft에 집어넣는다. 그 다음으로 들어오는 값들은..

3주차 5강은 수로 연결하기라는 문제였다. 문제 내용은 다음과 같다. 처음에는 문제가 이해가 되지 않아 그림판을 이용해 이해를 해보았는데 뭔가 학교에서 풀어봤던 문제라는 느낌이 났었다. 풀이는 기억나지 않았지만 익숙한 문제라는 느낌을 받았다. 그래도 풀이를 어떻게 하는게 좋을까하면서 고민했는데 도저히 모르겠어서 해설을 먼저 보게 되었다. 해설에서는 동적계획법을 이용해서 문제를 해결했는데 참고해 작성한 코드는 다음과 같다. d[i][j]를 i번째 파이프에서 부터 j번째 파이프까지 연결하기 위한 비용이라고 했을 때, d[i][j] = min(d[i][k] + d[k + 1][j] + 비용)인것을 이용해 문제를 해결하는 방식이였다. 정답을 내는 코드를 보고 이해를 해보면 이해가 되는데 막상 내가 풀때는 풀이 ..

3주차 3강은 별들의 전쟁이라는 문제였다. 문제 내용은 다음과 같다. 스타크래프트 게임이 생각나는 문제였는데 목표로하는 인구수와 각 유닛이 인구수를 얼마나 차지하는지을 알 때, 최소유닛수로 목표 인구수를 충족시키는 문제였다. 처음 문제를 읽었을 때, 먼저 Greedy 알고리즘이 떠올라 Greedy 알고리즘을 이용해 해결을 해보려다가 Greedy 알고리즘을 사용해 문제를 풀었을 경우 생산 가능한 목표 인구수 더라도 최대값을 먼저 고르다가 생산 불가능한 목표 인구수가 될 것이 염려되어 포기하고 다른 방법이 없나 생각하다가 모르겠어서 해설을 참고해 코드를 작성하게 되었다. 작성한 코드는 다음과 같다. 이 방식은 동적계획법을 사용한 방법인데 d[i]가 인구수 i를 만들기 위해 필요한 최소 인구수라고 하고 각 유..