반응형 자료구조13 (Python/PCCP1회 모의고사 1번) 외톨이 알파벳 문제 설명 알파벳 소문자로만 이루어진 어떤 문자열에서, 2회 이상 나타난 알파벳이 2개 이상의 부분으로 나뉘어 있으면 외톨이 알파벳이라고 정의합니다. 문자열 "edeaaabbccd"를 예시로 들어보면, a는 2회 이상 나타나지만, 하나의 덩어리로 뭉쳐있으므로 외톨이 알파벳이 아닙니다. "ede(aaa)bbccd" b, c도 a와 같은 이유로 외톨이 알파벳이 아닙니다. d는 2회 나타나면서, 2개의 부분으로 나뉘어 있으므로 외톨이 알파벳입니다. "e(d)eaaabbcc(d)" e도 d와 같은 이유로 외톨이 알파벳입니다. 문자열 "eeddee"를 예시로 들어보면, e는 4회 나타나면서, 2개의 부분으로 나뉘어 있으므로 외톨이 알파벳입니다. "(ee)dd(ee)" d는 2회 나타나지만, 하나의 덩어리로 뭉쳐있.. 2023. 5. 26. 크루스칼 알고리즘 프로그래머스 LV3 레벨을 풀던중 https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제를 푸는데 당연히 난 다익스트라를 사용하여 푸려고 했다. def solution(n, costs): costs = sorted(costs, key=lambda x:(x[2])) print(len(costs)) dist =[1] + [0] * (n-1) graph = [ [] for _ in range(n)] for ( x, y, z ) in costs: g.. 2023. 5. 23. (Pyhton/Heap) 힙 (Heap) Heap :이진 트리의 한 종류 루투 노드가 언제나 최댓값, 최솟값 완전 이진 트리여야함 (레벨 k-2 까지는 모든 노드가 2개의 자식을 가진 포화 이진트로 , k-1 에서는 노드가 순차적) maxheap, minheap 이진탐색트리와의 비교 1, 완전한 크기순인가 >> 아니다 2. 빠르게 검색할 수 있는가 >> 아니다 >> 3. 부가 제약조건? >> 완전이진트리 여야함 최대힙 (Max Heap) __init__() : 빈 최대힙 생성 insert(item) - 새로운 원소 삽입 remove() 최대 원소를 반환 (root node) >> 동시에 삭제 표현 (배열 이용) 왼쪾 자식의 번호 : 2*m , 오른쪽은 2*m +1 부모 m // 2 노드 마지막 노드에서만 삭제/추가 가능 insert 구현 cla.. 2022. 12. 16. (Python/이진트리) 이진트리(3) 이진 탐색트리: 모든 노드에 대해서 왼쪽 트리에 있는 데이터는 모두 현재 노드의 값보다 작고 오른쪽 노드는 반대 인 이진트리 힙큐랑은 다르다 힙큐는 맨 위 노드가 최솟값 노드 배열 이용/ 이진트리 이용 이진트리 : 장점 : 데이터 원소의 추가, 삭제가 용이 단점: 공간 소요가 큼 거의 O(logn) 임 노드는 키와 밸류를 가지고있음. insert (key, data) - 추가 remove(key) - 삭제 lookup(key) - 찾기 inorder() - 키 순서대로 데이터 나열 min(),max() -최소 최대 원소 삽입 구현 (insert) class Node: def __init__(self, key, data): self.key = key self.data = data self.left = No.. 2022. 12. 6. (Python/이진트리)이진트리(2) 2) 넓이 우선 순회 원칙 - 수준이 낮은 노드를 우선으로 방문 - 같은 수준의 노드들 사이에는 부모 노드 방문순서에 따라 방문 왼쪽이 오른쪽보다 우선 dfs 와 유사 재귀적 비효율 한 노드를 방문할때 나중에 방문할 노드들은 순서대로 기록해둬야함 >> 큐(queue) 사용 스택에 a ,b, c 순서로 들어가고 내려갈 자식노드가 없으면 큐에스 팝해주고 하는식 구현 문제 import queue class ArrayQueue: def __init__(self): self.data = [] def size(self): return len(self.data) def isEmpty(self): return self.size() == 0 def enqueue(self, item): self.data.append(it.. 2022. 12. 1. (Python/이진트리)이진트리(1) size() - 노드의 수 depth() 트리의 깊이 traversal : 순회 Node 는 Data ,leftchild, rightchild 를 가진다. 순회 종류: 1.깊이 우선순회 중위 순회 : 가운데 자기자신 left > 자신 > right 전위 순회 : 자기자신 먼저 후위 순회 : 자기자신이 맨 마지막 D에 입장에서 생각했을때 자기자신 D를 맨 마지막에 방문하고 그 다음 B에 left , right, 자신 순서니깐 D 다음에 B가 아닌 E 부터 방문한다. 1-1 depth 구현 class Node: def __init__(self, item): self.data = item self.left = None self.right = None def size(self): l = self.left.siz.. 2022. 12. 1. 이전 1 2 3 다음 반응형
