프로그래밍 해볼까

DFS와 BFS1. DFS(Depth-First-Search, 깊이우선탐색) 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 대표적으로 백트래킹에 사용한다. 일반적으로 재귀호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다. 구조상 스택 오버플로우를 유의해야 한다. 갈림길이 나타날 때마다 ‘다른 길이 있다’는 정보만 기록하면서 자신이 지나간 길을 지워나간다. 그러다 막다른 곳에 도달하면 직전 갈림길까지 돌아가면서 ‘이 길은 아님’이라는 표식을 남긴다. 그렇게 갈림길을 순차적으로 탐색해 나가다 목적지를 발견하면 그대로 해답을 내고 종료한다. 장점 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비..

[Java] Bubble Sort 거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O(n2)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용됩니다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름입니다. 위키백과-거품정렬 import java.util.Scanner; public class BubbleSort { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int N; int[] array; N = sc.nextInt(); array = new int[N]; for(..

[Java] Rank Algorithm(순위 알고리즘) 지정한 범위에서 순위를 구하는 알고리즘입니다.1등, 2등, 3등 . . . 과 같이 순위를 구할 수 있습니다.먼저 순위 배열을 1로 초기화 합니다.반복문을 돌면서 나보다 큰 수가 나오면 1 증가시킵니다. public class RankAlg { public static void main(String[] args) { int[] grade = new int[]{47, 98, 56, 33, 85}; //성적 int[] rank = new int[]{1, 1, 1, 1, 1}; //등수 //rank 구하기 for(int i=0 ; i