📚순열(Permutation) - 순열은 서로 다른 n개의 원소 중 r개를 선택하여 일렬로 나열하는 것을 말합니다. 이 때, 같은 원소가 중복되지 않고, 순서가 중요합니다. 예를 들어, 3개의 원소 A, B, C 중에서 2개를 선택하여 만들 수 있는 순열은 AB, AC, BA, BC, CA, CB입니다. - nPr : 서로 다른 n개에서 순서를 고려하여 r개를 뽑는 경우의 수를 의미합니다. - 예를 들어 4P2일 경우 4! / (4-2)! = 12 가지입니다. 1,2,3,4 중 2개를 뽑는 경우의 수를 나타내면 다음과 같습니다. (1,2), (1,3), (1,4) -> 3가지 (2,1), (2,3), (2,4) -> 3가지 (3,1), (3,2), (3,4) -> 3가지 (4,1), (4,2), (4,3..

💡병합 정렬(Merge sort) - 병합 정렬은 분할 정복방법을 사용하여 리스트를 정렬하는 알고리즘입니다. i) 병합 정렬 과정 - 리스트를 반으로 나눕니다. - 각각을 재귀적으로 정렬합니다. - 두 리스트를 다시 하나의 리스트로 합칩니다. 이때 두 리스트는 이미 정렬되어 있는 형태입니다. ii) 병합 정렬 특징 병합 정렬은 안정적인 정렬 알고리즘입니다. 안정적인 정렬 알고리즘이란, 같은 값의 원소가 여러 개 존재할 경우, 입력 배열에서의 순서가 유지되는 정렬 알고리즘을 말합니다. 병합 정렬은 분할 정복 알고리즘을 사용합니다. 이는 문제를 작은 문제로 분할하여 해결하는 방법으로, 재귀적인 호출을 이용하여 문제를 해결합니다. 병합 정렬의 시간 복잡도는 평균적으로 O(nlogn)입니다. 이는 입력 크기가 ..

정렬 알고리즘 이란 - 원소들을 일정한 순서대로 열거하는 알고리즘입니다. - 대표적인 알고리즘에는 아래와 같이 존재합니다. - 병합 정렬, 힙 정렬, 퀵 정렬의 경우 다음 포스팅에서 확인하시면 될 것 같습니다. 삽입 정렬 (Insertion sort) 선택 정렬 (Selection sort) 버블 정렬 (Bubble sort) 병합 정렬 (Merge sort) 힙 정렬 (Heap sort) 퀵 정렬 (Quick sort) 💡삽입 정렬 - 삽입 정렬은 데이터를 하나씩 확인하면서, 각 데이터를 적절한 위치에 삽입 하는 방법입니다. - 선택정렬처럼 동작을 직관적으로 이해하기 쉽지만, 선택정렬보다는 구현 난이도가 높고 실행시간 면에서 더 효율적입니다. i) 삽입 정렬 과정 1) 삽입정렬은 이미 정렬된 영역( ..

퀵 정렬 - 퀵 정렬은 대표적인 분할 정복 알고리즘 중 하나로 평균적으로 가장 빠른 실행 시간을 가지는 정렬 알고리즘 입니다. - 퀵 정렬은 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이 중복되서 나타나..

문제 한수는 크기가 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같다. 알고리즘은 분할정복과 재귀함수를 사용하며 분할정복을 간..

재귀함수란 - 재귀함수란, 함수가 자기 자신을 호출하여 문제를 해결하는 알고리즘입니다. 즉, 함수의 정의에서 함수 자신을 참조하는 것입니다. - 재귀함수는 보통 문제를 작은 부분 문제로 분할하여 해결할 수 있을 때 사용됩니다. 이때, 재귀함수는 각각의 부분 문제를 해결하는 데에도 같은 함수를 호출하게 됩니다. - 이러한 재귀함수의 가장 대표적인 사용 예제는 팩토리얼(Factorial)과 피보나치수열(Fibonacci) 입니다. 재귀함수의 장단점 장점 - 코드가 간결하고 이해하기가 쉽다. - 반복문을 사용하지 않아도 동일한 결과를 얻을 수 있다. 단점 - 함수를 호출할 때마다 스택 메모리에 쌓이기 때문에, 메모리를 많이 사용한다. - 깊이가 너무 깊어지면 스택 오버플로우가 발생할 수 있다. - 반복문을 사..

복잡도에 대해서 1. 크게 시간 복잡도(Time Complexity)와 공간 복잡도로 나눌 수 있다. 2. 알고리즘의 성능 평가 및 효율성을 나타내는 척도이다. 3. 동일한 기능을 수행하는 알고리즘이 있을때 복잡도가 낮을수록 좋은 알고리즘이라 말한다. 1. 시간 복잡도 - 시간 복잡도(Time Complexity)는 알고리즘이 실행되는 동안 수행하는 기본적인 연산 횟수의 총량을 나타내며, 입력 크기에 대한 함수로 표현됩니다. 즉, 입력 크기가 증가함에 따라 알고리즘이 실행되는 데 걸리는 시간의 증가량을 나타내는 것입니다. 시간 복잡도를 표기하는 방법 Big-O(빅-오) ⇒ 상한 점근 Big-Ω(빅-오메가) ⇒ 하한 점근 Big-θ(빅-세타) ⇒ 그 둘의 평균 위 세 가지 표기법은 시간 복잡도를 각각 최악..

WEEK01 - 컴퓨팅 사고로의 전환 이번주는 컴퓨팅 사고로의 전환 WEEK01주 차여서 파이썬을 사용하여 배열, 문자열, 반복문과 재귀함수, 시간복잡도, 정렬, 완전탐색, 정수론 등을 학습하는 시간입니다. 평소 파이썬을 자주 사용해보지않아서 기초 문법이 많이 부족한 상태였는데 e-book과 유튜브 강의를 통해 조금이나마 발전할 수 있었던 것 같습니다. https://www.youtube.com/watch?v=T6z-0dpXPvU 위 강의는 나도코딩 유튜브강의인데 100분짜리로 기본적인 문법들을 설명해 줘서 한 번쯤 듣기 좋은 거 같아요! 문제 소개 오늘 풀어본 알고리즘들 중에서 백준 알고리즘(9020번 - 골드바흐의 추측)과 (1914번 - 하노이탑)에 대해서 간단하게 정리해보려고 합니다. 1. 골드바..