문제풀이

import sys
from collections import deque           # deque 라이브러리 사용
input = sys.stdin.readline

# dfs 함수
def dfs(graph, v, visited):
    visited[v] = True                   # 방문 처리
    dfsSearch.append(v)                 # 탐색 리스트에 삽입

    graph[v].sort()                     # 인접 정점 리스트 오름차순으로 정렬
    for u in graph[v]:                  # 인접 정점 순환
        if not visited[u]:              # 방문하지 않은 정점이면
            dfs(graph, u, visited)      # 재귀로 방문 -> (스택과 같음)

# bfs 함수
def bfs(graph, v, visited):
    q = deque()                         # 큐 초기화
    visited[v] = True                   # 시작 정점 방문 처리
    q.append(v)                         # 시작 정점 큐에 삽입

    while q:                            # 큐가 빌때까지 반복
        node = q.popleft()              # 큐에서 하나 가져옴
        bfsSearch.append(node)          # 탐색 리스트에 삽입
        graph[node].sort()              # 인접 정점 리스트 오름차순으로 정렬
        for u in graph[node]:           # 인접 정점들 순환
            if not visited[u]:          # 인접 정점에 방문하지 않았다면
                q.append(u)             # 큐에 삽입
                visited[u] = True       # 방문 처리

n, m, v = map(int, input().split())     # n:정점 수, m:간선 수, v:정점 번호
graph = [[] for i in range(n+1)]        # 0부터라서 +1 (0번은 버림)
for _ in range(m):                      # 간선 수 만큼 입력
    a, b = map(int, input().split())    # 정점 a, b가 간선으로 이어져있음을
    graph[a].append(b)                  # 해당 정점 인덱스에 연결된 정점을 삽입해 입력
    graph[b].append(a)                  # (인접 리스트 방식)

dfsSearch = []                          # dfs 탐색 순서를 저장할 리스트
bfsSearch = []                          # bfs 탐색 순서를 저장할 리스트

visited = [False] * (n + 1)             # visited를 정점 수만큼 초기화 (0부터라서 +1)
dfs(graph, v, visited)                  # dfs 실행
visited = [False] * (n + 1)             # 다시 초기화
bfs(graph, v, visited)                  # bfs 실행

print(*dfsSearch, sep=' ')              # 출력
print(*bfsSearch, sep=' ')

문제

숫자를 입력 받아 오름차순으로 버블정렬, 선택정렬, 삽입정렬, 퀵정렬, 병합정렬하는 알고리즘을 구현하고 정렬된 리스트를 모두 출력하세요.

(시간은 이 정도 입력으로 차이가 없네..)

입력 예제

10
1 4 3 2 5 9 8 6 7 10

예제 출력

1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10

import sys, time
input = sys.stdin.readline

def selection(n, list):
    for i in range(n-1):
        _min = list[i]                              # 가장 작은 값으로 처음 값 선택
        idx = i                                     # 처음 값 인덱스
        for j in range(i+1, n):
            if list[j] < _min:                      # 다음 값들은 다 돌며 가장 작은 값 선택
                _min = list[j]
                idx = j
        list[i], list[idx] = list[idx], list[i]     # 정렬되지 않은 가장 앞의 값과 선택된 가장 작은 값을 스왑
    return list

def bubble(n, list):
    for i in range(n):
        for j in range(n-i-1):
            if list[j] > list[j+1]:                     # 다음값과 비교해 더 크면
                list[j], list[j+1] = list[j+1], list[j] # 바꿔서 끝에부터 정렬
    return list

def insertion(n, list):
    for i in range(1, n):
        key = list[i]                       # key : 정렬할 원소
        idx = i - 1
        while idx >= 0 and list[idx] > key:
            list[idx+1] = list[idx]         # 정렬할 값보다 크면 한칸씩 미룸
            idx -= 1
        list[idx+1] = key                   # 작은거 뒤에 키를 넣음
    return list

def quick(n, list, start, end):
    if start >= end:            # 원소가 1개인 경우 그대로 둠
        return
    pivot = start               # 피벗은 첫번째 원소
    i = start + 1
    j = end
    while i <= j:               # 엇갈릴 때까지 반복
        while(i <= end and list[i] <= list[pivot]):     #끝에 도달하거나 피벗보다 큰 값을 찾을 때까지 반복
            i = i + 1
        while(j > start and list[j] >= list[pivot]):    #피벗에 도달하거나 피벗보다 작은 값을 찾을 때까지 반복
            j = j - 1
        if(i > j):                                      # 엇갈린 상태(작은 값의 인덱스가 큰 값의 인덱스보다 작으면, 피벗 값과 작은 값을 교환)
            list[pivot], list[j] = list[j], list[pivot]
        else:                                           # 엇갈리지 않은 상태 (작은 값의 인덱스가 큰 값의 인덱스보다 크면, 작은 값과 큰 값을 교환)
            list[i], list[j] = list[j], list[i]
    quick(n, list, start, j - 1);                                # 피벗보다 작은 값들에 대해서도 새로운 피벗을 설정하여 퀵정렬 실행
    quick(n, list, j + 1, end);                                  # 피벗보다 큰 값들에 대해서도 새로운 피벗을 설정하여 퀵정렬 실행
    return list

def merge(n, list):
    if len(list) < 2:                                   # 1개면 그냥 리턴
        return list

    mid = len(list) // 2                                # 중간값
    lList = merge(n, list[:mid])                        # 왼쪽 리스트 재귀 호출
    rList = merge(n, list[mid:])                        # 오른쪽 리스트 재귀 호출

    mergedList = []
    l = r = 0
    while l < len(lList) and r < len(rList):            # (정렬된) 두 리스트 비교해서 정렬
        if lList[l] < rList[r]: # l is  greater
            mergedList.append(lList[l])
            l += 1
        else:
            mergedList.append(rList[r])
            r += 1
    mergedList += lList[l:]                             # 나머지 이어붙임
    mergedList += rList[r:]
    return mergedList                                   # 정렬된 리스트 정렬

n = int(input())
li = list(map(int, input().split()))

timeList = []

print(*selection(n, li), sep=" ")
print(*bubble(n, li), sep=" ")
print(*insertion(n, li), sep=" ")
print(*quick(n, li, 0, n-1), sep=" ")
print(*merge(n, li), sep=" ")