하루하루 성장하는 개발자가 되자

DFS(Depth - First Search)와 BFS(Breadth - First Search) 그래프 탐색 깊이 우선 탐색 // 너비 우선 탐색 ex) 가다가 갈림길을 만났을 때 dfs -> 갈 때까지 다 가보고 다시 돌아오거나 하는 것 bfs -> 양쪽을 다 보고 가다가 또 갈리면 그 경우까지 다 문제로 나올 때는 미로 찾기 / 출구 찾기 / 어디 있는 물건 찾기 등 방문되는 순서가 다를 것이다. 그래프를 matrix로 표현하기 1. 기본 상태 - 완벽 대칭 시멘틱 하다. 0과 1은 서로 연결되어있다. 양쪽 다 연결되어있다. 대칭 2. 방향성이 있는 경우 - 대칭 x 시멘틱 하지 않다. 방향성이 있다. - 한쪽으로만 이동할 수 있다. 0에서 2는 가능하지만, 2에서 0은 불가능 - 비대칭 3. 웨이..

평균 수행 시간이 O(logN)인 알고리즘 한번 수행될 때마다 정렬되어야 하는 수의 범위가 1/2로 줄어드는 경우 퀵 정렬 이외의 다른 알고리즘은 추가적인 메모리가 필요함 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 힙 정렬(Heap Sort) Merge Sort 병합 정렬은 메모리를 가지고 있다. 처음에 엘리먼트들을 분배. 다시 병합을 하면서 처음에는 2개짜리로 2개 2개를 - 4개짜리로 4개 4개를 8개짜리로 병합하면서 정렬 Heap Sort 실제 구현은 배열로 많이 한다. 추상적으로 나타낼 때는 밑에 이미지처럼 나타낸다. 가장 작은 값 맨 위로 하면 min heap 반대는 max heap EX) 우선순위 가장 높은 애 먼저 할 때 maxheap 우선순위 해서 사용 가능 Heap..

평균 수행 시간이 O(n^2)인 알고리즘 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort), 선택 정렬(Selection Sort) 각 요소가 다른 요소와 평균 한번 이상씩 비교를 하여 정렬됨 min 정렬 기준 선택 정렬 -> 배열 요소 중에 가장 작은 값 선택해서 뽑아와서 정렬 버블 정렬 -> index 0-1 자리 비교 - 큰 값 1 자리로 -> 1-2 비교 - 큰 값 2로 -> 1번 수행할 때마다 가장 큰 값 맨 뒤로 정렬 삽입 정렬 -> 0-1 자리 비교해서 정렬된 상태에서, 추가로 하나하나 삽입해서 정렬하는 방식 -> 삽입 방법 : 이전 요소들과 비교 - 작으면 앞으로 - 크면 비교한 요소 뒤에 위치하도록 정렬 3개의 정렬 방식 모두 수행 속도가 요소 n개에 의존하고, ..

문제 정의 여러 개의 수가 정렬된 순서로 있을 때 특정한 수를 찾는 방법 단순 반복문을 이용하면 수의 개수에 따라 비교 횟수가 증가하는 O(n)의 수행이 이루어짐 수가 정렬된 상태에서는 이진 탐색(binary search)을 활용하면 매번 비교되는 요소의 수가 절반으로 감소될 수 있으므로 O(logN)의 수행으로 원하는 수를 찾을 수 있음 수의 예 : [12, 25, 31, 48, 54, 66, 70, 83, 95, 108] 83의 위치를 찾아보세요 88의 위치를 찾아보세요 해결 방법 수가 정렬된 상태이므로 중간의 값을 하나 선택한다. 찾으려는 값이 그보다 크면 범위를 오른쪽으로 그보다 작으면 범위를 왼쪽으로 좁힐 수 있다. 한번 비교 할때 마다 1/2씩 범위가 좁혀진다. 나의 시도... 실패. whil..

문제 정의 여러 개의 수가 배열에 있을 때 그중 가장 큰 값과 가장 작은 값을 찾는다. 배열의 몇 번째에 있는지 순서를 찾는다. 반복문을 한번만 사용하여 문제를 해결한다. 수의 예 : [10, 55, 23, 2, 79, 101, 16, 82, 30, 45] 해결하기 배열에 있는 수 중 맨 처음에 있는 값을 max와 min으로 가정하고, 배열의 마지막 숫자까지 비교하면서 더 큰 수나 더 작은 수가 나올 때 max와 min의 값을 바꾸도록 한다. 그때의 위치를 변수에 저장한다. 변수 선언 나열된 수의 배열 가장 큰 값 max 가장 작은 값 min 위치 표시 해줄 maxPos / minPos -> 0번째부터 반복문 선택 for - if - if 포인트! 배열의 끝까지 확인 numbers.length ( len..

wait( ) / notify( ) 메서드를 활용한 동기화 프로그래밍 리소스가 어떤 조건에서 더 이상 유효하지 않은 경우 리소스를 기다리기 위해 Thread 가 wait() 상태가 된다. wait() 상태가 된 Thread은 notify()가 호출될 때까지 기다린다. 유효한 자원이 생기면 notify()가 호출되고 wait() 하고 있는 Thread 중 무작위로 하나의 Thread를 재시작하도록 한다. 오래 기다렸거나, 우선순위 높은 Thread가 먼저 재시작되는 것이 아닌 무작위 - 영원히 선택되지 못하는 Thread 있을 가능성 존재 - notifyAll() 호출 권장 notifyAll()이 호출되는 경우 wait() 하고 있는 모든 Thread가 재시작 된다. 이 경우 유효한 리소스만큼의 Threa..

멀티 Thread 프로그래밍에서의 동기화 critical section과 semaphore critical section 은 두 개 이상의 thread가 동시에 접근하는 경우 문제가 생길 수 있기 때문에 동시에 접근할 수 없는 영역 semaphore는 특별한 형태의 시스템 객체이며 get/release 두 개의 기능이 있다. 한 순간 오직 하나의 thread 만이 semaphore를 얻을 수 있고, 나머지 thread들은 대기(blocking) 상태가 된다. semaphore를 얻은 thread 만이 critical section에 들어갈 수 있다. 노란색이 critical section // 일종의 메서드 구간이 될 수도 있고 블록 구간이 될 수도 있다. // 열쇠 get()으로 들어가서 잠근다. //..

Thread 클래스의 여러 메서드들 우선순위 / join / Thread 종료하기 priority / join() / while(!flag) Thread PRIORITY - 우선순위 Thread.MIN_PRIORITY(=1) ~ Thread.MAX_PRIORITY(=10) - 1~10까지 가능 디폴트 우선순위 : Thread.NORMAL_PRIORITY(=5) 우선순위가 높은 Thread가 CPU의 배분을 받을 확률이 높다 우선 순위가 높다고 반드시 먼저 수행이 된다는 것은 아님 X setPriority()/getPriority() Thread 우선순위 예제 Thread 생성해주고 extends Thread Thread 확인 메서드 currentThread( ) 우선순위가 비슷비슷하기 때문에 예상 실행 ..

자바에서 Thread 만들기 Thread 란? process : 실행 중인 프로그램 : 프로그램이 실행되면 OS로부터 메모리를 할당받아 프로세스 상태가 됨 thread : 하나의 프로세스는 하나 이상의 thread를 가지게 되고, 실제 작업을 수행하는 단위는 thread임 multi-threading 여러 thread가 동시에 수행되는 프로그래밍, 여러 작업이 동시에 실행되는 효과 다운로드하면서 화면에 보인다던지 / 여러 작업이 동시에 이루어지는 것처럼 보이는 - thread는 각각 자신만의 작업 공간을 가짐 ( context ) thread는 thread 마다 독립적! 자신의 변수나 처리방법 등을 가지고 있음 각 thread 사이에서 공유하는 자원이 있을 수 있음 (자바에서는 static instanc..

데코레이터 패턴을 활용한 커피 머신 프로그램 Decorator Pattern 자바의 입출력 스트림은 decorator pattern 임 여러 decorator들을 활용하여 다양한 기능을 제공 상속보다 유연한 구현 방식 데코레이터는 다른 데코레이터나 또는 컴포넌트를 포함해야 함 지속적인 기능의 추가와 제거가 용이함 component와 decorator는 동일한 것이 아님 ( 기반 스트림 클래스가 직접 읽고 쓸 수 있음, 보조 스트림은 추가적인 기능 제공 ) 예제) 커피를 만들어보아요~ Decorator Pattern을 활용하여 커피를 만들어 봅시다. 커피( 에티오피아 아메리카노 ) 카페 라떼 = 아메리카노 + 우유 모카 커피 = 아메리카노 + 우유 + 모카시럽 커피는 컴포넌트고, 우유, 모카시럽, whip..