코딩테스트 (16) 썸네일형 리스트형 백준 13907번(JAVA)-세금 2차원 DP를 활용한 다익스트라 문제이 import java.util.*; import java.io.*; class Node implements Comparable { int v; int w; int c; Node(int v,int w,int c) { this.v=v; this.w=w; this.c=c; } public int compareTo(Node o) { return w-o.w; } } public class Main { public static int[][] dp; public static int N; public static int S; public static int D; public static void main(String[] args) throws IOException{ // TODO.. 백준 10217번(JAVA) - KCM Travel, 재채점 후 새로운 풀이 분명히 맞았던 문제인데 갑자기 재채점 되면서 시간초과로 틀렸다. 알고보니 어떤 분이 질문게시판에 예시로 어떤 입력을 보여주면서, 이걸로 하면은 대부분의 코드들이 시간초과가 나온다고 질문글을 올렸고(1년전) 그게 최근에 검토가되서 재채점이 된 것이다. 내 기억이 맞다면 이 문제는 꽤 많은 사람들이 맞춰가지고, 다익스트라 분류로 들어가면 상위권에 노출되던 문제였다. 그런데 재채점 후 저~~ 하위권으로 내려갔을 정도로 재채점 후 많은 분들이 틀렸다 그래서 내 다익스트라를 조금 더 다듬어봤다. import java.util.*; import java.io.*; class Node implements Comparable { int v; int c; int d; Node(int v,int c,int d) { thi.. 백준 16236번 -아기상어 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net BFS이지만 신경써줘야 할게 많아서 까다로운 문제이다. 필자도 몇번의 시도끝에 풀었다. 많은 풀이들이 있지만 나는 나만의 방식으로 풀었다. 먹이의 최단거리는 어떻게 구했는가?? 우선순위 큐를 사용해서 count, y좌표 ,x 좌표 순서로 오름차순으로 정렬했다. 이렇게 되면 같은 거리일때 더 위쪽에 있고, 만약 같은 y좌표라면 더 왼쪽에 있는 좌표를 선택하게 될것이다. 처음 Node를 만들 .. 백준 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승 부모를 저장한다. 예를들어 위 그림과 같은 트리가 있다고 가정해보자. 기존에는 바로 위의 부모만 저장했다. 그래서 .. 유니티 2D싱글톤 패턴 원래는 개발일지를 매일매일 써서 만들어지는 과정을 상세하게 보여주고 싶었는데 귀찮아서 그러진 못했다. 어쨋든 최근에 배운 싱글톤 패턴에 대해 작성해보겠다. 계속해서 개발을 하다보니 public 변수로 선언해서 inspector창에서 드래그앤 드랍으로 계속 참조해줘야되기도 귀찮고 이 오브젝트는 계속해서 참조할거 같은데 어떻게 하면 효율적으로 전역변수처럼 쓸수 있을까?? 하고 고민하다가 찾아낸게 싱글톤 패턴이다. 우선 씬의 GameManager라는 오브젝트와 스크립트를 만든다 그리고 그 GameManager라는 스크립트에 자주 참조되는 오브젝트들을 선언한다 그러면 어느 스크립트에서든 GameManager를 통해서 오브젝트들을 참조할 수 있다. 게임의 시작화면이다. 플레이어도 바뀌고 배경도 바뀌고 많이 바뀌었.. 백준 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.. 이전 1 2 다음
