인접행렬 인접리스트 인접행렬 인접리스트 비교
Problem Solving/자바 문법
이터레이터는 헷갈린다. 이전의 것이 반환되는데 이것을 둘사이를 이어주는 링크에 위치한다고 생각하면 이해가 쉬울 수도 있다. iterator(4)도 존재할 수 있고 그 이후도 존재할 수 있다. 값은 null일 것이다.
배열 리스트 vector는 Collection이전의 클래스. 속도가 비교적 느림. 또한 코테는 싱글스레드이기에 코테에서는 맞지않다. ArrayList 와 LinkedList ArrayList add는 O(N)이지만 평균적으로는 O(1)이다 Capacity가 전부 찼을경우에만 O(N)인데 1.5배씩 크게 만들기 때문에 크기가 커질수록 grow가 적어진다. 더군다나 크기가 작을 때 grow는 O(상수)급이기에 크게 신경 ㄴㄴ 결론: 최악 O(N)이지만 O(1)로 여겨도 크게 문제 없다. 코테에서는 신경쓰기 import java.util.Arrays; public class MyArrayList { private static final int DEFAULT_CAPACITY = 10; private int si..
범위를 좁혀가면서 경계선을 찾는다.
비트 연산자는 말 그대로 비트 단위로 연산이 이루어지는 연산자이다. '암호화' 작업처럼 임의의 숫자를 만든다거나, 메모리 용량이 부족할 때, 계산이 복잡해서 속도가 느려질 때 비트 연산자를 이용해서 빠른 속도로 계산을 할 수 있다. 데이터는 컴퓨터 내부에서 0과 1로 이루어져 있기 때문에, 0 또는 1로 표현할 수 있는 최소단위인 비트로 계산할 때 속도가 빠른 것이라고 이해할 수 있다. 비트 (bit) : 0 또는 1로 표현할 수 있는 최소 단위, 8비트가 모이면 1 바이트(Byte)가 된다. 비트 논리 연산자 & | ^ ~ & (AND) 연산자 두 개의 비트값이 모두 1인 경우에만 연산 결과 값이 1이 된다. int num1 = 5; int num2 = 10; int result = num1 & num..
HashSet 기본적인 SET 순서가 뒤죽박죽임 HashSet은 Set 인터페이스의 구현 클래스입니다. 그렇기에 Set의 성질을 그대로 상속받습니다. Set은 객체를 중복해서 저장할 수 없고 하나의 null 값만 저장할 수 있습니다. 저장 순서가 유지되지 않습니다. 만약 요소의 저장 순서를 유지해야 한다면 JDK 1.4부터 제공하는 LinkedHashSet 클래스를 사용하면 됩니다. Set 인터페이스를 구현한 클래스로는 HashSet과 TreeSet이 있는데 HashSet의 경우 정렬을 해주지 않고 TreeSet의 경우 자동정렬을 해준다는 차이점이 있습니다. Set의 가장 큰 장점은 중복을 자동으로 제거해준다는 점입니다. 삽입 삭제 조회 시 0(1)을 기대할 수 있지만 해시충돌 같은 이슈로 더 늘어 날 ..
시간복잡도 대표 표현식 위일수록 빠르다. 빠른 순서 ↑ 상수 시간 O(1) 로그시간 O(log N) 직선형 시간 O(N) 2차 시간 O(n^2) 지수 시간 O(C^n) 느린 순서 ↓ LIST #ArrayList 시간복잡도 add : O(1) remove : O(n) get : O(1) Contains : O(n) iterator.remove : O(n) java 1.2에 추가, thread-safe 보장 안함 특징 : 데이터 추가,삭제를 위해 임시 배열을 생성해 데이터를 복사 - 대량의 자료를 추가/삭제시 복사가 일어 나게 되어 성능 저하를 일이킴 - 데이터의 인덱스를 가지고 있어 데이터 검색시 빠름 #LinkedList 시간복잡도 add : O(1) remove : O(1) get : O(n) Cont..
가장 큰 차이는 삽입시의 순서가 지켜지느냐이다. HashMap의 경우 순서가 보장되지 않는다( 사전순도 아니다) 하지만 LinkedHashMap의 경우 넣은 순서대로 정렬이 된다. 반복문으로 키값을 출력시 알 수 있다. 성능의 차이는 있지만 크게 고려할 부분은 아닐 것이다. 공통점 데이터를 key-value 쌍으로 저장한다. 비동기로 처리된다. Key 중복을 허용하지 않는다. 하나의 null 값을 저장할 수 있다. Value 중복을 허용한다. 여러 개의 null 값을 저장할 수 있다. 차이점 HashMap 데이터의 삽입 순서를 보장하지 않는다. AbstractMap 클래스를 상속하고, Map 인터페이스를 구현한다. 연결리스트로 이루어진 배열로 구현됨 LinkedHashMap 데이터의 삽입 순서를 보장한다..
