(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) 개념시간 복잡도는 주어진 문제를 해결하는데 필요한 연산 횟수를 말한다.(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 ..

1. LIS란?LIS란 Longest Increasing Subsequence의 약자로 가장 긴 증가하는 부분 수열을 뜻한다. LIS 알고리즘 문제는 전체 수열을 주어지고, 그 안에서 가장 길고, 증가하는 부분 수열을 구해야 하는 문제들을 총칭이다. 난 부분 수열이 무엇인지부터 헷갈렸다. 따라서 먼저 수학적 배경지식을 공부하고, 마저 설명하겠다.1-1. 부분 수열이란 무엇인가? 수열은 수가 하나의 열로 나열된 형태를 뜻한다. (행군하는 군인을 떠올려보라!) 여기서 부분수열이란 주어진 수열의 일부 항을 원래 순서대로 나열하여 얻을 수 있는 수열 을 뜻한다. 만약 전체 수열 S 가 {1,2,3,4,5,6,7,8,9,10}이라면 {1}, {2,4,6,8,10}, {2,4,6}, {8,9,10} 모두 S의 부분..