1. 개념 퀵 정렬 : 나열된 데이터 내에서 기준값을 지정하여 각각의 데이터를 기준값보다 큰 데이터, 작은 데이터로 분류하는 것을 반복하는 정렬 * 시간 복잡도 : O(n²) 퀵 정렬 방법 - 나열된 데이터 내에서 pivot(기준값)을 정한다 - pivot을 제외한 데이터 배열의 시작과 끝을 각각 start, end 로 정한다 아래의 과정을 start와 end가 만날 때까지 반복한다. 1 ) start pivot. : pivot보다 큰 값이 제시될 때까지 end를 왼쪽으로 한 칸씩 옮긴다 3 ) start > end 가 되면(start값과 end 값이 엇갈리면) start와 end를 swap..

1. 개념 삽입 정렬 : 이미 정렬된 범위에 정렬되지 않은 데이터를 알맞은 위치에 끼어넣는 정렬 * 시간 복잡도 : O(n²) 삽입 정렬 방법 1) 두번째 인덱스에서 출발한다 2) 현재 선택한 데이터 앞부분은 이미 정렬된 범위이며 정렬된 범위 내에 선택한 데이터를 알맞은 위치에 넣는다 3) 반복 삽입 정렬이 버블 정렬, 선택 정렬과 다른 점 - 버블 정렬, 선택 정렬 : 첫 번째 인덱스부터 시작 / 삽입 정렬 : 두 번째 인덱스부터 시작 - 버블 정렬, 선택 정렬 : 정렬된 범위 방치 / 삽입 정렬 : 정렬된 범위 계속 이용 2. 문제 풀이 # 1 ATM 인출 시간 계산하기 - 백준 11399번 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수..

1. 개념 선택 정렬 : 나열된 데이터에서 최솟값 혹은 최댓값을 찾아 루프 범위 가장 앞에 있는 데이터와 swap 하는 정렬 * 시간 복잡도 : O(n²) 선택 정렬 방법(오름차순 기준) 1) 루프 범위에서 최솟값을 찾는다 2) 루프 범위에서 가장 앞에 있는 데이터와 최솟값 데이터를 swap해준다 - 최솟값이 제자리를 찾음 3) 제자리를 찾은 데이터를 제외하여 루프 범위를 재정비한다 4) 반복 2. 문제 풀이 # 1 내림차순으로 자릿수 정렬하기 - 백준 1427번 https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net # 입력 strin..

1. 개념 버블 정렬 : 서로 인접한 두 데이터 값을 비교하여 정렬하는 방식 * 시간 복잡도 : O(n²) 버블 정렬 과정 1) 버블 정렬이 필요한 루프 범위를 설정한다 ( 루프 범위에서 정렬이 끝난 숫자 제외 ) 2) 루프 범위 내에서 서로 인접한 데이터 값을 비교한다 3) swap 조건( 오름차순 : 앞 > 뒤 / 내림차순 : 앞 < 뒤 )에 부합하면 swap해준다 4) 루프 범위 내에서 swap이 모두 끝나면 루프 범위를 재설정해준다 5) 루프 범위의 크기가 0이 될 때까지 반복해준다 2. 문제 풀이 # 1 수 정렬하기 1 - 백준 2750번 https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘..

1. 개념 슬라이딩 윈도우 : 투 포인터를 이용해 범위를 지정해주고 지정된 범위를 옮겨가면서 문제를 해결하는 알고리즘 * 지정된 범위 : window 옮기기 : sliding 2. 문제 풀이 # 1 DNA 비밀번호 - 백준 12891번 https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net import sys input = sys.stdin.readline ans = [0] * 4 now = [0] * 4 # 윈도우 옮길 때 추..

1. 개념 투 포인터 : 2개의 포인터 파이썬에서는 리스트를 생성하고 리스트 index를 이용해서 포인터를 지정하면 된다. * 시간복잡도를 줄일 때 사용하기 좋다. 어떤 애들을 포인터로 지정하면 될까? 대표적인 경우 두 가지를 소개해보자면 (1) 속도가 다른 투포인터 -> slow runner, fast runner (2) 시작점과 끝점에서 출발해서 가운데에서 만나는 투포인터 [1] 속도가 다른 투포인터 : slow runner, fast runner i : slow runner j : fast runner [2] 시작점과 끝점에서 출발해서 가운데에서 만나는 투포인터 2. 문제 풀이 # 1 수들의 합5 - 백준 2018번 https://www.acmicpc.net/problem/2018 2018번: 수들..