알고리즘
-
[Python] programmers 메뉴 리뉴얼 - 구현 문제알고리즘/문제풀이 2021. 7. 3. 19:26
1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 2. 문제 요약 주문할 때 가장 많이 주문한 단품 메뉴로 구성 최소 2명 이상의 손님이 주문 3. 아이디어 정리 defaultdict에 조합 메뉴 횟수를 담아 가장 많이 주문된 요리를 찾는 풀이 하였다. 4. 문제 풀이 4-1. 내 풀이 from itertools import combinations from collections import def..
-
이진탐색(Binary Search) with Python알고리즘/문제풀이 2021. 1. 22. 21:29
이진 탐색을 알아보기 전에 가장 기본 탐색 방법인 순차 탐색을 알아보고 이진 탐색을 알아본다. 1. 순차 탐색 순차 탐색은 리스트 안에 있는 특정 데이터를 찾기 위해서 앞에서부터 차례대로 확인하는 방법이다. 앞에서부터 하나씩 확인해야 하기 때문에 시간 복잡도는 O(N)이 된다. 1-1. 구현하기 순차 탐색 소스를 구현하면 아래와 같다. 사람 이름 리스트 중 dongbin의 위치를 출력한다. def sequential_search(n, target, array): for i in range(n): if array[i] == target: return i + 1 array = ["hanul", "jonggu", "dongbin", "taeil", "sangwook"] print(sequential_searc..
-
해시 알고리즘알고리즘/문제풀이 2020. 9. 20. 23:00
이번 시간에는 해시 알고리즘에 대해서 알아본다. 해시 테이블과 해시 테이블에서 충돌이 발생하는 경우 해결방법 2가지를 알아본다. 1. Direct Addressing Table 크기가 U인 테이블 T를 생성하고 key k를 slot key에 저장하는 방식이다. 해당 테이블은 중복되는 키가 없다고 가정한다. 이는 삽입, 삭제, 검색 모두 O(1)이지만, 모든 키를 넣어야 하기 때문에 공간 낭비가 심하다. 예를 들어 모든 학생들에게 한 자리씩 할당해 준 것이다. 2. Hash Table key k를 저장할 때 slot k를 저장하는 것이 아니라 slot h(k)에 저장한다. key k가 slot h(k)로 해시되었다고 하며, h(k)를 key k의 해시값이라고 부른다. 이때 h( )는 해시 함수라고 부른다...
-
python 해시 테이블알고리즘/문제풀이 2020. 9. 20. 16:28
이번 시간에는 python 해시 관련하여 알아본다. python 해시 테이블 방식과 dict 자료형을 알아보고 자주 사용되는 모듈을 알아본다. 1. 파이썬 해시 테이블 파이썬에서 해시 테이블로 구현된 자료형은 딕셔너리다. 그렇다면 파이썬의 해시 테이블은 충돌 시 어떤 방식을 사용할까? 파이썬에는 오픈 어드레싱 방식으로 구현되어 있다. 파이썬에서 오픈 어드레싱 방식을 사용한 이유는 체이닝 시 malloc으로 메모리 할당하는 오버헤드가 높아서 오픈 어드레싱을 선택했다고 한다. 오픈 어드레싱 방식은 체이닝에 비해 성능이 좋다. 하지만 슬롯이 80% 이상 차게 되면 급격하게 성능 저하가 일어나며, 체이닝과 달리 로드 팩터 1 이상은 저장할 수 없다. 따라서 파이썬은 오픈 어드레싱 방식을 택해 성능을 높이지만 로..