개발 알다가도 모르겠네요

스택의 사용 사례 재귀 알고리즘 웹브라우저 뒤로가기 실행취소 괄호검사 후위표기법 dfs(깊이우선탐색) 배열 static int[] stack; static int size = 0; static void push(int item){ stack[size++] = item; } static int pop(){ if(size==0) return -1; int res = stack[size-1]; stack[size-1] = 0; size--; return res; } static int size(){ return size; } static int empty(){ if(size==0) return 1; return 0; } static int top(){ if(size==0) return -1; return st..

해시 테이블을 간단하게 설명하면? 데이터의 해시 값을 테이블 내 주소로 이용하는 탐색 알고리즘! 해시 테이블은 key-value 형식으로 데이터를 저장합니다. 검색하고자 하는 키 값을 입력받아 F(key) 해시함수를 통해 반환합니다. 반환받은 hashcode를 배열의 index로 환산해서 데이터 내 value에 접근합니다. 블록체인에서 각 사용자의 공공장부를 확인할 때 많이 사용합니다. 정보의 탐색 시간을 줄이기 위해 해시코드로 만들어 배포, 해시 코드를 비교합니다. 해시 코드를 배열의 개수로 나머지 연산해 배열에 나눠 담습니다. 즉 해시 코드 자체가 배열의 인덱스로 사용됩니다. 하나의 인덱스 안에 해시 코드가 중복돼서 모일 경우 Collision이 발생합니다. O(1) -> O(n) different ..

유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘입니다. 호제법이란 두 수가 서로 상대방 수를 나누어서 원하는 수를 얻는 방법을 말합니다. 구현과정 import java.util.*; public class Main{ public static int gcd(int a, int b) { //유클리드 호제법 if(b==0) return a; else return gcd(b,a%b); } public static int lcm(int a, int b) { return a*b/gcd(a,b); } public static void main(String[] args) { Scanner scan= new Scanner(System.in); int a= scan.nextInt(); int b= scan.next..

에라토스테네스의 체는 소수를 찾는 방법입니다. 2는 소수입니다. 자기 자신을 제외한 2의 배수를 모두 지웁니다. 3은 소수입니다. 3을 제외한 3의 배수를 모두 지웁니다. 4는 2의 배수로, 소수가 아니므로 1번 과정에서 이미 지워졌습니다. 5는 소수입니다. 5를 제외한 5의 배수를 모두 지웁니다. 7은 소수입니다. 7을 제외한 7의 배수를 모두 지웁니다. 이 과정을 x^2> n 이 될 때까지 반복합니다. 위의 그림의 경우 11^2 > 120 이므로 11보다 작은 수의 배수들만 지워져도 충분합니다. 결국 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수입니다. 이 문제는 에라토스테네스의 체를 이용하여 소수를 구해내는 문제입니다. 구현 과정 에라토스테네스의 체 im..

이분 그래프를 간단하게 설명하면? 모든 정점들을 두 가지 색으로만 칠하되, 인접한 정점끼리는 서로 다른 색을 칠해야 하는 그래프! 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프. DFS, BFS로 각각의 정점을 돌아다니며 한 가지 색으로 칠합니다. 다음 정점으로 방문하면서 인접 정점들은 다른 색으로 칠합니다. 탐색 진행시 자신과 인접 정점이 같은 색이면 이분 그래프가 아닙니다. 이분 그래프 특징 그래프의 정점의 집합을 둘로 분할하여 각 집합에 속한 정점끼리는 서로 인접하지 않도록 하는 그래프입니다. DFS와 BFS로 구현이 가능합니다. BFS의 경우 같은 레벨의 정점들은 모두 같은 색깔을 칠한다고 생각하면 쉽습니다. 연결 성분의..

DFS 넓게(wide) 탐색하기 전에 깊게(deep) 탐색합니다. 모든 노드를 방문하고자 할 때 이 방법을 선택합니다. BFS보다 좀 더 간단합니다. 검색 속도 자체는 BFS보다 느립니다. BFS 깊게(deep) 탐색하기 전에 넓게(wide) 탐색합니다. 두 노드 사이의 최단 경로 또는 임의의 경로를 찾고자 할 때 이 방법을 선택합니다. BFS는 재귀적으로 동작하지 않으며 선입선출(FIFO) 원칙으로 탐색합니다. 간선의 가중치가 1이거나, 정점과 간선의 개수가 적을 때 사용하면 효율적입니다.

BFS(Breath First Search)를 간단하게 설명하면? 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘! 시작 정점부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다. 큐를 이용하여 구현을 합니다. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리합니다. 위의 과정을 수행할 수 없을 때까지 반복합니다. BFS 구현 과정 인접리스트 import java.util.*; public class Main { public static boolean visited[]; public static int v; public static int e; pub..

DFS(Depth First Search)를 간단하게 설명하면? 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘! 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수없게 되면 다른 방향으로 다시 탐색을 진행하는 방식입니다. 스택이나 재귀함수를 이용하여 구현합니다. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 있다면 그 노드를 스택에 넣고 방문 처리합니다. 방문하지 않은 인접노드가 없다면 스택에서 최상단 노드를 꺼냅니다. 위의 과정을 수행할 수 없을 때까지 반복합니다. DFS 구현 과정 인접리스트 import java.util.*; public class Main { public static boolean visited[] publi..

합병 정렬을 간단하게 설명하면? 분할 정복을 이용한 정렬! 모든 숫자를 다 나눈 다음에 비교해 병합하는 분할, 정복 방식의 정렬입니다. 각각의 배열이 독립적으로 분할될 때까지 반으로 나눕니다. 독립적으로 분할된 배열들(왼쪽그룹과 오른쪽 그룹)을 차례차례 비교해 정렬하고 합칩니다. 위의 과정은 분할과정과 정복과정으로 나누어지며 마침내 결합하는 순환적인 형태를 띠고 있습니다. 구현 과정 import java.util.*; public class Main { //합병과정 static void merge(int[] A, int left, int mid, int right) { int i=left; //i는 왼쪽(시작)부터. (왼쪽 그룹) int j=mid+1; //j는 mid+1부터. (오른쪽 그룹) int[]..

퀵 정렬을 간단하게 설명하면? 분할 정복을 이용한 가장 빠른 정렬! 임의의 피봇을 정한 뒤 피봇의 위치를 확정해가며 정렬하는 구조입니다. 최초의 피봇을 정한 뒤 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 배열합니다. 피봇을 기준으로 왼쪽 퀵 소트, 오른쪽 퀵 소트를 진행합니다. 위의 과정은 분할과정과 정복과정으로 나누어지며 순환적인 형태를 띠고 있습니다. 구현 과정 - 1 (pivot을 end로 설정) import java.util.*; public class Main { static void quicksort(int[] A, int start, int end) { if(start