Etc96 [Java] 프로그래머스: 타겟 넘버 DFS 모든 노드를 방문해야 노드들의 합이 타겟 넘버와 같은지 확인할 수 있다. [그래프 탐색] BFS / DFS [그래프 탐색] BFS / DFS BFS(Breadth-First Search) : 너비 우선 탐색 한국에서 여러 경유지를 거쳐 미국으로 향할 때, 어떤 경로가 가장 최단 거리일까? 최대한 넓게 이동하다가 더 이상 이동할 수 없을 때 아래로 이동하는 방 cookiee.tistory.com 전체 풀이 class Solution { int answer = 0; public int solution(int[] numbers, int target) { dfs(numbers, 0, target, 0); return answer; } public void dfs(int[] numbers, int dept.. 2022. 11. 20. [Java] 프로그래머스: 게임 맵 최단 거리 BFS 최단 경로를 찾는 문제에서는 도착점에 도달한 순간 종료되는 BFS를 이용한다. DFS는 모든 경로를 탐색하기 때문에 적합하지 않다. [그래프 탐색] BFS / DFS [그래프 탐색] BFS / DFS BFS(Breadth-First Search) : 너비 우선 탐색 한국에서 여러 경유지를 거쳐 미국으로 향할 때, 어떤 경로가 가장 최단 거리일까? 최대한 넓게 이동하다가 더 이상 이동할 수 없을 때 아래로 이동하는 방 cookiee.tistory.com 전체 풀이 import java.util.*; class Solution { // 상하좌우 이동할 수 있는 좌표 int[] dx = {0, 1, -1, 0}; int[] dy = {1, 0, 0, -1}; public int solution(int[.. 2022. 11. 20. [그래프 탐색] BFS / DFS 대표적인 문제 유형 1. 경로 탐색(최단 거리, 시간) 2. 네트워크 연결 3. 조합 [Python] 백준 1260번: DFS와 BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. cookiee.tistory.com BFS(Breadth-First Search): 너비 우선 탐색 그래프에서 가까운 노드부터 우선적으로 탐색한다. 주로 두 정점 사이의 최단 경로를 찾을 때 사용한다. 방문한 노드를 차례로 저장한 후 꺼낼 수 있는 자료 구조 Queue를 사용한다. 경로가 매우 길 경우에는 탐색 가지가 증가함에 따라 많은.. 2022. 11. 19. [정렬] Comparable과 Comparator 객체를 서로 비교한다 Java에서 정렬을 할 때 흔히 Arrays.sort() 혹은 Collections.sort()을 사용한다. 이는 기본적으로 오름차순 정렬이 되어 있기 때문에 정렬 조건을 정의하기 위해서 인터페이스인 Comparable이나 Comparator를 활용해야 한다. 배열 {1, 3, 2}를 오름차순으로 정렬한다면 먼저 원소 1과 3을 비교한다. 1 - 3의 값은 음수이므로 선행 원소의 값이 더 작다는 것을 의미하고 자리를 바꾸지 않는다. 다음으로 원소 3과 2를 비교하는데, 3 - 2의 값은 양수이므로 후행 원소의 값이 더 작다는 것을 의미하여 자리를 바꾼다. 양수일 경우: 자리를 변경한다. 음수일 경우: 자리를 변경하지 않는다. Arrays.sort(arr, (a, b) -> { ret.. 2022. 10. 18. [Java] 프로그래머스 : K번째수 K번째수 문제 분석 배열1과 2차원 배열인 배열2가 주어진다. 배열1의 i번째부터 j번째까지 수를 정렬하여 k번째 수를 반환해야 한다. 배열2는 [i, j, k]를 원소로 가진다. 배열2의 길이는 고정되어 있지 않다. 먼저 반환값으로 사용할 배열을 생성한다. 배열2의 길이는 고정되어 있지 않으므로 length로 모든 요소를 순회하는 for문을 생성한다. 배열1에서 자른 요소들을 담을 list를 생성하고 배열1의 ([i][0] - 1)번 인덱스부터 ([i][1] - 1)의 인덱스를 넣는다. list를 정렬하고, get 메서드를 통해 k번째 요소를 뽑아서 반환값 담을 배열에 넣는다. 🤔 배열의 일부를 자르고 이를 담아 둘 곳이 필요하다는 점에서 한참 고민했다. 다른 효율적인 방법을 고민해 보기! 문제 풀기 .. 2022. 10. 11. [Java] 프로그래머스 : 위장 프로그래머스 : 위장 문제 분석 상의, 하의, 겉옷 등의 큰 분류 안에 여러 의상이 존재할 때, 입을 수 있는 조합의 수를 계산한다. Map을 생성하고, Key는 의상 분류, Value는 분류에 해당하는 의상의 수를 넣는다. 경우의 수는 각 Key의 Value들의 곱이다. 이때 겉옷은 입지 않고 상의와 하의만 입는 경우의 수도 있다. 각 옷의 개수에 + 1(안 입는 경우) 아무것도 입지 않는 경우는 없다. 전체에서 - 1 (상의의 수 + 1) x (하의의 수 + 1) x (겉옷의 수 + 1) - 1 문제 풀이 import java.util.*; class Solution { public int solution(String[][] clothes) { //옷의 종류를 Key로 하고, 해당하는 옷의 개수를 V.. 2022. 10. 10. 이전 1 2 3 4 5 ··· 16 다음
