말하는 컴공감자의 텃밭

치즈는 위험해..! 문제을 요약하면 1과 0이 맞닿으면 1시간 후, 1이 0이 된다. 모두 사라지는데 걸리는 시간과 사라지기 직전 시간대의 1이 몇개 있는지 출력하면 되는 문제이다. 외각에는 치즈가 없고, 하나 이상의 구멍이 존재하는데 이는 0과 맞닿은것이 아닌걸로 취급한다. 결국 치즈의 개수가 0까지 bfs()로 탐색을 지속하고, 외각에서부터 0 주변에 1이 있다면 0으로 바꾸고, 치즈 개수를 줄여주면 되겠다. 또한 한 사이클마다 치즈 개수를 저장하여 다 사라지기 직전 치즈 개수를 남겨주면 되겠다. 알고리즘 공부를 입출력이 너무 크지 않는 한 Scanner만 사용했는데 BufferedReader, StringTokenizer, BufferedWriter 을 사용해서 풀어보려 한다. 정리: https:/..

BufferedReader, StringTokenizer, BufferedWriter 코테 준비하면서 자바 기본 I/O인 Scanner 만 사용했었다. 스캐너는 데이터 유형을 유연하게 선택할 수 있지만 속도가 느리다는 단점이 존재했다. 메모리와 속도적으로 알고리즘 문제 풀이에서 제한이 생기는 경우가 존재해서 방식을 바꾸려고한다. 백준 입력 속도 비교 https://www.acmicpc.net/blog/view/56 첫째 줄에 정수의 개수 N (= 10,000,000), 둘째 줄부터 N개의 줄에 한 개의 자연수(10,000 이하)가 적힌 파일을 입력받는데 걸리는 시간을 측정. 10번 측정해서 평균값으로 순위를 매김 버퍼 크기 실행 속도(백준 참고) BufferedReader 8KB 0.6585 sec Sc..

이전 문제와 비슷하다. 사실 얘를 먼저풀었는데 블로그에 정리를 안했었네~ ++ https://hb-in99.tistory.com/89 백준 7576번 토마토 G5 - BFS 요즘 지문 긴게 좋더라.. 뭔가 풀고 뿌듯한 느낌이 든다. 이해 잘못하면 큰일이긴 한데 ㅎㅎ 이 문제는 쉬운 BFS인데 시작점이 여러개라는 점과 날짜를 어떻게 기록하지? 가 관건인 문제였다. 익 hb-in99.tistory.com 이 친구도 동일하지만 이번엔 층이 생겼다. 기존에는 row와 col로만 찾았다면 이젠 위층도 생겨버렸다. 전에 해서 쉽쥬~ 실수만 하지 맙시다. 큐에 익은 토마토 모두 넣고 bfs 돌리기!! 이왕 함수로 뺀겸 범위 체크도 분리해서 가독성 올려주었다. HTML 삽입 미리보기할 수 없는 소스

요즘 지문 긴게 좋더라.. 뭔가 풀고 뿌듯한 느낌이 든다. 이해 잘못하면 큰일이긴 한데 ㅎㅎ 이 문제는 쉬운 BFS인데 시작점이 여러개라는 점과 날짜를 어떻게 기록하지? 가 관건인 문제였다. 익은 토마토 주변에 안익은 토마토가 있다면, 하루지나고 익어버린다. 다 익는 최소 날짜를 출력해야하고, 못익거나 처음부터 다 익은 경우는 각각 -1, 0을 출력하면 된다. 날짜 출력이 관건인데 이를 +1로 해결했다. 이 방법을 찾지못해서 온갖 방법을 쓰다가 결국 남의 블로그들을 뒤져보았다 호호 ㅠㅠ 익은 토마토 근처에 토마토가 있다면, 익은 토마토의 값 +1을 해주어 마지막 토마토값을 출력하면 날짜가 되었다. 로직을 자연어로 정리하면 1. 익은 토마토 1을 발견하면 Que에 넣는다. 2. Que가 빌때까지 반복한다...

코테 준비할수록 DP 점화식을 찾거나 규칙 찾는거에 약한듯해서 DP위주로 준비하게 된다. 그래프는 이제 좀 감 잡았나 싶네 껄꼴껄~ 소주 땡긴다 문제를 읽고 가능한 수를 먼저 떠올리는 습관을 들였다. 문제를 보면 한 스티커를 선택하면 상하좌우 모두 사용이 불가능하다. 따라서 연속적으로 사용할 수 없고, 지그재그로 사용하면 가장 많은 수의 스티커를 붙일 수 있다. 하나의 경우가 더있는데 이런 경우도 존재했다. 어릴적 바둑배웠는데 '날일자' 日 생각나네 그러면 점화식을 세워준다. > DP[0][3] = DP[1][0] + arr[0][3] 또는 DP[1][2] + arr[0][3] 아래 스티커 >> DP[1][3] = DP[0][0] + arr[1][3] 또는 DP[0][2] + arr[1][3] 으로 점화..

오래걸렸다. 순환되는 경우를 고려했는데 생각해보니 필요가 없었다. 단방향 간선이 주어지고, 1->2 갈수있고, 2->3, 3->1 이라면 1에서 1,2,3 모두 갈 수 있게 표기해야하는 문제다. 가보자. 플로이드 위셜은 N^3으로 음수가 없는 최단 경로의 가중치를 계산하는데 적합하다. 3중 for문을 사용하여 탐색하고, i에서 j로 갈수 있다면, i -> k , k -> j가 가능한지 판단해서 초기화 해준다. 이 문제는 가중치는 없으나 i에서는 j만 갈 수 있으나 j를 거쳐 k로 가는 방법도 알아야 하므로 사용했다. HTML 삽입 미리보기할 수 없는 소스 애를 먹었다. k i j. 순이 아닌 i j k로 작성했기 때문이다. i에서 j로 간다면 i j 와 j k가 갈 수 있는지 판단하는건 당연한데 로직을 ..

깔린 브론즈들은 다 지우고 싶다.

햄버거 재료를 제한된 칼로리에 맞게 조합하고, 민기의 선호도가 가장 높은 조합의 점수를 출력하면 된다. DFS를 이용해 재귀를 통해 제한된 칼로리 이내의 모든 경우를 찾아 주었다. HTML 삽입 미리보기할 수 없는 소스 아 간단하네~ 했는데 에? T가 높은 인풋도 있나보다. public static void dfs(int depth, int cal, int point) { answer = Math.max(answer, point); for (int i = depth; i < N; i++) { if (cal + ingredient[i][1] L) { return; } // 모든경우 다 찾았으므로 if (depth == N) { answer = Math.max(answer, point); return; } ..