본문 바로가기

시간복잡도10

[프로그래머스] - N개의 최소공배수(C++) N개의 최소공배수 문제 설명두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요. 제한사항arr은 길이 1이상, 15이하인 배열입니다.arr의 원소는 100 이하인 자연수입니다. 입출력 예arrresult[2,6,8,14]168[1,2,3]6 시작 코드#include #include using namespace std;int solution(vector a.. 2025. 5. 4.
[프로그래머스] - 멀리 뛰기(C++) 멀리 뛰기 문제 설명효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2칸) 의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다. 제한사항n은 1 이상, 2000 이하인 정수입니다. 입출력 예nresult4533 입출력 예 설명 입출력 예 #1 위에서 설명한 내용과 같습니다. 입출력 .. 2025. 4. 27.
에라토스테네스의 체(Sieve of Eratosthenes) 에라토스테네스의 체(Sieve of Eratosthenes)오늘은 "에라토스테네스의 체"에 대해서 알아보도록 하겠습니다. 일단 이 이름을 처음 듣는 분들은 딱봐도 이전에 말씀드린 유클리드 호제법 처럼 옛날에 만들어진 개념이라는 생각이 들 것 같습니다. 이 개념은 고대 그리스의 수학자 에라토스테네스가 만든 소수 판별 알고리즘으로, 1부터 특정 수 n까지의 모든 소수를 빠르게 구할 때 사용하는 효율적인 방법입니다. 원리일단 이름을 체라고 한 것을 보면 뭔가 거름망 혹은 걸러낸다는 생각이 자연스럽게 듭니다. 소수(Prime Number)는 1과 자기자신만을 약수로 가지는 1보다 큰 자연수이고, 이 개념의 기본 아이디어는 가장 작은 소수부터 시작해서 그 배수를 지워나가는 방식으로 동작합니다. 1부터 n까지의 소.. 2025. 4. 22.
유클리드 호제법(Euclidean algorithm) 유클리드 호제법 (Euclidean algorithm)  이번에는 유클리드 호제법에 대해 알아보도록 하겠습니다. 먼저 유클리드 호제법이 뭔지 알아보겠습니다. 유클리드 호제법(Euclidean algorithm) 또는 유클리드 알고리즘은 두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법으로, 알고리즘을 공부할 때, 최대공약수(GCD, Greatest Common Divisor)와 최소공배수(LCM, Least Common Multiple)을 구하는 데 유용하게 사용되는 방식 입니다. 원리이름은 거창해보이고 복잡할 것 같지만, 그 원리를 보면 그다지 복잡하지 않습니다. "두 수의 최대공약수는, 큰 수에서 작은 수를 나눈 나머지와 작은 수의 최대공약수와 같다." 라는 원리로 접근하여 값을 도출하는 알.. 2025. 4. 13.
정렬 - 합병정렬(Merge Sort) 합병정렬(Merge Sort)오늘은 마지막으로 알아볼 정렬인 합병정렬입니다. 합병정렬 또한 이전에 살펴 본 퀵정렬과 같은 분할 정복 방식을 채택한 알고리즘으로 결과적으로는 퀵정렬과 동일한 O(nlogn)의 시간복잡도를 가집니다. 하지만 여러 상황에 따라 퀵정렬과는 차이점이 존재하니 자세히 살펴봐야 합니다.#include using namespace std;// 두 개의 정렬된 부분 배열을 병합하는 함수void merge(int arr[], int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; int* leftArr = new int[n1]; int* rightArr = new int[n2].. 2025. 4. 4.
정렬 - 버블정렬(Bubble Sort) 버블정렬(Bubble Sort) 이전에 알아본 선택정렬 다음은 버블정렬입니다. 버블 정렬을 간단하게 요약하면 "옆에 있는 값과 비교하여 더 작은 값을 반복적으로 앞으로 보내는 정렬 방법" 입니다. #include using namespace std;void bubbleSort(int arr[], int n) { for (int i = 0; i arr[j + 1]) { swap(arr[j], arr[j + 1]); } } }}void printArray(int arr[], int n) { for (int i = 0; i  위 소스코드는 C++로 짜여진 1~10까지의 숫자를 오름차순으로 정렬시키는 버블정렬입니다. 위 소스코드에서 p.. 2025. 2. 7.
정렬 - 선택정렬(Selection Sort) 선택정렬(Selection Sort) 지금부터는 다양한 종류의 알고리즘에 대해서 알아보도록 할 것입니다. 알고리즘의 종류는 매우 다양하지만 그 중에서 가장 많이 알려져있는 정렬에 대해서 차근차근 알아보겠습니다. 정렬에는 종류가 다양한데 그 중 가장 기본적인 것은 선택정렬입니다. 1~10까지의 숫자가 무작위로 있을 때 오름차순으로 정렬하는 것을 예시로 많이 사용하여 각 알고리즘의 동작과정을 살펴보는 것이 보편적입니다. 선택정렬은 "가장 작은 것을 선택하여 앞으로 보내는 방법" 입니다. #include using namespace std;int main() { int arr[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9}; int n = 10, minIndex, temp; .. 2025. 1. 31.
알고리즘 - 알고리즘의 정의 알고리즘의 정의안녕하십니까. 알고리즘 카테고리를 만들어놓고 언젠가 정리해야지 하다가 이제야 건들게 되었습니다. 기초부터 차근차근 알고리즘에 대해서 정리할 예정입니다. 그럼 바로 시작하겠습니다. 컴퓨터 구조의 기초알고리즘을 이야기 하기 전에 컴퓨터 구조에 대한 기초적인 내용부터 정리하고 가도록 하겠습니다. 결국 우리가 알고리즘을 짜고 사용하는 이유는 컴퓨터와 밀접한 연관이 있기 때문입니다. 컴퓨터의 정의는 전자회로를 이용한 고속 자동 계산기로 3가지 주요한 구성요소 하드웨어, 소프트웨어, 데이터로 구성되어 있습니다. 컴퓨터에는 다양한 부품이 있지만, 그 중 우리에게 중요한 것은 저장소입니다. 옜날에는 하드디스크를 사용했지만, 요즘은 SSD를 많이 사용합니다. 그런데 하드디스크는 우리가 알고있는 포인터와 비.. 2025. 1. 25.
[자료구조 4장] - 연결리스트(2) 연결리스트(2) 단순 연결리스트 구조와 연결방법 저장하려는 연결리스트 구조의 노드들은 첫 노드부터 꼬리에 꼬리를 물고 한 방향으로 연결되어 있으며 마지막 노드의 포인터는 NULL 값을 가진다. ex) 문자열의 집합 {"bake", "cake", "sake", "take"}을 알파벳 순서로 연결리스트에 저장하는 경우 헤드 노드 : 첫 번째 노드의 포인터 헤드 노드의 포인터를 잃으면 리스트 안의 전체 데이터에 접근할 수 없게 된다. 화살표는 다음 자료의 기억 장소 번지이며, 마지막 노드의 다음 데이터는 없으므로 NULL값을 가지게 된다. 이렇게 단순 연결리스트는 헤드 노드로부터 NULL 값을 가지는 노드까지 한 방향으로 연결되어 있다. 연결리스트를 사용하여 프로그램을 작성할 때, 리스트의 끝을 검사하는 경우.. 2024. 1. 30.
[자료구조 1장] - 컴퓨터와 프로그램의 이해(2) 컴퓨터와 프로그램의 이해(2) 저번에 작성한 첫 글은 챕터 1의 1-1과 1-2까지의 내용을 정리한 것입니다. 이제부터는 소개말 없이 바로 내용을 작성할 생각입니다. 프로그램과 자료구조 프로그램 : 자료구조 + 알고리즘 자료와 자료형 기본 자료형 : int, float, double, char 등 포인터 자료 : 다른 변수의 메모리 주소 값을 가지는 기본 자료형 자료구조의 분류 선형 구조 : 자료의 전, 후 항목 사이의 관계가 1:1, 자료의 앞과 뒤의 순서가 명확하게 나란히 줄을 선 형태인 리스트 구조 -> 배열, 스택, 큐, 연결리스트 등 비선형 구조 : 자료 항목 사이에 어떤 자료와 관계가 있는 다른 자료가 여러 개인 경우, 즉 1:n 또는 n:m의 관계인 그래프적 특성을 갖는 자료구조 -> 조직의.. 2023. 12. 24.

티스토리툴바