[알고리즘] 삽입 정렬(Insertion sort) 의 개념 with c++

삽입 정렬이란 자료 배열의 모든 요소를 앞에서 부터 비교하고자 하는 타겟값(tmp)과 정렬된 값을 비교하여 자신의 위치를 찾아 삽입하면서 정렬해나가는 알고리즘이다. 매번 비교할 때마다 앞 부분에 해당하는 범위 모두 타겟값과 비교하여 해당 원소를 삽입할 수 있는 위치를 찾아 배열 위치에 넣는다. 📌정렬 과정(오름차순) 1. 2번째 원소부터 비교 시작한다 2. 이전 위치에 있는 원소들과 타겟이 되는 원소들을 비교한다(타켓 원소는 임시변수에 넣는다) 3. 타겟 원소가 이전 위치에 있던 원소보다 작다면 위치를 바꾼다 4. 이전 데이터도 차례대로 비교하며 정렬해나간다 5. 이 방법을 반복해서 정렬한다 📌특징 구현이 간단하다 배열이 길어질수록 효율이 떨어진다 선택 정렬이나 버블 정렬과 같은 O(n^2) 알고리즘에 ..

[알고리즘] 버블 정렬(Bubble sort)의 개념 with c++

버블 정렬은 인접한 두 수를 계속해서 비교하여 정렬하는 알고리즘이다. 1. 인접한 두 수를 대소를 비교한다. 2. 내림차순, 오름차순에 따라 두 수의 자리를 바꾼다. 3. 나머지 값들도 동일하게 처리한다. 구현이 매우 간단하여 코드 구현이 쉽지만, 비교 작업이 많기 때문에 시간 복잡도(n^2) 로 오래걸린다는 단점이 있다. 적은 양의 데이터를 정렬할때는 버블 정렬을 쓸 수 있지만, 대용량의 데이터를 정렬시 엄청 시간이 소요될 것이다. 📌 버블 정렬 c++ 코드 구현 #include using namespace std; int main(){ //버블정렬-오름차순 int n, i,j, tmp, a[101]; scanf("%d", &n); for(i=0; i

[알고리즘] 선택 정렬(Selection Sort) 의 개념 with c++

선택 정렬(Selection Sort) 선택 정렬은 제자리 정렬 알고리즘의 하나로 정렬되지 않은 데이터들 중에서 가장 작은 값을 추출하여 가장 맨 앞으로 정렬해나가는 알고리즘이다. 1. 배열 중에 최솟값을 찾는다. 2. 최솟값을 맨 앞으로 정렬시킨다.(swap) 3. 나머지 값들도 동일한 방식으로 정렬해나간다. 알고리즘이 단순하고 사용할 수 있는 메모리가 제한적인 경우 사용하기에 용이하며, 구현이 간단하지만 비효율적인 방법인 알고리즘이다. 📌시간 복잡도 기준값과 비교값들 중 최솟값을 찾기 위해 이중 for문 필요 - 첫 번째 회전 비교 횟수 : 1 부터 (n-1) = n-1 - 두 번째 회전 비교 횟수 : 2 부터 (n-1) = n-2 ... => 최솟값 찾기 : n-1, n-2, ..., 2, 1 번 ..

[Coding test Basic with c++] N!의 표현법

문제 임의의 N에 대하여 N!은 1부터 N까지의 곱을 의미한다. 이는 N이 커짐에 따라 급격하게 커진 다. 이러한 큰 수를 표현하는 방법으로 소수들의 곱으로 표현하는 방법이 있다. 먼저 소수는 2, 3, 5, 7, 11, 13... 순으로 증가함을 알아야 한다. 예를 들면 825는 (0 1 2 0 1)로 표현이 가능한데, 이는 2는 없고 3은 1번, 5는 2번, 7은 없고, 11은 1번의 곱이라는 의미이다. 101보 다 작은 임의의 N에 대하여 N 팩토리얼을 이와 같은 표기법으로 변환하는 프로그램을 작성해 보자. 출력은 아래 예제와 같이 하도록 한다. ▣ 입력설명 첫 줄에 자연수 N(3

[Coding test Basic with c++] Anagram(아나그램 : 구글 인터뷰 문제)

문제 Anagram이란 두 문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아 나그램이라고 합니다. 예를 들면 AbaAeCe 와 baeeACA 는 알파벳을 나열 순서는 다르지만 그 구성을 살펴보면 A(2), a(1), b(1), C(1), e(2)로 알파벳과 그 개수가 모두 일치합니다. 즉 어느 한 단어를 재 배열하면 상대편 단어가 될 수 있는 것을 아나그램이라 합니다. 길이가 같은 두 개의 단어가 주어지면 두 단어가 아나그램인지 판별하는 프로그램을 작성하세 요. 아나그램 판별시 대소문자가 구분됩니다. ▣ 입력설명 첫 줄에 첫 번째 단어가 입력되고, 두 번째 줄에 두 번째 단어가 입력됩니다. 단어의 길이는 100을 넘지 않습니다. ▣ 출력설명 두 단어가 아나그램이면 “YES"를 출력..

[Coding test Basic with c++] 자릿수의 합

문제 N개의 자연수가 입력되면 각 자연수의 자릿수의 합을 구하고, 그 합이 최대인 자연수를 출력 하는 프로그램을 작성하세요. 각 자연수의 자릿수의 합을 구하는 함수를 int digit_sum(int x)를 꼭 작성해서 프로그래밍 하세요. ▣ 입력설명 첫 줄에 자연수의 개수 N(3 max) { max=sum; res=num; } else if(sum==max){ if(num > res) res=num; } printf("%d\n",res); } return 0; } 각 n개의 자연수 개수만큼 digit_sum 함수를 실행시킨다. 각 자연수의 자릿수 구하기 위해 자연수 x를 10으로 나누어 떨어진 나머지 값은 자연수의 맨 끝값이 되니 tmp에 저장하고 sum에 더해준다. x값은 10으로 나눈 값으로 셋팅하면..

[Coding test Basic with c++] 모두의 약수

문제 자연수 N이 입력되면 1부터 N까지의 각 숫자들의 약수의 개수를 출력하는 프로그램을 작성하 세요. 만약 N이 8이 입력된다면 1(1개), 2(2개), 3(2개), 4(3개), 5(2개), 6(4개), 7(2개), 8(4 개) 와 같이 각 숫자의 약수의 개수가 구해집니다. 출력은 다음과 같이 1부터 차례대로 약수의 개수만 출력하면 됩니다. 1 2 2 3 2 4 2 4 와 같이 출력한다. ▣ 입력설명 첫 번째 줄에 자연수 N(5

[Coding test Basic with c++] 올바른 괄호

문제 괄호가 입력되면 올바른 괄호이면 “YES", 올바르지 않으면 ”NO"를 출력합니다. (())() 이것은 괄호의 쌍이 올바르게 위치하는 거지만, (()()))은 올바른 괄호가 아니다. ▣ 입력설명 첫 번째 줄에 괄호 문자열이 입력됩니다. 문자열의 최대 길이는 30이다. ▣ 출력설명 첫 번째 줄에 YES, NO를 출력한다. 입력예제 (()(()))(() 출력예제 NO 풀이 #include using namespace std; int main(){ // 올바른 괄호 char a[100]; int i, cnt=0; scanf("%s", &a); for(i=0; a[i]!='\0'; i++){ if(a[i]=='(') cnt++; else if(a[i]==')') cnt--; if(cnt