본문 바로가기

분류 전체보기381

[자료구조] 해시 테이블(Hash Table) 해시 테이블(Hash Table) 해시 테이블은 (Key, Value)식으로 데이터를 저장하는 자료구조 해시함수(Hash Function)를 사용하여 변환한 값을 index로 삼음 해시 함수(Hash Function)를 사용해 Key 값을 색인(index)으로 변환하는 과정을 해싱(Hashing)이라고 함 대표적인 예로 파이썬의 dictionary, 루비의 Hash, 자바의 Map 등이 있음 해시 테이블의 특징 기본 연산으로는 search, insert, delete가 있음 순차적으로 데이터를 저장하지 않음 key를 통해서 value를 얻을 수 있음 => 이진탐색트리나 배열에 비해 속도가 빠름 커다란 데이터를 해시해서 짧은 길이로 축약할 수 있기 때문에 데이터를 비교할 때 효율적 value는 중복 가능하.. 2023. 3. 15.

[Swift] 프로그래머스 LV.1 명예의 전당 (1) 프로그래머스 LV.1 모음 명예의 전당 (1) 문제 설명 "명예의 전당"이라는 TV 프로그램에서는 매일 1명의 가수가 노래를 부르고, 시청자들의 문자 투표수로 가수에게 점수를 부여합니다. 매일 출연한 가수의 점수가 지금까지 출연 가수들의 점수 중 상위 k번째 이내이면 해당 가수의 점수를 명예의 전당이라는 목록에 올려 기념합니다. 즉 프로그램 시작 이후 초기에 k일까지는 모든 출연 가수의 점수가 명예의 전당에 오르게 됩니다. k일 다음부터는 출연 가수의 점수가 기존의 명예의 전당 목록의 k번째 순위의 가수 점수보다 더 높으면, 출연 가수의 점수가 명예의 전당에 오르게 되고 기존의 k번째 순위의 점수는 명예의 전당에서 내려오게 됩니다. 이 프로그램에서는 매일 "명예의 전당"의 최하위 점수를 발표합니다. 예를.. 2023. 3. 15.

[Swift] 프로그래머스 LV.1 기사단원의 무기 프로그래머스 LV.1 모음 기사단원의 무기 문제 설명 숫자나라 기사단의 각 기사에게는 1번부터 number까지 번호가 지정되어 있습니다. 기사들은 무기점에서 무기를 구매하려고 합니다. 각 기사는 자신의 기사 번호의 약수 개수에 해당하는 공격력을 가진 무기를 구매하려 합니다. 단, 이웃나라와의 협약에 의해 공격력의 제한수치를 정하고, 제한수치보다 큰 공격력을 가진 무기를 구매해야 하는 기사는 협약기관에서 정한 공격력을 가지는 무기를 구매해야 합니다. 예를 들어, 15번으로 지정된 기사단원은 15의 약수가 1, 3, 5, 15로 4개 이므로, 공격력이 4인 무기를 구매합니다. 만약, 이웃나라와의 협약으로 정해진 공격력의 제한수치가 3이고 제한수치를 초과한 기사가 사용할 무기의 공격력이 2라면, 15번으로 지.. 2023. 3. 15.

[자료구조] 우선순위 큐(Priority Queue) 우선순위 큐(Priority) 순서에 상관없이 우선수위가 높은 데이터가 먼저 나가는 형태의 자료구조 우선순위 대기열이라고도 함 대기열에서 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료구조 일반적으로 힙(Heap)을 사용하여 구현 모든 항목에는 우선순위가 있음 우선순위가 높은 요소는 우선순위가 낮은 요소보다 먼저 큐에서 제외 두 요소의 우선순위가 같은 경우 큐의 순서에 따라 제공 우선순위 큐 구현 방법 배열, 연결리스트, 힙을 이용하여 구현 가능 구현 방법 삽입 (enqueue) 삭제 (denqueue) 배열 (unsorted array) O(1) O(N) 연결 리스트 (unsorted linked list) O(1) O(N) 정렬된 배열 (sorted array) O(N) O(1) .. 2023. 3. 13.

[자료구조] 힙(Heap) 힙(Heap) 완전 이진트리 기반의 자료구조 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조 우선순위 큐를 위해 만들어진 자료구조 반정렬상태(느슨한 정렬상태) 유지 큰 값이 상위에 있고 작은 값이 하위에 있는 정도 중복된 값 허용 힙의 종류 최대 힙(max heap) 부모 노드의 키 값이 자식노드의 키 값보다 크거나 같은 완전 이진트리 최소 힙(min heap) 부모 노드의 키 값이 자식 노드의 키 값 보다 작거나 같은 이진트리 힙의 활용 시뮬레이션 시스템 네트워크 트래픽 제어 운영 체제에서의 작업 스케쥴링 수치 해석적인 계산 힙의 구현 힙을 저장하는 표준적인 자료구조는 배열 구현을 쉽게 하기 위해 배열의 첫 번째 인덱스인 0은 사용되지 않음 특정 위치의 노드 번호는 새로운.. 2023. 3. 13.

[프로그래머스 LV.1] 과일 장수 프로그래머스 LV.1 모음 과일 장수 문제 설명 과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 1점부터 k점까지의 점수로 분류하며, k점이 최상품의 사과이고 1점이 최하품의 사과입니다. 사과 한 상자의 가격은 다음과 같이 결정됩니다. 한 상자에 사과를 m 개씩 담아 포장합니다. 상자에 담긴 사과 중 가장 낮은 점수가 p (1 ≤ p ≤ k)점인 경우, 사과 한 상자의 가격은 p * m입니다. 과일 장수가 가능한 많은 사과를 팔았을 때, 얻을 수 있는 최대 이익을 계산하고자 합니다.(사과는 상자 단위로만 판매하며, 남는 사과는 버립니다) 예를 들어, k = 3, m = 4, 사과 7개의 점수가 [1, 2, 3, 1, 2, 3, 1]이라면, 다음과 같이 [2, 3, 2, 3]으로 구성된 사.. 2023. 3. 13.

이전 1 ··· 22 23 24 25 26 27 28 ··· 64 다음

티스토리툴바