본문 바로가기

알고리즘

[알고리즘] 기수 정렬(Radix Sort) 기수 정렬이란?​ 기수 정렬 (Radix Sort)은 자리수를 비교하며 정렬을 진행하는 알고리즘 이다. 기수 정렬의 종류 1. LSD (Least Significant Digit) 방식의 정렬​ 가장 작은 자릿수부터 정렬을 진행 (숫자로 치면 일의 자리수부터) 가장 작은 자릿수부터 큰 자릿수까지 비교해야 한다는 단점이 있지만, 코드 구현이 MSD에 비해 간결하다 2. MSD (Most Significant Digit) 방식의 정렬​ 가장 큰 자릿수부터 정렬을 진행 LSD와 비교했을 때 정렬 상태 확인등의 추가 작업이 필요하지만, 중간에 정렬이 완료될 수 있다는 장점이 있다 기수 정렬의 과정​ 기수 정렬의 과정을 배열 [134,224,232,122] 을 이용해 LSD방식과 MSD방식으로 각각 설명하고자 한.. 더보기
[알고리즘] 퀵 정렬(Quick Sort) 퀵정렬이란?​ 퀵정렬(Quick Sort)은 퀵이라는 이름답게 평균 속도 O(N*logN)을 자랑하는 매우 빠른 정렬 알고리즘이다. 퀵정렬은 분할정복(Divide & Conquer) 알고리즘의 하나로, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속하는 알고리즘이다. 퀵정렬의 전체적인 정렬 과정​ 퀵정렬은 임의의 pivot 값을 기준으로 pivot 의 좌측에는 pivot 보다 작은값을 두고 우측에는 pivot 보다 큰 값을 두는 방식으로 정렬을 진행한다. 전체적인 정렬 과정은 다음과 같다. 1. 리스트 안의 임의의 요소 하나를 선택한다. 이를 피봇(pivot) 이라고 하자. 2. pivot을 기준으로 pivot의 왼쪽에는 pivot보다 작은 원소를, pivot의 오른쪽에는 pivot보다 큰 원소.. 더보기
[알고리즘] 삽입 정렬 (Insertion Sort) 삽입 정렬이란?​ 삽입 정렬(Insertion Sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 비교하면서 자리를 교환(swap)하는 정렬 방법이다. 삽입 정렬의 과정​ 1. 현재 타겟이 되는 숫자와 이전 위치에 있는 원소들을 비교한다. (첫번째 타겟은 두번째 원소부터 시작) 2. 타겟이 되는 숫자가 이전 위치에 있던 원소보다 작다면 위치를 서로 교환한다. 3. 그 다음 타겟을 찾아 위와 같은 방법으로 반복한다. 위와 같은 삽입 정렬의 과정을 토대로 삽입 정렬의 전체적인 과정에 대해서 설명하자면 다음과 같다. (a) : 첫번째 타겟은 두번째 원소부터 시작하므로 7이다. 7 이전 위치에 있는 원소인 3과 비교했을 때 3이 더 작으므로 위치를 스왑하지 않는다. (b) : 두번째 타겟인 2와 이전 위치.. 더보기
[알고리즘] 버블 정렬(거품정렬, Bubble Sort) 버블 정렬이란 (거품 정렬, bubble sort)​ 버블 정렬은 서로 인접한 두 원소의 크기를 비교하여 정렬하는 방법이다. 구현은 간단하나 시간복잡도가 O(n^2) 으로 상당히 비효율적이다. 버블 정렬 예시 및 시간복잡도 증명​ 간단한 예시를 통해 버블 정렬 과정을 나타내면 다음과 같다. 위 그림에서 확인할 수 있듯이, 5개의 요소를 거품 정렬을 적용해서 정렬하면 비교연산이 4회 + 3회 + 2회 + 1회 = 10회 소요되는 것을 확인할 수 있고, 요소의 개수를 N개로 일반화하면 (N-1) + (N-2) + (N-3) + ... + 2 + 1 가 된다. 이를 공차가 1인 등차수열 공식에 대입해보면, 결과적으로 N*(N+1) / 2 임을 알 수 있다. 이를 시간복잡도로 표현해보면 O(n^2) 임을 확인할.. 더보기
[알고리즘] 선택정렬(Selection Sort) 선택 정렬 선택 정렬이란 제자리 정렬 알고리즘 중 한가지 방법이다. 보통 오름차순으로 정렬되는 선택 정렬은 다음과 같은 과정으로 이루어져 있다. 가장 작은 원소 값을 찾는다. 그 값을 맨 앞에 있는 값과 교체를 한다. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다. 하나의 원소만 남을 때까지 위의 과정을 반복한다. 선택 정렬 예시​ 예시를 통해 좀 더 자세히 살펴보자. 위 그림과 같이, [5, 3, 8, 1, 2, 7] 로 구성된 배열이 있다고 하자. 앞에서부터 탐색하여, 가장 작은 원소 1을 찾은 후 맨 앞의 값 5와 교체한다. 1의 위치를 확정짓고 [3,8,5,2,7] 중 가장 작은 수 2를 맨 앞의 값 3과 교체한다. 같은 방법으로 [8,5,3,7] 중 가장 작은 수 3과 맨 앞의 값 8.. 더보기
[백준] 11660 구간 합 구하기 5 (Python 파이썬) https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 설명 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 여기서 (2, 2)부터 (3, 4)까지 합을 구하.. 더보기
[백준] 16139 인간 (Python 파이썬) https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 문제 설명 특정 문자열 S, 특정 알파벳 α와 문자열의 구간 [l,r]이 주어지면 S의 l번째 문자부터 r번째 문자 사이에 α가 몇 번 나타나는지 구하는 프로그램을 작성하자. 문자열의 문자는 0번째부터 세며, l번째와 r번째 문자를 포함해서 생각한다. 풀이 과정 이 문제는 누적 합 으로 풀어야 시간초과 없이 해결할 수 있다. 만약, 매번 l부터 r.. 더보기
[백준] 2559 수열 (Python 파이썬) https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 문제 설명 그림과 함께 제공되는 문제이니 자세한 문제설명은 위 링크를 참조해주세요. 풀이 과정 이 문제는 누적 합 으로 푸는 문제이다. 누적합을 이용하지 않고 단순 합계를 이용한다면 시간초과 오류가 나게 된다. 한번 구간합을 구하는 시간복잡도는 O(n)이고 m번동안 수행을 하게 된다면 총 시간복잡도는 O(nm)이 되는데 데이터가 10만개가 되면 시간초과 오류가 나게 된다. 그래서 매번.. 더보기

티스토리툴바