반응형 백준알고리즘39 그리디 알고리즘 greedy 알고리즘은 매 결정 순간 비용이 적은 것을 선택하는 알고리즘이다. 그리디 알고리즘은 이전의 탐욕 선택이 이후 선택에 영향을 주지 않는 문제에서 자주 사용된다. (독립적) 왜냐, 최적해에 근사한 값일 뿐 최적해를 만족하지 못한다. A-B가 B-C경로에 영향주지 않음. 또, 전체 최적해가 부분 문제에 대해서도 최적해를 만족하는 문제에서 사용된다. A-B 와 B-C은 전체인 A-C최적해의 부분 문제가 되기 때문에 그리디 알고리즘을 적용하기 적절한 문제다. 그렇지만 속도가 매우 빨라 동적계획법과 그리디 알고리즘이 혼용되어 쓰이기도 한다. 이제 그리디 알고리즘 풀어야지... 참고한 블로그 st-lab.tistory.com/143 2021. 4. 26. 백준알고리즘:p18870 좌표압축 분류: 정렬 ▶문제 입력받은 숫자의 순위를 정해서, 입력받은 순서대로 순위를 나타내면 된다. ▶통과 못한 코드_시간초과 //백준알고리즘 제출시 클래스 이름은 Main으로 바꿔야 됨 package sort; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; public class p18870 { //좌표정렬_시간초과 public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(.. 2021. 4. 8. 백준알고리즘:p10814 나이순 정렬 순서가 좀 바뀌었지만 풀긴 먼저 풀었었다. 여러 방식으로 풀어보느라 정리를 미뤄놨던 터라 분류: 정렬 ▶문제 ▶sort로 정렬 Comparator //백준알고리즘 제출시 클래스 이름은 Main으로 바꿔야 됨 package sort; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; import java.util.StringTokenizer; public class p10814 { //나이순 정렬 public static void main(String[] args) throws IOExceptio.. 2021. 4. 8. 백준알고리즘: p15649~15652 N과 M(1, 2, 3, 4) 분류: 백트래킹 처음에 백트래킹도 생소하고 어떻게 접근해야될 지 몰라서 다른 사람들이 어떻게 풀었는지 설명을 좀 찾아봤다. st-lab.tistory.com/114?category=862595 이 글에서 많이 도움을 받았다. 나중에 잘 모르겠으면 다시 보기... 백트래킹 설명과 dfs와의 차이점 등을 알 수 있었다. ▶문제15649 ▶코드 //백준알고리즘 제출시 클래스 이름은 Main으로 바꿔야 됨 package backtracking; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class p15649 { //1부터 N까지의 수로 M개 짜리 수열 모두 출력해라 publi.. 2021. 4. 8. 백준알고리즘:p11650, p11651 좌표 정렬하기 분류: 정렬 ▶문제 comparator를 이용해서 풀었다. comparator를 쓰려면 compare 메소드를 오버라이드 해줘야 한다. -comparator 인터페이스를 쓰는 경우 : 정렬 대상 클래스의 코드를 직접 수정할 수 없는 경우 -또는, 객체에 이미 존재하고 있는 정렬 기준과 다른 정렬 기준으로 정렬할 경우 ▶코드 //백준알고리즘 제출시 클래스 이름은 Main으로 바꿔야 됨 package sort; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; import java.util.Stri.. 2021. 4. 6. 백준알고리즘:p1427 소트인사이드 분류: 정렬 ▶문제 ▶코드1 아스키코드를 사용해서 풀었다. 크기가 10인 cnt배열을 만들고 s.charAt()으로 char-48인 인덱스에 +1 ( 문자 0~9 는 아스키코드값 48~59 ) 그리고 cnt배열을 거꾸로 돌면서 카운트값만큼 인덱스값을 출력,, //백준알고리즘 제출시 클래스 이름은 Main으로 바꿔야 됨 package sort; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class p1427 { //소트인사이드 public static void main(String[] args) { try.. 2021. 4. 6. 이전 1 2 3 4 ··· 7 다음 반응형
