태야

<내 풀이>

- 1차 시도

n = int(input())
dots = []

for i in range(n):
    [x, y] = map(int, input().split())
    dots.append([x, y])

for j in range(0, n-1):
    curIdx = j
    for k in range(j+1, n):
        if(dots[curIdx][0] > dots[k][0]):
            curIdx = k
        if(dots[curIdx][1] > dots[k][1]):
            curIdx = k
    dots[j][0], dots[curIdx][0] = dots[curIdx][0], dots[j][0]
    dots[j][1], dots[curIdx][1] = dots[curIdx][1], dots[j][1]


for i in range(n):
    print(dots[i][0], dots[i][1])

: 시간 복잡도가 O(n^2)이라 안될 거 같았는데.. 역시나 시간 초과로 통과하지 못했다.

- 2차 시도

n = int(input())
dots = []

for i in range(n):
    dots.append(list(map(int, input().split())))

dots = sorted(dots, key=lambda x: (x[0], x[1]))

for i in dots:
    print(*i)

: 구글링을 통해 다른 사람들이 한 풀이를 참고했다. 일단 모르는 개념들이 많아서 이해하는데 어려움이 있었는데, 개념을 알고 나니 정말 간단하게 구현을 할 수 있다는 것을 알았다.

1) sorted(iterable, *, key=None, reverse=False)

: 첫 번째 인자로 정렬하고자 하는 반복 가능한 자료형을 넣는다. key인자의 값으로 함수를 넣어주면 함수의 반환 값을 기준으로 정렬을 해준다. 마지막 인자를 True로 하면 내림차순으로 정렬을 하게 된다.

2) lambda 함수

: 익명 함수를 만들 때 사용하며, 재사용이 되지 않는 간단하게 사용하는 함수이다. 함수명을 쓰지 않고 'lambda 인자 : 표현식' 형태로 사용하고 리턴 값을 보낸다.

3) Packing, Unpacking Operator *

 알고리즘, 자료구조 - 선택 정렬 

선택 정렬이란?

리스트 안의 원소들 중 최솟값을 찾아 리스트의 앞쪽으로 보내고, 그 뒤에 남은 원소들에 대해서 반복적으로 최솟값을 찾아 정렬하는 알고리즘이다. 간단한 알고리즘이지만 성능면에서는 느리기 때문에 좋지 않은 방식이다.

- 선택 정렬 알고리즘의 구체적인 개념

1. 첫 번째 원소를 선택, 그 뒤의 원소들과 차례대로 비교해 최솟값을 찾는다.

2. 찾은 최솟값을 첫 번째로 옮긴다.

3. 두 번째 원소를 선택, 3번째 원소부터 끝까지 비교해 최솟값을 찾는다.

4. 위의 과정들을 계속 반복한다.

위의 알고리즘 방식을 보면 코드상에서 2개의 반복문이 필요하고 이는 시간 복잡도 면에서 O(n^2)의 시간이 걸린다.

- 시간 복잡도

0번 요소: (n-1) 번 비교

1번 요소: (n-2) 번 비교

 ...

n-2번 요소: 1번 비교

n-1번 요소: 0번 비교

전체 비교 횟수는 0+1+2+3+...+n-2+n-1 = (n-1)(n-1+1) / 2 가 된다. n의 수가 커지면 결국 n^2이 큰 영향을 가지고 나머지는 무시할 수 있다. 따라서 시간 복잡도는 O(n^2)가 된다. 

예제

def select_sort(li):
    n = len(li)

    for i in range(0, n-1): #0번째~n-2번(뒤에서 2번째)
        min_idk = i
        for j in range(i+1, n): #비교하려는 값 뒤부터 끝까지 비교
            if(li[j] < li[min_idk]): # 비교하려는 값보다 뒤에 값이 작다면
                min_idk = j 		 
        li[i], li[min_idk] = li[min_idk], li[i] # 최솟값 위치 변경 

    return li


print(select_sort([2, 4, 5, 1, 3])) # [1, 2, 3, 4, 5]