코딩테스트 (16) 썸네일형 리스트형 백준 10159번(JAVA) 플로이드-와샬 알고리즘을 이용하는 문제이다. 플로이드-와샬 알고리즘은 최단거리를 찾는 문제에서 가장 간단하다. 3중for문, 이것만 기억하면 된다. 3중for문이니까 당연히 시간복잡도는 O(v^3)이다. 그래서 보통 플로이드-와샬 알고리즘을 사용하는 문제들은 정점의 수가 1000을 넘지 않는 것 같다. 플로이드-와샬 알고리즘에 대한 기본적인 설명은 따로 하지 않겠다. 이 문제에서는 일단 입력을 받을때 1 2 이렇게 받으면 map[1][2]=1, map[2][1]=2 이렇게 했다. 1의 값은 앞에인덱스가 뒤에 인덱스보다 무겁다는 뜻, 2의 값은 앞에 인덱스가 뒤의 인덱스보다 보다 가볍다는뜻이다. 플로이드-와샬 알고리즘을 사용할때 기준점이 되는 k인덱스를 기준으로 map[i][k]==1&&map[k][j]=.. 2D 총알구현,발사 이번 포스팅에서는 총알을 구현하고 발사하는거 까지 해보겠다. 일단 본격적으로 스크립트를 수정하기에 앞서서 Edit->ProjectSettings->Input Manager에 들어가서 아래사진과 같이 Fire1버튼을 A로 설정해주자. 나는 이번 프로젝트에서 총알 발사 버튼을 A로 해줄꺼여서 아래처럼 설정했으므로 자기가 편한대로 해도 무방하다. 이제 스크립트를 설명하겠다 스크립트를 설명하기에 앞서서, 이전 포스팅과 스크립타가 많이 달라졌다. 위에 사진을 보면 알겠지만 부모오브젝트를 Helmet으로 두고 자식오브젝트에 weapons를 넣었다. 그래서 Player.cs 에서 Weapone.cs 스크립트를 불러서 왼쪽방향키를 누를땐 캐릭터를 기준으로 왼쪽에 위치하고 왼쪽으로 총구를향하게 했다. 바뀐 코드는 아래와.. 백준 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.. 백준 1238번(JAVA) 처음에는 어떻게 풀어야 할지 감이 안잡혔다. 일단 왕복거리를 구한다는 것은 알았다. X번에서 각 마을까지의 최소거리는 X번에서 다익스트라를 실시하면 된다. 그럼 각 마을에서 X번까지의 최소거리를 구하기 위해서 1번에서 N번까지(X번을 뺀) 모두 다익스트라를 실시하면 될까? 그렇다면 다익스트라를 총 N번 실행해야 한다. 딱봐도 시간초과의 느낌이 나지않는가? 그래서 생각해낸 방법은 X에서 2번실행하는것이다. 제일 중요한것이 간선을 입력 받을 때 거꾸로도 입력받는것이다. 예를 들어 a에서 b로 가는 가중치w의 간선이 있다면 b에서 a로 가는 가중치w의 간선도 추가해 주는것이다. 자세한 설명은 아래 글에서 잘 설명 되어있다. 꼭 한번 참고해 보길 바란다.steady-coding.tistory.com/106 [B.. 백준 15686번(JAVA) brute force 문제이다. 시간초과때문에 몇 번이고 다시 풀었던 문제이다. 시간초과를 피하며 구현을 잘하면 된다 이 문제의 핵심은 3가지라고 생각한다. 지도를 입력받으며 치킨집과 가정집의 위치를 미리 선언한 ArrayList에 넣는다. ArrayList를 사용함으로써 지도 전체를 탐색하며 거리를 계산하는게 아니라 ArrayList에서 각각 꺼내와서 거리를 계산한다. 이러면 시간을 훨씬 단축시킬 수 있다. 치킨집 ArrayList에서 M개의 치킨집을 고르는것은 backtrack으로 구현한다. 만약 백트랙하다가 치킨집의개수가 M개가 되면 바로 DFS()함수를 호출해서(이름은 그냥 막 지었다) M개의 치킨집에대한 치킨거리를 구한다. Backtrack을 할때 재귀함수로 호출하는데 호출할때 시작점은 이전에 .. 백준 1826번(JAVA) 아래 문제와 매우 비슷하다. 우선순위큐에 객체를 넣어서 객체끼리 비교할 줄 알면 수월하게 풀 수있다. 아래 문제도 같이 참고해서 보면 비슷한 유형이라는걸 알 수 있다. 2021.04.30 - [백준 문제풀이(JAVA)/그리디 알고리즘] - 백준 1781번(JAVA) 백준 1781번(JAVA) 처음엔 이 문제를 그리디 알고리즘에 넣어야 하나, 우선순위 큐 카테고리로 넣어야 하나 고민했다. 근데 뭐 큰 의미없는 거 같아서 걍 그리디 알고리즘에 넣는다. 처음에는 그냥 단순히 마감시 red-tiger.tistory.com 우선 입력값을 거리가 가장 작은게 앞에오도록(우선순위가 크게) 정렬한다. 이중 while문을 사용한다 첫 번째 while문에서는 (현재가지고연료 이전 1 2 다음
