Blog Posts

Graph

Graph

연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조로 Tree도 그래프의 일종인데 그래프 중에서도 사이클이 허용되지 않는 그래프이다. 1. 개념 정점(vertex) / 노드(node) : 위치 간선(edge) / 링크(link) : 위치간의 관계 인접 정점 : 간선에 의해 직접 연결된 노드 차수 : 하나의 노드에 인접한 노드의 수 경로 길이 : 경로를 구성하는 데 사용된 간선의 수 단순 경로 : 경로 중에서 반복되는 간선이 없을 경우 사이클 : 단순경로의 시작 정점과 종료 정점이 동일한 경로 오일러 경로 : 모든 간선을 한 번만 통과하면서 처음 정점으로 돌아오는 경로 오일러 정리 : 간선이 짝수일 때만 오일러 경로가 존재 부분 그래프 : 원래의 그래프의 일부 정점 및 간선으로 이루어진 그래프...

Read More
Splay Tree

Splay Tree

Splaying이라는 기법이 사용되며, 이는 특정 노드에 대해 접근을 하면, 이를 루트로 위치하도록 재배치 하는 기법의 트리 1. 특징 구현이 단순 많이 접근한 노드에 대해서 빠른 접근이 가능하다 접근 빈도가 불균등하거나 비 랜덤 패턴의 경우 O(lgn)보다 더 유리하다. AVL-Tree와 RB-Tree와 달리 추가 데이터 저장 필요 없다. 최악의 경우 높이가 선형, 즉 O(n)이 나올 수 있다. 세그먼트 트리로 이용이 가능하다. k번째 원소 찾기, 구간 합, lazy Propagation, 구간 뒤집기 모두 쉽게 할 수 있다. x노드를 접근한다면, splay를 통해 root로 올라오면서 x보다 작은 노드들은 Left에, 큰 노드들은 Right에 모이는 특성을 이용...

Read More
AA Tree

AA Tree

RB-Tree를 응용한 트리로 RB-Tree의 많은 조건을 일부 제거하여 구현을 더 간단하게 만든 트리로 균형을 맞추기 위해 레벨의 개념을 사용한 트리이다. 부모와 레벨이 같은 자식 노드의 연결을 수평 링크라고 하며, 이 노드를 구분하기 위해 RED라는 개념을 이용한다. 1. 특징 왼쪽 자식은 RED가 될 수 없다. 연속으로 RED가 올 수 없다. (이중 RED 불가 == 이중 수평 링크) 루트에서 null가지 leafnode까지의 경로에는 동일한 수의 블랙 노드가 존재한다. (RB Tree의 규칙) 모든 leaf node의 레벨은 1이다. 모든 왼쪽 자식의 레벨은 부모의 레벨보다 1 낮다. 모든 오른쪽 자식의 레벨은 부모와 같거나 1 낮다. 모든 오른쪽 손자의 레벨은 할아버지 노드보다 낮다. 1보다 큰 레벨의 모든 노드들은 2개의 자식을 갖는다. 왼쪽 트리를 얼핏 보면 RB-Tree같지만 왼쪽 자식은 RED를 갖지 않는 AA-Tree이고, 이를 레벨을 기준으로 보면 오른쪽과 같이 그려 볼 수 있다....

Read More
포인터

포인터

메모리 주소를 값으로 갖는 데이터 타입 1. 선언 방법 메모리주소를 가리킬 데이터타입형에 *를 붙이면 해당 타입의 메모리주소를 담는 포인트형을 선언 할 수 있다. & 를 이용해서 변수의 메모리주소 시작값을 할당 할 수 있다. 메모리 주소 시작값은 하나의 값으로 일종의 숫자 값이다. 2. 사용 방법 포인터 변수를 선언할때 말고 사용하는 시점에 변수앞에 *를 붙이면 메모리주소에 들어있는 값을 의미하고 이를 이용해 메모리주소에 값을 할당 할 수 있다....

Read More
Set

Set

  • Java
  • 2021년 6월 1일

Set은 자바의 Collection중에 객체를 중복하지 않고 하나만 저장하는 자료구조로 List와 다르게 저장순서(index)를 따로 저장하지 않기 때문에 이를 통해 접근할 수 없다. Set interface 제공 메서드 메서드 리턴 값 설명 add(E e) boolean 객체 추가성공하면 true addAll(Collection c) boolean 컬렉션을 추가하면 데이터들을 Set에 맞게 저장 remove(Object o) boolean 객체 삭제 contains(Object o) boolean 객체가 포함되었는지 여부 eqauls(Object o) boolean 같은지 비교 clear() void Set 초기화 iterator() Iterator set 요소 접근하기 위한 Iterator객체 반환...

Read More
제어문

제어문

1. if문 제어문 중에 하나로 다른 언어들과 사용목적은 동일하며 ifelse ifelse 를 똑같이 지원한다. 1) 선언 방법 Java나 c처럼 **()**로 조건문을 감싸지 않고 바로 조건문을 작성하면 되고 Java처럼 조건문은 bool타입을 반환해야 한다. C/C++처럼 0이 false, 1이상이 true로 인식되지 않는다....

Read More
구조체

구조체

여러 필드를 묶어서 사용하는 타입으로 C의 structure와 비슷하며, go에서는 별도의 클래스를 키워드를 제공하지 않지만 구조체를 이용해서 클래스를 정의할 수 있다. 1. 선언 struct을 이용해서 구조체를 선언하고 해당 형식의 구조체를 특정 이름이라는 타입으로 부르도록 하겠다라는 의미로 type을 이용해서 선언을 해주면 된다....

Read More
연산자

연산자

1. 산술 연산자 구분 연산자 연산 피연산자 타입 사칙 연산과 나머지 + 덧셈 정수, 실수, 복소수, 문자열 - 뺄셈 정수, 실수, 복소수 * 곱셈 정수, 실수, 복소수 / 나눗셈 정수, 실수, 복소수 % 나머지 정수, 실수, 복소수 비트 연산 & AND 비트연산 정수 | OR비트 연산 정수 ^ XOR비트 연산 정수 &^ 비트 클리어 정수 시프트 연산 « 왼쪽 시프트 정수 « 양의 정수 » 오른쪽 시프트 정수 » 양의 정수 산술 연산은 다른 언어의 연산과 별로 다를 것이 없으며 go는 강타입 언어이기 때문에 반드시 피연산자들끼리의 타입이 같아야만 에러가 발생하지 않는다....

Read More
Permutation(순열)

Permutation(순열)

1. next_permutation c++에는 algorithm헤더에 매개변수의 배열/iterator의 다음 순열을 적용시켜 바뀌었다면 true/false를 반환해주는 메서드가 존재해서 이를 do~while문으로 쉽게 순열문제를 해결할 수 있다. 하지만, 자바는 존재하지 않기 때문에 다음과 같이 구현할 수 있다. 2. swap 구현하기가 가장 쉬워 보통 알고리즘문제에 순열이 등장할때 많이쓰는 방식중 하나로 재귀함수를 이용한 백트래킹을 이용한 방법이다....

Read More
List를 Array로 Array를 List로 변환

List를 Array로 Array를 List로 변환

  • Java
  • 2021년 5월 27일

List와 Array간의 변환은 기본적으로 for문을 이용하여 하나하나 바꾸어주면 변환이 가능하다. 하지만 for이 아닌 stream API를 이용해서 더 간편하게 바꿀 수 있는 방법을 정리한다. 1. List에서 Array로 변환 1) List -> Object[] List에서 Wrapper객체배열로 바꾸는 것은 List의 toArray() 함수를 이용하면 쉽게 바꿀 수 있고 toArray() 의 매개변수로 변환할 객체배열을 넘겨주면 해당 타입의 배열로 바꾸어 반환된다....

Read More
Categories
Tags