1. 정의A = Bq + R일 때, A와 B의 최대공약수 G는 B와 R의 G와 같다. 를 활용하여, 연쇄적인 나눗셈으로 A,B의 최대공약수를 구하는 방법을 말한다. 2. 원리정의에서 연쇄적인 나눗셈이라고 한 이유는 다음과 같다. 1. A = Bq + R 2. B = Rq + R'3. R = R`q + 0 간단하게 3번안에 끝나는 예시를 보자. A,B의 G는 B,R의 G와 같음.B,R의 G는 R,R'의 G와 같음.마지막 식에서 나머지가 없으므로, R'는 R의 약수임. R과 R'의 최대 공약수는 당연하게도 R'임. 이제 연어처럼 3 -> 1로 거슬러 올라가면 종국에 A,B의 최대공약수는 R'랑 같음.3. 증명(1) A와 B와 R이 같은 G를 공유하는가?A = Ga, B = Gb (G가 최대공약수임으로, a와..

1. Binary-Search란 무엇인가요?정렬된 배열 혹은 List 에서 탐색 구간을 절반씩 줄여가며 특정 값을 찾는 탐색법이다. 다음과 같이 진행 된다.(0) 기본적인 용어는 다음과 같다.target: 찾고자 하는 값, start : 왼쪽 포인터,(index=0에서 시작), end: 오른쪽 포인터(배열 끝에서 시작), mid: 두 값의 중간에 위치한 값(1) mid를 구하고 target 값과 대소관계를 비교한다.(2) mid > target 이면, mid 값이 target값으로 향하도록, end = mid-1 로 탐색 영역을 절반 줄인다.(3) mid target 이면, start = mid +1 이 되도록 하여, 탐색 영역을 절반 줄인다.(4) mid == target 이면 값을 구했으므로, 이분 ..

(0) 그래프란?a. 정의값을 담고 있는 정점(Vertex)와 그 정점들을 잇는 간선(Edge)으로 이루어져 있는 자료구조b. 그래프 관련 용어용어뜻정점(Vertex or Node)데이터를 저장하는 곳간선(Edge)정점과 정점을 잇는 선인접하다.정점 A와 B가 간선으로 이어져 있으면, 정점 A와 B는 서로 인접하다.라고 한다. 인접 정점: 하나의 정점 A와 간선으로 이어져 있는 정점들을 인접정점이라고 한다. 위의 예시에서 B는 A의 인접정점이다.차수하나의 정점 A와 연결된 간선의 개수이다. a의 예시에서 정점2의 차수는 3이고 정점4의 차수는 4이다. 진입 차수: 방향이 있는 그래프에서 외부로부터 들어오는 간선의 개수를 말한다. 진출 차수: 방향이 있는 그래프에서 외부로 뻗어나가는 간선의 개수를 말한다...

[toc]1. DFS(깊이 우선 탐색)(1) 정의그래프 탐색 기법 중 하나이다.DFS는 시작 정점에서 갈 수 있는 분기들 중 하나를 택하여, 해당 분기에서 갈 수 있는 최대 깊이까지 탐색한 후, 다음 분기로 넘어가서 같은 작업을 반복하는 완전 탐색 기법이다.해당 Tree 구조를 DFS로 순회하면, 1->2->3->4->5->6->7->8->9->10->11->12->13 순으로 조회한다.(2) 시간 복잡도O(V+E)V: 정점, E: 간선(3) 구현 방법재귀를 이용해 구현한다. (재귀가 가지는 stack의 성질 이용)방문배열을 활용하여, 한 번 방문한 노드는 재방문하지 않는 것이 핵심이다.사전세팅: 방문 배열 만들기, 그래프를 인접행렬 혹은 인접 리스트로 표현재귀 함수를 만들어 DFS 구현public st..

1. 하나의 숫자에 대한 소수 판별(1) 방법판별해야할 숫자를 N이라고 하면 다음과 같은 방법으로 N이 소수인지 여부를 판별할 수 있다.int N = Integer.parseInt(br.readLine());for(int i = 2; i(2) 왜 √N까지만 확인하면 되나요?예를 들어서 설명해보겠다. N == 64라면,√N은 8이다.ab = 64라면  √N 은 8*8 처럼 a와 b가 같은 수이다.만약 a 따라서 a √N 이 되면 반자동적으로 b > √N 이 된다.따라서 만약에 특정 수 N에 대하여 2 ~ √N까지의 수 중에 나누어 떨어지는 수가 없다면, √N보다 큰 수 중에서도 나누었을 때, 나누어 떨어지는 숫자가 없다는 말이다.왜냐하면 2 ~ √N의 수 중 N을 나누었을 때, 나누어 떨어지는 a란 수가 ..

1. 버블 정렬(1) 정의인접한 원소끼리 비교 후에, 정렬되어 있지 않다면, 두 원소의 위치를 swap한다.이런 식으로 정렬하게 되면 배열 혹은 리스트의 오른쪽부터 값들이 정렬되어 쌓이게 된다.예시사진 출처: 블로그(2) 시간 복잡도: O(n^2)2. 선택 정렬(1) 정의정렬이 되어있지 않은 범위 내에서의 최소값 혹은 최대값을 맨 오른쪽 혹은 맨 왼쪽으로 몰아넣는다.이후 정렬되지 않은 부분 내의 최소값 혹은 최대값을 다시 찾아 아까 몰아넣은 곳으로 또 몰아넣는다.밑의 사진은 오름차순 정렬을 선택 정렬로 행한 것이고, 최소값을 오른쪽으로 몰아넣었다.사진 출처: 블로그(2) 시간 복잡도: O(n^2)3. 삽입 정렬(1) 정의정렬된 범위 내에 현재 값을 삽입할 적절한 위치를 찾는다. (오름 차순, 내림차순일 ..

1. 시간 복잡도 란?(1) 개념시간 복잡도는 주어진 문제를 해결하는데 필요한 연산 횟수를 말한다.(2) 표기 방법의 종류시간 복잡도를 표기하는 방법에는 다음의 3 가지가 있다.이름설명빅-오메가 표기법문제를 풀기 위해 주어진 상황이 최선의 상황일 때 필요한 연산 횟수를 나타내는 표기법빅-세타 표기법문제를 풀기 위해 주어진 상황이 보통의 상황일 때 필요한 연산 횟수를 나타내는 표기법빅-오 표기법문제를 풀기 위해 주어진 상황이 최악의 상황일 때 필요한 연산 횟수를 나타내는 표기법예를 들어 설명1~100의 숫자가 랜덤한 순서로 저장된 배열이 주어졌을 때, 해당 배열에서 56의 INDEX를 찾아서 출력하라 라는 문제를 풀어야 한다고 하자.이때 내가 선택한 방법은 배열의 첫 번째 인덱스부터 일일히 조회이다.빅-오..

0. 설명 하려는 것 (1) 순열, 조합, 중복 순열, 중복 조합의 정의 (2) JAVA 언어를 썼을 때, 구현 방법 1. 순열 (1) 순열의 뜻 nPr = n 개 중에서 r개를 중복 없이 뽑아서 순서 있게 나열하는 것을 말한다. 따라서 {1, 2, 3, 4, 5} 중 5P3 에서 {1, 2, 3} 과 {1, 3, 2}는 다른 숫자이다. (2) 구현 방법 순열은 재귀로 구현한다. 순열을 재귀로 구현하기 위해서는 다음과 같은 구성요소들이 필요하다. 전체 원소들에 대한 방문 배열 isVisited [] : 순열로 값을 뽑을 때, 중복이 없어야 하므로, 방문 배열을 통해, 이미 방문한 지점은 그냥 지나치도록 구현 해야 한다. 뽑힌 r개의 원소를 담을 배열 output [] : 전체 원소가 담긴 배열을 arr ..