알고리즘
[프로그래머스] K번째수
문제 설명 [i, j, k] 를 원소로 가진 2차원 배열 commands 가 주어지면 i 부터 j 번째까지 배열을 자르고 정렬한 후에 k 번째에 있는 수를 배열에 담아서 return 해주는 문제입니다. 문제 풀이 먼저 commands 에 들어있는 값들을 i, j, k 라는 변수에 담아주고 싶었습니다. 이왕이면 i, j, k 라는 변수 이름보다는 의미있는 네이밍을 통해 start, end, asnwerIdx 라는 변수에 담아주었습니다. 이때 배열 디스트럭처링을 사용했습니다. 배열 디스트럭처링을 사용하면 간결하고 보다 더 가독성이 좋아진다는 장점이 있습니다. const [start, end, answerIdx] = command; start 부터 end 까지의 배열을 복사하고 정렬해주었습니다. 이때 slic..
[자바스크립트] 정렬 구현해보기
정렬 구현 버블 정렬 버블 정렬은 두 인접 원소를 검사해 정렬 하는 방법입니다. 아래와 같은 gif 파일 처럼 정렬을 시작하고 구현이 단순하다는 장점이 있습니다. 하지만 시간 복잡도가 평균, 최상, 최악 모두 O(N^2) 으로 굉장히 비효율적인 정렬 알고리즘 입니다. function bubbleSort(array) { // 인덱스와 바로 옆에 있는 인덱스 + 1 값을 비교하기 때문에 i 는 array.length - 1 까지 for (let i = 0; i a..
Tree 에 대해서 알아보자! (자료구조, 알고리즘)
안녕하세요 원재입니다 ^ㅡ^ 이번 글에서는 빠른 탐색을 위해 사용되는 트리 자료구조에 대해서 알아보려고 합니다! Tree 는? Tree 는 말 그대로 나무입니다 ^ㅡ^ 읽어주셔서 감사합니다가 아니라 생뚱맞게 왜 자료구조를 공부하기 위해 작성된 게시글에서 갑자기 나무 사진을 들고 여러분들에게 소개를 하고있을까요? 한번 위에 있는 나무를 뒤집어 볼까요? 독자분들이 물구나무서기를 할 필요없이 제가 완벽하게 뒤집었습니다. 근데 이게 무슨 소용이 있길래 제가 어마무시한 노력과 정성 그리고 시간을 들여 나무를 뒤집어버렸을까요? 바로 아래 배울 자료구조로서의 트리의 생김새가 마치 나무를 뒤집은 것과 비슷하게 생겼기 때문입니다. 위 그림이 우리가 알아볼 트리입니다. 꽤나 비슷하게 생기지 않았나요? 사실 저도 뒤집어놓고..
Union-Find(Disjoint-Set) 에 대해, + BOJ 4195
안녕하세요 원재입니다 ^ㅡ^ 이번에는 알고리즘에서 주로 쓰이는 (특히 그래프 알고리즘) Union-Find 에 대해서 알아보려고 합니다! Union-Find 는? Union-Find 의 가벼운 첫 인상을 알려드리자면, Union-Find 는 우리 조상님 찾기 라고 볼 수 있습니다! 조상님이라고 부르세요 위와 같은 그래프가 있다고 생각해 봅시다. 루트 노드는 1 과 5 가 되겠죠? 3,4 를 자식으로 가지는 1번 트리와, 6, 2를 자식으로 가지는 5번 트리가 존재한다고 생각하겠습니다. 그렇다면 우리는 Union-Find 를 통해 4의 조상님은 1이에요! 라는 것을 Find 할 수 있습니다. 그렇다면 Union 은 어떨때 사용할까요? 바로 족보 구매 입니다. 족보입니다 만약 위와 같은 노드에서 5번 노드가..