빽 투더 기본기 [알고&자구 1편]. 정렬
기본 정렬에 대해서 정리해 놓는다. 그냥 나 알아보기 쉽게, 직관적으로만 설명한다. 시간 복잡도 O(n^2) 정렬 선택 정렬 뒤에 가장 큰, 또는 가장 작은 값을 현재 인덱스 뒤부터 찾아, 앞의 인덱스부터 하나씩 채워나가는 정렬. # selection sort a = [3,1,2,5,4,6,7] size = len(a) for i in range(size): for j in range(i+1, size): if a[j] < a[i]: a[i], a[j] = a[j], a[i] print(a) 버블 정렬 뒤에 가장 큰, 또는 가장 작은 값을 뒤로 밀어밀어 보내, 마지막 인덱스부터 하나씩 채워나가는 정렬 # bubble sort a = [3,1,2,5,4,6,7] size = len(a) for i in r..
파이썬 정렬, 다중 조건으로 한 번에 하기.
파이썬으로 문제를 풀다보면, 여러 조건으로 소팅을 해야하는 경우가 있다. 일반적인 소팅은 다음과 같이 sorted() 혹은 .sort() 를 사용한다. a = [4,1,2,5,7,3,6] b = sorted(a) # b = [1,2,3,4,5,6,7] sorted() 를 찬찬히 살펴보면 다음과 같다. a = [(1, 2), (0, 1), (5, 1), (5, 2), (3, 0)] # 인자없이 그냥 sorted()만 쓰면, 리스트 아이템의 각 요소 순서대로 정렬을 한다. b = sorted(a) # b = [(0, 1), (1, 2), (3, 0), (5, 1), (5, 2)] # key 인자에 함수를 넘겨주면 해당 함수의 반환값을 비교하여 순서대로 정렬한다. c = sorted(a, key = lambd..
[BOJ] 12100. 2048 (Easy)
문제 2048 (Easy) (https://www.acmicpc.net/problem/2048) 풀이 1. 초기 접근 문제조건 해석 판이 주어지고, 각 스텝마다 판 전체의 값이 달라진다. 움직이는 방향은 4가지 이므로, 바뀌는 판도 4가지 경우가 생긴다. 특정 스텝에서 멈추고, 가장 큰 값을 반환해야 한다. BFS 문제다. 알고리즘 전체적인 BFS 문제, 바뀌는 것은 전체 판이니, BFS queue 에 전체 판을 넣어주면 된다. 한 번에 4가지 경우의 판이 생기고, 총 5번까지 해야하니, 최대 경우의 수는 4^5 = 1024개다. 각 방향에 대하여 움직이는게 좀 까다로운데, 이를 별도의 함수 move(board, di) 로 두자. 먼저 이전의 판 board 와 움직이는 방향 di 를 넘겨받아, 움직임이 ..
하나씩 점을 찍어 나가며