알고리즘

문제 풀이 문제를 바로 이해하진 못했지만 이해만 한다면 쉽게 풀 수 있는 문제이다. 후위 표기식은 연산이 뒤에 등장하는 식으로 ABC*+ 라면 ABC*이 A?(B*C)가 된뒤에 +가 오게 되면 A+(B*C) 가되는것이다. 쉽게 말해 문자가 아닌 연산이 오게 되면 앞에 문자 2개를 연산에 의해 계산해주면 된다. 연산이 나오면 최근에 PUSH한 값을 연산해 주는 것이므로 Stack을 사용하면 쉽게 풀 수 있다. import java.io.*; import java.util.*; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamRea..

문제: 백준 1406 에디터 풀이 처음에 ArrayList로 풀었다가.. 시간초과가 나오고.. 다시 LinkedList로 바꿧지만 역시 시간초과로 결국 Stack를 이용하여 풀었더니 드디어 통과 되었다. 스택 2개를 이용해서 풀건데 lStack에는 커서의 왼쪽값들을 넣어줄거고 rStack에는 커서의 오른쪽 값들을 넣어줄거다. 초기에 입력받은 값들은 커서의 왼쪽에 있기때문에 lStack에 넣어준다. 입력받은 테스트 횟수만큼 반복할건데 L,D,B,P에 따라 if문을 추가한다. 스택은 FILO구조를 갖고 있기때문에 커서의 왼쪽값인 lStack의 값들을 rStack에 담아준다. rStack에 있는 값을 꺼내면서 출력한다. import java.io.*; import java.util.*; class Main {..

풀이 문제는 그렇게 어렵지 않다. 공백이 나올 때마다 그전까지 나온 단어를 뒤집어 주기만 하면 되는 문제이다. 첫 번째 풀이는 String[]에 공백 단위로 끊어 넣어준다. StringBuilder의 reverse()를 이용해 문자열을 뒤집어 준 뒤 다시 배열에 넣어준다. 배열을 출력한다. import java.io.*; class Main { public static void main(String args[]) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //테스트카운트를 입력받는다 int N = Integer.parseInt(br.readLine()); for (int j = 0;..

삽입 정렬(Insertion Sort) 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열이라는 가정하에 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하며. 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다. -정렬 방식삽입 정렬은 두 번째 자료부터 시작하며 왼쪽 값과 비교하여 왼쪽 값보다 작다면 교환한다. 하지만 앞쪽은 이미 정렬되어있다는 가정하에 비교하므로 왼쪽 값과 비교하여 왼쪽 값이 더 작다면 교환하지 않고 끝낸다. public class InsertionSort { public static void main(String[] args) { int[] arr = {7, 5, 2, 4, 3, 1, 9, 6, 0, 8}; insertionSort(arr); for ..

Selection Sort [선택 정렬] 선택 정렬은 제자리 정렬 알고리즘의 하나로 입력 배열외의 다른 추가 메모리를 요구하지 않는 정렬방법이며 선택정렬은불안정 정렬이다. 배열에 앞에서부터 최솟값 또는 최댓값을 찾아 교환하는 방식의 알고리즘으로 선택 정렬의 과정은 이렇다. 주어진 리스트 중에 최솟값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)). 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. public class 선택정렬 { public static void main(String[] args) { int[] arr = {7, 5, 2, 4, 3, 1, 9, 6, 0, 8}; selectionSort(arr); for (int i : arr) { System.out.p..

유클리드 호제법 이 문제를 풀기 위해 최대공약수와 최소공배수가 필요했다. 두 수의 최대 공약수를 구하는 기본적인 방법은 소인수분해를 한 뒤 공통부분을 찾는 것이다. 하지만 이렇게 하면 시간 복잡도가 O(n)이 된다. 또한 알고리즘으로 소인수분해를 구현하는 거 또한 간편하지 않다. 유클리드 호제법이란 두 수의 최대공약수를 쉽게 구할 수 있는 방법으로 시간 복잡도를 줄여 간편하면서도 효율적인 알고리즘이다. 두 수의 최대공약수 찾는 법 유클리드 호제법은 (a, b) 두 수가 있을 때 a를 b로 나눈 나머지가 0이 아니라면 b에 나머지를 넣고 a에 원래 b에 있던 값을 넣어 나머지가 0이 될 때까지 구하는 방법이다. 즉 (a, b) a%b=r 일때 (a,b) , (b, r) 두 개의 최대공약수는 같다는 것이다...