minTech

Queue와 Priory Queue 일반적으로 알고있는 큐(queue)는 LIFO(Last In First Out)구조를 갖는 stack과 달리 FIFO(First In First Out)구조를 갖고 있어, 먼저 들어간 아이가 먼저 나오는! 그런 데이터 순서를 갖고 있다. 우선순위 큐(Priority Queue) 는 들어간 순서와는 상관없이 각 요소에 우선순위를 할당하고, 우선순위가 높은 데이터가 먼저 나온다. 자바스크립트의 경우에는 파이썬과 달리 우선순위 큐의 구현이 내장되어있지 않기 때문에 힙(heap) 이라는 자료구조 개념을 갖고, 직접 코드를 통해 구현해야한다. 그렇다면 힙(Heap)을 통해 우선순위 큐를 구현하기 전에 힙에 대해서 알아보자!힙(Heap)이란 완전 이진 트리 구조를 갖는 자료 ..

백준 1074번!! 문제크기가 2**N, 2**N 인 2차원 배열을 Z모양으로 탐색하려한다.  N>1 인 경우, 이를 4등분한 후에 또 Z모양으로 방문한다.예시는 아래와 같음! N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하자.  풀이주키워드는 "사분면"과 "재귀함수" 이다. 간단하게 말하자면 제 1, 2, 3, 4분면으로 나눠서 사분면마다 그 전의 사분면만큼의 숫자를 더해주는 로직이다.  말로 하면 어려우니까 N은 3에서 7행 7열을 예를 들어보겠슴니다. 1. N = 3 일때 여기서 7행 7열은 제 4사분면이다.  2. N = 2일 때이제 위의 4사분면만 잘라서 다시 가져온다면 아래와 같다.N이 3이었을 때, 한 사분면에는 16개씩 있으며, 1,2,3 을 지나 제 4사분면은 16 * 3인 ..

프로그래머스 72413번 합승 택시 요금 해당 문제는 a와 b가 같은 출발지에서 출발하는데 서로의 목적지까지 얼마나 최소의 택시요금으로 갈 수 있는지 구하는 문제이다.이는 결국 그래프의 최단 거리를 구하는 것이다. 그렇다면 그래프의 최단 거리를 구하는 알고리즘은 크게 3가지가 있다.다익스트라(Dijkstra)벨만 포드(Bellman-ford)플로이드 와샬(Floyd Wrashall)이 중에서 해당 문제에 대해 적용하는 알고리즘은 플로이드 와샬 알고리즘이다.  플로이드 와샬 (Folyd Warshall) 알고리즘 1.  어떠한 한 노드에서 특정 다른 노드까지의 최단 거리를 구하는 다익스트라 알고리즘, 벨만 포트 알고리즘과 달리     플로이드 와샬은 모든 노드에 대한 최단 거리를 구한다. 2. 음의 가중치..

이진 트리트리 구조는 하나의 루트로부터 여러 갈래로 뻗어나가는 구조를 말한다. 이진 트리라는 것은 아래 그림과 같이 트리 구조 중에서도 자식 노드가 최대 2개를 갖는 구조이다. 자식 노드가 최대 2개이기 때문에 왼쪽, 오른쪽으로 구분이 가능하다.    이진 트리의 종류1. Full Binary Tree (정 이진 트리)- 모든 노드의 자식노드가 2개 이거나, 아예 없다. 2. Complete Binary Tree (완전 이진 트리)- 마지막 레벨을 제외한 모든 노드가 2개의 자식 노드를 가진다.    마지막 레벨의 노드는 최소 왼쪽이 다 채워져 있다. 3. Perfect Binary Tree (포화 이진 트리)- 모든 노드의 자식 노드가 2개이며, leaf node의 레벨이 같다.    이진 트리 구현이..

Longest Common Subsequence vs Longest Common SubstringLCS 알고리즘에는 주로 Longest Common Subsequece(최장 공통 부분 수열) 을 의미하지만, 가끔 Longest Common Substring(최장 공통 부분 문자열)을 의미하기도 한다. 1. Longest Common Substring두 문자열 사이에 공통적인 연속된 부분 문자열을 말한다. 포인트는 '연속된' 이다. 'ABCDE'와 'BGCDE' 의 최장 공통 부분 문자열은 'CDE'가 될 것이다.   2. Longest Common Subsequece 두 문자열 사이에 공통적인 부분 문자열을 말한다. 이는 연속적일 필요가 없다.하지만 순서가 뒤바뀐 것은 인정하지 않는다. ex) EDCB'..

Union-find는 언제 사용할까?Union-find에 대해 알기 전에, 먼저 해당 알고리즘을 사용해야하는 간단한 예시를 들어보겠다.사람들의 연결 관계가 주어졌을 때, 서로 친구인 그룹의 수를 구하시오.이 때, 관계는 양방향이다. 입력- n = 5 ( 사람 수는 5명)- 친구 관계: [[1, 2], [2, 3], [4, 5]]출력- 친구 그룹의 수: 2 이는 눈으로 알기 쉽게 노드 상으로 보자면 아래와 같다.  결국, 해당 문제는 노드 싸이클의 개수를 묻는 것이다. 이 싸이클을 구하기 위해서 사용하는 알고리즘을 [ Union-find(유니언 파인드) ]   Union-find 알고리즘유니온 파인드 알고리즘은 두 가지의 연산을 진행한다.Initialization : 각 노드가 각각의 집합에 포함되도록 초..

1. Math.ceil : 올림소수 값이 존재하기만 하면 올린다. Math.ceil(3.14) // 4  2. Math.floor : 내림소수 값이 존재하기만 하면 소수점 밑의 값을 모두 버린다. Math.ceil(3.14) // 3  3. Math.round: 반올림우리가 아는 반올림과 동일하게 동작한다.소수점 밑이 0.5 이상이면 올림, 그 아래면 내림을 한다. Math.round(3.14) // 3Math.round(3.56) // 4

DFS를 알기 전에 먼저 재귀함수에 대해서 알아보겠다. 🕵️ 재귀함수 재귀함수는 자기가 자기 자신을 호출하는 함수를 말한다. function solution() { function recursive(n) { recursive(n - 1); } recursive(3); } 위의 코드를 보면 알 수 있듯이 recursive 함수 내부에서 recursive 함수를 호출한다. 함수를 멈추는 아무런 조건을 넣어주지 않았기 때문에 recursive(3)이 먼저 호출될 것이고, 그 다음에는 recursive(2), recursive(1), recursive(0) ... 무한 루프를 돌 것 이다. 만약 여기에 조건을 추가해주면 해당 함수를 반복문처럼 사용이 가능하다. function solution(n) { funct..