힙(Heap) 대표 문제 풀이 : 더 맵게 힙(Heap) 최대/최소 원소를 O(1) 시간으로 빠르게 찾을 수 있음 종류 : 최대 힙(max heap), 최소 힙(min heap) 연산 : 힙 구성(heapify, O(n log n)), 삽입(insert, O(log n)), 삭제(remove, O(log n)) 힙의 구현과 응용 최대 힙을 기준으로 root node에 최댓값이 위치 완전 이진트리로 구성돼 있으며, 배열을 이용해서 구현 가능 응용 : 정렬(Heapsort), 우선순위 큐 (priority queue) Python에서의 힙 적용 연산 : heapify(list), heappop(list), heappush(list, value) import heapq # 리스트 L로부터 min heap 구성..
해시(Hash) 대표 문제 풀이 : 완주하지 못한 선수 해시(Hash) 만약 이름 대신 번호가 주어졌다면? => 선형 배열 이름을 키(key)로 하여 해시 함수(Hash function)를 통해 해시 테이블(hash table)에 매핑 풀이 (1) 사전(Dictionary)의 원소들을 해시를 이용해 O(1) 시간에 접근 가능 사전을 활용하여 "이름 : 이름 수"로 저장하여 마지막 남은 사람의 이름 반환 코드 get(x, 0) : x라는 키가 존재하면 해당 값을, 존재하지 않으면 0을 반환 최종 시간 복잡도 : O(n) def solution(participant, completion): d = {} # O(n) for x in participant: d[x] = d.get(x, 0) + 1 # O(n) ..
문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제 이해2차원 행렬 arr1과 arr2를 입력받아 행렬곱을 수행하여 반환곱할 수 있는 배열만 주어짐풀이arr1의 한 행과 arr2의 한 행을 행렬곱 연산하여 tmp에 append 및 하나의 행이 완성되면 arr3에 append행렬곱 풀이는 글로 설명해서는 이해가 잘 안될 것 같다... (행렬곱에 대해 잘 모른다면 아래 링크 참고)삼중 반복문을 활용 - (1) arr1의 행 수만큼 반복, (2) arr2의 열 수만큼 반복, (3) arr1의 열 수만큼 반복행렬곱이 된 수들을 저장할 배열 tmp, 행렬곱 연산 ..
문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 한 번호가 다른 번호의 접두어인 경우가 있는지 확인 전화번호를 담은 배열 phone_book 어떤 번호가 다른 번호의 접두어인 경우 False, 그렇지 않다면 True 반환 풀이 배열 phone_book을 모두 확인하여 접두어가 있으면 False, 접두어가 없다면 True 반환 배열 phone_book의 길이는 최대 1,000,000이므로 시간 초과에 유의 => 연산 횟수를 줄이기 위해 배열과 문자열의 길이를 변수를 통해 저장 및 조건문 추가 sort 메소드를 통해 phone_book을 정렬 ..
