2018/05/10 삼성 SDS Expert 대비 교육 모범답안

muse 2년, 8개월 전

랜덤 소트


#include<stdio.h>

int N;
int A[10];
double e[50000];

void init(){
// Get inputs
int i, fac = 1;
scanf("%d", &N);
for(i=0;i<N;i++){
scanf("%d", &A[i]);
fac *= (i+1);
}
for(i=0;i<fac;i++) e[i] = -1;
e[0] = 0;
}

int hash_seq(int *A){
// index of sequence A
int i, j, lower_count, cnt = 0, fac = 1;
for(i=2;i<N;i++) fac *= i;
for(i=0;i<N;i++){
lower_count = A[i] - 1;
for(j=0;j<i;j++){
if(A[j] < A[i]) lower_count--;
}
cnt += lower_count * fac;
if(i < N-1) fac /= (N-i-1);
}
return cnt;
}

double dfs(){
int i, j, hs = hash_seq(A);
// Not visited yet
if(e[hs] < 0){
int count = 0;
e[hs] = 0;
for(i=0;i<N-1;i++){
for(j=i+1;j<N;j++){
if(A[i] > A[j]){
int t;
t = A[i]; A[i] = A[j]; A[j] = t;
e[hs] += dfs() + 1;
t = A[i]; A[i] = A[j]; A[j] = t;
count++;
}
}
}
if(count > 0) e[hs] /= count;
}
return e[hs];
}

int main(){
init();
printf("%.8lf\n", dfs());
return 0;
}

muse 2년, 8개월 전

Trie 예시


#include<cstdio>
#include<cstdlib>
#include<cstring>

struct NodeTrie{
int count;
NodeTrie *chld[26];
};

NodeTrie* getNodeTrie(){
NodeTrie *p = (NodeTrie *)malloc(sizeof(NodeTrie));
p->count = 0;
for(int i=0; i<26; i++) p->chld[i] = NULL;
return p;
}

void addTrie(NodeTrie *p, char *s){
int l = strlen(s);
int i, c;
for(i=0;i<l;i++){
c = s[i] - 'a';
if(p->chld[c] == NULL){
p->chld[c] = getNodeTrie();
}
p = p->chld[c];
}
(p->count)++;
}

int countTrie(NodeTrie *p, char *s){
int l = strlen(s);
int i, c;
for(i=0;i<l;i++){
c = s[i] - 'a';
if(p->chld[c] == NULL){
return 0;
}
p = p->chld[c];
}
return p->count;
}

void clearTrie(NodeTrie *p){
if(p == NULL){
return;
}
int i;
for(i=0;i<26;i++){
clearTrie(p->chld[i]);
}
free(p);
}

int main(){
NodeTrie *root = getNodeTrie();
addTrie(root, "ab");
addTrie(root, "abc");
addTrie(root, "ab");
addTrie(root, "abcd");
addTrie(root, "bac");
printf("%d\n", countTrie(root, "ab"));
printf("%d\n", countTrie(root, "a"));
printf("%d\n", countTrie(root, "bac"));
printf("%d\n", countTrie(root, "ba"));
printf("%d\n", countTrie(root, "abcd"));
clearTrie(root);
return 0;
}

muse 2년, 8개월 전

Trie malloc 없이


#include<cstdio>
#include<cstring>

struct NodeTrie{
int count;
NodeTrie *chld[26];
NodeTrie(){
count = 0;
for(int i=0;i<26;i++) chld[i] = NULL;
}
};

void addTrie(NodeTrie *p, char *s){
int l = strlen(s);
int i, c;
for(i=0;i<l;i++){
c = s[i] - 'a';
if(p->chld[c] == NULL){
p->chld[c] = new NodeTrie();
}
p = p->chld[c];
}
(p->count)++;
}

int countTrie(NodeTrie *p, char *s){
int l = strlen(s);
int i, c;
for(i=0;i<l;i++){
c = s[i] - 'a';
if(p->chld[c] == NULL){
return 0;
}
p = p->chld[c];
}
return p->count;
}

void clearTrie(NodeTrie *p){
if(p == NULL){
return;
}
int i;
for(i=0;i<26;i++){
clearTrie(p->chld[i]);
}
delete p;
}

int main(){
NodeTrie *root = new NodeTrie();
addTrie(root, "ab");
addTrie(root, "abc");
addTrie(root, "ab");
addTrie(root, "abcd");
addTrie(root, "bac");
printf("%d\n", countTrie(root, "ab"));
printf("%d\n", countTrie(root, "a"));
printf("%d\n", countTrie(root, "bac"));
printf("%d\n", countTrie(root, "ba"));
printf("%d\n", countTrie(root, "abcd"));
clearTrie(root);
return 0;
}
댓글 쓰기