[코딩테스트] 이진 탐색 알고리즘
순차 탐색 : 리스트 안에 있는 특정 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 : 정렬되어 있는 리스트에서, 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법으로 시작점/끝점/중간점을 이용해서 탐색 범위를 명시해주어야 한다. 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾는다면, 1. array = [0,2,4,6,8,10,12,14,16,18] 시작점:array[0]=0, 끝점:array[9]=18, 중간점:array[4]=8(소수점 이하 제거) 찾고자 하는 4가 중간점인 8보다 작다. 그러므로 중간점을 포함하여 오른쪽 부분은 필요가 없으므로 날려보자. 2. array = [0,2,4,6] 시작점:array[0]=0, 끝점:array[3]=6, 중간점:array..
2023. 1. 25.
[코딩테스트] 정렬 알고리즘(2) 퀵 정렬 계수 정렬
퀵 정렬 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다. 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘이며, 병합 정렬과 더불어 대부분 프로그래밍 언어 정렬 라이브러리의 근간이 된다. 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다. 1. array = [5,7,9,0,3,1,6,2,4,8] 이라고 할 때, 피벗의 값은 5로 선택한다. 2. 왼쪽에서부터 5보다 큰 데이터인 7이 선택되고, 오른쪽에서부터 5보다 작은 데이터인 4가 선택된다. 이 두 데이터의 위치를 서로 변경해준다. 3. array=[5,4,9,0,3,1,6,2,7,8]인 상태에서, 왼쪽에서부터 5보다 큰 데이터인 9가 선택되고, 오른쪽에서부터 5보다 작은 데이터인 2가 선택..
2023. 1. 24.
[코딩테스트] 구현, 시뮬레이션과 완전 탐색
코딩테스트에서 말하는 구현 문제라는 것은, 풀이(알고리즘)를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제다. -알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 -실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 -문자열을 특정 기준에 따라 끊어 처리하는 문제 -적절한 라이브러리를 찾아서 사용해야 하는 문제 ( 순열, 조합을 예로 들면 itertools를 사용해서 대응 가능하지만 이를 모르면 방대하게 구현해야 함) 2차원 공간, 행렬(Matrix)에서의 방향 벡터가 자주 활용된다. #동,북,서,남 : 방향성을 명시해주기 위해서 리스트나 배열 형태로 나타낸다. dx= [0,-1,0,1]#행 dy= [1,0,-1,0]#열 #현재 위치 x,y = 2,2 for i in range(4) ..
2022. 12. 24.
