백준 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

비결정적 유한 인식기(nfa)

비결정적 유한 인식기(nfa)는 다음과 같이 정의 된다. $$ M=(Q,\Sigma,\delta,q_0,F)$$ Q,∑,q_0,F는 dfa에서와 같이 정의되고, δ는 다음과 같다. $$\delta : Q * (\Sigma \cup \{\lambda\})->2^Q$$ 내부 상태 Q에서 람다를 포함한 심벌들의 전이함수는 Q의 멱집합이 될 수 있다. 무슨 뜻이냐면 내부상태 q_0에서 다음과 같은 전이 함수가 있다 가정했을때, 다음상태를 여러개가 될 수 있다는 뜻이다. $$\delta(q_1,a)=\{q_0,q_2\}$$ 즉 dfa는 방향 그래프에서 현재 상태는 하나의 심벌에 대해 하나의 간선만 진출 간선만 가질수 있지만, nfa에서는 여러개의 진출 간선을 가질수 있다는 것이다. 또한 nfa는 λ(람다)를 허용..

• format_list_bulleted 계산이론
• · 2021. 4. 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

유한 오토마타 -결정적 유한 인식기(dfa)

결정적 유한 인식기, 줄여서 dfa는 유한개의 상태를 가지고 있는 오토마타다. dfa는 다음과 같이 정의 될 수 있다. $$M=(Q,\Sigma,δ,q_0,F)$$ Q는 내부 상태, 즉 그래프로 치면 노드에 해당하고, ∑는 심벌들의 유한집합, 즉 방향 그래프의 간선에 해당한다. 또한 δ는 전이 함수이고, q_0은 처음 시작하는 지점, 즉 입력을 받는 지점을 나타낸다. F는 승인상태들의 집합이다. 승인상태는 이중 원으로 표시한다. 전이함수는 다음과 같이 표기한다. $$\delta(q_0,a)=q_1$$ 상태 q_0에 a가 입렵될 시 q_1상태로 전이 한다는 뜻이다. 이를 가시적으로 표현하기 위해 보통 전이 그래프를 사용해서 표시한다. 확장 전이함수를 사용해 함수를 나타내는 경우도 있다. $$\delta(q..

• format_list_bulleted 계산이론
• · 2021. 4. 5.
• textsms

백준 2108번 통계학(Java)

보기엔 쉬워보였지만 막상 풀어보니 최빈값 구하는데 시간이 매우 많이 들었다. 산술평균은 Math.round()를 써서 반올림을 했다. 최빈값을 제외한 나머지는 정렬해서 정렬하 위치에 값에 따라 계산을 해 풀었다. 이 문제의 핵심인 최빈값은 다른 풀이들은 모두 int형 8001개의 배열에 각 index에 해당하면 값을 +1씩 해주는 식으로 풀었지만, 나는 그게 웬지 싫어서 다른방식으로 풀어보았다. 백준에서는 시간오버가 뜨긴 했지만 작동은 잘 되긴 한다. 최빈값 풀이 방법 배열 list가 있다고 하자 1 3 6 3 2 4 1) 이 배열을 Arrays.sort(list)로 정렬 1 2 3 3 4 6 2) 정렬을 한 후 중복되지 않는 수의 배열과 해당 수들에 개수의 배열을 만든다. num_list count_l..

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