목록자료구조 + 알고리즘/[Programmers] (7)

알고리즘 문제풀이

[Programmers] 프로그래머스 - 디펜스 게임

링크 디펜스 게임 문제의 조건을 확인해보면 문제가 원하는 답이 무엇인지는 추측할 수 있으나 접근하는 방법을 떠올리기 쉽지 않다. 문제에서 주어진 조건을 정리해보면 아래와 같다 준호는 초기 $n$ 명의 병사를 가진다. 매 라운드마다 enemy[i] 마리의 적이 등장한다 무적권은 $k$ 번 사용할 수 있다 행위 현재 남은 병사보다 적이 더 많을 경우 게임은 종료 현재 남은 병사보다 적이 더 적을 경우 게임을 진행 무적권을 사용할 경우 병사의 수가 줄지 않는다 무적권을 사용하지 않을 경우 병사의 수가 줄어든다. Target := 무적권을 최대 $k$ 번 사용하여 준호가 진행할 수 있는 최대 라운드는? 이제 Constraint도 고려해보자. 1 $\leq$ n $\leq$ $10^9$ 1 $\leq$ k $\l..
자료구조 + 알고리즘/[Programmers] 2022. 12. 10. 03:42
[프로그래머스 코딩테스트 고득점 Kit] - 이분 탐색

[프로그래머스 코딩테스트 고득점 Kit] - 이분탐색 입국 심사 - level 3 문제 제한사항 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다. 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다. 심사관은 1명 이상 100,000명 이하입니다. 문제의 조건대로 시뮬레이션을 통해 최적해를 찾는 방법은 시간 제한 내에 문제를 해결할 수 없다는 것을 입출력의 제한사항으로 파악할 수 있다. 입국심사를 기다리는 사람의 최대 수가 $10^9$이라는 것을 고려한다면, $O(N)$으로도 해결하기 힘들다. 다른 관점에서 문제를 생각해보아야한다. 결정론적인 방법으로 생각해보자, 함수 $F(k)$ 를 다음과 같이 정의해보자. $F(k)$ : $k$시간..
자료구조 + 알고리즘/[Programmers] 2022. 1. 13. 16:52
[프로그래머스 코딩테스트 고득점 Kit] - 완전 탐색

프로그래머스 코딩테스트 고득점 Kit - 완전 탐색 모의고사 - level1 문제 1번, 2번, 3번 수포자가 찍는 방식에서 일정 주기를 가지고 반복되는데, 이 주기를 찾아서 배열에 저장한다. 이 후, answers를 순회하며 정답과 1대 1비교를 통하여 각각의 수포자가 맞힌 문제의 개수를 계산하여 비교한다. #include #include using namespace std; vector solution(vector answers) { vector answer; vector v(3); v[0].assign({1,2,3,4,5}); v[1].assign({2,1,2,3,2,4,2,5}); v[2].assign({3,3,1,1,2,2,4,4,5,5}); int scores[3] = {0, }; for(in..
자료구조 + 알고리즘/[Programmers] 2022. 1. 9. 02:14
[프로그래머스 코딩테스트 고득점 Kit] - 힙(heap)

프로그래머스 코딩테스트 고득점 Kit - 힙(Heap) 더 맵게 - Level2 문제 문제에서 주어진 Operation을 한번 수행할 때 마다, 전체 음식의 수는 1개씩 줄어든다. 즉, 최대 $N$번 Operation을 수행한다. scoville의 길이가 최대 $1,000,000$인 것을 고려한다면 , 매 Operation마다 $O(N)$ 의 탐색으로 최소 값을 찾는 것은 시간 초과인 것이 자명해보인다. 즉 $O(logN)$ 이하로 최솟 값을 찾아야 하는데, 이 때 쓰일 수 있는 자료구조가 Min-heap이다. Min-Heap의 특성 상 각각의 서브트리에 존재하는 루트노드가 항상 자식 노드보다 큰 것이 보장되고 최상위 루트 노드의 값이 전체 노드의 최솟값이므로 $O(1)$에 최소값을 찾을 수 있다. 이 ..
자료구조 + 알고리즘/[Programmers] 2022. 1. 6. 00:20
[프로그래머스 코딩 테스트 고득점 Kit] - 해시

프로그래머스 고득점 Kit - 해시 Hash Table 방식의 충돌 issue + string hashing에 필요한 cost를 고려하여 Red-Black Tree 기반의 Map을 사용하였습니다. 접근 시간 : $O(logN)$ 삽입 시간: $O(logN)$ 완주하지 못한 선수 문제 participant 배열을 순회하며, 해당 string에 대응되는 노드의 값을 1씩 증가 completion 배열을 순회하며, 해당 string에 대응되는 노드의 값을 1씩 감소 Map에 존재하는 노드 중, 값이 1이상인 것은 마라톤 경기를 완주하지 못한 사람. #include #include #include using namespace std; string solution(vector participant, vector ..
자료구조 + 알고리즘/[Programmers] 2022. 1. 4. 19:18
[프로그래머스 코딩 테스트 고득점 Kit] - 정렬

프로그래머스 코딩테스트 고득점 Kit - 정렬 K번째 큰 수 - level1 문제 주어진 commands에 포함되어 있는 parsing정보를 이용하여 array를 파싱한 데이터를 정렬하여 값을 구하면 되는 간단한 문제 $K: commands의 길이$, $N : Array의 길이$ 라 할 때 총 시간 복잡도는 $O(KNlogN)$가 된다. #include #include #include using namespace std; vector solution(vector array, vector commands) { vector answer; for(const auto& cmd : commands){ int from = cmd[0], to = cmd[1], kth = cmd[2]; vector subArray; ..
자료구조 + 알고리즘/[Programmers] 2022. 1. 4. 17:30
이전 Prev 1 2 Next 다음