목록알고리즘+자료구조 (10)
DevKim
[ 개념 ] - 맨 앞부터 스캔하여 순서대로 검색하는 선형탐색과 달리, 이진탐색은 우선, data가 sorting 되어있다는 가정 하에 탐색을 진행한다. 원리는 간단하다. 중앙 값을 선정하여 탐색의 범위를 좁혀나가는 것. 탐색하고자하는 key값이 중앙값 보다 크면 left의 값을 중앙값+1로, key값이 중앙값보다 작으면 right를 중앙값-1로.. 이렇게 점차 탐색 범위를 줄여주는 것이다. [ 적용 기준 ] - 보통 어떤 x에 관해 함수 f(x)가 증가하거나 감소하는 함수일때 start,end를 x에 관한 최소값과 최대값으로 설정하여 이진 탐색으로 문제 해결 [ 코드 ] #검색 대상은 반드시 오름 차순 정렬 되어있어야함! #정렬 되어있다고 가정했을 때의 예제 from typing import Any,S..
python으로 Linked List 구현을 해보았다. c언어로 구현하다가 파이썬으로 구현하려니 헷갈리고 어색하다 1. Link에 대한 구현 class Node: def __init__(self,data): self.data=data self.next=None head=Node(3) next_node=Node(5) head.next=next_node 2. 단순 연결리스트 - 단순 연결리스트의 경우 head가 필요하므로 생성, 길이를 계산하는 것보단 길이를 가지고 있는게 좋을 것 같아서 길이를 추가하였다 * 성능 : O(n) < O(1) 이기 때문 class Node: def __init__(self,data): self.data=data self.next=None #입력받은 객체의 문자열 버전을 반환 d..