[알고리즘] 버블 정렬(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

[Coding test Basic with c++] 영어단어 복구

문제 현수의 컴퓨터가 바이러스에 걸려 영어단어가 뛰어쓰기와 대소문자가 혼합되어 표현된다. 예를 들면 아름다운 이란 뜻을 가지고 있는 beautiful 단어가 “bE au T I fu L” 과 같이 컴퓨터에 표시되고 있습니다. 위와 같이 에러로 표시되는 영어단어를 원래의 표현대로 공백을 제거하고 소문자화 시켜 출력하는 프로그램을 작성하세요. ▣ 입력설명 첫 줄에 바이러스에 걸린 영어단어가 주어진다. 바이러스에 걸린 영어단어의 길이(공백포함)는 100을 넘지 않는다. 문자사이의 공백은 연속적으로 존재할 수 있습니다. 입력은 알파벳과 공 백만 주어집니다. ▣ 출력설명 첫 줄에 소문자로 된 정상적인 영어단어를 출력한다. 입력예제 bE au T I fu L 출력예제 beautiful 풀이 #include usin..