SK_MOUSE 개발일기

그래프의 가장 긴 깊이를 찾는 그래프 깊이 문제이다. 그래프 문제라고 해서 별 다른것이 아니라, BFS를 통해서 가장 깊이있는 경우를 마지막에 출력하면 그 깊이를 알 수 있다. check와 connect를 boolean으로 배열로 형성하여 방문했는지, 연결됐는지를 체크하는 용도로 사용한다. 이때 n이 아니라 n+1로 할당하는 이유는, 노드의 번호가 1부터 시작하기 때문이다. import java.util.LinkedList; import java.util.Queue; class Solution { public int solution(int n, int[][] edge) { boolean[] check = new boolean[n+1]; boolean[][] connect = new boolean[n+1]..

입국심사 실패코드(완전탐색방법) class Solution { class Tester{ long startT, spendT; Tester(long startTime, long spendingTime){ startT = startTime; spendT = spendingTime; } } public long solution(int n, int[] times) { long answer = 0; long time =0; PriorityQueue q = new PriorityQueue(//오름차순 정렬. (o1,o2)-> (int)((o1.spendT+o1.startT) - (o2.spendT+o2.startT)) ); for(long t : times) q.offer(new Tester(0, t));//0초일..

ArrayList에 하나씩 값을 넣어야한다는 편견을 깨주었다. 한가지의 순서를 각각의 list[i]에 value + " " + value2 를 하여 일련의 String을 이어붙이고 이를 sort하여 가장 낮은차순의 배열을 추출할때 사용한다. import java.util.ArrayList; import java.util.Collections; public class TravelRoute { boolean[] visited; //방문한지 안한지를 체크하는 visited배열 ArrayList answers; public String[] solution(String[][] tickets) { visited = new boolean[tickets.length]; answers = new ArrayList(); ..

단어는 charAt메소드를 이용해서 String에서 글자를 각각 비교할 수 있다. public class WordConversion { int answer; //최소 단계 boolean[] used; //단어를 사용 중인지를 판단하는 visited와 같은 역할을 하는 배열 public int solution(String begin, String target, String[] words) { answer = 51; //단어 최대값이 50이므로 used = new boolean[words.length]; dfs(begin, target, 0, words); return answer == 51 ? 0 : answer; //answer이 51이면 target과 같은 단어가 없는 것으로 판단. } public v..

아래의 내용은 DFS로 구현하였다. 이 문제는 DFS로 푸는 문제인것을 확인했고, boolean visited[] 배열을 이용하여 방문한 노드를 체크하는 방식인 것도 알았다. 고민은, 한 뭉텅이가 연결되고, 카운트++; 한 뭉텅이가 연결되고, 카운트++; 위처럼 코드를 작동하게 하려면 어떻게 재귀함수를 작성하느냐였다. 결론은, "main 메소드에서" 방문하지않은 노드들만 호출하는 동시에 카운트++;을 하면 된다. 그러면 메인 메소드에서, 한 뭉텅이당 하나의 노드만 호출되고, 나머지 노드들은 재귀로써 방문처리된다. class Solution { void dfs(int i, boolean[] check, int[][] computers){ check[i] = true; for(int j=0; j

DFS/BFS 문제를 처음 접해서 다른 이들의 코드를 참고했다. 다음은 DFS 코드이다..예술이다.. class Solution { public int solution(int[] numbers, int target) { int answer = 0; answer = dfs(numbers, 0, 0, target); return answer; } int dfs(int[] numbers, int n, int sum, int target) { if(n == numbers.length) {//노드를 모두 탐색했을때만 타겟과 합이 같은지 검사한다 if(sum == target) { return 1; } return 0; } return dfs(numbers, n + 1, sum + numbers[n], target..

개미병사들이 집을 한칸 건너 터는 문제와 비슷하다. 유의할 점은, 집들이 아래와 같이 동그랗게 원으로 배치된다는 점이다. 기본적인 점화식은 아래와 같다. A[n] = Max( A[n-2] + A[n] , A[n-1]) 이 때, 첫번째 집이 선택되는경우와 아닌 경우로 나누어서 1. 첫번째 집이 선택되는 경우 : pick[0] 2. 첫번째 집이 선택되지 않는 경우 : pick[1] 두가지 케이스를 같이 for문에서 연산을 돌린다. class Solution { public int solution(int[] money) { int[][] pick = new int[2][money.length]; pick[0][0] = money[0]; pick[0][1] = money[0]; pick[1][0] = 0; pi..

배열의 초기화 기본타입(Primitive type)의 배열의 경우 초기값을 가지고 있다(int = 0 / String = "") ex) int[] , String 참조타입(Reference type)의 배열의 경우는 엘리먼트의 초기값이 null 임을 주의하자 ex) Integer[] 아래링크에서, DP를 사용할때 초기화 스킬을 사용한다는 것에서 아이디어를 얻었다. 2020/10/13 - [코딩테스트/개념정리] - DP(=다이나믹 프로그래밍,Dynamic Programming) 심화 DP(=다이나믹 프로그래밍,Dynamic Programming) 심화 동적계획법(Dynamic programming)은 자료구조에서 동적할당(Dynamic Allocation)과는 다르다. 알고리즘에서 사용되는 "다이나믹(Dy..

동적프로그래밍(Dynamic Programming)의 기본형이 되는 문제이다. Math.max값을 이용하여 이전 인덱스의 값과 비교하여 주어진 배열에 직접 업데이트 하는 방식이다. import java.util.Arrays; class Solution { public int solution(int[][] triangle) { int answer = 0; for (int height = 1; height < triangle.length; height++) { for (int i = 0; i < triangle[height].length; i++) { if (i == 0) {//맨왼쪽 triangle[height][0] += triangle[height - 1][0]; } else if (i == trian..

아래와 같이 number 와 N이 주어지면 N을 몇번을 사용해서 number값을 만들어 낼 수 있는지 구하는 문제이다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 아래와 같은 코드는 점화식을 이용하여, 완전탐색을 하는 방식이다. 아마도 DFS 방식이 이 방식이 아닌가 싶다. 아직은 DFS에 대해 다뤄보지 않아서, 추후 코멘트를 남기겠다. 유사, Combination을 떠오르게 하는 점화식이다. Set을 배열로 각각의 인덱스Set에 여러개의 값이 들어갈 수 있다는 방식을 알아야한다. Set[] setArr = new HashSet[9]; * : combination을 이용하여 각각의 연산기호에 따른 값을 넣는다. (A[2] *..