전체 글 (89) 썸네일형 리스트형 JAVA - 백준 알고리즘 - 11399 ATM 이 문제는 백준 단계별 풀어보기 그리디알고리즘에 분류된 문제이다. 이 문제는 정렬을 사용하면 쉽게 풀 수 있다. N번째 사용자가 ATM사용을 마무리하는 시간은 첫번째 사용자가 이용하는데 걸린 시간 + 두번째 사용자가 이용하는데 걸린 시간 + 세번째 사용자가 이용하는데 걸린 시간 + --- N번째 사용자가 이용하는데 걸린 시간 이기때문에 오름차순 정렬시 N번째 사용자가 ATM사용을 마무리하는 시간이 최소가 된다. Arrays.sort() 를 이용하여 오름차순 정렬을 하였다. 만약 오름차순이 아닌 다른 정렬기준을 사용하는 문제였다면 Comparator을 이용하여 정렬기준을 구현하면 된다. import java.io.BufferedReader; import java.io.IOException; import j.. JAVA - 백준 알고리즘 - 1541 잃어버린 괄호 이 문제는 백준 단계별로 풀기 그리디알고리즘에 분류된 문제이다. 이 문제를 푸는 방법은 "-" 부호 뒤에 온 숫자들을 모두 빼주면 된다. StringTokenizer 를 이용하여 "-" , "+" 를 기준으로 숫자들을 잘라주었다. "-" 부호를 기준으로 앞 쪽에 있던 숫자들 , 첫번째 Token의 숫자들 더해주고 "-" 부호를 기준으로 뒷 쪽에 있던 숫자들 , 두번째 Token의 숫자들은 마이너스를 해주었다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int result; p.. JAVA - 백준 알고리즘 - 1931번 회의실 배정 백준 단계별 풀기에 그리디알고리즘으로 분류되어있는 문제인데, 간단하게 풀릴줄 알았지만 생각보다 시간이 오래 걸렸다. Comparator의 정렬함수를 적절히 구현하여 간단하게 답을 구했다. 정렬 방식 1. 끝나는 시간이 같을때 => 시작하는 시간이 이른 순서대로 2. 끝나는 시간이 다를때 => 끝나는 시간이 이른 순서대로 1번을 정렬해주는 이유는 시작시간과 끝나는 시간이 같은 경우를 고려해주기 위해서이다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; import java.util.String.. [코딩테스트][알고리즘] 3. Greedy(그리디) Greedy 알고리즘은 현시점의 최적해를 찾는 것을 통해 문제의 최적해를 구하는 것이다. 문제 P 를 여러 단계로 나누어서 해결해보자. 각 단계는 P1 , P2 , P3 .... P이라고 한다면 그리디 알고리즘으로 문제를 풀기 위해서는 P1, P2, P3 에 적용한 조건들이 모든 P에 대해서 똑같이 적용되어야 한다. 문제를 보고 가장 먼저 떠오르는 방법(가장 쉽게 떠올릴수 있는 방법)이 그리디알고리즘 일 확률이 높다. 추천문제 : 1. https://www.acmicpc.net/problem/15655 2. https://www.acmicpc.net/problem/1080 3. https://www.acmicpc.net/problem/1969 4. https://www.acmicpc.net/problem.. [코딩테스트][알고리즘] 2. Backtracking(빽트레킹) Backtracking 이란 알고리즘은 거창하게 보이지만 사실 별거 없다. 하지만 backtracking 알고리즘이 사용되는 문제는 몇 문제를 제외하고는 난이도가 엄청 높다고 한다. Backtracking은 완전탐색을 진행하다가 조건에 맞지 않는 경우 탐색을 중단하고 이전 단계로 돌아가는 방법이다. 빽트레킹의 경우에 시간복잡도를 계산하기는 힘든 경우가 많다. 얼마나 많은 조건을 추가하느냐에 따라서 실행속도가 달라진다. 추천문제 : 1. https://www.acmicpc.net/problem/15655 2. https://www.acmicpc.net/problem/9663 3. https://www.acmicpc.net/problem/2580 4. https://www.acmicpc.net/problem.. 코딩테스트를 위한 자바(java) 순열함수 구현 - 3 c, c++ 과 같은 다른 언어에서는 라이브러리로 순열함수를 지원하지만 자바에서는 순열함수 라이브러리를 지원하지 않아 직접 구현해야한다. N개의 원소 중 M개를 뽑아 나열하는 모든 경우를 구하는 함수를 구현하는 코드는 다음과 같다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.StringTokenizer; public class P15654 { static int N, M; static ArrayList list = new ArrayList(); sta.. 코딩테스트를 위한 자바(java) 정렬 - 2 오름차순 정렬하기 public static void main(String[] args) { ArrayList list = new ArrayList(); list.add(3); list.add(10); list.add(1); list.add(4); Collections.sort(list); for(int i = 0 ; list.size() > i ; ++i) { System.out.println(list.get(i)); } // 결과 = 1 3 4 10 } 내림차순 정렬하기 public static void main(String[] args) { ArrayList list = new ArrayList(); list.add(3); list.add(10); list.add(1); list.add(4); Col.. [코딩테스트][알고리즘] 1. Brute Force(브루트포스 , 완전탐색) brute force는 완전 탐색이라고도 불리며, 모든 경우의 수를 직접 대입해보는 방법으로 가장 간단하게 문제를 풀 수 있는 방법이다. 풀이법이 잘 생각나지 않는 문제라면, 완전 탐색을 이용해 코딩을 한 후 최적화하는 과정을 사용한다면 문제를 해결에 도움을 받을 수 있을 것이다. 완전 탐색의 시간 복잡도는 주로 O(N!), O(2^N)이다. 시간 복잡도를 알고 있으면, 문제의 조건을 보고 필요한 알고리즘을 유추하는 방법도 있다고 하니 시간 복잡도에 대해 알아놓으면 좋을 것 같다. 완전 탐색은 반복문을 이용하는 방법, 재귀 함수를 이용하는 방법이 있는데 보편적으로 사용되는 것은 재귀 함수라고 한다. 반복문의 경우 길이가 변하는 문제를 다룰때 구현이 복잡해진다는 단점이 있다. 초보자의 경우에는 재귀함수가 .. 이전 1 ··· 8 9 10 11 12 다음