본문 바로가기

언어99

알고리즘 6 미로 찾기 문제 입구에서 출구로 통하는 길을 찾는 미로 찾기 문제 스택을 활용하여 문제를 해결할 수 있음 출구 탐색을 위해 BFS나 DFS로 해결할 수 있음 아래 그림에서 Enter 에서 Exit을 찾아가는 path의 좌표를 출력하세요 움직 일 수 있는 방향의 예: [2,2] 위치에서 볼 수 있는 도달 가능 위치는 N(2,1), E(3,2), S(2,3), W(1,2) 하나의 위치를 방문할 때마다 stack에 위치를 저장한다.(push) 저장된 위치에서 더 이상 갈 곳이 없는 경우 되돌아 간다. (pop) stack에서 꺼낸 위치에서 가지 않은 곳을 찾아 간다. 미로 정의 package algorism.ch06; public class Maze { public int[][] myMaze ={ {0, 1,.. 2021. 5. 30.
알고리즘 5 최단거리 구하기 모든 노드 중 연결된 최단거리를 가진 노드를 찾는다. 노드 v에 인젒한 노드 w에 대해 다음 조건이 성립하면 w에 대한 최단 거리를 업데이트 한다. (즉 원래 w로 가던 거리보다 v를 거쳐 가는 거리가 더 가까우면 w로 가는 거리는 v를 거쳐가는 것으로 최단 거리를 수정) Yw = Yv + Cvw if Yv + Cvw < Yw package algorism.ch05; class MyGraph{ private int count; //노드 수 private int[][] vertexMatrix; // matrix로 그래프 표시 private int[] distance; // 특정 노드에 대한 각 노드의 최단 거리 private boolean[] visited; // alread visited.. 2021. 5. 30.
알고리즘 3 정렬 알고리즘 평균 수행 시간이 O(n^2)인 알고리즘 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort), 선택 정렬(Selection Sort) 각 요소가 다른 요소와 평균 한번 이상씩 비교를 하여 정렬 됨 Insertion Sort 구현 Insertion Sort의 기본 개념은 이미 정렬된 상태의 요소에 새로운 요소를 추가할 때 정렬하여 추가하는 개념(손안의 카드) 두 번째 요소 부터 이전 요소들과 비교하면서 insert될 위치를 찾아가며 정렬하는 알고리즘 package algorism.ch03; public class InsertionSort { public static void insertionSort(int[] arr, int count) { int i = 0, j = .. 2021. 5. 30.
알고리즘 2 정렬된 수에서 하나의 수의 위치 찾기 문제 정의 여러 개의 수가 정렬도니 순서로 있을 때 특정한 수를 찾는 방법 단순 반복문을 이용하면 수의 개수에 따라 비교 횟수가 증가하는 O(n)의 수행이 이루어짐 수가 정렬된 상태에서는 이진 탐색을 활용하면 매번 비교되는 요소의 수가 절반으로 감소될 수 있으므로 O(logN)의 수행으로 원하는 수를 찾을 수 있음 수의 예: [12, 25, 31, 48 ... ] 83의 위치를 찾아보세요 88의 위치를 찾아보세요 해결 방법 수가 정렬된 상태이므로 중간의 값을 하나 선택한다. 찾으려는 값이 그보다 크면 범위를 오른쪽으로 그보다 작으면 범위를 왼쪽으로 좁힐 수 있다. 한번 비교할 때마다 1/2씩 범위가 좁혀진다. package algorism.ch02; public cl.. 2021. 5. 30.
알고리즘 1 나열된 수에서 최솟값과 최댓값 구하기 문제 정의 여러 개의 수가 배열에 있을 때 그 중 가장 큰 값과 가장 작은 값을 찾는다. 배열의 몇 번째에 있는지 순서를 찾는다. 반복문을 한번만 사용하여 문제를 해결한다. 수의 예: [10, 20, 33.....] 해결방법 배열에 있는 수 중 맨 처음에 있는 값을 max와 min으로 가정하고, 배열의 마지막 숫자까지 비교하면서 더 큰수나 더 작은수가 나올 때 max와 min의 값을 바꾸도록 한다. 어떻게 메모리를 활용하는지가 중요 package algorism.ch01; public class MinMaxProblem { public static void main(String[] args) { int[] numbers = {10, 55, 23, 2, 79, 101,.. 2021. 5. 30.
wait() / notify() 메서드를 활용한 동기화 프로그래밍 리소스가 어떤 조건에서 더 이상 유효하지 않은 경우 리소스를 기다리기 위해 Thread가 wait() 상태가 된다. wait() 상태가 된 Thread은 notify()가 호출 될 때 까지 기다린다. 유효한 자원이 생기면 notify()가 호출되고 wait() 하고 있는 Thread 중 무작위로 하나의 Thread를 재식작 하도록 한다. notifyAll()이 호출되는 경우 wait()하고 있는 모든 Thread가 재시작 된다. 이 경우 유효한 리소스만큼의 Thread만이 수행될 수 있고 자원을 갖지 못한 Thread의 경우는 다시 wait() 상태로 만든다. 자바에서는 notifyAll() 메서드의 사용을 권장한다. 도서관에서 책을 빌리는 예제 package ch67; import java.util.A.. 2021. 5. 29.

티스토리툴바