행복의 주문, 디리릿!!

#라이브러리 없이 코딩하기

구현 알고리즘

• Merge Sort

• Quick Sort

다음번에 시도해 보기

• 퀵소트로 구현하면 시간을 더 단축시킬 수 있는 문제인 것 같으니 도전해보기 (머지소트 실행시간 : 80ms)

+ 퀵소트는 시간을 단축시키지는 않았지만, 머지소트에 사용되는 포인터 어레이 만큼의 메모리 사용량을 줄일 수 있었다.

(아래 : merge sort, 위 : quick sort)

소스 코드 (merge sort)

#include <stdio.h>

#define MAX_NODE 100001

struct Node {
	char name[11];
	int korean, english, math;
} nodes[MAX_NODE], *nt[MAX_NODE], *tmp[MAX_NODE];

void mstrcpy(char* dst, const char* src) {
	while(*src) {
		*dst++ = *src++;
	}
	*dst = '\0';
}
int mstrcmp(const char* a, const char* b) {
	while (*a && *a == *b) {
		++a; ++b;
	}
	return *b - *a;
}

int cmpScore(Node *n1, Node *n2) {

	if (n1->korean != n2->korean)
		return n1->korean - n2->korean;
	if (n1->english != n2->english)
		return n2->english - n1->english;
	if (n1->math != n2->math)
		return n1->math - n2->math;
	return mstrcmp(n1->name, n2->name);
}

void mergeSort(int start, int end) {

	if (start < end) {
		int mid = (start + end) / 2;
		mergeSort(start, mid);
		mergeSort(mid + 1, end);

		int s1 = start;
		int s2 = mid + 1;
		int idx = start;
		while (s1 <= mid && s2 <= end) {
			if (cmpScore(nt[s1], nt[s2]) > 0)
				tmp[idx++] = nt[s1++];
			else
				tmp[idx++] = nt[s2++];
		}
		while (s1 <= mid) tmp[idx++] = nt[s1++];
		while (s2 <= end) tmp[idx++] = nt[s2++];

		for (int i = start; i <= end; i++)
			nt[i] = tmp[i];
	}
}

int main() {
	int n;
	scanf("%d", &n);

	char name[11];
	int a, b, c;
	for (int i = 0; i < n; i++) {
		scanf("%s %d %d %d", name, &a, &b, &c);

		Node* newN = &nodes[i];
		mstrcpy(newN->name, name);
		newN->korean = a;
		newN->english = b;
		newN->math = c;

		nt[i] = newN;
	}

	mergeSort(0, n-1);

	for (int i = 0; i < n; i++) {
		printf("%s\n", nt[i]->name);
	}
}

소스코드 (quick sort)

#include <stdio.h>

#define MAX_NODE 100001

struct Node {
	char name[11];
	int korean, english, math;
} nodes[MAX_NODE], * nt[MAX_NODE];

void mstrcpy(char* dst, const char* src) {
	while(*src) {
		*dst++ = *src++;
	}
	*dst = '\0';
}
int mstrcmp(const char* a, const char* b) {
	while (*a && *a == *b) {
		++a; ++b;
	}
	return *b - *a;
}

int cmpScore(Node *n1, Node *n2) {

	if (n1->korean != n2->korean)
		return n1->korean - n2->korean;
	if (n1->english != n2->english)
		return n2->english - n1->english;
	if (n1->math != n2->math)
		return n1->math - n2->math;
	return mstrcmp(n1->name, n2->name);
}

void quickSort(int start, int end) {
	if (start >= end) return;

	int pivot = start;
	int i = pivot + 1;
	int j = end;
	Node* tmp;

	while (i <= j) {
		while (i <= end && cmpScore(nt[i], nt[pivot]) > 0)
			i++;
		while (j > start && cmpScore(nt[j], nt[pivot]) < 0)
			j--;
		
		if (i > j) {
			tmp = nt[j];
			nt[j] = nt[pivot];
			nt[pivot] = tmp;
		}
		else {
			tmp = nt[i];
			nt[i] = nt[j];
			nt[j] = tmp;
		}

	}

	quickSort(start, j - 1);
	quickSort(j + 1, end);
}

int main() {
	int n;
	scanf("%d", &n);

	char name[11];
	int a, b, c;
	for (int i = 0; i < n; i++) {
		scanf("%s %d %d %d", name, &a, &b, &c);

		Node* newN = &nodes[i];
		mstrcpy(newN->name, name);
		newN->korean = a;
		newN->english = b;
		newN->math = c;

		nt[i] = newN;
	}

	//mergeSort(0, n-1);
	quickSort(0, n - 1);

	for (int i = 0; i < n; i++) {
		printf("%s\n", nt[i]->name);
	}
}

#라이브러리 없이 코딩하기

구현 알고리즘

• Hash

• Merge Sort

소스 코드

#include <stdio.h>
#define MAX_TABLE 500017
struct Hash {
    char name[21];
    Hash* next;
} h[MAX_TABLE], * ht[MAX_TABLE], * target[MAX_TABLE];
int h_idx = 0, t_idx = 0;

unsigned long getHash(const char* str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
    {
        hash = (((hash << 5) + hash) + c);
    }

    return hash;
}

int mstrcmp(const char* a, const char* b) {
    while (*a && *a == *b) {
        ++a; ++b;
    }
    return *a - *b;
}
void mstrcpy(char* dst, const char* src) {
    while (*src)
        *dst++ = *src++;
    *dst = '\0';
}

void mergeSort(int start, int end) {
    if (start < end) {
        int mid = (start + end) / 2;
        mergeSort(start, mid);
        mergeSort(mid + 1, end);

        int s1 = start;
        int s2 = mid + 1;
        int idx = start;
        while (s1 <= mid && s2 <= end) {
            if (mstrcmp(target[s1]->name, target[s2]->name) <= 0) {
                ht[idx++] = target[s1++];
            }
            else {
                ht[idx++] = target[s2++];
            }
        }
        while (s1 <= mid) ht[idx++] = target[s1++];
        while (s2 <= end) ht[idx++] = target[s2++];

        for (int i = start; i <= end; i++)
            target[i] = ht[i];
    }
}

int main() {
    int n, m;

    scanf("%d %d", &n, &m);

    char name[21];
    for (int i = 0; i < n; i++) {
        scanf("%s", name);

        unsigned long key = getHash(name) % MAX_TABLE;

        Hash* newH = &h[h_idx++];
        mstrcpy(newH->name, name);

        newH->next = ht[key];
        ht[key] = newH;
    }

    for (int i = 0; i < m; i++) {
        scanf("%s", name);

        unsigned long key = getHash(name) % MAX_TABLE;
        for (Hash* cur = ht[key]; cur != 0; cur = cur->next) {
            if (mstrcmp(cur->name, name) == 0) {
                target[t_idx++] = cur;
                break;
            }
        }
    }

    mergeSort(0, t_idx - 1);

    printf("%d\n", t_idx);
    for (int i = 0; i < t_idx; i++) {
        printf("%s\n", target[i]->name);
    }
}

은 바로 다음 주 미래의 나

#라이브러리 없이 코딩하기

구현 알고리즘

• Hash

• Merge Sort

생각해 볼 거리

• Quick Sort로 구현해보기

소스 코드

#include <stdio.h>

#define MAX_TABLE 1000017

struct Hash {
    char name[6];
    bool in;
    Hash* next;
} h[MAX_TABLE], * ht[MAX_TABLE], * workin[MAX_TABLE];
unsigned int h_idx = 0;

unsigned long getHash(const char* str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
    {
        hash = (((hash << 5) + hash) + c);
    }

    return hash;
}

int mstrcmp(const char* a, const char* b) {
    while (*a && *a == *b) {
        ++a; ++b;
    }
    return *a - *b;
}
void mstrcpy(char* dst, const char* src) {
    while (*src)
        *dst++ = *src++;
    *dst = '\0';
}

void mergeSort(int start, int end) {
    if (start < end) {
        int mid = (start + end) / 2;
        mergeSort(start, mid);
        mergeSort(mid + 1, end);

        int s1 = start;
        int s2 = mid + 1;
        int idx = start;
        while (s1 <= mid && s2 <= end) {
            if (mstrcmp(workin[s1]->name, workin[s2]->name) >= 0) {
                ht[idx++] = workin[s1++];
            }
            else {
                ht[idx++] = workin[s2++];
            }
        }
        while (s1 <= mid) ht[idx++] = workin[s1++];
        while (s2 <= end) ht[idx++] = workin[s2++];

        for (int i = start; i <= end; i++)
            workin[i] = ht[i];
    }
}

int main() {
    int n; // >=2, <=1,000,000

    scanf("%d", &n);

    char name[6], state[6];
    for (int i = 0; i < n; i++) {
        scanf("%s %s", name, state);

        unsigned long key = getHash(name) % MAX_TABLE;

        if (state[0] == 'e') {
            bool exists = false;
            for (Hash* cur = ht[key]; cur != 0; cur = cur->next) {
                if (mstrcmp(cur->name, name) == 0) {
                    exists = cur->in = true;
                }
            }

            if (!exists) {
                Hash* newH = &h[h_idx++];
                newH->in = true;
                mstrcpy(newH->name, name);

                newH->next = ht[key];
                ht[key] = newH;
            }
        }
        else {
            for (Hash* cur = ht[key]; cur != 0; cur = cur->next) {
                if (mstrcmp(cur->name, name) == 0) {
                    cur->in = false;
                }
            }
        }
    }

    // sort
    int w_idx = 0;
    for (int i = 0; i < h_idx; i++) {
        if (h[i].in)
            workin[w_idx++] = &h[i];
    }
    mergeSort(0, w_idx - 1);

    // result
    for (int i = 0; i < w_idx; i++) {
        printf("%s\n", workin[i]->name);
    }
    
    return 0;
}

! quickSort 사용해서 나중에 다시 구현해보기. 시간 초과가 난다. 다시 공부해보도록 하자.

void swap(Hash *arr[MAX_TABLE], int a, int b) {
    Hash* tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
}

int partition(Hash *arr[MAX_TABLE], int left, int right) {
    int low = left + 1;
    int high = right;

    while (low <= high) {
        while (low <= right && mstrcmp(arr[left]->name, arr[low]->name) <= 0) {
            //피벗보다 큰 값 찾기
            low++;
        }
        while (high >= left + 1 && mstrcmp(arr[left]->name, arr[high]->name) > 0) {
            high--;
        }
        if (low <= high)
            swap(arr, low, high);
    }
    swap(arr, left, high);
    return high;
}

void quickSort(Hash *unsorted[MAX_TABLE], int left, int right) {
    if (left < right) {
        int pivot = partition(unsorted, left, right);
        quickSort(unsorted, left, pivot-1);
        quickSort(unsorted, pivot + 1, right);
    }
}

#라이브러리 없이 코딩하기

#이지만 atoi는 직접 구현하니 시간초과라

#라이브러리 사용

구현 알고리즘

• Hash

생각해 볼 거리

• 이중 for loop 안에서 break를 사용하면 왜 실행 시간이  8ms 늘어날까?

• 시간 초과 나지 않도록 atoi 직접 구현해보기

소스 코드

#include <stdio.h>
#include <stdlib.h>

#define MAX_TABLE 100017
#define MAX_NAME 21

struct Hash {
    char name[MAX_NAME];
    Hash* next;
    unsigned long int idx;
} h[MAX_TABLE], * ht[MAX_TABLE];
unsigned int h_idx = 1;

unsigned long getHash(const char* str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
    {
        hash = (((hash << 5) + hash) + c);
    }

    return hash;
}

void mstrcpy(char* dst, const char* src) {
    while (*src)
        *dst++ = *src++;
    *dst = '\0';
}

int mstrcmp(const char* a, const char* b) {
    while (*a && *a == *b) {
        ++a; ++b;
    }
    return *a - *b;
}

int main() {

    int m, n; // >=1 , <= 100,000
    scanf("%d %d", &m, &n);

    char name[MAX_NAME];
    for (int i = 1; i <= m; i++) {
        scanf("%s", name);

        unsigned long key = getHash(name) % MAX_TABLE;

        Hash* newH = &h[h_idx++];
        newH->idx = i;
        mstrcpy(newH->name, name);

        newH->next = ht[key];
        ht[key] = newH;
    }

    for (int i = 0; i < n; i++) {
        scanf("%s", name);

        if ('0' <= name[0] && name[0] <= '9') {
            printf("%s\n", h[atoi(name)].name);
        }
        else {
            unsigned long key = getHash(name) % MAX_TABLE;

            for (Hash* cur = ht[key]; cur != 0; cur = cur->next) {
                if (!mstrcmp(cur->name, name)) {
                    printf("%d\n", cur->idx);
                }
            }
        }
    }
}

얼마 전에 오랜만에 코딩 시험을 치루며, 구글링 없이 문법조차 다 까먹어 C언어로 제대로 코딩할 수 없던 날 발견했다. Java로 풀어볼까도 했지만, 라이브러리 없이 코딩을 해나가야하는 것도 자신이 없어 시험 시작 1시간 후, 시험을 중도 종료를 하였다. 그래서 이번에 다시 코딩 공부를 시작하며, 8년전 학부 1학년 때 살짝 배웠던 Python을 내 두번째 메인 개발 언어로 만들어 보고자 한다. 

오랜만에 코딩공부를 시작하며 LeetCode에 가입하고, 첫 날이니 Easy 에서도 제일 첫번째에 있던 #1 Two Sum을 골라보았다.

Solution

// JAVA
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap();
        
        for(int i=0 ; i < nums.length ; i++)
            map.put(nums[i], i);
        
        for(int i=0 ; i < nums.length ; i++)
            if(map.containsKey(target-nums[i]) && i != map.get(target - nums[i]))
                return new int[] {i, map.get(target-nums[i])};
        
        return new int[2];
    }
}

Python Dictionaries(딕셔너리)는 Java에서 HashMap과 같은 기능을 하며 key:value 형식으로 값을 저장한다. 
선언을 할 때에는 보통은 parameterName = {} 를 사용하고 parameterName = dict()로도 생성가능하다.
(List 생성은 =[], =list())

// Python
class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        complement_dict = {} // 딕셔너리 생성
        nums_len = len(nums)
        for i in range(nums_len):
            complement = target - nums[i]
            if complement in complement_dict:
                return [complement_dict[complement], i]
            else:
                if nums[i] in complement_dict:
                    continue
                complement_dict[nums[i]] = i

[참고]

leetcode.com/problems/two-sum/

dojang.io/mod/page/view.php?id=2213