개발자 일기장.

[백준 5214] 환승 문제 알고리즘 bfs문제 메모리 관리 풀이방법 bfs를 통해서 문제를 푸는데 메모리가 터지는 것을 염두하고 문제를 짜야한다. 처음에는 일반적인 bfs인줄 알고 풀었는데 바로 메모리가 터졌다. 보통 1억개가 넘어가면 300MB가 넘어간다는 이야기를 이 문제를 풀면서 알았다.(100,000개에 100,000개씩 연결이 되면 100억 정도되는데 그러면 메모리가 터져버린다.) 해결책은 1~100000까지는 일반적인 역, 100001 ~ 101000까지는 하이퍼루프 번호로 정해서 연결시켜버리는 것이다. 이해를 돕는 사진 핵심 코드 #include #include #include #include using namespace std; #define MAX 100000 + 1 vector adj..

3190. 뱀 문제 알고리즘 시뮬레이션 풀이방법 문제에서 요구하는 대로 순서를 나눠서 풀면 쉬운 문제 다음 위치 지정 밖을 나가거나 자기 몸을 무는 경우 종료 다음 위치가 사과가 아니면 꼬리 제거 전진 방향 바꾸기 핵심 코드 #include #include #include using namespace std; #define MAX 100 + 1 enum {BLANK, SNAKE, APPLE}; pair dir[4] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} }; // R, D, L, U int N, K, L; int board[MAX][MAX]; deque snake; map comm; int main() { // input cin >> N; cin >> K; for (int i ..

2616 소형기관차 문제해결 사진 문제 알고리즘 DP 풀이방법 해당 위치 지점을 포함한 횟수 dp 배열을 구해서 푼다. 핵심 코드 import java.io.*; import java.util.*; public class Main { private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); private static int N, M; // N => number of train, M = count of valid train private static int[][] dp; // dp[][] data private static int MaxValue = 0; // Max Value public st..

2580 스도쿠 문제해결 사진 문제 알고리즘 dfs 백트래킹 풀이방법 넣을 수 있는 빈칸을 체크한다 해당 빈칸에 수 하나씩 넣으면서 가능한지 확인하고, 가능 한 경우 다음 빈칸을 확인한다 불가능인 경우 해당 수를 다른 수로 바꾼다. 핵심 코드 import java.util.*; class pos{ int y; int x; public pos(int y, int x) { this.y = y; this.x = x; } } public class Main { static final int MAX = 9; static int board[][] = new int[MAX][MAX]; static ArrayList blankList = new ArrayList(); // 빈칸 위치 static void dfs(Arr..

2352 반도체 설계 문제 알고리즘 LIS 풀이방법 LIS 풀이대로 풀었다. 가장 긴 오름차순 부분 수열을 찾으면 된다. 핵심 코드 import java.io.*; import java.util.*; public class Main { static final int MAX = 40000; static int N; static int Port[]; static Vector PortV; public static void main(String[] args) throws NumberFormatException, IOException { init(); solution(); } public static void init() throws NumberFormatException, IOException { Buffere..

1987 알파벳 문제해결 사진 문제 알고리즘 dfs 풀이방법 dfs를 돌린다. 생각할 것 동일한 알파벳 체크를 할 것이므로 visited[][]를 구현하지 않아도 된다. 꼭 board[R-1][C-1]가 끝이 아닐 수 있다. 요거를 생각을 못해서 정답률이 박살이 났다. 핵심 코드 import java.util.*; import java.io.*; public class Main { private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // private static final BufferedWriter bw = new BufferedWriter(new // OutputStreamWriter..