Slowly, Step by Step

파이썬 힙 자료구조 내부적으로 정렬된 힙으로, get할 때 작은 값부터 꺼내진다. heapq 모듈 사용한다. import heapq 사용하기 heapq.heappush(heap, item) : item을 heap에 추가 heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨. heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N) ) import heapq heap = [] heapq.heappush(heap, 50) heapq.heappush(heap, 10) heapq.heappush(heap, 20) print(heap) result = heapq.heappop(..

문제 문제 설명 스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다. 예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다. 종류이름 얼굴 동그란 안경, 검정 선글라스 상의 파란색 티셔츠 하의 청바지 겉옷 긴 코트 스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다. 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다. 같은 이름을 가진 의상은 존재하지 않습니다. clo..

문제 문제 설명 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조대 : 119 박준영 : 97 674 223 지영석 : 11 9552 4421 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요. 제한 사항 phone_book의 길이는 1 이상 1,000,000 이하입니다. 각 전화번호의 길이는 1 이상 20 이하입니다. 같은 전화번호가 중복해서 들어있지 않습니다. 입출력 예제..

문제 문제 풀이 (1) 해시 사용 #include #include #include #include using namespace std; //마라톤선수들이 마라톤에 참여했다. //단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주한다. string solution(vector participant, vector completion) { string answer = ""; //참여자에 없는 원소를 반환해야 한다. unordered_map participants; for(string name : participant){ ++participants[name]; } for(string name : completion){ --participants[name]; } for(auto pair : participa..

1. 해시 테이블이란 해시테이블은 key, value로 데이터를 저장하는 자료구조이다. [해시함수] ex) 1~10의 값을 저장할 때, %연산을 이용하여 배열크기를 줄여 사용 %연산이 같은 두개이상의 원소를 같은 배열원소에 넣는 경우. 이 때 충돌이 발생할 수 있다. 2. #include 해시 테이블로 구현한 자료구조로 map보다 더 빠른 탐색이 가능하다. 중복된 데이터를 허용하지 않고, map에 비해 데이터가 많을 시 더 좋은 성능을 보인다. empty() 맵이 비어있는지 확인하는 함수 비어있으면 1을 반환한다. size() operator [] um [ "key" ] = 2; map_name[key] = value find(key) key에 해당하는 원소를 찾는 함수 count(key) key에 해당..

문제 문제풀이 #include #include #include #include using namespace std; struct cmp { bool operator()(vector a, vector b) { return a.at(1) > b.at(1); } }; int solution(vector jobs) { int answer = 0; priority_queue pq; //우선순위 큐 min heap int size = jobs.size(); int time=0; //이차원배열 정렬하기 sort(jobs.begin(), jobs.end()); int idx = 0;int j=0; while(idx < size || !pq.empty()){ //현재 시간보다 이하에 들어온 작업들을 모두 넣는다. if(..

문제 입출력 문제풀이 #include #include #include #include #include using namespace std; int solution(int n, vector edge) { int answer = 0; //n개의 노드가 있는 그래프가 있습니다. //1번 노드에서 가장 멀리 떨어진 노드의 개수 구하기 //최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들 //이차원 배열이 주어지고 1번 노드에서 출발. 노드의 개수 주어짐. //[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] //1번에서 2번으로 가는 최단 경로는? //coninfo : 각 연결되어 있는 시작 노드와 끝 노드들을 넣어 연결 정보 저장 // vector co..

문제 입출력 문제풀이 #include #include #include using namespace std; int solution(vector scoville, int K) { int answer = 0; int i = 0; while(1){ sort(scoville.begin(), scoville.end());//정렬 if(scoville[i] >= K){ break; } else { answer++; int new_input = scoville[i] + (scoville[i+1] * 2); scoville.erase(scoville.begin(),scoville.begin()+2);// //scoville.erase(scoville.begin()+1); scoville.push_back(new_inp..

문제 #include #include #include #include using namespace std; int main(void) { int n = 0; string input; cin >> n; for (int i = 0; i > input; stack s; int size = input.size(); for(int k =0;k

1. 비선형 문제 계층적 문제 순환 종속성 2. 트리 : 상하 반전된 형태 트리 순회 : 루트 노드를 기준으로 지어진 용어 A B C 1. preorder A B C 2. inorder B A C 3. postorder B C A 3. 다양한 트리 구조 이진 검색 트리 ( Binary search tree) (1) 원소 검색 (2) 새 원소 삽입하기 (3) 원소 삭제하기 (4) 시간복잡도 검색의 경우 매번 검색 범위가 절반으로 줄어든다. T(N) = T(N/2) + 1 => T(N) = O(log N) 균형 트리 N 항 트리 4. 힙 완전 이진 트리 : 마지막 레벨의 노드를 제외하고는 모두 두 개의 자식 노드가 존재 최대 힙 (max heap) : 부모 노드가 두 자식노드보다 항상 커야 한다는 불변성 유..