전체 글
-
GitHub Desktop(Pull, Push)Git/GitHub 2021. 5. 8. 22:53
깃(Git)은 컴퓨터 파일의 변경사항을 추적하고, 여러 사용자간 협업을 위한 분산 버전 관리 시스템이다. 기본적으로 Git은 버전 관리, 백업, 협업 등 매우 다양하지만 심오한 개념을 가지고있고 GUI를 이용한 방식, CLI를 이용한 방식이 있지만 CLI는 초보자가 바로 능숙하게 다루기엔 다소 어려운 부분들이 존재한다. 이 글에서는 GUI방식을 기반으로 개발된 GitHub DeskTop 프로그램의 Pull을 이용하여 GitHub 서버에서 자료를 가져오는 방법과 Push를 이용하여 서버로 자료를 보내는 방법만 매우 담백하게 작성하였다. *Clone -> Clone은 쉽게 말해 GitHub(Server)에 저장된 내용을 내 컴퓨터(Local)로 가져오는 작업이다. (1) 먼저, 아래 그림과 같이 GitHub..
-
[Java]누적 합(Prefix Sum , Cumulative Sum)Algorithm/수학&기타 2021. 4. 22. 13:46
*누적 합(Prefix Sum, Cumulative Sum) -> 누적 합이란, 말 그대로 나열된 수의 누적된 합을 말한다. -> 조금 더 엄밀히 말하면, 수열 An에 대해서, 구간 [1, 1]의 합, 구간 [1, 2]의 합, 구간 [1, 3]의 합, ..., [1, n]의 합을 누적 합이라고 한다. ※ 따라서 Prefix Sum의 각 요소는 해당 해당 인덱스까지의 부분 합(Partial Sum)을 의미한다. 부분 합은 급수에서 말하는 그 부분합의 의미가 맞다. *누적 합의 사용 -> 누적 합은 그 목적에 따라 다양한 문제에 활용이 가능하다. -> 대표적으로 누적 합을 사용하는 문제는 카운팅 정렬(Counting Sort), 구간 합 구하기가 존재한다. *단순 반복을 이용한 구간 합 구하기 -> 이 글의..
-
[Java]거듭 제곱의 계산Algorithm/수학&기타 2021. 4. 20. 17:17
*거듭 제곱의 계산 -> 거듭 제곱을 구현하는 방법은 간단하다. 기본적으로는 그 정의 그대로 어떤 수를 n번 곱하여 거듭제곱을 구현 가능하다. 하지만 n번 곱하기 때문에 시간복잡도는 O(n)이 걸린다는 것을 알 수 있다. *개선된 거듭 제곱의 계산 -> 이러한 거듭 제곱은 분할 정복을 기반으로 시간복잡도를 O(logN)까지 줄일 수 있다! -> 기본적인 아이디어는 다음과 같다. 예를 들어 5^10을 계산한다고 생각하였을 때, 아래와 같은 과정을 거쳐서 그 값을 구하는 것 이다. -> 따라서, 재귀를 이용하여 다음과 같은 거듭제곱을 구현할 수 있음을 알 수 있다. *구현 -> 점화식도 구하였으니 그대로 구현하기만 해주면 된다. import java.util.Scanner; public class Expon..
-
페르마의 소정리(Fermat's Little Theorem)Algorithm/수학&기타 2021. 4. 20. 00:36
*페르마의 소정리(Fermat's Little Theorem) -> 우선 페르마의 소정리를 활용하기 위해서는 기본적으로 모듈러 산술(연산)과 합동식에 대한 이해가 선행되어야 한다. 다음 포스팅을 참고하도록 하자. sskl660.tistory.com/75 모듈러 산술(Modular Arithmetic) *모듈러 산술(Modular Arithmetic) -> 모듈러 산술(모듈러 연산)은 정수의 합과 곱을 어떤 주어진 수의 나머지를 이용하여 정의하는 방법을 말한다. -> 쉽게 말해 나머지를 이용한 산술 연산이라고 생 sskl660.tistory.com -> 페르마의 소정리는 특정한 상황에서 어떤 수의 나머지를 빠르게 구할 때 사용이 가능하다. 특정한 상황은 아래 정리를 참고하도록 하자. 쉽게 말해 a^(p -..
-
모듈러 산술(Modular Arithmetic)Algorithm/수학&기타 2021. 4. 19. 23:54
*모듈러 산술(Modular Arithmetic) -> 모듈러 산술(모듈러 연산)은 정수의 합과 곱을 어떤 주어진 수의 나머지를 이용하여 정의하는 방법을 말한다. -> 쉽게 말해 나머지를 이용한 산술 연산이라고 생각하면 된다. 사칙 연산과 마찬가지로 정수의 나머지에도 연산과 관련된 개념이 존재한다. -> 모듈러 연산은 정수론, 컴퓨터 과학의 보안 등 여러 분야에서 유용하게 사용될 수 있다. 알고 있다면 알고리즘 문제에서 몇몇 연산을 편하게 할 수 있는 방법을 생각하는 기반이 될 수 있다. 모듈러 연산 자체를 응용한 문제는 그렇게 많지 않지만, 이를 기반으로한 수학적 개념(정수론)의 기반이 되기 때문에 이해해두도록 하자. *모듈러 산술 연산과 합동(Congruent) -> 모듈러 산술 연산 : 쉽게 말해 ..
-
[Java]유클리드 호제법(Euclidean Algorithm)Algorithm/수학&기타 2021. 4. 19. 18:16
*유클리드 호제법(Euclidean Algorithm) -> 유클리드 호제법은 두 개의 자연수 or 두 개의 다항식의 최대공약수를 구하는 방법이다. ※ a는 b의 피제수(즉, 나누어지는 수)이므로 a > b이다. ※ 따라서 수식의 q는 몫, r은 나머지를 의미한다(따라서 r은 0보다 같거나 크고 b보다는 작아야 한다). -> 유클리드 호제법은 최대공약수를 구하는데 사용한다고 하였다. 최대공약수는 수학적으로 두 수의 모든 약수를 나열한 뒤 공통되는 약수 중 최대를 선택하거나 소인수 분해를 이용한 방법이 있지만, 유클리드 호제법을 이용하면 더 빠른 시간 안에 최대공약수를 구할 수 있다. *유클리드 호제법의 사용 -> 피제수가 제수에 의해 나누어 떨어진다면, 그 피제수와 제수의 최대공약수는 제수이다. 이 명제..
-
[Java]플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)Algorithm/그래프&최단경로 2021. 4. 15. 22:44
*플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) -> 플로이드-워셜 알고리즘은 음수 사이클이 없는 그래프내의 각 모든 정점에서 각 모든 정점에 까지의 최단거리를 모두 구할 수 있는 알고리즘이다. 다익스트라 알고리즘과는 다르게 그래프에 음수 사이클만 존재하지 않으면, 음의 가중치를 갖는 간선이 존재해도 상관이 없다는 것이다. ※음수 사이클 : 사이클의 모든 경로를 지나 원래 지점으로 돌아 왔을때, 최종적인 비용이 음수가 되는 경우. *플로이드-워셜 알고리즘의 이해 -> 플로이드-워셜 알고리즘은 다이나믹 프로그래밍 기법을 사용한 알고리즘이고, 인접 행렬을 이용하여 각 노드간 최소 비용을 계산한다. -> 플로이드-워셜 알고리즘은 모든 노드에서, 모든 노드로 가는 최소 비용을 단계적으로 ..
-
[Java]크루스칼 알고리즘(Kruskal Algorithm)Algorithm/그래프&최단경로 2021. 4. 15. 17:15
*크루스칼 알고리즘(Kruskal Algorithm) -> 크루스칼 알고리즘은 그래프에서 최소 비용 신장 부분 트리(최소 신장 트리 : Minimum Spanning Tree(MST))를 찾는 알고리즘이다. ※ 최소 신장 트리, 신장 트리와 같은 용어를 조금 더 자세히 알고 싶다면 위키백과를 참고하도록 하자. ko.wikipedia.org/wiki/%EC%8B%A0%EC%9E%A5_%EB%B6%80%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84 신장 부분 그래프 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 그래프의 신장 부분 나무 그래프 왼쪽의 그래프는 오른쪽과 같이 총 8개의 신장 부분 나무 그래프들을 갖는다. 그래프 이론에서, 신장 부분 그래프(身長部分gr..
-
[Java]서로소 집합(Disjoint Set)(Union-Find)(Merge-Find Set)Algorithm/자료구조 for Algorithm 2021. 4. 15. 11:08
*서로소 집합(Disjoint Set) -> 서로소 집합 자료구조는 상호 배타적으로 이루어진 집합(서로소 집합 : 공통 원소가 없는 두 집합)을 효율적으로 표현하기 위해 만들어진 자료구조이다. -> 서로소 집합은 서로 다른 두 개의 집합을 병합하는 연산(Union)(Merge)과 집합의 원소가 어떤 집합에 속해 있는지 판단하는 연산(Find)을 기반으로 구현되기 때문에, Union-Find 혹은 Merge-Find Set이라고도 불린다. -> 서로소 집합을 구현하는 방법은 연결 리스트를 이용하는 방법과, 트리를 이용하는 방법이 있는데, 이 글에서는 트리를 이용하는 방법에 대해서만 다룬다. *서로소 집합의 단순 구현(트리) -> 서로소 집합은 기본적으로 총 3가지 연산(MakeSet, Find, Union..
-
[Database]서브 쿼리(MySQL)Web/Database 2021. 4. 12. 14:33
*서브 쿼리(SubQuery) -> 서브 쿼리란 말 그대로 다른 쿼리 내부에 포함되어 있는 쿼리를 말한다. -> SELECT 문을 이용한 데이터 조회는 결과적으로 검색 조건을 만족하는 또 하나의 테이블을 만들어 내는 것을 의미한다고 볼 수 있다. 이러한 점을 활용하여 검색 결과 테이블을 활용하여 다시 쿼리를 진행하는 것을 서브 쿼리라고 생각하면 이해하기 쉽다. *서브 쿼리의 종류 -> 서브쿼리는 쿼리의 위치가 어디에 있느냐에 따라서 세 가지 종류로 나눌 수 있다. (1) 중첩 서브 쿼리(Nested Subquery) : WHERE절에 사용하는 서브 쿼리. (2) 인라인 뷰(Inline View) : FROM절에 사용하는 서브 쿼리. (3) 스칼라 서브 쿼리(Scalar Subquery) : SELECT절..