[JAVA]/자바[JAVA] 백준

https://www.acmicpc.net/problem/16946쉬워보였다. 처음에는 BFS 처음에는 그냥 속는셈 치고 문제 그대로 풀어보았다.주어진 입력을 전부 탐색하면서 벽(* 1)을 만났을 때마다 BFS 를 해준다. 그리고 이동할 수 있는 칸(* 0)의 개수를 구해서 저장해준다. 하지만, 당연히,시간초과 생각해보면,N이 최대 1,000 이고, BFS 는 최대 O(NlogN) 의 시간복잡도를 갖는다.따라서 모든 맵의 노드들에 대해(* N^2) 벽(* 1)을 만나면 BFS(* NlogN) 을 진행하므로 최대 시간복잡도는 N^3 * logN(* 10억, 10초)을 갖는다. 시간 단축을 위해서는? 시간 단축을 위해서는 중복 계산을 피해야한다. 다음과 같은 입력이 들어왔다 가정해보자4 51100100111..

https://www.acmicpc.net/problem/28707처음에는 BFS를 생각했었다.하지만 정답은 역시 다익스트라였다. BFS? 한 상태에서 여러 가지 경우로 뻗어 나갈 수 있고, 최단 거리나 최소 비용을 원하는 것이므로 처음에는 BFS 를 생각했었다.주어진 배열의 최대 길이가 8이니, 가능한 모든 배열 원소들의 조합의 경우의 수는 8! = 40320 개이다. 제한시간은 1초이므로, 중복을 제외할 수 있다면 충분하다고 생각했다. 그러기 위해서는 각 배열의 상태가 하나의 노드가 되어야했다.배열이 하나의 노드가 되어 탐색이 되어야한다는 것이다. Hash? 그래서 처음 생각한 것은 Hash 였다. 해쉬값을 통해 배열을 임의의 int 타입 데이터로 변환한다면해쉬값을 내용으로 하는 노드를 만들 수 있을..

https://www.acmicpc.net/problem/1509분할정복이다. 문제 이해 우선 팰린드롬 분할의 수가 최소가 되려면 일반적으로 팰린드롬 분할들의 길이가 길면 된다.팰린드롬 분할들의 길이가 길면 당연히 분할의 수가 반대로 줄어들기 때문이다. 그렇다면 팰린드롬의 길이를 늘릴 방법은 무엇일까? 우선 팰린드롬이 되는 조건먼저 살펴보자 조건 팰린드롬은 첫 문자와 마지막 문자가 일단 같아야한다.예를 들어 {A, B, A} 는 팰린드롬이다. 첫 문자와 마지막 문자가 같기 때문이다.{A} 는 팰린드롬이다. 첫 문자이자 마지막 문자가 A로 같기 때문이다. 하지만, 위 조건만으로는 부족하다.예를 들어 {A, B, C, A} 는 팰린드롬이 아니다. 첫 문자와 마지막 문자가 같아도 말이다. 그 다음 조건으로는 ..

https://www.acmicpc.net/problem/2098그냥 외판원 순회문제 .. 근데 나는 몰랐고 ;; 외판원 순회 외판원 순회 문제는여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 때, 모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서를 구하는 문제이다. 그래프 이론의 측면에서 해당 문제는 가장 작은 가중치를 갖는 해밀턴 순환을 구하는 문제로 치환할 수 있다. 해당 문제는 NP-난해라는 것이 증명되었다는 점에서 유명하다. NP-난해 NP-난해, NP-hard 는 NP에 속하는 모든 판정 문제를 다항 시간에 풀 수 없는 문제들의 집합이다.다항 시간이란 우리가 흔히 말하는 시간복잡도의 형태인 O(N) 과 같은 형태이다. 미리 말하자면,..

https://www.acmicpc.net/problem/22632024.06.02 - [자료구조 및 알고리즘] - 자료구조 및 알고리즘 #13 - Tree Traversal and Parsing 자료구조 및 알고리즘 #13 - Tree Traversal and Parsing1. Tree traversal 트리의 모든 노드들을 방문하는 과정을 트리 순회, Tree Traversal 이라고 합니다. 이때 방문은 정말 "방문" 만 하는 것이 아니라 해당 노드에서 어떤 수행을 하는것을 의미합니다. 일hw-hk.tistory.com에 나온 Inorder 와 Postorder 를 통해 Preorder 를 추론하는 방법을 그대로 사용했다.구현Preorder 는 root 가 가장 먼저 나오는 방식의 순회이다.Post..

https://www.acmicpc.net/problem/13460 어떤 상태에서 나아갈 수 있는 상태가 여럿이 있고, 이를 모두 탐색을 해야하는 경우는(* 반드시 그래프가 아니더라도)너비 우선 탐색으로 풀 수 있다.(* 아니면 A* 알고리즘도 생각해볼 수 있다.) 시간복잡도와 공간복잡도 너비 우산 탐색을 사용할 때는 시간복잡도와 공간복잡도가 중요하다. 최대 10번의 탐색이 이루어져야 하고,현재 상태에 대해서 최대 두 방향의 가능성이 존재하기 때문에(* 이전에 선택했던 방향과 그 반대 방향은 제외한다. 예를 들어 왼쪽으로 기울였었는데 다시 왼쪽으로 기울이거나 오른쪽으로 기울이는건 의미없는 반복이다.)최대 4(* 처음은 네 방향 모두 가능하기 때문에) * 2 * 2 * 2 * ... * 2 ≒ 2^11 =..

https://www.acmicpc.net/problem/17143그냥 구현문제이다.근데 시간복잡도 이슈가 있는... 처음 생각 그냥 행과 열의 크기가 최대 100이므로 시간복잡도를 생각하지 않고 구현을 해봤다.상어들이 낚시꾼에 의해 잡히기도 하고 서로 잡아 먹히기도 하니, 삭제가 잦을 거라고 판단 하고,LinkedList로 상어들을 저장해주었다. 그 후 상어들이 이동하고,LinkedList안에 있는 상어들 중 같은 위치에 있는 상어들을 찾아서(* 물론 선형으로)잡아 먹는 것 까지 구현을 했다. 하지만, LinkedList의 최대길이는 100 x 100 으로 10,000 이고, List안에 있는 상어들끼리의 관계를 파악하기 위해두 번 for문을 돌리면 10,000 x 10,000 으로 반드시 시간초과가 ..

https://www.acmicpc.net/problem/140032024.07.03 - [자바[JAVA]/자바[JAVA] 백준] - BOJ(백준 온라인 저지) 2568번 with 자바[JAVA] BOJ(백준 온라인 저지) 2568번 with 자바[JAVA]https://www.acmicpc.net/problem/2568전깃줄이 교차? 전깃줄이 교차한다는 것은 무엇일까?두 개의 전깃줄이 교차하려면 A의 위치와 B의 위치가 꼬여있어야한다. 예를 들어 임의의 두 전깃줄 a, b가 있다고hw-hk.tistory.com에서 사용했던 LIS 알고리즘을 이용하면 쉽게 풀 수 있다. 코드import java.io.BufferedReader;import java.io.IOException;import java.io.I..