Sort 함수: Sorted 혹은 a.sorted를 활용하여 리스트를 정렬하는 방식
Default값은 오름차순 형식으로 반환
내림차순으로 값을 보고싶은 경우는 a.sort(reverse = True) or sorted(a, reverse = True)해주면 된다.
또한, lambda함수를 이용해서 리스트안의 리스트 기준으로 오름, 내림차순을 정할 수 있다.
다중 조건을 주고 싶을 때에는 튜플 형식으로 앞에오는 것을 우선조건으로 할 수 있다.
sorted(c, lambda x: (x[0], x[1]))
바이너리 서치 - 이진탐색(Binary search)
- Big O - O(log N)
- 정렬된 자료를 반으로 나누어 탐색하는 방법
- 자료는 오름차순 또는 내림차순으로 정렬된 자료여야 한다.
- 퍼포먼스가 아주좋고 구현하는 중에 dynamic programming, recursion을 볼 수가 있다.
- 참고로 insert sort(삽입정렬), bubble sort, selection sort는 O(n^2)의 성능을 갖고 있다.
정렬 알고리즘 - O(n^2)
- 삽입정렬: 배열을 두개로 나누어서 작은것부터 왼쪽 배열에 삽입
- 선택 정렬: 가장 작은 값을 골라 맨 앞자리부터 바꿔서 정렬 (삽입정렬과 매우 유사)
- 버블 정렬: 두 원소를 비교해서 가장 큰 값을 뒤로보내면서 정렬 (배열 요소의 수만큼 반복)
알고리즘 수행시간 유형 N
- 알고리즘 분석결과는 입력되는 자료 수 N에 대하여 수행 시간을 함수 관계로 표현한것
1 (유형)
입력 자료의 수에 관계없이 일정한 실행 시간을 갖는 알고리즘.
실행시간이 상수. (몇번만 실행되는 경우 도전해볼만한 알고리즘)
Log N (유형)
입력자료수에 따라 log N의 관계를 만족한다면 입력자료수가 늘어남에 따라 실행시간이 조금씩 늘어나는 구조.
주로 커다란 문제를 일정한 크기를 갖는 문제로 쪼갤 때 나타나는 유형
효율이 좋은 알고리즘은 Log N 유형이다.
N (유형)
입력한 자료수에 따라 선형적으로 입력시간이 늘어나는 형태.
납득할만한 실행 시간을 갖는다.
N log N (유형)
커다란 문제를 각각의 독립적인 문제로 쪼개어 풀고 독립적으로 해결된 부분들을 하나를 모으는 경우에 나타난다.
선형 N 유형보다 시간이 좀 더 걸린다.
N^^2 (유형)
이중루프를 사용할 때 나타나는 유형이다. 시간이 꽤나 많이 걸리는 유형
백준문제들
하노이의 탑
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.
아래 그림은 원판이 5개인 경우의 예시이다.
입력
첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.
출력
첫째 줄에 옮긴 횟수 K를 출력한다.
두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.
def hanoi_top(n, start, end, middle):
if n == 1:
print(f'{start} -> end')
return
else:
hanoi_top(n-1, start, middle, end)
print(f'{start} -> end')
hanoi_top(n-1, middle, end, start) 하노이 탑을 옮기는 과정을 재귀함수 형태로 풀으면 되는 구조이다.
hanoi_top이 만약 1개라면 1번에서 3번으로 바로 옮기면 된다. 그게 아니라면, n-1개 만큼을 중간에 옮기고 첫번째 판을 마지막으로 옮긴다. 그리고 나서 마지막 두개를 오른쪽으로 옮기는 과정이다.
문제
2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.
출력
첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.
num = int(input())
list1 = list()
for i in range(num):
k = list(map(int, input().split()))
list1.append(k)
final_list = sorted(list1, key = lambda x: (x[1], x[0]))
for i in final_list:
x = i[0]
y = i[1]
print(x, y)
