정렬

[ Javascript ] 계수정렬

개념 계수정렬은 굉장히 특이한 녀석이다. 똑같은 수가 많이 존재하는 배열을 정렬하는데 가장 좋다. 로직은 무식하게 각 숫자의 갯수를 세는 것 괜히 영어로 CountingSort가 아니다. 구현 const countingSort = (inputArray) => { const maxNumber = Math.max(...inputArray); const result = []; const countArray = Array.from({ length: maxNumber + 1 }).map(() => 0); inputArray.forEach((num) => { countArray[num]++; }); countArray.forEach((numberCount, index) => { for (let x = 0; x < ..

[ Javascript ] 병합정렬

개념 병합정렬은 배열의 중간 인덱스를 찾고, 그 값을 기준으로 반을 나눈다. 이걸 배열 길이가 1일때까지 반복한 뒤에, merge라는 함수를 통해 나눴던 두 배열을 동시에 인덱스를 진행시키며 새로운 배열에 결과를 저장한다. 이걸 다시 원본 배열에다가 복사해 넣어주면된다. 이게 재귀적, 병렬적으로 일어나기 때문에 아주 빠르고 안정적으로 작동한다. 구현 mergeSort 이 함수가 배열의 중간 인덱스를 찾아서 반으로 나눈 뒤 배열의 길이가 1일때까지 재귀적으로mergeSort를 부른다. 이후, 나눈 인덱스 기준 왼쪽배열과 오른쪽배열의 처리가 끝났다면, 두 배열을 다시 merge해준다. const mergeSort = (inputArray, left, right) => { if (left < right) { ..

[ Javascript ] 버블정렬

개념 버블 정렬은 처음부터 끝-1의 인덱스에 대해서 해당 인덱스의 오른쪽 값과 비교하여 값을 변경해주는, 간단한 정렬 알고리즘이다. 실제 값끼리 수를 비교하여 진행하므로 비교기반의 알고리즘이고, 추가적인 메모리가 필요하지 않다. 구현 const bubbleSort = (inputArray) => { for (let x = 0; x inputArray[currentIndex + 1]) { let temp = inputArray[currentIndex +..

1931 백준 파이썬

옛날에 풀었던 문제 두 번 정렬해서 해결했다. n=int(input()) li=[] for _ in range(n): a,b=map(int, input().split()) li.append([a,b]) cnt=1 li.sort(key=lambda x:x[0]) li.sort(key=lambda x:x[1]) time=li[0][1] for i in range(1,n): if li[i][0]>=time: cnt+=1 time=li[i][1] print(cnt)

1946 백준 파이썬

생각보다 어려웠던 문제 두개를 정렬해서 하려고 했다. 하나의 첫번째 인덱스에 해당하는 값을 다른 리스트에서 찾고, 그 위치 이후에 있는 값을 outarr에 저장해서 n-len(outarr)를 하려고 했다. import sys input=sys.stdin.readline t=int(input()) for _ in range(t): n=int(input()) l=[] for _ in range(n): l.append(list(map(int,input().split()))) l.sort(key=lambda x:x[0]) seoryu=l[:] stop=l[0] l.sort(key=lambda x:x[1]) myeongeop=l[:] mtop=l[0] outarr=[] for x in range(n): if my..

11497 백준 파이썬

숫자라기보다 정말 높이라고 생각하고, 그림을 그려보아서 빠르게 접근할 수 있었던 문제. 정렬되었을 때, 높이차가 가장 안나게 하려면 현재 통나무 인덱스의 다음다음번째 인덱스를 옆으로 가져와야 한다. 다만 갑자기 max쓸지, min쓸지 하다가 좀 헤맸다. t=int(input()) for _ in range(t): m=0 n=int(input()) l=list(map(int,input().split())) l.sort(reverse=True) for x in range(n-2): m=max(m,abs(l[x]-l[x+2])) print(m)

정렬 알고리즘(파이썬, 자바스크립트) - 선택, 삽입, 버블정렬

실버 2 찍었다. 근데 풀다보니까 더 이상 무지성 때려박기로는 안된다는 생각이 들어서 알고리즘을 공부하기로 했다. 1. 선택정렬 현재 위치에 들어갈 값을 찾아 정렬하는 배열이다. 인덱스 값을 증가 시키며 인덱스 이후의 최소값과 값을 바꿔주는 방식이며, 반복문을 두번 사용하기 때문에 시간복잡도는 N(O^2)이다. 파이썬 코드(오름차순) arr=[2,5,3,1,8,7,6,9,4] for j in range(0,len(arr)): low=arr[j] for i in range(j,len(arr)): if low>=arr[i]: low=arr[i] index=i arr[index],arr[j]=arr[j],low print(arr) 자바스크립트 코드(오름차순) 2. 삽입 정렬 현재위치에서 이하의 배열을 비교, ..