본문 바로가기

Programming150

쉘 정렬 (Shell Sort) 1. 쉘 정렬 간격(gap)을 이용해서 굵직굵직한 삽입정렬을 하자 ※ 삽입정렬은 어느 정도 이미 정렬된 배열에서 효과적 ∴ 1. 간격을 이용해서 굵직굵직한 그룹별 삽입 정렬을 한다. (큰 숫자들 대충 뒤로, 작은 숫자들 대충 앞으로) 2. 큰 틀에서 어느정도 정렬이 된 상태가 된다. 3. 이후에 정석 삽입정렬을 해서 완벽히 정렬 ※ gap 전체 원소 수의 1/2 → 이전 gap의 1/2 → 이전 gap의 1/2 → ...... → 1 2. 쉘 정렬 예제 ex ) 30 60 90 10 40 80 40 20 10 60 50 30 40 90 80 오름차순 정리하시오. #include void shellSort(int arr[], int len) { for(int h=len/2 ; h>0 ; h/=2) { fo.. 2022. 6. 6.
[c++ 줍줍] 대문자 <=> 소문자 ▷ 문제 상황 대문자 → 소문자 소문자 → 대문자 변환하기 ▶ 해결 방법 1 아스키 코드 숫자값 이용하기 대문자(A)와 소문자(a) 차이값 1st 알파벳(A) 와 last 알파벳(Z) 차이값 32 25 char small = s[i] - 32; // 대 -> 소 char large = s[i] + 32; // 소 -> 대 ▶ 해결 방법 2 이미 만들어져 있는 메소드 이용 ( #include 필요 ) 대 → 소 소 → 대 tolower(대) = 소 toupper(소) = 대 char small = tolower(s[i]); // 대 -> 소 char large = toupper(s[i]); // 소 -> 대 2022. 5. 30.
[c++ 줍줍] 문자열 내에 존재하는 특정 문자열 치환 ▷ 문제 상황 문자열 내부에 있는 특정 새끼 문자열을 다른 새끼 문자열로 치환하는 방법 ex ) "HappyBirthdayToYou" → "HappyChildren'sDayToYou" ▶ 해결 방법 1 replace( ) 이용 replace(시작 index , 바꾸려는 만큼의 길이 , "치환 문자열") #include using namespace std; int main() { string str1 = "apple-banana"; cout 2022. 5. 22.
[c++ 줍줍] string 공백 기준으로 잘라서 새 배열에 저장 ▷ 문제 상황 string을 공백 기준으로 잘라서 새 배열에 저장하는 방법 ex) "Happy birthday to you" → A[ ] = { "Happy", "birthday", "to", "you" } ▶▶ 해결 방법 sstream 라이브러리의 stringstream 이용하기 #include int main() { string s1 = "Happy birth day to you"; stringstream A(s1); A.str(s1); string item; while(A >> item) { cout 2022. 5. 22.
[프로그래머스 Lv.2] 124 나라의 숫자 / c++ [출처] https://programmers.co.kr/learn/courses/30/lessons/12899 코딩테스트 연습 - 124 나라의 숫자 programmers.co.kr ▷▷ 문제 124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다. 124 나라에는 자연수만 존재합니다. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다. 자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요. ▶▶ KEY 1. 뭔가 n진수 표현하는 유형 같으므로 n으로 나눈 몫과 나머지를 이용할 것이라 생각 2. 규칙성을 찾기 위해 일단 충분히 나열해보기 3. 규칙 발견.. 2022. 5. 22.
[c++ 줍줍] switch 문 ▷ switch 문 int n; string end; swith(n) { case 0: end = "4"; break; case 1: end = "1"; break; case 2: end = "2"; break; } ▷ 기본적으로 switch 문은 모든 case를 다 돌기 때문에, 그럴 필요 없으면 case마다 break; 작성 2022. 5. 21.
[C++ 기초] c++ 프로그램 구성, namespace 1. c++ 프로그램의 구성 #include int main() { std::cout 2022. 5. 20.
퀵 정렬 (Quick Sort) 1. 퀵 정렬 ▶ 분할정복 알고리즘 input 배열을 반복적으로 분할해서 계산하는 알고리즘이며, 평균 시간복잡도가 O(N*logN) 특정한 값 a을 기준으로 a보다 큰 수, a보다 작은 수를 나누자 ! ※ 특정한 값 a = pivot ※ 일반적으로 첫번째 원소를 pivot 값으로 설정한다. 2. 퀵 정렬 예제 ex ) 3 7 8 1 5 9 6 10 2 4 오름차순 정리하시오. #include int number = 10; int data[10] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 }; void show() { for (int i = 0; i < number; i++) { printf("%d ", data[i]); } } void quickSort(int* a, int start,.. 2022. 5. 9.
삽입 정렬 (Insertion Sort) 1. 삽입 정렬 각 숫자를 적절한 위치에 삽입하자 ! ※ 한번 수행할 때마다 [앞] 정렬된 부분의 원소 수가 1개 증가, [뒤] 정렬 안된 부분의 원소 수는 1개 감소됨 반복해서 수행하면 결국 [뒤] 정렬 안된 부분에는 아무 원소도 남지 않고 모두 정렬됨 ※ 선택/버블 vs. 삽입 ▶ 선택, 버블: 이미 알맞게 정렬되어 있더라도 차례가 되면 정렬당함 (위치 바꾸는 과정 거침) : 비효율적 ▶ 삽입: 필요할때만 위치를 바꿈 : 효율적 이번 주자 앞에 있는 애들은 다 이미 알맞은 위치에 정렬되어 있는 상태이므로 다시 정렬할 필요 없음 2. 삽입 정렬 예제 ex ) 1 10 5 8 7 6 4 3 2 9 오름차순 정리하시오. #include int main(void) { int a[] = { 1, 10, 5, .. 2022. 5. 6.

티스토리툴바