전체 글 (121) 썸네일형 리스트형 이분 탐색 - Binary Search 이분 탐색 이란 탐색 범위를 두 부분으로 분할 하면서 찾는 방식 처음부터 마지막까지 돌면서 탐색하는 것 보다 훨씬 빠른 장점이 있다. 시간의 복잡도 전체 탐색 : O(N) 이분 탐색 : O(logN) 진행 순서 데이터를 정렬해야 한다. 시작 값인 start, 끝 값인 end로 중간 값인 mid 를 설정해야한다. mid값과 내가 구하고 싶은 값을 비교한다. 구할 값이 mid보다 높으면 start = mid + 1 구할 값이 mid보다 낮으면 end = mid-1 이 것을 start>=end가 될 때 까지 반복한다. Code public static int solution(int[] arr, int M) { // arr 배열에서 M을 탐색 Arrays.sort(arr); // 정렬 int start = 0;.. [JAVA] 백준 16234번 - 인구 이동 풀이방법 - 그래프 탐색 알고리즘을 이용해서 푸는 문제였다. 그 중 BFS 알고리즘을 사용해서 풀었다. - BFS 알고리즘을 이용한 이유는 각 좌표에서 이웃한 국가들, 그리고 연합과 이웃한 국가들 중에서 연합이 될 수 있는 좌표들만 탐색하면 되기 때문이다. (전체 탐색 필요 X) - 전체 map을 첫 좌표 (0,0) 부터 마지막 좌표 (n,n) 까지 탐색 하면서 BFS알고리즘을 이용해 인구 수 차이가 L~R 사이인 나라를 찾고 union 큐에 넣어줬다. > 처음엔 map과 같은 2차원 배열을 만들어서 연합이면 map[i][j] = 1로 설정해서 union 정보를 저장하려 했으나 탐색하는 과정을 한번 더 거쳐야 하는 복잡하고 번거로운 방법이라 생각하여 큐로 방법을 바꾸었다. > 큐를 사용하면 그때 그때 연.. 그래프 탐색 - DFS & BFS # DFS (깊이 우선 탐색) 루트, 혹은 임의 노드까지 다음 브랜치로 넘어가기 전에 해당 브랜치를 모두 탐색하는 알고리즘이다. 자기자신을 호출하는 순환 알고리즘의 형태로써 스택이나 재귀함수로 구현한다. 그래프의 모든 경로를 방문해야할 경우에 사용에 적합하다, # DFS Code // i 정점부터 시작. public static void dfs(int i) { visit[i] = true; // 이미 방문한 노드인지 체크를 위한 배열, Boolean System.out.print(i + " "); // j는 dfs 배열의 새로운 브랜치를 뜻함. // map은 그래프를 나타내며 그래프 연결 정보를 // map[a][b] = map[b][a] = 1; 로 저장한다. (a노드와 b노드가 연결되어있다(1)는 정.. [JAVA] 백준 14675번 - 단절점과 단절선 풀이방법 - 이번 문제에서 핵심은 단절점과 단절선을 트리에서 구한다는 점이다. 트리는 사이클이 존재하지 않고 모든 정점이 연결되어있다고 명시되어있다. 이를 이용하면 첫번째로 어떤 간선을 제거하더라도 해당 간선이 포함된 그래프가 2개 이상으로 나오게 된다. 따라서 질의 k가 2일때는 반드시 yes를 출력하면 된다. - 두번째로 어떤 정점을 제거했을때 해당 정점이 포함된 그래프가 2개 이상으로 나오지 않는 경우는 해당 정점이 '루트노드'이거나 '단말노드'일 경우이다. 루트노드나 단말노드가 아닌 단절점인 노드는 트리의 정점 개수 N만큼 반복하여 연결정보를 입력 받을 때 2번이상씩 나오게 되어있으므로 전체 연결정보를 배열에 담은 뒤 인덱스 값이 '1'인 노드가 단절점이 아닌 노드라고 보면 된다. 따라서 질의 k.. 삽입 정렬 - Insertion Sort 개념 선택 정렬과 유사하지만 좀 더 효율적인 알고리즘이다. 2번째 원소부터 시작하여 그 앞의 원소들과 비교하고 삽입할 위치를 지정한 후 원소를 뒤로 옮기고 지정된 자료를 삽입하여 정렬한다. 동작 과정 - 2번째 위치의 값을 temp에 저장 (첫번째 원소 앞에는 어떤 원소도 없기 때문) - temp와 이전 원소들을 비교하며 삽입해 나간다 - 위치 값을 저장하고 반복한다. Code void insertionSort(int[] arr) { for(int index = 1 ; index = 0) && (arr[prev] > temp) ) { arr[prev+1] .. 선택 정렬 - Selection Sort 개념 선택 정렬은 버블 정렬과 유사한 알고리즘으로 해당 순서에 원소를 넣을 위치는 이미 정해져있고 어떤 원소를 넣을지 선택하는 알고리즘이다. 동작 과정 1. 주어진 배열 중에 최소값을 찾는다. 2. 찾은 최소 값을 맨 앞에 위치한 값과 교체한다. 3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다. Code void selectionSort(int[] arr) { int indexMin, temp; for (int i = 0; i < arr.length-1; i++) { indexMin = i; for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[indexMin]) { indexMin = j; } } // 4. swap(arr[indexM.. 버블 정렬 - Bubble Sort 버블 정렬의 개념 버블 정렬은 선택 정렬과 유사한 알고리즘으로 서로 인접한 두 원소의 크기를 비교하고 조건에 맞지 않으면 서로 자리를 교환하여 정렬하는 알고리즘이다. 거품 정렬의 동작 과정 n번째와 n+1번째 원소를 비교하여 조건에 맞지 않으면 교환한다. 1회전 할 때 가장 큰 원소가 제일 마지막 순서에 정렬되고 이 수는 2회전 정렬에서 제외된다. Code void bubbleSort(int[] arr) { int temp = 0; for(int i = 0; i arr[j]) { // swap(arr[j-1], arr[j]) temp = arr[j-1]; arr[j-1] .. [JAVA] 백준 7662번 - 이중 우선순위 큐 문제 이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다. 정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 값 자체를 우선순위라고 간주하자. .. 이전 1 ··· 11 12 13 14 15 16 다음
