알고리즘

[백트래킹] 백트래킹의 설명과 간단한 예제풀이

백트래킹(Backtracking) 1. 백트래킹이란? 백트래킹은 알고리즘 기법 중 하나로, 재귀적으로 문제를 하나씩 풀어가면서 현재 재귀를 통해 확인 중인 노드(상태)가 제한된 조건에 위배되는지 판단하고, 만약 해당 노드가 제한된 조건을 위배한다면 그 노드를 제외하고 다음 단계로 나아가는 방식이다. 가장 중요한 점은 제한조건을 위배한다면 그 노드를 제외한다는 점이다. 백트래킹은 현재 상태에서 다음상태로 가는 모든 경우의 수를 찾아서 이 모든 경우의수가 더 이상 유망하지 않다고 판단되면 이전의 상태로 돌아가는 것을 말한다. 여기서 더 이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기(pruning)라고도 한다. 따라서 한마디로 정의하면 DFS를 통해 모든 노드를 깊이 우선 탐색을 하면서 더 이상 필요..

[그리디 알고리즘] 그리디 알고리즘의 설명과 간단한 코테 예제풀이

그리디알고리즘(Greedy Algorithm) 그리디(Greedy)란 '탐욕스러운, 욕심 많은' 이란 뜻이다. 그리디 알고리즘은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방식이다. 하지만 순간의 최적의 선택을 한다고 해서 최종적인 해답이 최적이라는 보장이 없다. 따라서 그리디 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로도 최적인 문제들일때 그리디 알고리즘을 적용할 수 있다. 여기서 가장 중요한 점은 그리디 알고리즘을 이용하면 최적해를 찾지 못할 수 도 있다는 것을 항상 명심해야한다. 그렇다면 그리디 알고리즘을 적용하여 최적해를 구할 수 있는 문제는 어떤 조건을 만족할까? 1. greedy choice property : 현재 선택이 이 후의..

[브루트 포스] 브루트 포스의 설명과 간단한 코테 예제풀이

브루트 포스(Brute Force) 브루트 포스는 모든 경우의 수를 무식하게 탐색하면서 요구조건을 충족한 결과만 가져오는 것을 말한다. 이 알고리즘의 가장 큰 특징은 모든 영역을 전체 탐색 한다는 점이다. 전체를 탐색하는 방법에서 1. 선형 구조를 전체적으로 탐색하는 순차 탐색 2. 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS) , 너비 우선 탐색(BFS)가 기본적인 도구이다. 실제로 알고리즘을 풀때는, 이 문제가 브루트포스로 해결이 가능한지 확인 후 불가능하다면 어떤 알고리즘을 적용해서 시간복잡도를 줄이며 간단하게 짤 것인지 고민해야한다. (DP, 누적합 , 이분탐색 등등) 브루트 포스에 가장 대표적인 예제로 백준 블랙잭 문제가 있다. 2798번 블랙잭 문제 카지노에서 제일 인기 있는 게임..

성적 정렬하기 (내림차순)

문제 입출력 문제풀이 이 문제는 지난번에 만들었던 성적 정렬하기(오름차순)에서 내림차순으로 바꾸는 문제이다. 문제에서 내림차순으로 바꿀때 사용하는 방법은 Collections.reverseOrder() 함수를 사용하면 된다. 하지만 이때 주의 할점은 Collections.reverOrder() 함수는 Collection의 도움을 받아야 하기 때문에 기본형에는 사용할수 없고 Wrapper 클래스로 선언해야 한다. 따라서 int가 아닌 Integer로 선언해야한다. import java.util.Arrays; import java.util.Collections; class Main { public static void main(String[] args) { Integer array[] = {88, 50, 3..

성적 정렬하기 (오름차순)

문제 입출력 문제풀이 따로 정렬 알고리즘을 구현하지 않고 내장 메서드를 이용하는 것이기 때문에 Arrays.sort() 에 해당된 배열 인자값만 잘 넣어주기만 하면되는 간단한 문제이다. import java.util.Arrays; class Main { public static void main(String[] args) { int array[] = {88, 50, 38, 100, 90, 100, 99, 65}; System.out.println("정렬전 "+Arrays.toString(array)); Arrays.sort(array); System.out.print("정렬후 "+Arrays.toString(array)); } } 느낀점 자바에서 배열을 오름차순 정렬할때는 Arrays.sort() 함수를..

Java 자바의 배열 정렬(Sorting)

배열 정렬 int 배열 정렬 - 오름차순 , 내림차순 Array.sort()에 인자로 배열을 전달하여 주면 인자로 전달된 배열이 오름차순으로 정렬해준다. sort() 함수 내부에서 변수 arr의 순서를 변경해주기 때문에 따로 arr을 할당해 줄 필요도 없다 import java.util.Arrays; class Main { public static void main(String[] args) { int array[] = {88, 50, 38, 100, 90, 100, 99, 65}; System.out.println("정렬전 "+Arrays.toString(array)); Arrays.sort(array); System.out.print("정렬후 "+Arrays.toString(array)); } } 여..

랜덤숫자 생성후 최댓값 최솟값 출력

문제 입출력 문제 풀이 자바 100제에서 알고리즘 카테고리에 기초적인 문제이다. 단순히 배열을 생성하고 그 배열에 랜덤한 숫자를 넣어주고 그 배열에 인덱스 0부터 끝까지 하나씩 비교하여 최솟값과 최댓값을 찾아내면 된다. import java.util.Scanner; import java.util.*; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub int[] arr = new int[10]; for(int i=0; i