데굴데굴 굴러가는 개발 블로그

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class 백준_S3_11659_구간합구하기4 { static int dist, farNode; static ArrayList tree[]; static boolean[] isVisited; public static class Node{ // 위치, 가중치 int pos; int weight; Node(int pos, int weight){ this.pos = pos; this.weight = weight; } } pu..

처음에 해당 문제를 접했을때에는 최소힙, 최대힙 두개의 PriorityQueue를 이용해서 제거해나가며 마지막 제거 연산에서 최소힙의 값 == 최대힙의 값이 되는경우 EMPTY로 처리하면 되겠다 싶었다. 하지만 적용할 연산의 개수가 K O(log N) package Baekjoon.Gold; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class 백준_G4_7662_이중우선순위큐 { static int T, Q; static TreeMap map = new TreeMap(); static boolean isEmpty; public sta..

전형적인 백트래킹 문제라는데 사실 아직 문제를 보면 딱 ㅇㅇ로 푸는거구나~ 하는 생각이 안드는 경우가 많다. 왜 백트래킹을 쓰는지에 대해 생각을 해보니 1. 일단 완탐을 해야 하는거 같지만 2. 한번 완료하면 더이상 탐색을 할 필요가 없음 (많은 정답중에 사전식으로 하나만 출력하기 때문) 3. 따라서 해당 경우를 가지치기를 하기 위해서 -> 백트래킹 사용 이런식으로 생각해야 하지 않을까 싶다. 개인적으로 백트래킹이라는 냄새를 맡으면 조금 쉬운 문제가 아닐까..? 싶다 DP를 풀다와서 그런가 실버DP문제보다 골드문제가 더 쉬운건... 기분탓이겠지... 풀이과정 - map[9][9]에 스도쿠를 입력 받아준다. - 모든 칸을 너비기준으로 탐색해야 하기 때문에 DFS가 적합 - dfs는 depth를 기준으로 d..

백준 3040번 백설공주와 일곱 난쟁이와 굉장히 유사한 문제라고 생각해서 "개꿀이당 ㅎㅎ" 이러고 풀었다가 호되게 당한 문제... 맞왜틀!!!!!!! 맞왜틀!!!!! 을 외치며 30분동안 더 고민하게 한 문제였다. 채점중 97%에서 자꾸 틀려서 진짜 답답했는데 반례를 보자마자 고개를 끄덕였던 문제.. 풀이 방법 1. 10명의 난쟁이 中 7명을 순서 상관 없이 뽑아야 한다는 조건에서 '조합'으로 풀어도 되는 문제라고 생각 2. 10개의 입력을 배열1로 받고 3. 10C7 연산을 실행 4. 생성된 새로운 배열2의 값들의 합이 100인지 확인 5-1. 100 이라면 -> 정답 처리 #중요# 10개중에 7개의 합이 100이 되는 다른 경우가 또 출력되지 않도록 isEnd = true로 변경시켜주기 5-2. 10..