코딩테스트 관련 내용정리 (2)

▼▼▼ 이전글 보러가기 ▼▼▼

2021/02/20 - [코딩테스트] - 코딩테스트 관련 내용 정리 (1)

코딩테스트 관련 내용 정리 (1)

 

파이썬 튜플의 특징

- 파이썬에서 튜플을 원소로하는 리스트가 있을 때, 리스트를 정렬하면 기본적으로 각 튜플을 구성하는 원소의 순서에 맞게 정렬된다는 특징이 있다.

 

파이썬 count 함수

- 해당 리스트에서 값이 몇개 있는지 반환하는 함수

 

 

이진탐색(Binary Search) ; 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘

---

- 이진탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘

- 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있음

- 찾으려는 데이터와 중간점에 위치해 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것

- 탐색 범위가 2,000만을 넘어가는 경우, 처리해야 할 데이터의 개수나 값이 1,000만 단위 이상으로 넘어가는 경우 

- 시간복잡도 O(logN)

 

▶ 재귀함수 사용

# 재귀함수로 구현한 이진 탐색 소스코드
def binary_search(array, target, start, end):
	if start>end: 
    	return None # 존재하지 않음
    
    mid = (start+end)//2 # 몫 연산자 int((start+end)/2) 
    # target이 존재하면 인덱스 리턴
    if array[mid]==target:
    	return mid
    # 타켓이 중간값보다 작은 경우 왼쪽 확인  
    elif array[mid] > target: 
    	return binary_search(array, target, start, mid-1) # 끝점을 중간점 전으로 이동
    else:
    	return binary_search(array, target, mid+1, end) # 시작점을 중간점 다음으로 이동
  

  # 함수 호출
  result=binary_search(array, target, 0, n-1)
  if result==None:
  	print("존재하지 않음")
  else:
  	print(result+1)
  
     

▶ 반복문 사용

# 반복문을 사용한 이진 탐색 코드
def binary_search(array, target, start, end):
	while start<=end:
    	mid=(start+end)//2
        
        if array[mid]==target:
        	return mid # 찾음
        elif array[mid] > target:
        	end = mid-1
        else:
        	start = mid+1
    
    return None # 없음
    
 result=binary_search(array, target,0,n-1)
 if result==None:
 	print("존재하지 않음")
 else:
 	print(result+1)

 

빠르게 입력받기

- 데이터의 개수가 1000만개 이상 / 탐색 범위가 1000억 이상인 경우 

- sys 라이브러리의 readline() 함수를 이용할 것

import sys
input_data = sys.stdin.readline().rstrip() # rstrip() 필수!!!!

 

문자열 뒤집기

name = 'james'
print(name[::-1])

 

 

 

참고문헌 및 출처 | 나동빈. 2020. 이것이 취준을 위한 코딩 테스트다 with 파이썬. 한빛미디어