본문 바로가기

분류 전체보기

 (112)
[프로그래머스 Level1] 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세..
[프로그래머스 Level1] 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 순위당첨 내용 1 6개 번호가 모두 일치 2 5개 번호가 일치 3 4개 번호가 일치 4 3개 번호가 일치 5 2개 번호가 일치 6(낙첨) 그 외 로또를 구매한 민우는 당첨 번호 발표일을 학수고대하고 있었습니다. 하지만, 민우의 동생이 로또에 낙서를 하여, 일부 번호를 알아볼 수 없게 되었습니다. 당첨 번호 발표 후, 민우는 자신이 구매했던 로또로 당첨이 가능했던 최고 순위와 최저 순위를 알아보고 싶어 졌습니다. 알아볼 수 없는 번호를 0으로 표기하기로 하고, 민우가 구매한 로또 번호 6개가 44, 1, 0, 0, 31 25라고 가정해보겠습니다. 당첨 번호 ..
[알고리즘 강의] 파트23. 힙(Heaps) (2) 최대 힙에서 원소의 삭제 1. 루트 노드의 제거 - 이것이 원소들 중 최댓값 2. 트리 마지막 자리 노드를 임시로 루트 노드의 자리에 배치 3. 자식 노드들과의 값 비교와 아래로, 아래로 이동 - 자식은 둘 있을 수도 있는데, 어느 쪽으로 이동? 큰 값 최대 힙에서 원소의 삭제 - 복잡도 원소의 개수가 n인 최대 힙에서 최대 원소 삭제 -> 자식 노드들과의 대소 비교 최대 횟수: 2 * log2n 최악 복잡도 O(logn)의 삭제 연산 최대/최소 힙의 응용 1. 우선 순위 큐 (priority queue) - Enqueue 할 때 "느슨한 정렬" 을 이루고 있도록 함: O(logn) - Dequeue 할 때 최댓값을 순서대로 추출: O(logn) - 제 16강에서의 양방향 연결 리스트 이용 구현과 효율성..
[알고리즘 강의] 파트22. 힙(Heaps) (1) 힙 (Heap) 이란? 이진 트리의 한 종류 (이진 힙 - binary heap) 1. 루트 (root) 노드가 언제나 최댓값 또는 최솟값을 가짐 (모든 서브트리의 루트에서) - 최대 힙 (max heap), 최소 힙 (min heap) 2. 완전 이진 트리여야 함 재귀적으로도 정의됨 (어느 노드를 루트로 하는 서브트리도 모두 최대 힙) 이진 탐색 트리와의 비교 1. 원소들은 완전히 크기 순으로 정렬되어 있는가? 이진탐색: YES, 힙 NO 2. 특정 키 값을 가지는 원소를 빠르게 탐색할 수 있는가? 이진탐색: YES, 힙 NO 3. 부가의 제약 조건은 어떤 것인가? 힙 - 완전이진트리 최대 힙(Max Heap)의 추상적 자료구조 연산의 정의 - __init__() : 빈 최대 힙을 생성 - insert..
[알고리즘 강의] 파트21. 이진 탐색 트리(Binary Search Trees) (2) 이진 탐색 트리에서 원소 삭제 1. 키(key)를 이용해서 노드를 찾는다. - 해당 키의 노드가 없으면, 삭제할 것도 없음 - 찾은 노드의 부모 노드도 알고 있어야 함 (아래 2번 때문) 2. 찾은 노드를 제거하고도 이진 탐색 트리 성질을 만족하도록 트리의 구조를 정리한다. 인터페이스의 설계 입력: 키 (key) 출력: 삭제한 경우 True 해당 키의 노드가 없는 경우 False 이진 탐색 트리 구조의 유지 1. 삭제되는 노드가 leaf 노드인 경우 그냥 그 노드를 없애면 됨 -> 부모 노드의 링크를 조정 (좌? 우?) * 삭제되는 노드 (X)가 root node인 경우는 root에 None 을 넣음 -> 트리 자체가 없어짐 2. 삭제되는 노드가 자식을 하나 가지고 있는 경우 삭제되는 노드 자리에 그 자..
[알고리즘 강의] 파트20. 이진 탐색 트리(Binary Search Trees) (1) 이진 탐색 트리 모든 노드에 대해서, - 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고 - 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족하는 이진 트리 (중복되는 데이터 원소는 없는 것으로 가정) (정렬된) 배열을 이용한 이진 탐색과 비교 - 이진 탐색 트리의 장점: 데이터 원소의 추가, 삭제가 용이 - 이진 탐색 트리의 단점: 공간 소요가 큼 - 항상 O(logn) 의 탐색 복잡도? X 이진 탐색 트리의 추상적 자료구조 데이터 표현 - 각 노드는 (key, value) 의 쌍으로 장점: (1) 키를 이용해서 검색 가능 (2) 보다 복잡한 데이터 레코드로 확장 가능 연산의 정의 - insert(key, data): 트리에 주어진 데이터 원소를 추가 - remove..
[알고리즘 강의] 파트19. 이진 트리 - 넓이 우선 순회(breadth first traversal) 넓이 우선 순회 (breadth first traversal) 원칙 - 수준(level)이 낮은 노드를 우선으로 방문 - 같은 수준의 노드들 사이에는, ㄴ 부모 노드의 방문 순서에 따라 방문 ㄴ왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문 - 재귀적(recursive) 방법이 적합한가? X 한 노드를 방문했을 때, 나중에 방문할 노드들을 순서대로 기록해 두어야 함 -> 큐(queue)를 이용하자 넓이 우선 순회 알고리즘 설계 1. (초기화) traversal
[알고리즘 강의] 파트18. 이진 트리(Binary Trees) 이진 트리의 추상적 자료구조 연산의 정의 - size(): 현재 트리에 포함되어 있는 노드의 수를 구함 - depth(): 현재 트리의 깊이 (또는 높이; height) 를 구함 - 순회 (traversal) 이진 트리의 구현 - 노드 (Node) class Node: def __init__(self, item): self.data = item self.left = None self.right = None 이진 트리의 구현 - 트리 (Tree) class BinaryTree: def __init__(self, r): self.root = r 이진 트리의 구현 - size() - 재귀적인 방법으로 쉽게 구할 수 있음! class Node: def size(self): l = self.left.size() ..

티스토리툴바