알고리즘 (25) 썸네일형 리스트형 백준 3176번(JAVA) 백준 문제중 11438번 LCA2가 있는데, 트리를 타고 올라갈때 한 칸 씩 올라가는게 아니라 2의N승씩 올라가는 빠른 LCA가 있다. 밑에 문제를 풀 줄 안다면 이번 3176번도 손 쉽게 풀 수있다. https://www.acmicpc.net/problem/3176 3176번: 도로 네트워크 첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양 www.acmicpc.net 빠른 LCA탐색 문제는 부모를 2의N승 부모를 저장한다. 예를들어 위 그림과 같은 트리가 있다고 가정해보자. 기존에는 바로 위의 부모만 저장했다. 그래서 .. 유니티 모바일에서 네트워크 연결 확인 과정은 많이 생략했지만 이미 생각한 곳까지는 다 구현해서 스토어에도 내놓았다. 처음 작품이니만큼 정말 많이 부족하지만 일단 완성했다는 것에 의미를 둔다. 그런데 출시해놓고 보니깐 wifi,data연결을 체크를 안 했던 것이 생각났다. 로그인도 해야되고 스테이지를 깨거나 죽었을때 계속 DB에 접근해야하는데 네트워크 상태를 확인 안 해주다니 말이안된다. 계속 wifi,data가 연결되어 있는지 확인하게 코드를 짜보겠다. void Update() { if(Application.internetReachability==NetworkReachability.NotReachable)//인터넷 연결이 안되어있다면 { } } 구글링 하니 위에 처럼 하면 네트워크를 체크 할 수 있다고 했다. 하지만 좀 더 알아보니 저 방식.. 백준 11003번(JAVA) 문제가 많이 더럽다. 로직이나 알고리즘을 요구한다기보단 어떻게든 시간을 줄여야한다. 빠른 입출력을 요구하고 덱을 활용하는데 add가 아닌 offer를 쓰고 poll이아닌 remove를 쓰고 peek이 아닌 get을 쓰고 문제 자체는 어렵지 않다. 뭐 슬라이딩 윈도우라는 이름이 있다는데 그런거 잘 몰라도 충분히 풀 수 있다. 필자는 솔직히 이 로직 하나만 봤을때 이게 플레 5문제인가 싶다. 우선 덱을 활용하는 문제인데 앞에서 뒤로 갈때 오름차순이다. 출력할땐 당연히 맨 앞의 숫자를 출력하면 된다. 이 때 맨 앞의 숫자가 주어진 범위를 벗어났으면 맨 앞의 숫자를 삭제해준다. 입력을 받을 땐 while문을 써서 맨 뒤에 숫자가(q.getLast()) 입력할 숫자보다 작을 때 까지 계속 q.removeLast(.. 백준 17472번(JAVA) 이번에 푼 문제는 크게 3가지 단계를 걸치면 된다. 1.섬별로 번호 붙이기 2.섬간의 다리(간선)정보 넣기 3. 2번을 통해 나온 섬간의 간선정보를 바탕으로 프림알고리즘을 수행하여 최소스패닝트리, 즉 각 섬을 모두 연결하는데 필요한 최소한의 비용을 구한다. 섬별로 번호를 붙이는건 어렵지 않다. 0이아닌 땅을 밟으면 BFS를 실행해주어 연결된 모든 1을 한 섬으로 지정한다 이 때 변수 islans_cnt변수가 BFS를 실행할때마다 +되어서 번호를 붙여준다. 그 후 섬간의 다리 정보를 입력받는데 꽤나 까다로운 조건이 붙어있다. 그렇기에 그점에 잘 유의해서 if문을 작성해준다 필자는 오른쪽,왼쪽,아래쪽,위쪽 4개의 for문을 사용했는데 이걸 한 개의 for문으로 줄일 수 있으면 좋겠다. 마지막으로 프림알고리즘.. 백준 11562번(JAVA) 플로이드 와샬 문제이다. 항상 플로이드 와샬은 간선의 가중치를 행렬에 저장하는 식이었는데 이번에는 간선의 가중치가 아니라 다르게 접근하면 된다. map[n+1][n+1]을 일단 Integer.MAX_VALUE로 채워준다. map[n+1][n+1]은 long형식으로 설정해줘야지 오버플로우가 안 발생한다. 예를 들어 입력을 받을때 u에서 v로가는 일방통행 도로가 있다고 하면 map[u][v]=0이다. 하지만 map[v][u]는 어떻게 설정해야 할까 일방통행 도로를 양방향으로 바꿔줘야한다. 즉, u에서 v로가는 일방통행도로 1개를 양방향으로 바꿔주면 되므로 map[v][u]=1이다. 입력을 받을때 이 점을 유의해서 받아준다. 그 후 3중 for문을 실행해준다. 한 기점(내 소스코드에서는 i로 설정) map[j.. 백준 14442번(JAVA) 벽 부수고 이동하기2 문제이다. 벽 부수고 이동하기1문제랑 매우 유사하기 때문에 같이보면 좋을듯 하다. www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제풀이는 간단하다. 객체를 생성할줄만 알면 문제는 매우 쉬워진다. 객체에는 좌표를 나타내는 x,y 그리고 몇칸째이동중인지를 나타내는 count 마지막으로 벽을 몇개를 부쉈는지를 나타내는 crash변수를 만들어낸다. 또한 BFS에서 필수인 방문체크 배열은 visited[i][j][k].. 백준 17404번(JAVA) 골드이상의 DP문제는 3차원으로 DP배열을 구현해서 문제푸는것이 수월하다. 이 문제는 기존 RGB거리 문제에 조건을 하나 더 추가한것으로 2번째 인덱스에 첫번쨰집의 색깔을 지정해놓고 풀면된다. 기존 RGB문제와 3차원배열을 활용한 DP문제링크를 걸어둘테니 참고하면 이 문제를 푸는데 매우 도움이 될듯하다. www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 2021.05.08 - [백준 문제풀이(JAVA)/DP(다이나믹프로그래밍)] - 백준 .. 백준 1563번(JAVA) 3차원 DP로 해결하는 문제이다 골드 4이상부터는 대부분 3차원DP로 풀어야 하는 것 같다. int[][][][ dp=new int[N][2][3];으로 선언해주고 [][][]에서 첫번째는 날짜를 2번째는 지각을 한 상태이면 1, 아니면0, 마지막인덱스는 연속결석날짜를 의미한다. dp[4][1][2]는 4번째날 지각을 한상태에서 2번연속 결석을한 경우의수를 의미한다. 일단 만약 날짜가 1일이면 지각,결석,출석 한가지씩이어서 3을 출력하고 시스템종료 그다음 2틀째날에는 총 8가지 경우의수가 있다. 각각 맞게 설정해주고 bottom-up방식으로 구현하기 위해 for문을 i=2부터 실행해준다. 자세한 사항은 아래 소스코드를 보며 이해하자. 소스코드 import java.util.*; public class M.. 이전 1 2 3 4 다음
