Toolofv 님의 블로그

퀵 정렬(Quick Sort)은 병합 정렬(Merge Sort)와 비슷하게 분할정복(Divide and Conqueror)의 방법으로 정렬되는 알고리즘이다. 퀵 정렬은 시간복잡도로는 복불복이다. 최선, 평균의 경우 $O(n\ log\ n)$이지만 최악의 피벗을 선택했을 경우 $O(n^{2})$이다. 공간복잡도는 추가적인 배열을 만들지 않는 In-Place 방식의 경우 추가배열이 만들어지지 않지만 재귀함수 호출로 인해 $O(log\ n)$이다. 추가적인 배열을 선언하는 Non-In-Place 방식은 $O(n)$이다. 퀵 정렬(Quick Sort)  1. pivot을 왼쪽으로 몰거나 오른쪽으로 몰아 하는 방식이 있다.(아래는 왼쪽 이동하는 방법이다.)2. pivot값을 지정한 후 l ,  r 을 pivot값..

정렬 알고리즘은 사실 실제로 구현해서 사용할 일은 없는 것 같다. 매일 잊어먹기 때문에 기록의 용도로 올린다. 병합 정렬(Merge Sort)의 시간복잡도는 최악의 경우부터 최선의 경우 모두 $O(n\ log\ n)$이고, 공간복잡도는 $O(n)$이다. 배열의 크기에 비례하는 공간이 필요하다.  병합 정렬(Merge Sort)  병합 정렬은 배열을 재귀함수로 계속 분할하고 끝에서부터 병합하면서 정렬이 되는 구조다. 타고타고 병합이 완료되면서 정렬된다. - 코드import syssys.setrecursionlimit(10**6)input = sys.stdin.readlined = [1, 6, 8, 2, 9, 3, 7, 5, 4]def merge_sort(d): if len(d) = len(l) or ..

힙(Heap) 정렬 알고리즘은 정렬의 용도로 주로 쓰인다고 볼 수는 없는 것 같다. 힙 자료구조는 원소가 들어갈 때 최댓값, 최소값을 꺼내쓰는데 효율적이기 때문에 다익스트라(dijkstra) 알고리즘같은 경우에도 사용된다. 시간복잡도는 $O(n\ log\ n)$이다. 완전이진트리(complete binary tree)다. 파이썬의 경우 heapq 모듈을 사용한다. 힙 자료구조화와 정렬은 좀 다르다.  Siftdown( )의 경우 범위를 받고 부모노드(parent)를 지정한다. 바로 밑의 자식 노드를 child로 지정한 후 오른쪽의 자식 노드와 비교해 큰 값을 최종 child로 정한다. 지정된 부모노드와 자식 노드를 비교하고 자식 노드 값이 크면 바꿔준다.(최대힙의 경우) 그 것을 반복하면 부모노드와 자식..

백준 - 2583 영역 구하기첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. www.acmicpc.net문제눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.예를 들어 M=5, N=7 인 모눈종이 위에 과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 와 같이 3개의 분리된 영역으로 나누어지게 된다.   와 ..

백준 - 2573 빙산첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. www.acmicpc.net문제지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다.  빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되..

백준 - 10026 적록색약적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. www.acmicpc.net문제적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 ..

백준 - 16236 아기 상어첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.www.acmicpc.net문제N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는..

백준 - 2941 크로아티아 알파벳첫째 줄에 최대 100글자의 단어가 주어진다. 알파벳 소문자와 '-', '='로만 이루어져 있다. 단어는 크로아티아 알파벳으로 이루어져 있다. 문제 설명의 표에 나와있는 알파벳은 변경된 형태로 입력된다.www.acmicpc.net문제예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. čc=ćc-dždz=đd-ljljnjnjšs=žz= 예를 들어, ljes=njak은 크로아티아 알파벳 6개(lj, e, š, nj, a, k)로 이루어져 있다. 단어가 주어졌을 때, 몇 개의 크로아티아 알파벳으로 이루어져 있는지 출력한다.dž는 무조건 하나의 알파벳으로 쓰이고, d와 ž가 분리된 것으로 보지 않는다. lj..

백준 문제www.acmicpc.net 문제 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B의 인덱스는 1부터 시작한다. 입력 첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, N2)보다 작거나 같은 자연수이다. 출력 B[k]를 출력한다. 필요한 도구 1. 이분 탐색 알고리즘 - 좌, 우측 탐색 : 찾는 값이 없을 경우 가장 근접한 방향의 값을 출력하거나, 찾는 값이 여러 개일..