[JAVA]/자바[JAVA] 백준

https://www.acmicpc.net/problem/2568전깃줄이 교차? 전깃줄이 교차한다는 것은 무엇일까?두 개의 전깃줄이 교차하려면 A의 위치와 B의 위치가 꼬여있어야한다. 예를 들어 임의의 두 전깃줄 a, b가 있다고 할때, a의 전봇대 A에서의 위치를 a1, B에서의 위치를 a2 라고 하고,마찬가지로 b1, b2 라고 했을 때, a1 > b1 이면 a2 a1 b2 일때,전깃줄이 꼬인다고 할 수 있다. 그렇다면 한 전봇대에 대해 오름차순으로 정렬한 다음,반대편 전봇대에 연결되어있는 위치가 "꼬여있는"지를 확인하면 된다. 예를 들어,주어진 예제 입력의 경우에서,전봇대 B의 위치에 대해서 오름차순으로 정렬을 한 후 전봇대 A의 위치를 살펴보자. index01234567B124678910A426..

https://www.acmicpc.net/problem/28872024.06.09 - [자료구조 및 알고리즘] - 자료구조 및 알고리즘 #14 - Union-Find (Disjoint Set) and an Application 자료구조 및 알고리즘 #14 - Union-Find (Disjoint Set) and an Application1. an Application Union-Find 를 알아보기 전에 이것을 언제 사용하는지를 먼저 파악하는 것이 좋아보입니다. MST(* Minimum Spanning Tree), 최소신장트리는 Spanning Tree 중에서 사용된 간선들의 가중치 합이 최hw-hk.tistory.com문제를 처음 보자마자 최소 신장 트리 문제임을 알았다.하지만 기존의 최소 신장 트리..

https://www.acmicpc.net/problem/16566문제는 단순해 보였다.처음 문제를 읽자 마자 생각한 것은 다음과 같다.리스트에 민수가 뽑은 숫자들을 담는다.리스트를 정렬하고 철수가 보여주는 카드보다 큰 수의 숫자를 뽑는다.뽑은 숫자는 삭제하고 2번으로 돌아간다. 왜 리스트를 정렬하는가? 리스트를 정렬하지 않으면 철수가 보여주는 카드보다 큰 수들 중 가장 작은 수를 찾기 위해서는 선형탐색밖에 답이 없기 때문이다. 선형탐색의 시간 복잡도는 O(N) 이므로, 최대 4,000,000 x 10,000 = 40,000,000,000 의 연산이 필요하다. 대충 100,000,000 에 1초 이므로, 이는 반드시 시간초과가 발생한다. 하지만 정렬을 한다면 다르다. 정렬이 되어있는 자료구조에 대해서는 ..

https://www.acmicpc.net/problem/16236BFS 를 통해 최단거리를 구하는 문제인 것 같다.다만 같은 거리일 경우의 우선순위(* row index 가 작은게 먼저, col index 가 작은게 먼저) 가 추가적으로 붙어있다.그 외의 것들은 크게 다르지 않다. 이런식으로 쭉 풀어봤는데... 메모리 초과가 떴다. 처음이었다. Point 클래스를 너무 남발하면 그럴 수 있다더라...앞으로는 메모리도 좀 신경쓰면서 구현해야겠다. 처음에는 모든 가능한 노드에 대해 Point 객체를 생성해서 비교했었다. 이런 불필요한 인스턴스들은 메모리를 많이 잡아먹을 수 있다. 그래서 이동 가능할 수 있는 노드들을 Point 객체가 아닌, 그냥 row index 와 col index 를 이용했다. 또한 ..

https://www.acmicpc.net/problem/1167아.. 어렵다 처음 생각으로는 DFS 를 여러번 수행해서 각 노드에 대한 최대 길이를 구하려고 했지만N = 100,000 이고 DFS 를 각 노드에 대해 수행하면 빨라야 O(N^2) 이기 때문에 당연히 시간초과가 발생하는거였다.(* 10,000,000,000 번의 계산이 필요한데 일반적인 CPU 는 1억번의 연산 당 1초가 걸리기 때문에 100초가 걸린다.) 어쩔 수 없이 구글링을 해봤는데단 두 번의 DFS 만으로 트리의 지름을 알 수 있는 방법이 존재했다. 트리의 성질을 이용하면 가능한데, 자세한 증명은 아래 접은 글에 첨부해놓았다.더보기https://velog.io/@besyia0k0/Algorithm-diameter-of-tree [알..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 배열로 입력이 들어오고 하나 하나 찾아가는 느낌이 그래프와 BFS 로 풀면 되겠다고 생각했습니다. 토마토는 익은 토마토 주변 상하좌우로 안 익은 토마토들을 익게 만드는 것 또한 BFS 라고 생각했습니다. 여기에서 문제는 끝까지 탐색했을 때 모든 토마토가 안 익는 경우가 생기고 이를 어떻게 일반적인 경우와 구분할 것 인지 탐색이 끝까지 진행 되었을 때 며칠이 지났는지 어떻게 알 수 ..

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 리스트를 만들어 요소들을 저장하고 각 명령에 맞게 리스트의 값들을 수정하는 문제입니다. 해당 문제에는 2 가지의 명령이 있습니다. R: 배열의 순서를 뒤집습니다. D: 가장 앞에 요소를 삭제합니다. 만약 배열에 요소가 없을 때, D 명령을 수행하려 하면 error 를 출력하고 아닐 경우는 결과 배열을 출력합니다. 특이한 점은 배열의 요소들을 입력해줄 때 [ ] 를 포함하여 입력해준다는 점 입니다. [ ] 처리를 잘 하는 것이 중요해보입니다. 또한 R 연..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 2178 미로 찾기와 비슷한 input 이라서 "DFS BFS 를 활용하면 되지 않을까" 먼저 생각했습니다. 2178 번 문제와 비슷하게 시작하는 노드에서 부터 동 서 남 북으로 이동 가능한데, 한 번 방문한 곳은 더이상 방문하지 않는다. 0이 적혀있는 곳은 방문하지 않는다. 를 지켜가며 DFS 든 BFS 든 해서 노드의 개수를 구하는 방식으로 풀었습니다. 2178 번 문제와 달리 해당 문제에서는 ..