n . n

https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 별의 개수가 최대 100개이므로, 100개를 연결해서 만들 수 있는 모든 간선의 거리를 충분히 조사할 수 있음 맨 처음에는 모든 거리 값을 구한 후, 오름차순으로 정렬하고 isChecked 배열을 만들어 방문한 별에 대하여 true 처리를 하여 cycle을 피하려 했었다... 하지만 "방문" 이 아니라 "연결" 이 되어야 하므로.. 아래의 게시글을 참고했다 https://gmlwjd9405.gith..

Q . Index 란? RDBMS에서, 테이블에 대한 검색 속도를 향상시키는 자료 구조 테이블 내의 컬럼 1개, 또는 여러 개의 컬럼을 이용하여 생성 가능 - 해당 컬럼을 정렬 후 별도 공간에 이를 저장하여, 검색 시 테이블의 레코드를 full scan하지 않고 색인화 되어 있는 index 파일을 검색하여 검색 속도를 빠르게 함. 원하는 값을 탐색하는 속도가 빠름 Q . index의 장단점 장점 데이터들이 정렬된 형태를 갖고, 따라서 검색의 속도를 향상시킴 단점 - 인덱스가 Database의 10% 내외의 공간을 필요로 하므로, 이에 따른 추가적인 공간이 필요함 - 테이블의 데이터가 변경될 때 인덱스를 재작성해야 하므로 성능이 떨어짐 -> SELECT를 제외한 동작(INSERT, UPDATE, DELET..

Q . 교착 상태란? 둘 이상의 프로세스가 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하여, 무한 대기하는 상태 - 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생함. Q . 교착 상태의 발생 조건이란? 4가지 조건이 존재하며, 모든 조건이 충족되어야 교착 상태가 발생함. 1. 상호 배제(Mutual exclusion) 자원은 한 번에 한 프로세스만 사용할 수 있음 2. 점유 대기(Hold and wait) 최소한 하나의 자원을 점유하고 있는 동시에, 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 함. 3. 비선점(No preemption) 다른 프로세스에 이미 할당된 자원은 사용이 끝날 때까지 강제로는 빼앗을 수..

추상 메소드가 오직 하나인 인터페이스 여러 디폴트 메소드가 있더라도 추상 메소드가 하나이면 함수형 인터페이스라고 함. 람다 표현식은 함수형 인터페이스를 기반으로 작성됨. @FunctionalInterface 어노테이션을 사용하여 인터페이스가 함수형 인터페이스임을 명시하고, 조건에 맞는지를 검사할 수 있음 @FunctionalInterface interface CustomInterface{ //하나의 abstract method T operation(); //상관x default void defaultOperation(){ System.out.println("Default Operation"); } static void staticOperation(){ System.out.println("Static Op..

https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 횟수를 세는 규칙을 찾는 문제 0~9 페이지 묶음은 각 숫자가 1개씩 나온 묶음이다. 10~19 묶음에서 1의 자리 숫자들의 횟수는 1개씩으로 동일하지만, 10의자리 수 1은 그렇지 않다. 이를 이용하여 x0~x9 페이지로 묶어 각 자릿수(1의자리, 10의자리, 100의자리,,)마다 횟수를 카운트하기로 함. 먼저 첫 페이지를 x0으로, 마지막 페이지를 x9로 만들기 위하여 페이지를 조정한 후, 페이지 묶음에 대하여 수를 카운트하였다 import java.io.Bu..

Proxy is a structural design pattern that lets you provide a substitute or placeholder for another object. A proxy controls access to the original object, allowing you to perform something either before or after the request gets through to the original object. Proxy란 우리말로 대리자, 대변인 이라고 한다. 위의 프록시 패턴의 정의를 다시 정리해 보면 다음과 같다. - 프록시는 구조 패턴이다. - "대체자" 로서의 Proxy를 제공하는데, 이 "대체자"는 오리지널 객체에 대한 접근을 대행하여, 직접..

Q . OSI 7계층이란? - 컴퓨터 네트워크 프로토콜 디자인과 통신을 계층으로 나누어 설명한 모델 - 통신 접속에서 완료까지의 과정을 7단계로 정의한 국제 표준 규약 - 각 계층은 독립적이며, 각 계층별로 필요한 헤더가 추가되면서 캡슐화(전송) 응용 계층(Application layer) - 사용자와 네트워크 사이의 연결(서비스 제공) - 데이터 생성 - HTTP, FTP 프로토콜 표현 계층(Presentation layer) - 데이터 표현이 상이한 프로세스에 대하여 형식 설정 데이터가 하위 계층으로 향할 때(발신) : 통신에 알맞은 형태로 데이터를 변환 데이터가 상위 계층으로 향할 때(수신) : 사용자가 이해할 수 있는 형태로 변환 세션 계층(Session layer) - 데이터의 통신을 위한 사용..

https://www.acmicpc.net/problem/17435 17435번: 합성함수와 쿼리 함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자. f1(x) = f(x) fn+1(x) = f(fn(x)) 예를 들어 f4(1) = f(f(f(f(1))))이다. n과 x가 주어질 때 fn(x)를 계산하는 www.acmicpc.net 가능한 정점의 개수는 최대 20만개, 이동 횟수는 최대 50만개이므로 단순히 f(x) 함수 값을 계속 계산하는 방법으로 풀이한다면 당연히 시간초과가 난다.. 시간 복잡도를 줄이기 위하여 희소 배열을 사용하고, 이를 적용하여 이동 횟수에 대한 탐색을 log(n)으..

희소 배열 배열 원소의 개수가 배열 length보다 작은 배열 배열 원소의 위치가 연속적이지 않음. 메모리의 낭비가 심함. 희소 배열의 특징을 이용하여 그래프의 cycle을 탐색해나갈 수 있음 희소 행렬과 유사. (희소 행렬 : 행렬의 값 대부분이 0인 경우.) EX)) 위와 같이 사이클이 있는 그래프가 존재하며, 이 그래프의 정점(V)에서 시작하여 n번씩 이동한 후의 정점을 구해야 한다고 생각해 보자. 일반적인 방법으로는 n번씩의 "이동"을 통해 도착 정점을 구할 수 있다. 하지만 이 방식은 n의 값이 커질수록 큰 비용이 필요하며, 위의 그래프에서는 사이클이 존재하므로, 생략 없이 n번 모두를 이동하는 것은 비효율적이라고 생각할 수 있다. 이를 희소 배열을 적용하여 생각해 보았을 때, 간선의 이동 횟수..

Template Method is a behavioral design pattern that defines the skeleton of an algorithm in the superclass but lets subclasses override specific steps of the algorithm without changing its structure. 상위에서 알고리즘의 뼈대를 정의하고, 하위에서 구체적인 알고리즘을 재정의 하는 패턴 이 패턴을 아래의 예시로 보면, The Template Method pattern suggests that you break down an algorithm into a series of steps, turn these steps into methods, and put ..