전체 글 (88) 썸네일형 리스트형 백준 17779 <게리멘더링2> 게리맨더링 주어진 방법보다 어렵게 푼 방식이기 때문에 참고!! 만 하자! 이 문제는 DFS 즉 백트래킹으로 가능한 꼭지점 4개를 구하고 최소의 차이가 나는 값을 출력하는 것이다. 문제에서 처럼 푼다면 4중 포문으로 꼭지점의 좌표 d1, d2, 이렇게 구해서 계산을 하면 되겠지만 문제를 이해하고 계산하는 방법이 없다면 푸는 방법이다. DFS를 3번 돌려서 가능하다면 최솟값을 비교해주도록 했다. 이 그림으로 설명하자면 1의 꼭지점을 잡고 오른쪽 아래로 이동 꼭지점이 가능하다면 왼쪽 아래 대각선으로 이동이 가능하다면 1에서 2까지 온 거리만큼 3위 치에서 좌상 대각선으로 이동하는 문제이다. 이렇게 총 3번의 DFS로 문제를 해결할 수 있다. 1번에서 빨간방향으로 한번 이동해서 계산해주고 다시 돌아와 파란색 동.. 백준 1753 <최단 경로> 더보기 이 문제를 풀면서 두 가지 방법으로 문제를 풀어 볼 것이다. 우선순위 큐를 사용하지 않은 최단 경로 우선순위 큐를 사용한 최단 경로 이렇게 두가지 방법으로 풀어 본 이유는 우선순위 큐를 사용하는 것이 과연 빠른가? 하는 마음에서 사용하기로 했다. 차이가 있는 부분은 가장 작은 최소를 어떻게 찾을 수 있을까 부분이다. 전체 정점을 돌면서 방문하지 않았고 최소 거리인 점을 찾는 부분이다. 우선 순위 큐를 사용하게 되면 방문했던 곳이면 넘어가 주면 되고 그렇지 않은 경우에 가장 작은 경로를 반환해 주기 때문에 쉽게 구현을 할 수 있다. 즉 우선 순위큐를 사용하지 않으면 v^2를 요구하게 된다면 사용하게 된다면 vlogv+ elogv 시간이 걸려 시간을 단축할 수 있다. 이런 식으로 흐름이 진행되게 된다.. 백준 18513 <샘터> 치킨 집의 위치에서부터 BFS를 하는 문제! 생각보다 어렵지는 않았지만.. 그놈의 실수.. 실수.. ㅠ 접근 방법만 알게된다면 쉽게 풀 수 있는 문제였다. 문제를 먼저 이해하자고 하면 치킨집에서 가까운 순서대로 집을 놓고 개수를 구하는 것이다. 즉 가까운 곳부터 집을 놓는다 --> 너비 탐색 이렇게 되는 것이다. 이 문제에서 주요하게 생각해야 하는 점은 범위!! 총 거리의 합이 int형이 아니고 long 형의 범위가 된다는 것을 주의해야 한다! 이것 이외에도.. 메모리... 초과를 주의하자.. 이놈의 습관 때문에 방문처리를 해주는 visit함수를 boolean 형이 아닌 int 형으로 사용한다면... 메모리 펑... 펑... 초과를 하게 된다. 위에 num을 저렇게 크게 잡아준 이유는 음수에도 위치가 놓.. 이전 1 ··· 20 21 22 23 24 25 26 ··· 30 다음
