본문 바로가기

분류 전체보기256

[프로그래머스] - 영어 끝말잇기(C++) 영어 끝말잇기 문제 설명1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다. 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.이전에 등장했던 단어는 사용할 수 없습니다.한 글자인 단어는 인정되지 않습니다.다음은 3명이 끝말잇기를 하는 상황을 나타냅니다. tank → kick → know → wheel → land → dream → mother → robot → tank 위 끝말잇기는 다음과 같이 진행됩니다. 1번 사람이 자신의 첫 번째 차례에 tank를 말합니다.2번 사람이 자신의 첫 번째 차례에.. 2025. 5. 20.
[프로그래머스] - 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.
[프로그래머스] - 귤고르기(C++) 귤고르기 문제 설명경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다. 예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다. 경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때.. 2025. 4. 26.
에라토스테네스의 체(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.
정렬 - 퀵정렬(Quick Sort) 퀵정렬(Quick Sort) 오늘은 퀵정렬에 대해 알아보겠습니다. 퀵정렬은 "대표적인 분할정복 알고리즘으로 평균속도가 O(nlogn)" 입니다.#include #include using namespace std;// 배열을 분할하는 함수int partition(vector& arr, int low, int high) { int pivot = arr[high]; // 피벗을 마지막 요소로 설정 int i = low - 1; // 작은 요소들의 인덱스 for (int j = low; j & arr, int low, int high) { if (low arr = {10, 3, 8, 9, 1, 5}; int n = arr.size(); cout  퀵정렬은 평균적으로 수행시간이 .. 2025. 3. 26.
정렬 - 삽입정렬(Insertion Sort) 삽입정렬(Insertion Sort) 오늘은 삽입정렬에 대해 알아보겠습니다. 삽입정렬은 "각 숫자를 적절한 위치에 삽입하는 방식하는 정렬 방법" 입니다. #include #include using namespace std;// 삽입 정렬 함수void insertionSort(vector& arr) { int n = arr.size(); for (int i = 1; i = 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; // key 삽입 }}// 배열 출력 함수void printArray(const vector& arr) { for (int num :.. 2025. 2. 24.
정렬 - 버블정렬(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.

티스토리툴바