요깨비's LAB

위 문제는 자바 컬렉션인 Map을 활용하여 해결하였습니다. 옷의 종류를 Key값으로, 각 옷들을 Key값의 List배열에 담아주었습니다. 아래는 코드입니다. import java.util.ArrayList; import java.util.HashMap; import java.util.Iterator; class Solution { HashMap clothMap; int result = 1; public int solution(String[][] clothes) { clothMap = new HashMap(); ArrayList clothList; for (int i = 0; i < clothes.length; i++) { // clothMap.putIfAbsent(clothes[i][0], new Arr..

이번에도.. 오지게 오래 걸렸습니다... 순수 완벽하게 푼것이 아닌.. 백준 질문하기에서 반례들을 이용하면서 풀었구요.. 아직도 분기 처리 조건 생각하는거랑 로직을 제대로 생각 않하고 무작정 문제에 돌입하는 것... 참 안고쳐집니다. 좀만 풀이가 생각날 것 같으면 무조건 키보드에 손이 올라가는 이 흑우.. 처음 아이디어는 자료구조 Set 2개를 이용해서 DFS를 돌면서 각 방문 노드들을 Set에 넣어주면서 indexSet(첫째 줄 배열)이랑 valueSet(두번째 줄 배열)에 값들을 비교하면서 하려고 했는데 빛 좋은 개살구 마냥 아이디어만 좋았지 실제적으로 제 머리가 그걸 구현할 정도로 호환이 안되더군요.. 다음번에 다시 도전해서 올리겠습니다. 그냥 함수 재귀를 이용해서 풀었습니다. 여기에서 통과 조건은..

어후;; 20번 틀리고 21번째에 드디어 해결했네요... 알고보니 로직은 그럭저럭 맞는것 같았으나 BFS에 대한 공부 부족과 객체 지향 활용을 못한 원인이 가장 컸던 것 같습니다.. 차근차근 어떤 문제 상황에 부딪혔고 해결했는지 끄적여 보겠습니다. 저는 고수분들이랑 다르게 간단하고 명료하게 추상화해서 몇줄 안되는 코드로는 못짜서 코드가 길고 좀 보기 싫습니다.. 그냥 저만의 회고시간입니다.. 클래스 정의 우선 Vertax 클래스를 설계했습니다. class Vertax { private int index; private int color; // -1 색없음, 0 빨 1 파 private HashSet connectedEdges; // 해당 정점과 연결된 정점들을 저장 하기 위한 자료구조 public Ver..

문제 풀이 1. 다이나믹 프로그래밍을 적용할 수 있는 문제인지 확인 - 큰 문제를 작은 문제로 쪼갤 수 있으며, 작은 문제도 큰 문제와 같은 방법으로 풀 수 있고, 작은 문제들이 겹치는지? (Overlapping SubProblem) - 문제의 정답을 작은 문제의 정답으로부터 구할 수 있으며, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다. (Optimal Substructure) 2. 자료구조에(실무를 제외하고 일반적인 문제 해결과정에서는 보통 배열사용) 어떤 값을 저장할 것인지 문장으로 정리 - memoization[N] = "N개의 물건을 묶음 및 단일 조합을 통해 구매하여 지불할 수 있는 최대 금액" 3. memoization[N]의 값을 어떤 규칙을 통해 찾을 수 있는지 생각하기(점화식..

1. 개념 "하나의 문제는 한번만 풀도록 하는 알고리즘" - 핵심 다이나믹 프로그래밍은 문제의 답이 이용되는 구조를 이용한 알고리즘이다. 큰 문제를 작은 문제로 나눈다는 측면에서 분할정복(divide and conquer)알고리즘과 비슷하지만 다음과 같은 차이점이 존재한다. DAC DP 문제가 절반으로 줄어듬 문자게 -1로 줄어듬 Function problem 최적화 문제 결과가 한번 사용 결과가 여러번 사용됨 분할이 성능 향상 결과 재사용이 성능 향상 다이나믹 프로그래밍 알고리즘을 적용하기 위해서는 두가지 조건을 만족해야 한다.- 큰 문제를 작은 문제로 쪼갤 수 있으며, 작은 문제도 큰 문제와 같은 방법으로 풀 수 있고, 작은 문제들이 겹치는지? (Overlapping SubProblem) 문제를 작은..