본문 바로가기

Binarysearch

[프로그래머스] 입국심사 c++ 2020. 8. 22. [프로그래머스] 입국심사 c++ 문제링크: 입국심사 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 � programmers.co.kr 문제 설명 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그 곳으로 가서 심사를 받을 수도 있습니다. 모든 사람이 ..
[프로그래머스] 가사 검색 C++ 2020. 7. 27. [프로그래머스] 가사 검색 C++ 문제 링크 : 가사 검색 코딩테스트 연습 - 가사 검색 programmers.co.kr 친구들로부터 천재 프로그래머로 불리는 프로도는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다. 그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다. 가사에 사용된 모든 단어들이 담긴 배열 wor..
[알고리즘 개념 정리] 이진 탐색 Binary Search c++ 2020. 7. 27. [알고리즘 개념 정리] 이진 탐색 Binary Search c++ 탐색 알고리즘 중 하나 오름차순으로 정렬된 리스트에서 특정한 위치를 찾는 알고리즘 오름차순으로 정렬된 리스트의 중간 값을 임의의 값으로 선택하여, 찾고자 하는 Key 값과 비교하는 방식으로 돌아가는 알고리즘 정렬된 리스트에서만 사용할 수 있음 ⇒ 단점 검색할 떄마다 선형탐색과는 비교할 수 없는 속도 == logN(밑2) 구현 방법1_직접 구현 bool binarySearch(int *arr, int len, int key) { int start = 0; int end = len - 1; int mid; while(end - start >= 0) { mid = (start + end) / 2; // 중앙 값 if(arr[mid] == key..

티스토리툴바