minTech

백준 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..

알고리즘 분류 : 수학, 기하학, 많은 조건 분기 ❓Question 조규현과 백승환은 터렛에 근무하는 직원이다. 하지만 워낙 존재감이 없어서 인구수는 차지하지 않는다. 다음은 조규현과 백승환의 사진이다. 이석원은 조규현과 백승환에게 상대편 마린(류재명)의 위치를 계산하라는 명령을 내렸다. 조규현과 백승환은 각각 자신의 터렛 위치에서 현재 적까지의 거리를 계산했다. 조규현의 좌표 (x1,y1)와 백승환의 좌표 (x2,y2)가 주어지고, 조규현이 계산한 류재명과의 거리 r1과 백승환이 계산한 류재명과의 거리 r2가 주어졌을 때, 류재명이 있을 수 있는 좌표의 수를 출력하는 프로그램을 작성하시오. ‼️ Answer 조규현의 좌표와 백승환의 좌표를 기준으로 각각 r1과 r2를 반지름으로 가진 원을 그려준다. 👉..