[알고리즘] 정렬 - 백준 2750 1920 2108 1946 2470 1461 10026

 

정렬

데이터를 특정 기준에 따라 순서대로 나열하는 것

선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬이 있다.

 

 

선택 정렬

가장 기본적인 정렬 알고리즘으로 가장 작은 것을 왼쪽으로 계속 보내는 (오름차순의 경우) 정렬 방식

arr = [7, 3, 5, 9, 6, 2]

for i in range(len(arr)):
	min_idx = i
    for j in range(i+1, len(arr)):
    	if arr[min_idx] > array[j]:
        	min_idx = j
    arr[i], arr[min_idx] = arr[min_idx], arr[i]

시간 복잡도가 $ O(N^2) $ 이기 때문에 원소의 개수가 많으면 효율적이지 못한 알고리즘이다...

 

삽입 정렬

특정한 데이터를 적절한 위치에 삽입한다는 의미의 삽입 정렬이다.

특정 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다.

 

arr = [7, 3, 5, 9, 6, 2]

for i in range(1, len(arr)):
	for j in range(i, 0, -1):
    	if arr[j] < arr[j-1]:
        	arr[j], arr[j-1] = arr[j-1], arr[j]
        else:
        	break

시간 복잡도가 $ O(N^2) $ -> 데이터가 거의 정렬되어 있는 상태일 때 효과적

 

퀵 정렬

'피벗'이라는 것이 사용되는데, 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 과정에서,

기준을 피벗(pivot)이라 한다.

- 첫 번째 데이터를 피벗으로 정한 후 왼쪽 오른쪽 방향에서 피벗보다 큰 / 작은 데이터 위치 변경

- 위치가 엇갈릴 때 피벗과 작은 데이터 위치 변경

- 각 파티션의 왼쪽을 피벗으로 정렬 진행

대충 알겠는데 코드로 작성하면서 이해를 해보자.

arr = [5, 3, 9, 1, 4, 6, 2]

def quick_sort(arr, start, end):
	if start >= end:	# 원소가 1개인 경우 종료
		return
	pivot = start
	left = start + 1
	right = end
    
	while left <= right:
		while left <= end and arr[left] <= arr[pivot]:	# 피벗보다 큰 데이터를 찾을 때까지
			left += 1
		while right > start and arr[right] >= arr[pivot]:	# 피벗보다 작은 데이터를 찾을 때까지
			right -= 1
		if left > right:	# 엇갈리지 않으면
			arr[right], arr[pivot] = arr[pivot], arr[right]
		else:	# 엇갈리면
			arr[left], arr[right] = arr[right], arr[left]
	quick_sort(arr, start, right - 1)
	quick_sort(arr, right + 1, end)
    
    
quick_sort(arr, 0, len(arr)-1)

 

계수 정렬

특정 조건에 부합할 때만 사용 가능한, 매우 빠른 정렬 알고리즘이다. 정수 범위, 데이터 max - min 차이가 1,000,000 이하일 때 효과적으로 사용할 수 있다.

모든 데이터 범위의 리스트(초기값 0)를 선언하고, 데이터를 하나씩 확인하며 동일한 데이터 값의 리스트 인덱스의 데이터 값을 증가시키는 것이 계수 정렬이다.

arr = [7, 4, 2, 5, 6, 9, 0, 8, 3, 10, 1]

count = [0] * (max(arr) + 1)

for i in range(len(arr)):
	count[arr[i]] += 1
    
    
for i in range(len(count)):
	for j in range(count[i]):
    	print(i, end = ' ')
        
>>> 0 1 2 3 4 5 6 7 8 9 10

 

파이썬 정렬 라이브러리

 

arr = [7, 4, 2, 5, 6, 9, 0, 8, 3, 10, 1]

sorted(arr)
arr.sort()

 

 

 

 

백준 2750 수 정렬하기

n = int(input())
arr = []
for i in range(n):
    arr.append(int(input()))

for k in range(n):
    for j in range(n-1):
        if arr[j] > arr[j+1]:
            arr[j], arr[j+1] = arr[j+1], arr[j]
 
for x in arr:
    print(x)

 

 

백준 1920 수 찾기

계수 정렬 사용하면 되겠다 싶었는데... 메모리 초과가 계속 나와버린다.

초기 코드는 다음과 같다.

import sys
n = int(input())

nums = list(map(int, sys.stdin.readline().rstrip().split()))

m = int(input())

check = list(map(int, sys.stdin.readline().rstrip().split()))

count = [0] * (max(check) + 1)

for i in range(len(nums)):
    count[nums[i]] += 1
    
for i in range(len(check)):
    print(count[check[i]])

구글링 하니까 셋 사용해서 풀어서 허무했다...

import sys
n = int(input())

nums = set(map(int, sys.stdin.readline().rstrip().split()))

m = int(input())

check = list(map(int, sys.stdin.readline().rstrip().split()))

for i in check:
    if i not in nums:
        print(0)
    else:
        print(1)

 

백준 2108 통계학

n = int(input())

nums = [0] * n

for i in range(n):
    nums[i] = int(input())

nums = sorted(nums)

print(round(sum(nums)/n))

print(nums[n//2])



from collections import Counter

cnt = Counter(nums)

count = cnt.most_common(2)

if len(count) > 1:
    if count[0][1] == count[1][1]:
        print(count[1][0])
    else:
        print(count[0][0])
else:
    print(count[0][0])
    
print(nums[-1] - nums[0])

이거는 음.. 괜히 넣은 문제같기도하고..

 

백준 1946 신입 사원

시간 초과좀 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

초기 코드는 다음과 같다.

t = int(input())

for i in range(t):

    n = int(input())    
    score = {}
    for _ in range(n):
        a, b = map(int, input().split())
        score[a] = b
    keys = [m for m in range(1, n+1)]
    people = []
    for j in range(n):
        for k in range(0, j):
            if score[keys[j]] > score[keys[k]]:
                people.append(j+1)
                break
    print(n - len(set(people)))

하나 하나 비교하는게 틀렸다면 다른 방법을 찾아야지 뭐

 

import sys
t = int(input())

for _ in range(t):

    n = int(input())    
    score = []
    cnt = 1
    for i in range(n):
        score.append(list(map(int, sys.stdin.readline().rstrip().split()))) 
    score = sorted(score, key = lambda x: x[0])
    tmp = score[0][1]
    
    for j in range(1, n):
        if score[j][1] < tmp:
            tmp = score[j][1]
            cnt += 1
    print(cnt)

좀 그리디? 처럼 푸니까 풀렸다.

뭔가 모르는건 아닌데 자꾸 시간초과 뜨니까 화나 ㅠㅡㅠ..

 

 

백준 2470 두 용액

 

투 포인터 문제...! 구글링 전까지 몰랐는데 투 포인터 문제라는 것을 깨달았다.

사실 정렬을 sort로 해버리니까 음.. 다른 공부를 하는 느낌

import sys
n = int(input())
liquid = list(map(int, sys.stdin.readline().rstrip().split()))
liquid.sort()

left = 0
right = n-1
ans = 2000000000
answer = []

while left < right:
    l_left = liquid[left]
    l_right = liquid[right]
    
    tot = l_left + l_right
    
    if abs(tot) < ans:
        ans = abs(tot)
        answer = [l_left, l_right]
        
    if tot < 0:
        left += 1
    else:
        right -= 1
        
print(answer[0], answer[1])

 

 

백준 1461 도서관

 

n, m = map(int, input().split())

books = list(map(int, input().split()))

# -39 -37 -29 -28 -6 2 11

# max 값 찾고 그거만 한번 더하고 나머지 두번씩 더하면됨

split_p = []
split_n = []
maximum = 0
for b in books:
    maximum = max(abs(b), maximum)    
    if b > 0:
        split_p.append(b)
    else:
        split_n.append(abs(b))

split_p.sort(reverse = 1)
split_n.sort(reverse = 1)

result = 0

for i in range(0, len(split_p), m):
    result += split_p[i] * 2
    
for j in range(0, len(split_n), m):
    result += split_n[j] * 2
    
print(result - maximum)

 

 

백준 10026 적록색약

 

from collections import deque
n = int(input())

def bfs(g,x,y):
    visited[x][y] = 1
    q = deque()
    q.append((x,y))
    
    while q:
        x, y = q.popleft()
        dxdy = [(0,1), (0, -1), (1, 0), (-1, 0)]
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            
            if -1<nx<n and -1<ny<n:
                if g[nx][ny] == g[x][y] and not visited[nx][ny]:
                    visited[nx][ny] = True
                    q.append((nx, ny))


visited = [[0 for _ in range(n)] for _ in range(n)]

graph = [list(input()) for _ in range(n)]

can = 0
cant = 0
    

for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            bfs(graph, i, j)
            can += 1
            
visited = [[0 for _ in range(n)] for _ in range(n)]

for l in range(n):
    for i in range(n):
        if graph[l][i] == 'R':
            graph[l][i] = 'G'

for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            bfs(graph, i, j)
            cant += 1
            
print(can, cant)

흐어ㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓ문제가 날 푸는건지 내가 문제를 푸는건지..