백준 15649번 : N과 M(1)

백트래킹 문제의 가장 첫번째에 있는 문제. 매우 쉬울줄 알았으나, 생각보다 어려웠다. 백트래킹을 구현하는것 자체가 처음이니.. 백트래킹이란? 깊이 우선탐색을 하는것 처럼 변수에 허용되는 값을 하나씩 대입서 조건을 만족하지 않을것 같은 경우 해당 경로는 가지 않고 전 노드로 돌아가는 기법이다. 따라서 반복의 횟수를 줄일수 있다. 간단핟게 풀이를 설명하자면 출력할 수열의 길이를 가진 배열 하나와, 숫자의 사용여부를 표시하기 위한 배열을 하나만들고, 사용 여부 배열이 false인 index값을 출력할 배열에 입력하고 다시 메소드를 불러서 반복한다. 이때, 깊이가 출력할 수열의 크기가 같아지면 출력을 하고 전상태 노드로 돌아간다. import java.util.Scanner; public class Main {..

• format_list_bulleted Algorithm/백준
• · 2021. 5. 14.
• textsms

백준 18870번: 좌표 압축

문제를 이해하는데 시간이 꽤 걸렸다. 문제를 설명하자면, 입력 받은 수가 해당 입력받은 수들의 배열에서 자신보다 적은 수는 몇개가 있는지를 구하는것이다. 이때, 중복은된 수는 제외한다. 즉 2,1,1,4 이렇게 입력을 받으면 2를 압축시키면 1이 된다. 자신보다 작은 수 1이 있기 때문이고, 중복은 제외하기 때문이다. 푸는 방법은 처음에는 카운팅 정렬로 풀으려고 했지만 카운팅은 딱히 의미가 없기에 중복되지 않는 수를 가지는 배열을 만들고, 오름차순으로 정렬을 한 후 입력받은 배열에 해당하는 값을 중복되지 않는 배열의 값이 같은 인덱스를 출력하는 식으로 풀었다. 다만 이 알고리즘은 풀리기는 하나 시간초과가 뜬다. 아무래도 수가 넓게 퍼져있으면 그만큼 시간이 오래걸려서 그런듯 하다. import java.u..

• format_list_bulleted Algorithm/백준
• · 2021. 5. 12.
• textsms

백준 1181번: 단어정렬(Java)

글자수 순서대로 오름차순으로 정렬하되, 글자수가 같으면 사전순대로 정렬하는 문제. 단 같은 글자는 한번만 출력한다. Comparator를 사용해 정렬하지만 문자열을 정렬할때능 CompareTo를 사용해 정렬한다. CompareTo는 비교하는 객체가 비교하려는 객체보다 앞에 있거나 같은 위치에 있다면 음수와 0을 반환하지만 뒤에 있다면 양수를 반환한다. 따라서 사전순서대로 정렬을 할 수 있다. 그리고 같은 단어는 한번만 출력하면 되기에, 정렬을 한다음 출력한 단어를 저장하고 저장한 단어와 출력한 단어를 비교해 같지 않다면 출력을 하는 식으로 했다. import java.util.Arrays; import java.util.Scanner; public class Main { public static void..

• format_list_bulleted Algorithm/백준
• · 2021. 5. 8.
• textsms

백준 11651번 좌표정렬하기2

11650번의 반대버전. 따로 설명이 필요 없을듯 하다. 그냥 리턴하는 값만 바꾸면 된다. import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner=new Scanner(System.in); int n=scanner.nextInt(); int[][] arr=new int[n][2]; for(int i=0;i{ if(x1[1]==x2[1]) return x1[0]-x2[0]; else return x1[1]-x2[1]; }); for(int i=0;i

• format_list_bulleted Algorithm/백준
• · 2021. 5. 7.
• textsms

백준 11650번 좌표정렬하기(Java)

이번 문제를 통해 자바 기본기를 확실히 가져야겠다는 생각이 들었다. 정확히 어떤 메소드가 어떤 역할을 하고 어떤것을 리턴하는지 등등.. 이 문제는 x값을 기준으로 정렬을 하되, x값이 동일하면 y값 순서대로 오름차순으로 정렬하는 문제다. 처음에는 x와 y를 변수로 가지고있는 class를 만들어서 정렬을 했다. 그럴경우 정렬 알고리즘을 통해 정렬을 했어야 했는데, 퀵, 힙정렬등을 적용시켜봤지만, 전부다 시간초과가 떴다. 따라서 다른 정렬방법이 필요했는데, Comparator를 사용해서 정렬을 했다. Comparator은 sort에서 정렬을 할때 사용하는데, 어떤식으로 정렬을 할지 사용한다. Comparator은 두개의 객체를 받고, 정수를 리턴한다. 리턴값이 음수,0일경우에는 두개를 바꾸지 않고, 양수일경..

• format_list_bulleted Algorithm/백준
• · 2021. 5. 7.
• textsms

백준 1427번 소트인사이드(Java)

수를 입력받고, 그 수를 내림차순으로 정렬하면 되는 문제. 수를 정렬하려면, 각 숫자를 나눠야 하는데, 정수형은 일일히 나누려면 각 자릿수로 나눠야 하기에 String형태로 받고, split로 나눈후, 다시 정수형으로 변환 후 정렬을 해주었다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Collections; public class Main { public static void main(String[] args) throws IOException { BufferedReader br=new BufferedRea..

• format_list_bulleted Algorithm/백준
• · 2021. 4. 7.
• textsms