목록2020/04/05 (2)
훈훈훈
이번에는 알고리즘 유형 중 이분 검색에 대해 정리하려고 한다. 문제 유형으로는 숫자로 이루어진 문자열을 Input으로 받은 후 오름차순으로 정렬하여 특정 숫자의 인덱스 값을 반환하는 문제이다. # 풀이 과정 먼저 입력받은 문자열을 sort 메서드로 오름차순으로 정렬한다. 그 다음 아래 그림과 같이 첫 인덱스를 Left 그리고 마지막 인덱스에 Right를 설정한다. 그리고 Left와 Right의 평균 값을 Middle로 설정한다. 그 후 Middle 값이 찾고자 하는 숫자와 같은지 비교 후 같으면 Middle 값의 인덱스를 리턴하고, 그게 아니라면 Middle과 크기 비교 후 Middle이 크면 Left = Middle + 1 로 설정하고 그게 아니라면 Right = Middle -1 로 설정한다. 그리고..
이번에는 탐색 유형 중 하나인 회문 문자 검사(대소문자를 구분하지 않음) 유형에 대해 정리해보려고 한다. 회문 문자는 문자를 뒤로 뒤집어서 읽어도 같은 문자열이며, 문자열 중앙을 기준으로 대칭인 특징이 있다. 따라서 해당 유형의 알고리즘을 풀떄도 이러한 특징을 이용해서 풀어보려고 한다. # 풀이 과정 먼저 대소문자를 구분하지 않기 때문에 리스트에 있는 모든 요소들을 대문자 혹은 소문자로 변환하는 작업이 필요하다. 필자는 " .lower() " 메서드를 사용하여 모두 소문자로 변환하였다. 그 다음 아래와 같이 대칭되는 요소들을 비교하였다. Input으로 주어지는 문자열의 길이를 2로 나눈 후 그 횟수 만큼 아래와 같이 비교하면 된다. 문자열이 홀수로 주어지더라도 가운데 값은 비교하는데 의미가 없기 때문에 ..