알고리즘 검색 결과

해당 글 5건

[프로그래머스] 후보키 (C++)

후보키(Level 2) 문제 전체 문제 보기 코딩테스트 연습 - 후보키 [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2 programmers.co.kr 접근법 이번 문제는 하나 이상의 속성을 선택하여 만들 수 있는 후보키의 개수를 구하는 문제입니다. 하나 이상의 속성을 선택하기 위해서는 백트레킹을 활용하여 재귀적으로 접근할 수 있습니다. 재귀적으로 선택된 속성의 조합이 문제에서 주어진 "유일성"과 "최소성"을 만족하는지 검증하여 후보키로 확정 지..
Algorithms/Backtracking 2021. 11. 20. 18:09

[프로그래머스](Hash) 베스트앨범 (C++)

베스트앨범 (Level 3) 문제 전체 문제 보기 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 접근법 이 문제에는 서로 연관된 3가지(장르, 재생횟수, 노래의 고유번호)의 데이터가 나온다. 각 데이터간의 관계를 어떻게 정의할지 그리고 어떤 자료구조를 사용할지가 중요하다. 필자는 해시테이블을 이용해서 문제를 풀었다. 해시테이블을 이용하면 다음과 같은 장점이 있다. 해시 테이블을 사용하면 데이터 입력과 탐색을 \(O(1)\)회에 처리할 수 있기에 전체 시간 복잡도를 \(O(n)\)로 비교적 빠르게 처리할 수..
Algorithms/Hash 2021. 4. 16. 10:46

[프로그래머스](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