전체보기 (180) 썸네일형 리스트형 BFS(breadth first search) 그래프 순회 방법 중 하나 DFS가 깊이(depth)라면, BFS는 너비(breadth) 우선 탐색이기 때문에 정점에서 인접한 정점들을 우선 탐색한다. 주로 큐를 이용해 구현한다. 우선순위 큐로 구현한다면 다익스트라 알고리즘이 된다. BFS 진행은 3단계로 나눌 수 있다. 1. 시작 index를 정한다. 2. 정점의 이동반경을 확인한다. 3. 방문하지 않은 정점이 있다면, 탐색 큐에 넣어준다. BFS 탐색 순서는 다음과 같다. 시작 index는 1이라 가정한다. 인접 리스트에서 BFS 코드 더보기 import java.io.*; import java.util.*; class Main { static ArrayList[] graph = new ArrayList[10]; public static void m.. DFS(depth first search) 그래프 순회 방법 중 한가지 BFS가 너비(breadth)라면, DFS는 깊이(depth) 우선 탐색이기 때문에 정점에서 가장 멀리 떨어진 곳을 먼저 탐색한다. 주로 재귀를 통해 구현하기 때문에 백트래킹과 유사점을 갖는다. DFS 진행은 4단계로 나눌 수 있다. 1. 현재 정점과 인접한 간선들을 본다. 2. 해당 간선으로 통하는 정점을 방문했는지 본다. 3. 방문하지 않았으면 방문한다. 4. 막혔으면 되돌아간다. 다음 그래프를 DFS로 탐색하는 순서다. 왼쪽 간선부터 탐색하는 방법이다. 또한, 방향이 없는 무방향 그래프이다. 진행 순서를 붙이니 좀 지저분해 보이지만, 피보나치 수열을 재귀로 진행했을 때와 같다. 빨간 선은, 방문할 정점이 있는 노드로 호출되는 방향이다. 파란 선은, 갈 곳이 더 없기 때문.. 유니온 파인드(Union Find) 각 개체들의 집합 상태를 트리로 표현한 하나의 자료 구조다. 도식화한 모습이 트리 형태란 거지, 실제로 트리 자료구조를 직접 구현해야 하는 것은 아니다. 정확히는 각 개체들끼리 공통 부분이 없어야 한다는 조건이 있지만, 이 설명은 서로소란 것에 대한 수학적 접근이 필요하므로 위키를 보는 것을 추천한다. + 대부분 블로그 설명을 보면 정점끼리 묶는 예시가 많고 이 블로그도 그렇게 작성했다. 다만, 어떤 경우에는 정점이 아닌 다른 부분들을 합쳐야 한다는 것을 알아두자. ex) 간선의 가중치 등 다음과 같이 1~5 까지의 노드가 있다. 처음 각 노드들의 root 노드는 자기 자신이다. (부모 노드라 하는게 맞는데 편의상 root로 함) Union 서로 다른 두 개체를 합친다. 정확히는 값이 낮은 개체로 uni.. java stream이 for-loop보다 느린 이유 수정 이력 2022.12.27 맞춤법 수정 및 참조 문제 항목 추가 서론 프로그래머스에서 다른 사람들의 코드를 보면 stream을 사용한 코드들을 종종 보는데 정석적인 방식에 비해 몇 배 느린데도 숏 코딩+ 간결해 보인단 이유로 좋아요를 꽤 받는 걸 보니 이렇게 짜는 게 정말 좋은 건지 궁금해서 알아보게 됐다. 정확한 속도 측정에 관해서는 Reference 항목의 3번째 링크의 동영상을 보면 된다. https://programmers.co.kr/learn/courses/30/lessons/42578 위 문제에서 stream을 사용하지 않을 때와 사용했을 때 속도 차이다. 왼쪽이 stream을 사용하지 않은 코드 오른쪽이 stream을 사용한 코드다. stream이란? java 8부터 나온 함수형 inte.. 프로그래머스 - 쿼드압축 후 개수 세기 분할 정복 문제 1. 정사각형을 같은 크기로 4등분(길이 / 2) 2. 루프를 4번 돌려서 4등분한 길이만큼 정사각형 분할 3. 1~2 의 작업을 길이가 1이될 떄 까지 반복 4. 길이가 1일 때 현재의 원소 반환 5. 이렇게 분할된 값들을 모아서, 0과 1이 각각 몇 번 나왔는지 셈 6. 루프를 통해 0이나 1이 4번 나오면 적절히 처리해줌 7. 6번에서 0이 4번 나오면 0반환, 1이면 1 반환, 아니라면 2 반환 8. 5~7 반복 코드 더보기 class Solution { int[] answer = new int[2]; public int[] solution(int[][] arr) { int ret; ret = divide(arr, arr.length, 0 ,0); // 모든 원소가 0이나 1인 경.. 프로그래머스 - n^2 배열 자르기 예시 1번은 좌표료 표현하면 다음과 같이 표현할 수 있다. 여기서 규칙을 찾을 수 있다. 행과 열의 값중 최대 값 + 1이 해당 칸에 있는 수이다. 예를 들자면 (1, 2)에서 가장 큰 값은 2이고, 여기에 1을 더하면 3 그렇다면 공식을 다음과 같이 세울 수 있다. a = 행 / n b = 열 % n a, b 중 최대값 + 1 코드 더보기 더보기 class Solution { public int[] solution(int n, long left, long right) { int[] answer = new int[(int)(right - left + 1)]; int division = 0, remain = 0; int answerIndex = 0; while(left 프로그래머스 - 전력망을 둘로 나누기 dfs를 사용해 풀었다. 1. 1번 노드부터 dfs 실행. 방문한 노드는 다시 탐색하지 않는다. 2. 각 노드는 연결된 노드 중 방문하지 않은 노드들에 dfs 실행 3. 연결된 노드들에 대해 dfs가 끝난 노드는 자신을 포함해 dfs를 보낸 노드 수를 더한 값을 반환 ex) 예시 1번 기준 7번 노드에선 8, 9번 노드에 dfs를 실행하고 8, 9번은 각각 1을 반환 7번 노드에 대한 탐색이 끝났으면, 자기 자신을 포함해 3 반환. 4. 3번에서 반환된 값은 | (n - 반환 값) - 반환 값| 연산을 해 현재 답과 비교해 작은 것을 저장 5. 모든 노드의 탐색이 끝날 때 까지 2~4번 반복 이 결과가 끝날 때의 각 노드의 값들은 다음과 같다. (예시 1번 기준) 코드 더보기 더보기 import java.. 프로그래머스 - 이진 변환 반복하기 평범한 level 2문제 replaceAll이 생각보다 빠르지 않단 것을 알았다. 풀이 순서는 다음과 같다. 1. 문자열 s에서 0의 개수를 센다. 2. 문자열 s의 길이 - 0의 개수를 이진변환 한다. 3. 1이 되면 1,2번을 반복한 횟수와 그 떄 까지 센 0의 개수를 반환 내 풀이와 결과 더보기 더보기 class Solution { public int[] solution(String s) { // 이진 변환 횟수, 제거된 모든 0 int[] answer = new int[2]; int zeroCount = 0; int round = 0; while(true) { answer[0]++; zeroCount = 0; for(int i = 0; i < s.length(); i++) { if(s.charAt.. 이전 1 ··· 12 13 14 15 16 17 18 ··· 23 다음
