본문 바로가기

Java78

[JAVA] Comparable 이란? Comparable = 기본적인 정렬기준을 구현 - Comparable 저게 끝이다. 자바에서 정렬이 가능한 객체는 모두 Comparable 을 구현하고 있다. 아래의 코드를 보자. 우리가 흔히 쓰는 Arrays.sort(); 도 역시 Comparable 을 구현한 클래스에 대해서 작동한다. 아래 코드를 보면 Integer 클래스는 인터페이스 Comparable 를 구현했다. - Comparable 구현 예시 Student 클래스를 하나 정의하자. height 는 키이고 score는 점수다. 그리고 Arrays.sort(); 를 이용해 정렬해보자. 그러면 아래와 같은 에러가 뜰것이다. 요약하면 Comparable를 구현하지 않은 클래스의 정렬을 시도해서 생겼다. 즉 정렬가능한 객체가 아니라는 소리다. 정.. 2021. 2. 19.
[JAVA] 백준 7562 - 나이트의 이동 ( BFS) www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net -이동할 방향 코드 작성 static int[] dx = {-1,-2,-2,-1,1,2,2,1}; static int[] dy = {-2,-1,1,2,2,1,-1,-2}; 10시 방향부터 시계방향으로 8가지 위치를 지정한 것이다. 예를 들어, 기존의 위치가 (x,y) = (10,10) 이라고 가정하자. ( x + dx[0] , y + dy[0] ) = 10시방향 좌표 ( x + dx[1] , y + dy[1] ).. 2021. 2. 18.
[JAVA] 백준 2583 - 영역구하기 ( BFS + 구현 ) www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net - 사각형 칠하기 위와 같이 m=5 이고 n=7인 배열에서 왼쪽 아래 좌표(0,2) 와 오른쪽 위 좌표(4,4) 를 가지고 사각형에 해당되는 부분은 어떻게 체크 할것인가? 의 전체 큰 배열의 이름을 arr 라고 하자. (0,2) 와 (4,4)가 주어졌을 때 결과적으로 체크 되는 부분은 다음과 같다. arr[1][0] , arr[1][1] , arr[1][2] , arr[1][3] arr[2].. 2021. 2. 15.
[JAVA] 백준 - 2548 키순서 ( 플루이드 외샬 or BFS) www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 플루이드 외샬 알고리즘을 적용하면 빠르게 풀 수 있는데 나는 쓰지 않았다. BFS 를 쓰면 더 빠를 거라고 생각했기 때문이다. 실제로 더 빨라서 전체 백준 차트에서 2등했다. (물론 메모리를 좀더 쓰긴 했지만..) (2020.02.13 기준) BFS 풀이법 - 1번 정점에서 BFS를 시작하여 1번보다 큰 정점을 체크한다. 여기서는 2,4,5,6번이 체크된다. - 2번 정점에서 BFS를 시작하여 1번보다 큰 정점을.. 2021. 2. 13.
[JAVA] 백준 11404- 플로이드(플로이드-외샬 알고리즘이란?) www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net -플로이드-외샬 알고리즘 " 모든 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘" -원리 정점 i 에서 정점 j 까지 거리 = X 정점 i 에서 정점 k까지 거리 = Y 정점 k에서 정점 j 까지 거리 = Z 라고 할때, X = min ( Y+Z , X ) 를 정의한 것이 플루이드-외샬 알고리즘이다. -구현 문제를 바탕으로 구현해보자. 정점이 1번 부터 5번까지 있다고 가정하자. "원리"에서 예시로 들었던.. 2021. 2. 8.
[JAVA] 전구와 스위치 (백준 2138) ( 그리디) www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는(1) 상태와 꺼져 있는 (0) 상태 중 하나의 상태를 가진다. i(1 2020. 10. 23.
[JAVA] 백준 - 동전0 - 11047 (그리디) www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net # 풀이 스택을 이용하여 가장 단위가 큰 동전 부터 사용하면된다. 동전의 단위는 서로 배수 관계이므로 큰 동전 부터 사용해도 된다. 만약 동전끼리 배수 관계가 아니라면 적용되지 않는다. 예를 들어) ( 1, 3, 5, 6 ) 가 있다고 해보자. 8 원을 만들기 위해 큰 동전 부터 사용한다면 6원 1개 1원2개로 총 3가지 동전을 사용한다. 하지만 .. 2020. 10. 16.
[JAVA] 백준 - 4연산 14395( BFS) www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net 처음 숫자가 s 라고 할때 다음 숫자는 = s + s || s - s || s * s || s / s 이다. '-' 와 '/' 는 반드시 0 과 1 이된다. 사실 t 가 0 이면 '-' 를 반환하면 되고 t가 1이면 '/'를 반환하면 된다. 그렇다고 해서 '/' 와 '-' 를 연산에서 제거하면 안된다. 모든 경우의 수를 살펴야 한다. 예를 들어 s = 10 / t = 8 이라면 (((10 / 10) + .. 2020. 10. 16.
[JAVA] 백준 - 적록색약 10026 ( BFS ) www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 단순히 그룹으로 묶어주고 그룹이 몇개 나오는지 BFS 를 이용하여 해결한다. 관건은 적록색약이 있는 경우 초록색과 빨간색을 어떻게 처리 할지다. 본인은 아래 코드 처럼 처리하였다. if((curColor=='R' || curColor=='G') && (otherColor=='R' || otherColor=='G')) return true; else return curColor == otherColor; .. 2020. 10. 16.