Algorithms 검색 결과

해당 글 123건

[프로그래머스](Hash) 위장 (C++)

위장 (Level 2) 문제 전체 문제 보기 코딩테스트 연습 - 위장 programmers.co.kr 접근법 이 문제에서는 스파이가 가진 옷으로 서로 다른 옷의 조합의 경우의 수를 조합해 내는 것이 최종 요구사항 이다. 먼저 이 경우의 수를 어떻게 계산할 것인지 고민해 봐야한다. 입출력 예제의 첫번째 케이스를 예를 들어서 살펴보자. 우선 각 옷 종류에 따라서 스파이가 선택할 수 있는 경우의 수가 몇가지가 있는지 살펴보자. headgear: yellowhat을 입는 경우, green_turban을 입는 경우 총 2 개가 있다. eyewear: bluesunglasses을 입는 경우 1 개 가 있다. 이렇게 생각 할 수 있지만, 잘 생각해보면 해당 옷 종류를 입지 않는 경우도 존재 할 수 있다. 예를 들어서..
Algorithms/Hash 2021. 4. 15. 22:21

[프로그래머스] (Hash) 전화번호 목록 ( C++)

전화번호 목록(Level 2) 문제 전체 문제 보기 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 접근법 이 문제를 정렬을 통해서도 풀 수 있지만 Hash 카테고리에 있는 문제이니 만큼 출제 의도에 맞춰서 Hash를 써서 풀어 보았다. C++의 std::unordered_map은 해시 테이블의 자료구조로 삽입과 탐색에 \(O(1)\)의 성능을 보여준다. 이 해시 테이블을 활용하면 최대 전화번호 수를 \(n\), 전화번호 길이를 \(l\) 라고 한다면 \(O(l \cdot n)\) 시간 복잡도로 풀이가 가..
Algorithms/Hash 2021. 4. 15. 17:13

[프로그래머스] (Hash) 완주하지 못한 선수 ( C++)

완주하지 못한 선수 (Level 1) 문제 [전체 문제 보기] 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 접근법 이 문제는 정렬이나 다른 방법으로 풀 수도 있지만 Hash 카테고리에 있는 문제이니 만큼 출제 의도에 맞춰서 Hash를 써서 풀었다. C++의 std::unordered_map을 활용하면 \(log(n)\) 시간 복잡도로 풀이 가능하다. 이름을 key, 정수를 value로 하는 해시테이블을 만든후, 참가자이름에 따라 value++하고, 완주자 이름에 해당하는 value--를..
Algorithms/Hash 2021. 4. 15. 16:40