분류 전체보기99 이분탐색(Binary Search) 알고리즘 개요 이분탐색은 정렬된 데이터에서 검색 범위를 줄여나가며 원하는 데이터를 검색하는 알고리즘이다. 이진 탐색은 탐색을 반복할 때마다 탐색 범위를 반으로 줄인다. 탐색 범위가 1이 되는 최종 탐색 횟수를 k라고 하면, 1. 한 번 비교할 때의 범위는 n/2 2. 두 번 비교할 때의 범위는 n/4 3. 세 번 비교할 때의 범위는 n/8 ... k. k 번 비교할 때의 범위 n/(2^k)는 = 1 이고, k = log₂N 이다. 따라서 이진 탐색의 시간 복잡도는 O(logN)이 된다. 설명 0 1 2 3 4 5 6 7 8 9 2 5 6 9 12 13 14 18 20 23 위와 같이 정렬되어 있는 배열이 있을 때, 20을 찾는다고 가정해보자. 만약 순차탐색을 하면 0번째 인덱스, 1번째 인덱스, 2번째 인덱스 ... 2021. 10. 8. HTTP 상태코드 HTTP 웹 페이지와 같은 자원을 주고받을 때 사용하는 통신규약 상태코드 1xx: 조건부 응답, 요청을 받았으며 작업을 계속한다. 2xx: 성공, 클라이언트가 요청한 동작을 수신하여 이해했고 승낙했으며 성공적으로 처리했음 3xx: 리다이렉션 완료, 클라이언트는 요청을 마치기 위해 추가 동작을 취해야 함 4xx: 요청 오류, 클라이언트에 오류가 있음 5xx: 서버 오류, 서버가 유효한 요청을 명백하게 수행하지 못했음 2021. 10. 6. 데드락(Dead-lock) 데드락 둘 이상의 프로세스가 자원을 획득하기 위해 기다리는데, 이 lock을 잡고 있는 프로세스도 똑같이 다른 lock을 기다리면서 서로 블럭 상태에 놓이는 것을 말한다. 데드락은 다수의 프로세스가 같은 lock을 동시에 다른 명령에 의해 획득하려 할 때 발생할 수 있다. 데드락 조건 1. 상호배제: 한 자원에 대한 여러 프로세스의 동시 접근이 불가능해야 한다. 2. 점유와 대기: 자원을 가지고 있는 상태에서 다른 프로세스가 사용하고 있는 자원의 반납을 기다려야 한다. 3. 비선점: 다른 프로세스의 자원을 강제로 가져올 수 없다. 4. 환형대기: 각 프로세스가 순환적으로 다음 프로세스가 요구하는 자원을 갖고 있어야 한다. 데드락 해결 방법 1. 예방: 네 가지 조건 중 하나만을 해결한다. 2. 회피: 발.. 2021. 10. 4. [동기, 비동기] X [블로킹, 논블로킹] 동기(Synchronous) 개념 두 개 이상의 프로세스가 실행될 때 시스템 콜의 완료를 기다리는 것을 의미한다.예를 들어 A코드와 B코드가 있을 때, A 코드가 모두 진행될 때까지 B 코드가 대기하는 것이다. 특징 데이터를 주고 받는 순서가 중요할 때 사용 한 작업에 대한 시간이 길어질 경우, 전체 응답이 지연될 수 있음 비동기(Asynchronous) 개념 두 개 이상의 프로세스가 실행될 때 시스템 콜의 완료를 기다리지 않는 것을 의미한다.예를 들어 A코드와 B코드가 있을 때, A 코드가 모두 진행될 때까지 기다리지 않고 B 코드가 실행되는 것이다. 특징 요청 순서에 상관없이 동시에 다수의 작업을 처리 가능 작업이 끝날 때 이벤트를 감지하고 결과를 받아서 추가 작업을 해주는 경우도 있기 때문에, 동기.. 2021. 10. 4. 이전 1 ··· 8 9 10 11 12 13 14 ··· 25 다음
