알고리즘
-
퀵 정렬 - 퀵 정렬은 대표적인 분할 정복 알고리즘 중 하나로 평균적으로 가장 빠른 실행 시간을 가지는 정렬 알고리즘 입니다. - 퀵 정렬은 unstable한 알고리즘으로 호출될 때마다 새로운 리스트를 생성하며 리턴하기 때문에 기본적으로는 not-in-place 정렬이기도 하다. - 퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n^2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다. Unstable 퀵 정렬은 unstable한 알고리즘으로 unstable한 알고리즘이란, 정렬 후 같은 값들의 순서가 원래의 순서와 다를 수 있는 것을 말합니다. 예를 들어, [3, 1, 3, 4, 2]와 같은 배열을 퀵 정렬로 정렬하면 [1,2,3,3,4]와 같이 3이 중복되서 나타나..
[알고리즘] 퀵 정렬퀵 정렬 - 퀵 정렬은 대표적인 분할 정복 알고리즘 중 하나로 평균적으로 가장 빠른 실행 시간을 가지는 정렬 알고리즘 입니다. - 퀵 정렬은 unstable한 알고리즘으로 호출될 때마다 새로운 리스트를 생성하며 리턴하기 때문에 기본적으로는 not-in-place 정렬이기도 하다. - 퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n^2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다. Unstable 퀵 정렬은 unstable한 알고리즘으로 unstable한 알고리즘이란, 정렬 후 같은 값들의 순서가 원래의 순서와 다를 수 있는 것을 말합니다. 예를 들어, [3, 1, 3, 4, 2]와 같은 배열을 퀵 정렬로 정렬하면 [1,2,3,3,4]와 같이 3이 중복되서 나타나..
2023.04.10 -
문제 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다. 다음 예는 22 × 22 크기의 배열을 방문한 순서이다. N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 다음은 N=3일 때의 예이다. 위의 문제에서 우선적으로 생각해봐야하는 부분은 전체 배열의 크기의 패턴을 파악하고 4등분을 내서 1사분면, 2사분면, 3사분면 ,4사분면 형태로 나눠서 생각한다는 점이 key point같다. 알고리즘은 분할정복과 재귀함수를 사용하며 분할정복을 간..
[백준]1074 Z [Python]문제 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다. 다음 예는 22 × 22 크기의 배열을 방문한 순서이다. N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 다음은 N=3일 때의 예이다. 위의 문제에서 우선적으로 생각해봐야하는 부분은 전체 배열의 크기의 패턴을 파악하고 4등분을 내서 1사분면, 2사분면, 3사분면 ,4사분면 형태로 나눠서 생각한다는 점이 key point같다. 알고리즘은 분할정복과 재귀함수를 사용하며 분할정복을 간..
2023.04.10 -
재귀함수란 - 재귀함수란, 함수가 자기 자신을 호출하여 문제를 해결하는 알고리즘입니다. 즉, 함수의 정의에서 함수 자신을 참조하는 것입니다. - 재귀함수는 보통 문제를 작은 부분 문제로 분할하여 해결할 수 있을 때 사용됩니다. 이때, 재귀함수는 각각의 부분 문제를 해결하는 데에도 같은 함수를 호출하게 됩니다. - 이러한 재귀함수의 가장 대표적인 사용 예제는 팩토리얼(Factorial)과 피보나치수열(Fibonacci) 입니다. 재귀함수의 장단점 장점 - 코드가 간결하고 이해하기가 쉽다. - 반복문을 사용하지 않아도 동일한 결과를 얻을 수 있다. 단점 - 함수를 호출할 때마다 스택 메모리에 쌓이기 때문에, 메모리를 많이 사용한다. - 깊이가 너무 깊어지면 스택 오버플로우가 발생할 수 있다. - 반복문을 사..
[알고리즘] 재귀함수(Recursion function), 꼬리재귀함수(Tail call recursion)재귀함수란 - 재귀함수란, 함수가 자기 자신을 호출하여 문제를 해결하는 알고리즘입니다. 즉, 함수의 정의에서 함수 자신을 참조하는 것입니다. - 재귀함수는 보통 문제를 작은 부분 문제로 분할하여 해결할 수 있을 때 사용됩니다. 이때, 재귀함수는 각각의 부분 문제를 해결하는 데에도 같은 함수를 호출하게 됩니다. - 이러한 재귀함수의 가장 대표적인 사용 예제는 팩토리얼(Factorial)과 피보나치수열(Fibonacci) 입니다. 재귀함수의 장단점 장점 - 코드가 간결하고 이해하기가 쉽다. - 반복문을 사용하지 않아도 동일한 결과를 얻을 수 있다. 단점 - 함수를 호출할 때마다 스택 메모리에 쌓이기 때문에, 메모리를 많이 사용한다. - 깊이가 너무 깊어지면 스택 오버플로우가 발생할 수 있다. - 반복문을 사..
2023.04.09 -
복잡도에 대해서 1. 크게 시간 복잡도(Time Complexity)와 공간 복잡도로 나눌 수 있다. 2. 알고리즘의 성능 평가 및 효율성을 나타내는 척도이다. 3. 동일한 기능을 수행하는 알고리즘이 있을때 복잡도가 낮을수록 좋은 알고리즘이라 말한다. 1. 시간 복잡도 - 시간 복잡도(Time Complexity)는 알고리즘이 실행되는 동안 수행하는 기본적인 연산 횟수의 총량을 나타내며, 입력 크기에 대한 함수로 표현됩니다. 즉, 입력 크기가 증가함에 따라 알고리즘이 실행되는 데 걸리는 시간의 증가량을 나타내는 것입니다. 시간 복잡도를 표기하는 방법 Big-O(빅-오) ⇒ 상한 점근 Big-Ω(빅-오메가) ⇒ 하한 점근 Big-θ(빅-세타) ⇒ 그 둘의 평균 위 세 가지 표기법은 시간 복잡도를 각각 최악..
[알고리즘] 시간 복잡도, 공간 복잡도, 빅오(Big-O) 표기법복잡도에 대해서 1. 크게 시간 복잡도(Time Complexity)와 공간 복잡도로 나눌 수 있다. 2. 알고리즘의 성능 평가 및 효율성을 나타내는 척도이다. 3. 동일한 기능을 수행하는 알고리즘이 있을때 복잡도가 낮을수록 좋은 알고리즘이라 말한다. 1. 시간 복잡도 - 시간 복잡도(Time Complexity)는 알고리즘이 실행되는 동안 수행하는 기본적인 연산 횟수의 총량을 나타내며, 입력 크기에 대한 함수로 표현됩니다. 즉, 입력 크기가 증가함에 따라 알고리즘이 실행되는 데 걸리는 시간의 증가량을 나타내는 것입니다. 시간 복잡도를 표기하는 방법 Big-O(빅-오) ⇒ 상한 점근 Big-Ω(빅-오메가) ⇒ 하한 점근 Big-θ(빅-세타) ⇒ 그 둘의 평균 위 세 가지 표기법은 시간 복잡도를 각각 최악..
2023.04.09