Quick sort 특징
시간 복잡도에 따라서 o(nlogn)의 빠른 속도이지만, 데이터 값에 따라 O(n^2)나올 수 있다.
특정 범위에서 (start ~ end) 가장 왼쪽에 있는 숫자를 pivot으로 배치한다.
여러번의 swap 작업을 통해 pivot 의 위치를 결정하고, \
pivot 왼쪽에는 pivot보다 작은숫자를
pivot 오른쪽에는 pivot 보다 큰 숫자를 배치한다.
이 작업이 한번 끝나면 pivot의 4의 위치가 결정된다.
이번에는 구간을 나누어서 같은 작업을 진행하면 된다.
가장 작은 구간이 될때까지 재귀호출을 통해서 반복하여 위작업을 실행해준다.
세부과정
start = 0/ end 7 일때 가장 왼쪽을 pivot으로 둔다.
변수 a를 start + 1, 변수 b를 end로 설정해준다.
a++ 하면서 pivot보다 큰숫자를 찾는다.
b— 하면서 pivot보다 작은숫자를 찾는다.
찾았으면 swap하여 바꿔주고, 이과정을 a와 b가 엇갈리기 전까지 반복해준다.
엇갈렸으면 마무리 단계로 pivot과 b를 swap하면 된다.
이제 pivot왼쪽에는 전부 pivot보다 작은숫자들이 배되고, 오른쪽에는 큰 숫자들이 배치되게 된다.
0~7번 구간 까지 이 과정을 끝냈고, 이제 재귀호출을 통해 pivot 왼쪽 구간 (0~2), pivot 오른쪽 구간(4~7)에 대해서 이 과정을 또 수행시켜주면 된다.
#include <iostream>
int vect[10] = { 4,3,9,8,5,7,1,2 };
int n = 8;
void quicksort(int start, int end)
{
if (start >= end)
return;
int pivot = start;
int a = start + 1;
int b = end;
while (true)
{
while (a <= end && vect[a] <= vect[pivot])
a++;
while (b >= start && vect[b] > vect[pivot])
b--;
if (a > b)
break;
std::swap(vect[a], vect[b]);
}
std::swap(vect[pivot], vect[b]);
quicksort(start, b - 1);
quicksort(b + 1, end);
}
char main()
{
quicksort(0, n - 1);
return 0;
}
Python
복사
#include <iostream>
int vect[10] = { 4,3,9,8,5,7,1,2 };
int n = 8;
void quicksort(int left, int right)
{
int i = left, j = right;
int pivot = vect[(left + right) / 2];
/* partition */
while (i <= j)
{
while (vect[i] < pivot)
i++;
while (vect[j] > pivot)
j--;
if (i <= j)
std::swap(vect[i++], vect[j--]);
};
/* recursion */
if (left < j)
quicksort(left, j);
if (i < right)
quicksort(i, right);
}
char main()
{
quicksort(0, n - 1);
return 0;
}
Python
복사
숙제
문제 1번
한 문자열을 입력 받아주세요.
입력받은 문자열에서 대소문자 구분없이 'A' ~ 'F' 문자들이 각각 몇 개 존재하는지
STL unordered_map을 이용해서 출력 해 주세요.
[힌트]
1.
Header : #include <unordered_map>
2.
선언 : unordered_map<char, int> dic;
3.
사용 : dic['A']++;
4.
노드 존재 여부 확인 : if (dic.count('A') > 0)
입력 예제
FFFCFFFABCabc
출력 결과
A:2
B:2
C:3
D:0
E:0
F:6
문제 2번
VIP 분들을 모임에 참석하였습니다. N명의 이름과 나이를 입력 받아주세요.
그런데 동명이인을 가진, 초대받지 못한 SPY가 한 사람이 있습니다.
SPY가 사용한 이름을 출력하고,
SPY로 의심되는 두 명의 나이를 어린 사람부터 출력 해 주세요.
입력 예제
7
Jason 32
Tom 22
Pom 26
Samson 46
Tim 26
Bam 51
Tom 43
출력 결과
Tom
22 43
문제 3번
먼저 다섯명의 팀원 명단을 빠르게 검색할 수 있도록 세팅을 해주세요.
아래 세 가지를 구현을 해두고, Chaining에 세팅을 해 주세요.
1.
Honor's Method Hash Function
2.
Memory Pool을 이용한 Linked List
3.
Chaining
POP | TOM | MC | JASON | KFC |
이제 팀원이 맞는지 확인 해 달라는 N개의 요청에 대해 yes 또는 no로 응답을 해주면 됩니다.
Hash 자료구조를 이용해서 빠른 응답을 해 주세요.
(STL을 쓰지말고 풀어주세요.)
[힌트]
hash function에서 hash code값이 overflow로 인해 음수가 되지 않도록,
unsigned int로 hash code값을 구해주세요.
입력 예제
6
POP
TOM
MINCODING
MP
BBQ
KFC
출력 결과
yes
yes
no
no
no
yes
문제 4번
먼저 다섯명의 팀원 명단을 빠르게 검색할 수 있도록 세팅을 해주세요.
STL의 unordered_map을 이용하여 세팅을 하면 됩니다.
POP | TOM | MC | JASON | KFC |
이제 팀원이 맞는지 확인 해 달라는 N개의 요청에 대해 yes 또는 no로 응답을 해주면 됩니다.
Hash 자료구조를 이용해서 빠른 응답을 해 주세요.
[힌트]
string type을 key로,
int type을 value로 설정하면 됩니다.
입력 예제
6
POP
TOM
MINCODING
MP
BBQ
KFC
출력 결과
yes
yes
no
no
no
yes
문제 5번
아래 문자열을 하드코딩 해 주세요.
BOBOOBOBOBOBBM
이제 세 글자로 구성된 n개의 단어를 입력받아주세요.
입력받은 단어들이 위 문자열에 몇 개가 존재하는지 각각 출력 해 주세요.
[힌트]
입력받기 전, 미리 세 글자 단위로 Hash에 모두 Counting을 해 놓으면
빠르게 검색할 수 있습니다.
입력 예제
3
BOB
OOB
BBM
출력 결과
4
1
1
문제 6번
아래 (6 x 6) 2차배열을 하드코딩 해 주세요.
A | B | A | B | A | B |
C | D | C | D | C | D |
A | G | G | F | H | A |
B | B | F | A | B | C |
D | D | C | C | D | D |
F | F | D | H | A | S |
이제 (2 x 2) 의 패턴을 입력 받습니다.
이 패턴이 총 몇개가 있는지 Hash를 이용해서 출력 해 주세요.
입력 예제
A B
C D
출력 결과
4
문제 7번
5 x 5 사이즈의 모스부호가 전달되었습니다.
이 중, 다음과 같은 모스부호 중 하나라도 존재하는지 확인하여
yes 또는 no로 출력 해 주세요.
긴급신호 모스부호 List
1011
0011
1111
0000
1100
입력 예제
10101
11101
01010
11010
11010
출력 결과
no
문제 8번
알렉산드로 집안에서 딸 아이가 태어났습니다.
유명한 작명소에서 딸 아이의 이름을 잘 짓는 노하우를 배우게 되었습니다.
좋은 이름의 조건은 다음과 같습니다.
1.
소문자만 사용할 것.
2.
특수문자 사용금지.
3.
같은 알파벳이 2개 이하로만 사용할 것.
4.
모음 (A E I O U) 알파벳은 총 3개만 사용할 것.
알렉산드로가 지은 n개의 이름을 입력받고,
좋은이름인지 아닌지 good 또는 no를 출력 해 주세요.
입력 예제
3
kfcbbqioi
mincoding
samham_t
출력 결과
good
good
no
문제 1번
O(n + k) 속도를 보이는 Counting Sort를 구현하고자 합니다.
n개의 숫자를 입력받고, 그 과정을 출력 해 주세요.
Counting Sort 과정 1 : DAT 처리
Counting Sort 과정 2 : 누적합 구하기 ( [0] ~ [9] index 까지 총 10개 누적값만 출력 해 주세요. )
Counting Sort 과정 3 : 정렬하기 ( 정렬 결과를 출력 해 주세요. )
정렬하는 과정에서 만들어지는 누적값과 정렬값을 출력 해 주세요.
[세부 조건]
1.
정렬할 숫자의 최소 값 : 1
2.
정렬할 숫자의 최대 값 : 20
3.
1 <= n <= 10
입력 예제
5
5 2 2 1 2
출력 결과
0144455555
12225
문제 2번
현덕이는 영어공부를 위해 단어들만 모아서 암기장을 만들어 보려고 합니다.
_(언더바)를 제외한 모든 단어들을 배열에 저장하고자 합니다.
각 칸에 ' _ '를 기준으로 단어들을 string 배열에 parsing 해주세요.
[힌트]
string class의 메서드
string str = "ABC123";
1) int index = str.find("C1",1); // C1 글자를 1번 index부터 찾는다.
2) str.erase(1, 3); //1번 index부터 세 글자 지운다.
3) str.insert(1, "ABC"); // 1번 index에 ABC 글자 추가
4) string v = str.substr(3, 2); //3번 index부터 두 글자를 v에 저장
5) string v = to_string(351613); // 숫자 351613을 문자열로 만든다.
입력 예제
HOT_FRIED____CHICKEN_KFC_IS_BEST
출력 결과
1#HOT
2#FRIED
3#CHICKEN
4#KFC
5#IS
6#BEST
문제 3번
총 다섯 문장을 String 1차원 배열(string input[5])에 입력 받아주세요.
다섯 문장 속에 "MCD" 라는 단어가 총 몇개 있는지
string Class의 find 메서드를 이용하여 구해주세요.
입력 예제
SVCMCDMCD
CCCMCCD
MCDDT
MCDDDC
MMMMM
출력 결과
4
문제 4번
2000년도 채팅 열풍으로 이모티콘을 과도하게 쓰던 시대가 있었습니다.
유행이 지났지만 아직도 과도한 이모티콘을 이상하게 쓰는 사람들이 있습니다.
이를 제거&정리 해주는 프로그램을 작성해주세요.
1) (((( or )) 같은 너무 많은 괄호는 1개로 정리 => ( or )
2) 웃는 눈이(^^) 2개가 아니라 3개인 경우(^^^) 2개로 정리 => (^^)
3) 눈과 눈사이 한 글자가 _가 아닌것들이 있다면 모두 _로 정리 ^0^ => ^_^
[예시]
^^^^^^)))))) => ^^)
((((((^@^))((^#^)))) => (^_^)(^_^)
((^(_)^)) => (^(_)^)
입력 예제
(((((^0^))((^^^)))(^_^)))))
출력 결과
(^_^)(^^)(^_^)
문제 5번
독재자 알프레도는 국민들에게 금지어를 발표했습니다.
그의 정책에 맞게 단어를 수정해주는 프로그램을 작성해주세요.
입력 예제
ILOVEKFCANDMC!!
출력 결과
ILOVE#BBQ#AND#BBQ#!!
문제 6번
단어와 숫자들이 번갈아가며 적혀있는 한문장을 입력 받습니다. ex) AB154CDEF112F4G5
죄수명(단어)과 사건번호(숫자)가 한세트로 되어있지만, 띄어쓰기가 없기에 알아보기 힘듭니다.
죄수명과 사건번호를 각각 Parsing하고 사건번호에 17을 더한 값으로 출력 해주세요.
입력 예제
AB100CDEF112F4G5
출력 결과
AB#117
CDEF#129
F#21
G#22
문제 7번
뉴스 기사에서 웹사이트 URL만 추출하려고 합니다.
띄어쓰기가 없는 한줄의 기사를 입력받고, 다음 조건에 맞는 URL은 총 몇개인지 출력 해 주세요.
URL 조건
1.
대소문자 구분은 없습니다.
2.
시작단어는 "http://" 또는 "https://" 입니다.
3.
끝 단어는 ".com" 또는 ".co.kr" 또는 ".org" 또는 ".net" 입니다.
4.
시작단어와 끝 단어 사이에는 최소 3글자 이상 있어야 합니다.
입력 예제
ABHttp://bbq.comhttps://a.co.krBBQhttpS://KFC.org
출력 결과
2개
문제 8번
시스템에 입력되는 값이, 시스템 설계 상 허용되는 값인지 아닌지 확인하는 작업을 "유효성 검사"라고 합니다.
인공지능 AI 프로그램 세나는, 자신이 마음에 드는 문장만 인식합니다.
세나가 인식할 수 있는 문장인지 아닌지, 유효성 검사를 해주는 프로그램을 작성해야합니다.
띄어쓰기가 없는 한 문장이 입력됩니다.
다음 조건에 모두 허용이 된다면 pass, 하나라도 허용이 안된다면 fail을 출력 해 주세요.
[세나가 원하는 문자열 조건]
1.
"bad", "no", "puck" 부정적인 단어가 없어야 함
2.
연속적인 언더바 "_"가 총 5개 이하
3.
모든 알파벳이 5회 이하 쓰여야 함 (대소문자를 구분 함)
4.
숫자가 없어야 함
입력 예제
____bck____a_c_k_
출력 결과
pass
문제 9번
두 문자열을 입력받고, 가장 긴 같은 문자열을 찾으려고 합니다.
예를들어 ABCDEF와 OOBCDEOOAB에서 가장 긴 공통 문자열은 "BCDE" 입니다.
예를들어 QQQABQQQ 와 ABQQTT 에서 가장 긴 공통 문자열은 "ABQQ" 입니다.
string class의 find 메서드와 substr을 활용하여 가장 공통 문자열을 출력 해 주세요.
[힌트]
두 문자열 중 긴 문장을 A 문자열로두고, 짦은 문자열을 B 문자열로 둡니다.
먼저 B문자열 전체로 A 문자열에서 검색 해보고,
B문자열 일부로 A 문자열에서 검색을 시도해보면 됩니다.
B문자열을 한글자씩 줄여서 검색해 보다가, 발견되면 정답을 출력하면 됩니다.
입력 예제
ABCDEF
OOBCDEOOAB
출력 결과
BCDE
