hansjour 개발일지

문제 파악-n개의 노드가 주어지고, n개의 노드와 연결 된 노드의 인덱스에 연결이 유효하면 1, 유효하지 않으면 0을 표시한다.컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.각 컴퓨터는 0부터 n-1인 정수로 표현합니다.i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.computer[i][i]는 항상 1입니다.접근 방법💡-DFS 통해 인접한 노드 순회하고, 인접 없으면 네트워크 끝.그런 네트워크가 몇개인지 총 카운트 (DFS를 네트워크만큼 수행)-2차원 배열의 형태로 주어지는 연결 값을 보고, 각 노드가 어디와 연결되었는지 먼저 파악한다. -코드 작성의 원활함을 위해 셋 그래프를 인접 리스트 형태로 변환, O(n^2)-start노드는 1번부터 시작, ..

코드 구현import java.util.*;class Solution { public int solution(String begin, String target, String[] words) { Queue queue = new ArrayDeque(); boolean[] visited = new boolean[words.length]; queue.offer(new WordState(begin,0)); //방문 체크는 안해도 됨 while (!queue.isEmpty()){ //방문 (가까운 곳부터) WordState curr = queue.poll(); //방문한 곳이 내가 찾던 t..

문제 파악-주어진 배열을 끝까지 돌며 +,- 두 가지를 모두 구해 target값에 다다르는 경우의 수를 카운트주어지는 숫자의 개수는 2개 이상 20개 이하입니다.각 숫자는 1 이상 50 이하인 자연수입니다.타겟 넘버는 1 이상 1000 이하인 자연수입니다.접근 방법-완전 탐색이라서 dfs도 가능하지만, 큐가 조금 더 익숙해 큐로 풀이했다.-기준 뽑아 연결 된 노드(경우의 수)를 모두 큐에 넣고 같은 조건에서 값을 누적해나갔을 때 결과값을 비교-결과값이 맞기만 하면 카운트하면 되므로, 그냥 카운트한다.코드 구현import java.util.*;class Solution { public int solution(int[] numbers, int target) { Queue que=new Ar..

N-Queen  코드 구현import java.util.*;class Solution { int cnt=0; public int solution(int n) { //가로 세로 같은 줄에 있음 안되고, //대각선에 겹침 안됨.. //퀸 놓을 때마다 카운트, 말==n이면 카운트 //조건 뚫고 n개 다 놓을 수 있는 경우의 수를 구하기 //부모row != 자식row //부모col != 자식col //[row+1][col-1] || [row+1][col+1] => 대각선 //혹은 Math.abs(line[i]-col)==Math.abs(i-row) 여기서 i는 변하는 row값 int[] l..

https://leetcode.com/problems/word-search/  >접근 방법-dfs(backtrack)을 이용한 풀이dfs함수의 리턴값을 boolean으로 주어 방향마다 전진 가능한지 여부 체크-해당 노드가 유효하려면, 전진이 가능한지 여부도 체크해야함.-isValid() 조건 1) 범위 벗어나면X 2) 방문했으면X 3) charAt(idx)와 같아야함-재귀적으로 dfs 메서드 호출하고 하나라도 true를 반환하면 전체 탐색을 멈추고 true를 반환한다. 리턴되지 못하고 빠져나오면 false라는 의미이므로 방문 취소하고 다른 경우의 수 탐색-최종 리턴값이 boolean타입이기 때문에 dfs도 boolean타입인 게 헷갈리지 않음코드 구현class Solution { public boo..

https://leetcode.com/problems/permutation-sequence/  문제 파악1~n 까지의 수의 순열을 구하고, 그 중 k번째 순열을 문자열 형태로 리턴1 1 접근 방법-순열 문제코드 구현import java.util.*;class Solution { public String getPermutation(int n, int k) { String answer=""; List> permutations = new ArrayList(); boolean[] visited = new boolean[n]; String[] arr = new String[n]; for(int i=1;i(),visited,n,arr); ..

https://leetcode.com/problems/permutations/   문제 파악주어진 배열로 만들 수 있는 모든 순열 구하기1 10 All the integers of nums are unique. (요소 중복 허용)접근 방법💡 -재귀 함수가 리턴되면 마지막에 호출한 함수가 가장 먼저 리턴-리턴 되면 리스트에서 해당 원소 삭제, 방문 배열 초기화 - : 중복 허용, 순서 존재-방문 배열은 하나의 순열 안에서 이루어지는 것을 유의하자.해당 원소에 해당하는 경우의 수를 모두 순회하면서 겹치지 않게 표시 코드 구현import java.util.*;class Solution { //순열 문제 : 중복 허용, 순서 존재 public List> permute(int[] nums) { ..

https://leetcode.com/problems/combinations/ 문제 파악주어진 1~n까지의 범위 중에서, k개의 원소를 갖는 숫자 ‘조합’ 구하기1 1 접근 방법💡 backtrack() 함수 정의하여, 가장 작은 단위의 연산을 정의하고, 재귀적으로 해당 함수를 호출한다. 코드 구현class combinations { public List> combine(int n, int k) { //1~n까지 숫자 중에 k개를 짝지은 조합을 찾아내기 List> result = new ArrayList(); int start = 1; //시작점을 값으로 전달해주기. // 함수에 유동적으로 인자를 주고 싶을 때 사용, 함수에 인자가 증가하며 삽입될..

https://leetcode.com/problems/subsets/description/문제 파악주어진 배열에서 나올 수 있는 subset 모두 구하기(조합)1 10 All the numbers of nums are unique.접근 방법💡 -combination으로 순서가 없는 리스트를 담아 최종 result에 적재-”combinations” 문제와 흡사-조건 걸지 않고 조합 만들어지는대로(길이n) 결과로 반환하는 것이 포인트 코드 구현import java.util.*;class Solution { public List> subsets(int[] nums) { List> result = new ArrayList(); List curr = new ArrayList(); ..

피로도https://campus.programmers.co.kr/tryouts/140902/challenges  문제 파악💡 -dfs, bfs, dp로도 풀 수 있는 문제-가진 체력으로 각 던전을 돌며 최대 던전 돌 수 있는 횟수 구하기-똑같은 게 계속 반복된다. ⇒ 작은 문제로 줄여서 풀기 (재귀)-순차적으로 돌 필요 없고 어떤 조합이든 많이 돌 수 있는 방법 찾기.k는 1 이상 5,000 이하인 자연수입니다.dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.dungeons의 가로(열) 길이는 2 입니다.dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다."최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다."최소 필요 피로도..