본문 바로가기

분류 전체보기

자료구조 - 이진트리와 이진검색트리 이진트리(binary tree) 노드가 왼쪽 자식과 오른쪽 자식을 갖는 트리를 이진트리(binary tree)라고 한다. 이때 각 노드의 자식은 2명 이하만 유지해야 한다. 이진트리의 특징은 왼쪽 자식과 오른쪽 자식을 구분한다는 점이다. 완전이진트리(complete binary tree) 루트부터 노드가 채워져 있으면서 같은 레벨에서는 왼쪽에서 오른쪽으로 노드가 채워져 있는 이진트리를 완전이진트리라고 한다. 1. 마지막 레벨을 제외한 레벨은 노드를 가득 채운다. 2. 마지막 레벨은 왼쪽부터 오른쪽 방향으로 노드를 채우되 반드시 끝까지 채울 필요는 없다. 높이가 k인 완전이진트리가 가질 수 있는 노드의 최댓값은 2^k+1 - 1개이다. 따라서 n개의 노드를 저장할 수 있는 완전이진트리의 높이는 log n이.. 더보기
자료구조 - 트리(tree) BFS와 DFS에 대해서 알아보기 이전에 먼저, 트리라는 자료 구조에 대해 알 필요가 있다. 아래의 내용은 이지스퍼블리싱의 Do it! 자료구조와 함께 배우는 알고리즘입문 책을 참고하여 재구성하였다. 트리(tree) 데이터 사이의 계층 관계를 나타내는 자료 구조이다. 트리를 구성하는 요소는 노드(node)와 가지(edge)이다. 각각의 노드는 가지를 통해 다른 노드와 연결되어 있다. 트리 관련 용어 루트(root): 트리의 가장 윗부분에 위치하는 노드를 루트(root)라고 한다. 하나의 트리에는 하나의 루트가 있다. 리프(leaf): 트리의 가장 아랫부분에 위치하는 노드를 리프(leaf)라고 한다. 이때 '가장 아랫부분에 위치한다'라는 말은 물리적으로 가장 아랫부분에 위치한다는 의미가 아니라 더 이상 뻗.. 더보기
Codility Lesson13 - Ladder 🔍 문제 어떤 사다리가 있고, 발을 밟고 올라갈 수 있는 발판이 N개가 주어진다. 이때 발판을 한번에 이동할 수 있는 칸의 수는 1칸 아니면 2칸만 허용된다. 예를들어, 3개의 발판을 가진 사다리를 올라가서 꼭대기에 도달할 수 있는 방법은 [1, 1, 1] or [1, 2] or [2, 1] 로 세가지이며 4개의 발판을 가진 사다리를 올라가서 꼭대기에 도달할 수 있는 방법은 [1, 1, 1, 1] or [1, 1, 2] or [1, 2, 1] or [2, 1, 1] or [2, 2]로 5가지 방법이 존재한다. 따라서 주어진 사다리를 올라갈 수 있는 경우의 수를 return하면되는데, 발판의 수가 커질 수록 그 경우의 수는 기하급수적으로 커지기 때문에 배열 B에 주어진 수를 이용해서 2^B[i]를 한 값으.. 더보기
Codility Lesson12 - CommonPrimeDivisors 🔍 문제 두 배열 A와 B가 주어지고, 같은 index의 두 요소가 최대 공약수와 똑같은 인자를 가지고 있을 경우의 수를 구하는 문제이다. CommonPrimeDivisors coding task - Learn to Code - Codility Check whether two numbers have the same prime divisors. app.codility.com ✏️ 풀이 - JS Lesson의 소제목이 유클리드의 호제법이므로, 최대 공약수는 유클리드의 호제법을 이용해서 구해주었다. 유클리드 호제법 포스트보기 👉 유클리드 호제법(Uclidean algorithm) 먼저, 두 수의 최대 공약수를 구해 준 후, 각 수를 최대 공약수와의 최대 공약수를 다시 구해주면된다. 그리고 나서 각 수를 구한 .. 더보기
배열의 reduce() 파헤치기 배열의 reduce() 함수에 대해 정리해보려고 한다. 내용은 MDN 웹 문서 사이트를 참고하여 정리된 내용이며, 더 많은 예제와 자세한 내용은 아래 링크에서 볼 수 있다. 링크로 가기 👉 Array.prototype.reduce() reduce() reduce() 메서드는 배열에 대하여 주어진 리듀서(reducer)함수를 실행하고 결과 값을 반환한다. reduce()는 reduce(콜백함수, 초기값)와 같은 형태를 가지고 있으며, 배열의 각 요소가 주어진 콜백함수를 거치게 된다. 이 콜백함수를 리듀서(reducer) 라고 한다. 리듀서는 네가지 인자를 가진다. accumulator(누산기): 누산기는 콜백(리듀서)의 반환 값을 누적한다. 만약 초기값이 제공된다면, 리듀서의 첫번째 호출 시 accumul.. 더보기
Codility Lesson12 - ChocolatesByNumbers 🔍 문제 N개의 초콜릿을 원 형태로 나열한 뒤, 0번째 초콜릿을 먹고 포장지만 남긴다. 그리고나서 현재 먹은 초콜릿 자리 + M의 자리에 있는 초콜릿을 먹는다. 원의 형태로 나열되어 있으므로 초콜릿의 자리는 (i + M)%N의 공식으로 구하면 된다. 이 순서로 초콜릿을 먹어가면서 이미 먹고 포장지만 남은 초콜릿의 자리로 다시 돌아오게된다면 먹는것을 멈춘다. 이 과정을 거쳤을 때 먹게되는 초콜릿의 개수를 구하면 된다. ChocolatesByNumbers coding task - Learn to Code - Codility There are N chocolates in a circle. Count the number of chocolates you will eat. app.codility.com ✏️ 풀이 .. 더보기
유클리드 호제법(Uclidean algorithm) 최대 공약수란? 주어진 정수들의 공통된 약수들 중 가장 큰 약수를 말한다. 최대공약수를 구하는 방법은 소인수 분해와, 유클리드 호제법이있다. 두가지 방법으로 192와 72의 최대 공약수를 구하는 방법을 살펴보자. 소인수 분해 소인수 분해로 구할 때는 먼저 주어진 수들을 각자 소인수 분해한다. 그 후에 중복되는 부분을 서로 곱해주면 최대 공약수를 구할 수 있다. 192 = 2^6 * 3 = 2 * 2 * 2 * 2 * 2 * 2 * 3 72 = 2^3 * 3^2 = 2 * 2 * 2 * 3 * 3 이때, 중복되는 2^3 * 3 = 2 * 2 * 2 * 3 = 24로 두수의 최대 공약수는 24이다. 유클리드 호제법 유클리드 호제법은 두 정수의 최대 공약수를 재귀적으로 구하는 방법이며 소인수 분해보다 훨씬 빠.. 더보기
자료구조 - 스택과 큐(Stack and Queue), 링버퍼(Ring buffer) 스택(Stack) 스택은 데이터를 일시적으로 저장하기 위한 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO, Last In First Out)이다(가장 나중에 넣은 데이터를 가장 먼저 꺼낸다.). 스택에 데이터를 넣는 작업을 푸시(push)라고 하고, 스택에서 데이터를 꺼내는 작업을 팝(pop)이라고 한다. 이때, 푸시와 팝을 하는 위치를 꼭대기(top)이라고 하고, 스택의 가장 아랫부분을 바닥(bottom)이라고 한다. 스택의 push와 pop은 꼭대기 top자리에서만 이루어지므로 복잡도는 O(1)이다. 큐(Queue) 큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조이다. 스택과 다르게 큐는 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO, Fisrt In F.. 더보기
검색 알고리즘 - 선형 검색, 이진 검색 검색 알고리즘이란 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 알고리즘이다. 알고리즘에 들어가기 앞서, 복잡도에 대해 알아보자. 복잡도 알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도(complexity)라고 한다. 시간 복잡도(time complexity): 실행에 필요한 시간을 평가한 것 공간 복잡도(space complexity): 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것 선형 검색(linear search) 요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨앞부터 순서대로 요소를 검색하면 되는데, 이것이 선형 검색(linear search) 또는 순차 검색(sequential search)이라는 알고리즘이다. [검색이 종료되는 종료 조건.. 더보기
메소드와 함수 (Method and Function)의 차이점 You don't know JS(this와 객체 프로토 타입, 비동기와 성능)편을 읽던 중, 여타 언어에서 객체(클래스)에 부속된 함수를 주로 '메소드'라 부르고 자바스크립트 함수 역시 객체의 부속물이라 생각하기에 ... 엄밀히 말해 함수는 결코 객체에 속하는 것이 아니며, 객체 레퍼런스로 접근한 함수를 그냥 메소드라 칭하는건 그 의미를 지나치게 확대해 해석하는 것이다. 라는 구절을 읽으며 메소드와 함수의 차이점이 정확히 뭘까?라는 궁금증이 들었다. 여태까지는 단순히 어떠한 기능을 하는 코드 조각을 'Java에서는 메소드, JavaScript에서는 함수라고 부른다' 라고 생각해왔다. 구글링을 해보니 스택오버플로우에 동일한 질문이 올라와있어서 이를 참고해서 요약해보았다. 링크로 가기 👉 What's the.. 더보기

티스토리툴바