본문 바로가기

전체 글

 (159)
데크, 우선순위 큐 Deque스택과 큐의 특징을 모두 갖고 있는 복합 자료형양쪽 끝을 모두 추출할 수 있는 큐를 일반화한 형태의 추상 자료형Deque deque = new LinkedList();우선순위 큐어떠한 특정 조건에 따라 우선순위가 가장 높은 엘리먼트가 먼저 추출되는 자료형정렬 알고리즘을 사용하면 우선순위 큐를 만들 수 있다.시간 복잡도삽입,삭제: O(S(n))
Kotlin In Action - 코틀린이란 무엇이며, 왜 필요한가? 코틀린자바플랫폼에서 돌아가는 새로운 프로그래밍 언어간결하고 실용적이며, 자바와 상호운영성목적자바가 사용되는 곳에서 더 간결하고생산적이며 안전한 대체 용어 제공정적 타입 지정 언어모든 프로그램 구성 요소의 타입을 컴파일 시점에서 알 수 있고 프로그램 안에서 객체의 필드나 메소드를 사용할 때 마다 컴파일러가 타입을 검증장점성능: 실행 시점에서 어떤 메소드를 호출할지 알아내는 과정이 필요 없으므로 빠르다신뢰성: 컴파일러가 프로그램의 정확성을 검증유지 보수성: 타입을 미리 알 수 있어 처음 보는 코드를 다룰 때 쉽다도구 지원: 더 안전하게 리팩토링 가능하고, 더 정확한 코드 완성 기능 제공타입추론컴파일러가 문맥을 고려해 변수 타입을 결정한다.함수형 프로그래밍일급 시민인 함수 : 함수를 일반 값 처럼 다룰 수 있..
다익스트라 최단 거리를 구하는 알고리즘출발 노드와 모든 노드 간의 최단 거리 탐색에지는 모두 양수시간 복잡도: O(ElogV)원리인접 리스트로 그래프 구현하기최단거리 배열 초기화값이 작은 노드 고르기최단 거리 배열 업데이트 하기3~4 반복해 최단거리 배열 완성방문한 배열은 제외
위상 정렬 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘시간 복잡도 O(V+E)ex) '답이 여러가지 경우에는 아무거나 출력한다' 라는 말이 키핵심 이론진입차수: 해당 노드를 바라보는 엣지의 수그래프 데이터가 주어지면, 연결 리스트를 만들고, 진입 차수 배열을 0으로 초기화진입 차수가 0인 노드 선택, 정렬 배열에 저장가리키는 데이터를 -1씩 해준다.다시 0인 노드를 선택,  정렬 배열에 저장가리키는 데이터를 -1
자바의 신 17장 Annotation클래스나 메소드 선언시에 @을 붙이는 것용도: 제약사항 선언, 용도, 행위, 처리 등을 나타냄 @Override: override 된 것을 명시적으로 표시 @Deprecated: 사용되지 않는 것을 알려줌사용이유: 계도기간을 거쳐 상의 후 삭제해야 하므로@SuppressWarnings: 컴파일러에게 경고를 막는 것메타 어노테이션(커스텀 어노테이션)어노테이션을 선언할 때 사용java.lang.annotation을 import@Target: 어노테이션 적용 대상@Retention: 어노테이션 정보 유지 기간@Documented: Javadocs에 포함되는 지@Inherited: 어노테이션의 상속이 가능한지 @interface: 어노테이션 선언 시 Reflection 사용시 runtime에 ..
유니온 파인드 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산, 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘연결 되어 있지 않으면 자기 자신이 대표노드가 되므로, 자기 자신을 저장항상 대표 노드끼리 연결해 준다.find 작동 원리대상 노드 배열에 index값과 value 값이 같은지 확인다르면 value와 같은 index로 이동index와 value가 같을 때 까지 반복나오면서 값을 1로 만들어 줘야함유니온 파인드 목적같은 집합인지 찾는 것중요사항find 구현값이 들어오면 그 값이 index와 value가 같은지 확인find를 돌아 나오면서 값을 변경하는 경로 압축과정다르면 그 index위치의 value는 재귀로 find를 돌았을 때 시작노드
자바의 신 21장 Generic 제네릭단어의 뜻 : 일반적인클래스 내부에서 사용할 데이터 타입을 외부에서 지정하는 기법클래스와 인터페이스만 적용클래스에서는 T로 작성해도 되나, 사용시 즉 선언시에는 타입을 명시해줘야 함. 변성두 타입이 서로 상속 관계에 있을 때 각 타입을 Type Argument로 받고 있는 Base Type이 어떤 관계에 있는지에 대해 나타내는 것공변성, 반공변성, 무공변성공변성: 하위 타입 관계가 보존되는 성질 / 상한 경계반공변성: 상위 타입 관계가 보존되는 성질 / 하한 경계무공변성: 타입 일치가 엄격한 성질존재 목적: 형 시스템을 안전하고 유연하게 설계가능장점재사용성 증가컴파일 시 타입 에러 발견컴파일러가 타입 변환 수행주의사항원시타입(int, long)은 사용할 수 없다.제네릭 타입을 사용한 객체 생성은 불..
그래프 노드와 에지(연결선)로 구성된 집합 유니온 파인드 그래프의 사이클 유무 판별하는 알고리즘 위상 정렬 사이클이 없는 방향이 있는 그래프 일 때 ex) 수강신청, 테크트리 같이 전 후 관계가 있는 그래프 다익스트라, 벨만-포드, 플로이드-워셜 최단거리 알고리즘 S 시작점에서 다른 모든 노드로 가능 최단거리를 구하는 알고리즘 간선의 가중치가 음수면 안된다. (다익스트라) 간선의 가중치가 음수도 가능(벨만-포드) 시작점이 없고, 모든 노드에 최단거리, 대신 시간이 오래걸림(플로이드-워셜) 최소 신장 트리 모든 노드를 연결하는 데 최소 비용을 사용해서 하는 알고리즘 유니온 파인드를 포함 표현 방법 에지리스트 가중치 없는 그래프 구현 2차원 배열로 표현 가중치가 있는 그래프 2차원 배열을 3으로 저장 벨만 포드, ..

티스토리툴바