12865번: 평범한 배낭 대표적인 0 - 1 배낭 문제이다. 물건 N개와 배낭의 크기인 K가 주어지고 2번째 줄부터 물건의 가치와 무게가 주어진다. 이때 최대 가치를 구하는 문제다. 4 7 6 13 4 8 3 6 5 12 문제와 같이 예제가 주어졌을 경우 최대 담을 수 있는 물건은 4개 배낭의 최대 사이즈는 7이된다. 이에 맞는 배열을 준비하면 dp = new int[5][8]이 된다. 물건과 사이즈는 0이 될 수 없으므로 +1씩 해줬다. dp[0] = [0,0,0,0,0,0,0,0] dp[1] = [0,0,0,0,0,0,0,0] dp[2] = [0,0,0,0,0,0,0,0] dp[3] = [0,0,0,0,0,0,0,0] dp[4] = [0,0,0,0,0,0,0,0] 위와 같이 dp 배열이 초기화되어 ..
Problem Solving/백준
1106번: 호텔 0 - 1 배낭 문제로 생각하고 접근해야 하는 문제이다. 다만 배낭 문제의 경우 배낭 무게가 정해져 있어 무게를 초과한다면 넣을 수 없지만 이 문제의 경우 최소 C명 이상의 고객을 얻을 수 있는 최소 비용이기 때문에 C명을 넘더라도 최소 비용이라면 해당 값을 반환해야 한다. 풀이 과정 dp의 경우 C + 1명이 아닌 C + 101명으로 초기화 해주었는데 이는 하나의 도시에서 홍보를 통해 얻을 수 있는 고객이 최대 100명이기 때문이다. 앞서 말했듯 최소 C명이상의 고객을 얻을 수 있는 최소 비용이기 때문에 넘을 수 있는 최대 고객 수인 100명과 1번 인덱스부터 사용하기 위해 1명을 추가해줬다. 최소 비용을 구하는 문제이기 때문에 dp를 적당한 무한값으로 초기화해주고 0명을 얻기 위해서..
30869번- 빨리 기다리기 백준 아레나 신청해놓고 까먹고 있다가 부랴부랴 기억해서 참가했었다. 한 시간 반정도 남았을 때 도전했는데 처음 봤을 때는 쉽게 생각하고 BFS로 접근했었다. 제출하니까 시간 초과 뜨길래 다익스트라로 방향을 바꿨으나 시간이 없어서 못풀었었다. 그리고 다 풀고 나서 또 조건 제대로 안 읽어서 불가능할 경우 -1을 출력한다는 것을 못봤다. 그리고 나서는 ‘아 혹시 시간 합이 long이라서 그런가?’ 하고 엉뚱한 것만 손보고 있었다. 이것 때문에 한 15분 정도 더 해멨다.. 결국 접근법 자체는 다익스트라가 맞았다. 대신 고려해야할 점이 빨리 기다리기인데 빨리 기다리기를 사용하면 배차간격을 무시하고 바로 탈 수 있다는 점이다. 예시로 바로본다면 ① -> ②로 가는 소요시간은 2시간이..
5639번: 이진 검색 트리 참고 [백준] 5639번: 이진 검색 트리 - JAVA 고쳐야 할 것 코드를 너무 빨리 짜려는 습관 일정 시간 이상 지나면 굳혀진 방향을 수정 고려하기 구현 고민 일단 반복문으로 방향을 잡고 시작했다. 처음에는 current를 설정하고 current.data보다 작으면 current.left에 추가하고 current = current.left와 같이 현재 노드를 재설정해줬다. 그리고 current.data 보다 클 경우 current = current.parent로 부모로 올라가 설정하려 했다. 문제는 이렇게 위로 올라가려면 어디까지 올라가야 할지 설정하기가 어렵다는 점이다. 현재 노드의 왼쪽 서브 트리는 노드의 키값보다 작다는 것을 가지고 설정해보려 했으나 이 경우 root..
