본문 바로가기
728x90

코딩테스트/이진 탐색4

[python] 백준 14567번: 선수과목 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 import sys def binary_search(array,target,start,end): while start 2023. 1. 6.
<PART 2> 이진탐색-예제 부품찾기 전자 매장에는 부품이 N개 있습니다. 그리고 부품마다 고유 부품 번호가 존재합니다. 여기서 손님이 M개의 부품과 고유 부품 번호를 물어봐서 각각이 있는지 확인해야 합니다. 있으면 yes, 없으면 no를 출력하는 프로그램을 작성해봅니다. (1 start,end(14,14)->(15,14) 원하는 total=7일때 start,end가 15라면-> (total start,end(15,15)->(15,14) 가 되서 결국 같은 값으로 되기 때문에 /2만 하면 덜 잘려지는 14가 된다. - 재귀함수가 아닌 for문을 이용한 풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 n,m= list(map(int,input().spl.. 2022. 11. 6.
<PART 2> 트리 자료구조 데이터 베이스는 내부적으로 대용량 데이터 처리에 적합한 트리자료구조를 이용하여 항상 데이터가 정렬되어 있습니다. 따라서 데이터 베이스에서의 탐색은 이진 탐색과는 조금 다르지만, 이진 탐색과 유사한 방법을 이용해 탐색을 항상 빠르게 수행하도록 설계되어 있어서 데이터가 많아도 탐색하는 속도가 빠릅니다. 트리 자료구조는 노드와 노드의 연결로 표현합니다. 1. 트리는 부모 노드와 자식 노드의 관계로 표현합니다. 2. 트리의 최산당 노드를 루트 노드라고 합니다. 3. 트리의 최하단 노드를 단말노드라고 합니다. 4. 트리에서 일부를 떼어내도 트리 구조이며 이를 서브 트리라 합니다. 5. 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합합니다. 정리하자면 큰 데이터를 처리하는 소프트웨어는 대부분 데.. 2022. 11. 6.
<PART 2> 이진 탐색: 범위를 반씩 좁혀가는 탐색 이진 탐색: 리스트 내에서 데이터를 매우 빠르게 탐색하는 이진 탐색 알고리즘 이진탐색을 공부하기 전에 순차 탐색을 먼저 이해할 필요가 있습니다. 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용합니다. 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소를 찾을 수 있다는 장점이 있습니다. 그러므로 시간 복잡도는 O(N)입니다. count() 메서드도 내부에서는 순차 탐색이 수행됩니다. 위와 같이 처음부터 찾는 것을 순차탐색이라 합니다. - 이진 탐색 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘입니다. 위치를 나타내는 변수 3개를 사용하는데.. 2022. 11. 5.
728x90

티스토리툴바