인생은 디버깅이 되지 않잖아?

문제https://www.acmicpc.net/problem/11659 정답dp를 이용해 풀었고, 처음에 풀 때 시간 복잡도를 계산하지 않고 단순 구현하여 검사를 해보니 시간초과가 계속 떴다..!이런 경우엔 더 좋은 풀이 방법이 있다는 뜻이었고, 내 코드의 문제점은 dp 배열을 함수 내에서 새로 생성하여 dp 배열이 매번 초기화가 되어서 O(j-i)의 시간 복잡도를 가지게 되었다.  누적합을 미리 계산하여 dp 배열에 담은 뒤, j와 i 값을 받아 O(1)로 해결하였다.  import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;// https..

문제https://www.acmicpc.net/problem/2667    정답bfs 방식을 이용하였다. dfs 방식으로도 풀어보고 업데이트를 해야겠다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;class Points{ int x; int y; Points(int x, int y){ this.x = x; this.y = y; }}public class Main { static int[] dx = {-1,0,1,0}; static int[] dy = {0,1,0,-1}; static boolea..

문제https://www.acmicpc.net/problem/2178  풀이풀이의 핵심은 "최단경로"이다. bfs를 사용하여 풀었고, 이동하는 위치(1이 적힌)값을 이전의 거리 값 + 1을 하며 업데이트하며 목적지까지 이동하였다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;class Point { int x; int y; Point(int x, int y){ this.x = x; this.y = y; ..

문제https://www.acmicpc.net/problem/21610          해결시뮬레이션 문제 풀이 경험이 적던 필자는 "배열이 연결되어있다" 를 구현하기까지 많은 고민을 했었다. 아마 글을 보고 있는 다른 개발자 분들도 이 부분 구현하는 데 시간을 적지않게 쏟았으리라 생각된다. 구현 방법은 modulo 연산을 활용하는 것이다. 이 후 나머지 조건들을 충족시켜주면 된다. 자, 이제 코드를 보겠다.1. modulo 연산을 활용하여 구름의 위치를 이동한다.2. 물을 증가 시킨다.3. 구름을 사라지게 한다. (newCloud로 대체)4. 물 복사 버그를 구현한다.5. 새로운 구름을 생성한다.   - 기존 구름자리가 아니어야 함(!visited)   - 새로운 구름 영역의 물을 -2 시켜준다 pac..

문제https://www.acmicpc.net/problem/1926  풀이필자는 bfs를 이용하여 풀이하였습니다. 더 이상 1이 아닌 시점에 count ++를 해주고 그림의 크기가 가장 큰 값을 구하기 위해 Math.max 를 사용하였습니다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;class Point_그림{ int x; int y; Point_그림(int x, int y ) { this.x = x; ..

코드에 문제가 있거나 해석에 오류가 있는 부분 지적해주시면 감사하겠습니다. 오랜만에 글을 쓰게 되었는데,,, 자잘자잘한 개인사는 뒤로하고 바로 문제 풀이를 해보겠다. 이번 문제는 백준 1753번 문제이고 [최단 경로] 이다. 문제 제목을 보면 유추 할 수 있듯이 Djikstra 알고리즘을 적용하여 푸는 문제이다.    문제를 쭉 읽어보면 첫 번째 줄의 입력 값은 정점(이하 노드)의 개수 V, 간선의 개수 E를 적는다. 두 번째 줄의 경우 시작 노드를 적어주고 3번째 줄~ 마지막 줄 까지는 간선의 개수 만큼 (시작 노드, 목표 노드, 비용)이 주어진다.  핵심은 비용이 모두 양수라는 것. 최단 경로를 구하는 문제에서 비용이 모두 0이상이면 다익스트라 알고리즘을 적용하면 된다.  다익스트라 알고리즘은 검색을..