롱롱의 일기장
0%

작성일 Disqus:

벌써 5월이 끝나가고 있다. 작년 8월 대학교를 졸업한 후 개발 공부를 시작했으니 약 10개월 정도가 지났는데 새삼 느끼는 것이지만 시간 참 빠르다😱

지난 10개월간 열심히 했는지를 스스로 물어본다면 ‘물론 열심히 했지!’라고 답할 테지만 정말 그게 최선이었냐고 물어본다면 당장 올해 2~3월도 그렇고 중간중간 분명히 나태하게 보낸 시간이 있었기에 아니라고 답해야 할 것 같다. 시간이 정말 소중한데 그 시간을 낭비한 적이 있다는 게 너무 아쉽다. 특히 본격적으로 취준생활을 시작한 요새 아쉬움을 더 느끼는 중이다.

이번 주부터 커리어 코칭을 통해 피드백 받은 이력서, 포트폴리오를 가지고 본격적으로 구직활동을 시작했다. 주로 원티드 플랫폼을 활용해 여러 회사에 지원하고 있는데… 참 요새 ‘시장 상황이 좋지 않다, 개발자 취업난이다’라고 왜 얘기하는지 체감하고 있다. 50개의 기업에 지원했는데 (물론 아직 이력서를 열람하지 않은 회사도 있지만) 알림을 받을 때마다 불합격을 받으니 자존감이 깎여나간다. 이미 다른 지원자가 구해져서 일수도 있지만 서류 열람 1분 만에 불합격을 주는 회사도 있고.. 정확한 이유를 알 수 없으니 내가 많이 부족한가? 비전공자라 그런가? 자책하게 된다.

그래도 합격률이 10%도 안되기는 하지만 서류가 통과되어 면접 일정을 잡는 회사도 하나 둘 생기고 있다. 면접을 잘하는 것은 별개의 이야기니 만큼 열심히 준비해 봐야지! 사실 어쨌든 단 하나의 회사라도 합격하면 그만인거니까😀

작성일 Edited on Disqus:

😂 들어가며

기술면접을 대비하기 위해 공부를 하던중, 정렬 알고리즘에 관한 질문이 있었는데 쉽게 답변하지 못했다. 분명 코딩테스트 준비를 하면서 여러가지 정렬 알고리즘에 대해 살펴보고 구현해보았었는데 기록으로 남겨두지 않으니 휘발된 것 같다. 이번 기회에 기본적인 정렬 알고리즘들에 대해 정리해보고자 한다.

정렬 알고리즘?

먼저 정렬 알고리즘이란 목록 안에 저장된 요소들을 특정한 순서대로 재배치하는 알고리즘을 뜻한다.
효율적인 정렬을 위해 정렬 알고리즘이 필요하다고 할 수 있다.
정렬시 고려할 사항으로는 시간 복잡도, 메모리 사용량, 안정성(safety가 아니라 stable -> 데이터의 순서가 바뀌지 않느냐 여부 문제) 등이 있다.

모든경우에 대해 최선의 정답을 내는 알고리즘은 없으므로 정렬 알고리즘의 특성에 대해 잘 알아두고 적절한 상황에 맞는 알고리즘을 택해야한다.

기초적인 정렬 알고리즘 5개에 대해 살펴보자.

버블 정렬(Bubble Sort)

버블정렬은 서로 인접해 있는 요소 간의 대소 비교를 통해 정렬한다.
버블 정렬은 정렬 알고리즘 중 가장 단순한 알고리즘으로, 단순한 만큼 비효율적이다.
시간 복잡도가 최고, 평균, 최악 모두O(n^2)이며 공간복잡도는 하나의 배열만 사용하므로 O(n)이다.
동작 방식은 인접한 두 요소간의 대소 비교를 진행한다.

Bubble Sort

이를 코드로 구현하면 다음과 같다.

배열의 요소 개수만큼 반복하면서, 각 반복시 인접 요소를 비교해 바꾸어주는것이다. 반복시마다 가장 큰 요소는 마지막에 위치하게 되므로 제외하면서 반복한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const swap = (arr, i, j) => {
	[arr[i], arr[j]] = [arr[j], arr[i]];
};

const bubbleSort = (arr) => {
	const sortedArr = [...arr];
	const len = sortedArr.length;

	for (let i = 0; i < len; i++) {
		for (let j = 0; j < len - i - 1; j++) {
			if (sortedArr[j] > sortedArr[j + 1]) swap(sortedArr, j, j + 1);
		}
	}

	return sortedArr;
};

삽입 정렬(Insertion Sort)

삽입 정렬이란 정렬을 진행할 원소의 index보다 낮은 곳에 있는 원소들을 탐색하며 알맞은 위치에 삽입해주는 정렬 알고리즘이다.
알고리즘이 동작하는 동안 계속해서 정렬이 진행되므로 반드시 맨 왼쪽 index까지 탐색하지 않아도 된다는 장점이 있다.
모두 정렬되어 있는 Optimal한 경우 모든 원소가 한 번씩만 비교되므로 O(n)의 시간 복잡도를 가지며 공간복잡도는 하나의 배열만 사용하므로 O(n)이다.

Insertion Sort

이를 코드로 구현하면 다음과 같다.

첫 번째 for문은 정렬할 원소를 차례대로 선택하는 것이며, 두 번째 for문은 정렬할 원소보다 아래 인덱스에 있는 요소와 비교하는 것이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const swap = (arr, i, j) => {
	[arr[i], arr[j]] = [arr[j], arr[i]];
};

const insertionSort = (arr) => {
	const SortedArr = [...arr];
	const len = SortedArr.length;

	for (let i = 1; i < len; i++) {
		for (let j = i; j >= 0; j--) {
			if (SortedArr[j - 1] > SortedArr[j]) swap(SortedArr, j - 1, j);
		}
	}

	return SortedArr;
};

선택 정렬(Selection Sort)

선택 정렬이란 배열에서 최소값을 반복적으로 찾아 정렬하는 알고리즘이다.
시간복잡도 최선, 평균, 최악 모두 O(n^2)에 해당하는 비효율적인 알고리즘으로 정렬 여부와 상관없이 모든 경우의 수를 전부 확인한다.

Selection Sort

이를 코드로 구현하면 다음과 같다.
배열에서 최소값을 찾아 맨 앞의 값과 바꾼다. 바꿔준 맨 앞 값을 제외하고 같은 방법을 반복한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const swap = (arr, i, j) => {
	[arr[i], arr[j]] = [arr[j], arr[i]];
};

const selectionSort = (arr) => {
	const SortedArr = [...arr];
	const len = SortedArr.length;

	for (let i = 0; i < len; i++) {
		let min = i;
		for (let j = i + 1; j < len; j++) {
			if (SortedArr[min] > SortedArr[j]) min = j;
		}
		swap(SortedArr, i, min);
	}

	return SortedArr;
};

덧붙여 선택 정렬은 크게 2가지로 최소 선택 정렬과, 최대 선택 정렬이 있다.
최소 선택 정렬은 위처럼 오름차순으로 정렬하는 것이고 최대 선택 정렬은 내림차순으로 정렬하는 것이다.

퀵 정렬 (Quick Sort)

퀵 정렬은 분할정복법과 재귀를 사용해 정렬하는 알고리즘이다. 파이썬이나 자바에서 언어에서 자체 내장되어 있는 정렬 알고리즘도 퀵 정렬을 기반으로 한다.
시간 복잡도의 경우 최선과 평균일 때 O(nlogn)이며 최악의 경우에는 O(n^2)이다.
공간 복잡도의 경우 정렬된 원소를 담을 배열이 하나 필요로 하므로 O(n)이다.

Quick Sort

퀵 정렬에는 피봇(Pivot)이라는 개념이 사용된다. 피봇은 한 마디로 정렬 될 기준 원소를 뜻한다.
피봇 선택 방법에 따라 퀵 정렬의 성능이 달라지는데 최적의 피봇 선택이 어려워 보통 배열의 첫 번째 값이나 중앙 값을 선택한다.

퀵 정렬의 동작방식은 다음과 같다. 가령 예를 들어 배열 [29, 10, 14, 37, 1, 40]이 있고, 피봇을 임의로 29를 선택했다 가정하자.
이후 4를 기준으로 작은 것은 왼쪽으로 큰 것은 오른쪽으로 보내 [10, 14, 1] < 29 < [37, 40]을 생성한다.
다시 왼쪽에서부터 임의의 피봇 10을 설정하여 [1] < 10 < [14]를 생성하고 오른쪽에선 임의의 피봇 37을 설정하여 37 < [40]으로 나눈다.
만약 배열의 길이가 1이라면 정렬이 완료된 것이므로 분할된 배열을 합쳐준다.

이를 코드로 구현하면 다음과 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const quickSort = (arr) => {
	if (arr.length === 0) return [];

	const pivot = arr[0];
	const left = [];
	const right = [];

	for (let i = 1; i < arr.length; i++) {
		if (arr[i] < pivot) left.push(arr[i]);
		else right.push(arr[i]);
	}

	return quickSort(left).concat(pivot, quickSort(right));
};

병합 정렬(Merge Sort)

병합 정렬은 분할정복과 재귀 알고리즘을 사용하는 정렬 알고리즘이다.
시간 복잡도의 경우 최선, 평균, 최악 모두 O(nlogn)이며 공간 복잡도의 경우 정렬된 원소를 담을 배열이 하나 필요로 하므로 O(n)이다.
.

Merge Sort

퀵 정렬과 함께 두 개의 알고리즘이 사용된다는 측면에서 공통점을 가진다.
그러나 퀵 정렬이 피봇 선택후 피봇을 기준으로 대소를 비교하는 반면, 병합 정렬은 배열의 요소가 하나일때까지 이분할 한 다음, 대소관계에 따라 재배열 하며 원래 크기의 배열로 병합한다.
예를 들어 배열 [29, 10, 14, 37, 1, 40]이 있을 때, 첫 번째로 [29, 10, 14]와 [37, 1, 40]으로 분리한다.
두 번째로 [29, 10], [14], [37, 1], [40]으로 나눈다.
세 번째로 [29], [10], [14], [37], [1], [40]으로 나눈다.
이렇게 모든 원소가 분리되면 대소 관계를 고려하여 병합 과정을 거친다.
첫 번째로 [10, 29], [14], [1, 37], [40]이 되며, 두 번째는 [10, 14, 29], [1, 37, 40]이 된다.
마지막으로 하나의 배열로 병합되면서 [1, 10, 14, 29, 37, 40]와 같이 정렬이 완료된다.

이를 코드로 구현하면 다음과 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const merge = (left, right) => {
	const result = [];
	while (left.length !== 0 && right.length !== 0) {
		if (left[0] < right[0]) result.push(left.shift());
		else result.push(right.shift());
	}

	return [...result, ...left, ...right];
};

const mergeSort = (arr) => {
	if (arr.length === 1) return arr;

	const middleIndex = Math.ceil(arr.length / 2);
	const left = arr.slice(0, middleIndex);
	const right = arr.slice(middleIndex);

	return merge(mergeSort(left), mergeSort(right));
};

마치며

위에서 정리한 5가지의 정렬 방법 외에도 힙 정렬, 팀 정렬등 정말 많은 정렬 방법이 존재한다.
모든 정렬 방법을 다 탐구하고 외우기는 어렵지만 적절한 자료구조와 알고리즘을 활용해야 좋은 코드를 작성할 수 있는 만큼 꾸준히 CS 공부를 해야겠다🔥

작성일 Edited on Disqus:

원티드 프리온보딩 프론트엔드 인턴십

들어가며

원티드 프리온보딩 프론트엔드 인턴십의 4주차가 지나갔다. 정말 한달이 순식간에 지나간 것 같다.

저번주에는 과제가 없어 약간의 휴식과 더불어 기술면접 스터디를 준비하느라 따로 회고를 작성하지는 않았지만 이번주에는 과제, 이력서 작성등 겪은 일이 많아 회고가 필요할 것 같다.

원티드 프리온보딩 프론트엔드 인턴십 4주차 과제

2023.05.14 - 과제 발표

지난번 까지는 화요일 세션이 끝난 후 과제가 발표되어 금요일 자정까지 제출해야 했다면, 이번 주는 마지막 주다 보니 과제 피드백을 위해 일요일 낮 12시에 과제가 발표되어 수요일 자정까지 제출해야 했다. 그런데 월요일에는 커리어 코칭 세션, 기술면접 스터디가 있었고 화요일에는 인턴십 세션이 있었기 때문에 과제를 수행할 시간이 너무 촉박한것 아닌가 생각했다.(사실 매번 시간이 부족하다고 느낀것 같다).

다행히(?) 발표된 과제 내용을 확인해 보니 2주차 과제와 구현해야 하는 기능이 겹치는 부분이 존재해 생각보다 수월하게 진행할 수 있지 않을까 생각했다. 2주차와 마찬가지로 화요일 저녁까지 각자 과제를 수행해 오기로 했다. 특히 과제 평가 요소에 문서화가 포함되어 있어 각자의 과제 수행 내용에 대해 미리미리 기록을 해두기로 했다.

2023.05.14 ~ 2023.05.16 - 개인 과제 수행

4주차 과제는 제공된 기존 코드의 리팩토링 + 검색어 추천 기능 + 무한스크롤을 구현해야 했다. 검색어 추천 기능은 2주차 과제에서 진행한 적이 있어 어렵지 않을거라 생각했지만, api를 통해 받아오는 데이터의 형태가 달라 필요한대로 가공하는 작업이 필요했다.

무한스크롤은 스크롤 이벤트 혹은 Intersection Observer API를 이용해 구현할 수 있었는데, 여러 장점이 존재하는 Intersection Observer API를 이용했다.

기능 구현은 생각보다 수월하게 진행했지만 코드를 볼 때마다 더 좋은 방향성이 생각나 리팩토링 하는데 시간이 오래 걸렸다. 결국 개인적으로 과제를 수행하는 시간이 다 지났음에도 원하는 만큼 리팩토링을 진행하지 못해 아쉬움이 남았다.

더 자세한 구현사항들은 GitHub의 Issue, PR을 통해 확인 가능하다.

2023.05.16 - 개인 과제 수행 후 회의

그렇게 각자가 과제를 수행한 후 화요일 저녁에 모여 첫 회의를 진행했다.
한 사람 씩 어떻게 기능을 구현했는지, 어떤 항목을 리팩토링 했는지 설명했다. 문서화 항목을 대비해 미리 내용들을 구체적으로 적어오셔서 수월하게 의견을 공유할 수 있었다.

다만 기존 코드를 리팩토링 해서 그런건지 결과물이 다양해 합치는 과정이 어렵다고 느꼈다. 그래서 Best Practice로 평가된 항목들 (Intersection Oberserver API의 사용, 검색어 구현을 custom hook으로 분리 etc)이 제일 많이 적용된 내 코드를 기준으로 추가 항목들을 합치기로 했다.

2023.05.17 - 추가 리팩토링

그렇게 결과물을 합친 후 전체적으로 코드를 살펴보며 추가적으로 리팩토링 할 만한 부분들을 살펴보았다.

비슷한 로직이 중복적으로 사용되고 있어 제거했고, 사용성을 생각해 드롭다운의 구조를 변경했다. 또 디자인 시안에 맞게 디테일한 스타일링도 수정했다.

더 자세한 내용에 대해서는 README.md에서 살펴 볼 수 있다.

KPT

마지막 과제인 만큼 오랜만에 밤도 새워가면서 열심히 집중했다. 그런데도 시간이 부족해 원하는 만큼의 결과물은 얻어내지 못한 것 같다. 인턴십을 처음 시작했을 때와 비교해보면 정말 많이 늘었는데, 오히려 그럴수록 부족한 부분이 많이 보이는것 같다. 더 노력해야지!

Keep

  • 이번 주 역시 만족스러운 README.md 및 기록을 남길 수 있었다! PR과 Issue 생성 시에 미리 기록을 자세하게 해두니 훨씬 수월하게 문서 작업을 할 수 있었다.

  • Best Practice가 많이 적용된 결과물로 나의 과제가 뽑혔다. 1주차에는 Best Practice를 만족시킨 부분이 정말 적었는데 노력한 결과가 그래도 드러나는 것 같아 뿌듯하다. 앞으로도 열심히 해야지.

Problem

  • 과제의 평가 항목에 테스트 코드 작성이 존재했다. 테스트 코드를 작성한 경험이 없기도 하고 아직 Jest의 사용법도 잘 알지 못해 테스트 코드는 다른 팀원분께서 작성하셨는데, TDD를 적용해 개발하는 회사도 많은 만큼 꼭 테스트 코드에 대한 공부가 필요할 것 같다.

Try

  • 취업까지 화이팅! - 인턴십에 참가한 목적은 성장도 있지만 취업을 위해서였다. 인턴십을 잘 수료했다고 끝이 아닌만큼, 취직까지 더 노력하자. 기술면접, 이력서, 포트폴리오 아직 준비할게 많다… 그래도 화이팅!