Algorithm with Java

[Java] 비트 마스킹, Next_Permutation

작성자:
Featured image for [Java] 비트 마스킹, Next_Permutation

  1. 비트연산 연산자 설명 예시 & 비트 AND 연산 5 & 3 = 1 ^ 비트 XOR(배타적 OR) 연산 5 ^ 3 = 6 ~ 비트 NOT 연산 (1의 보수) ~5 = -6 << 왼쪽 시프트 연산 (비트를 왼쪽으로 이동) 5 << 2 = 20 >> 오른쪽 시프트 연산 (비트를 오른쪽으로 이동) 5 >> … 더 읽기

[Java] 트리

작성자:
Featured image for [Java] 트리

  Tree에 대한 이론은 앞서 정리했었다. 1. 이진트리 – 특성 2. 이진 트리 – 구현 가. 배열 – 노드 번호를 인덱스로 사용 이진트리를 배열로 표현할 때 주의점 나. 배열 – 값을 인덱스로 사용 노드 번호를 인덱스로 사용하지 않고 별도의 클래스를 정의하고 그곳의 멤버 변수로 저장한다. 대신 특정한 value값을 인덱스로 사용한다. (ex. 배열의 인덱스, ascii 코드) … 더 읽기

[Java] 연결 리스트

작성자:
Featured image for [Java] 연결 리스트

  1. 리스트 순서를 가진 데이터의 집합을 가리키는 추상자료형. 값의 중복을 허용한다. 2. 연결 리스트 가. 단순 연결 리스트 다음 노드에 대한 참조값만 가지고 있음. 1) 단순 연결 리스트 응용 – Stack 스택은 한쪽 끝에서만 삽입/삭제가 발생하므로 단순 연결 리스트로도 충분히 구현할 수 있다. 단순 연결 리스트로 스택을 구현할 때 top으로 1번 자리가 2번보다 더 … 더 읽기

[Java] Heap

작성자:
Featured image for [Java] Heap

1. Heap 가. 데이터 삽입 나. 데이터 삭제 최댓값 혹은 최솟값이 저장된 루트 노드만 제거할 수 있다. 우선순위 큐(priority queue)를 구현하거나, 힙 정렬(heap sort)을 만들 때 사용된다. 출처 : https://namu.wiki/w/힙 트리 다. 구현 최소힙 예시 (코드 출처 : https://go-coding.tistory.com/25) 라. 관련 문제 1927번: 최소 힙 11279번: 최대 힙 11286번: 절댓값 힙 5. Priority Queue

[알고리즘] 12891. DNA 비밀번호

작성자:
Featured image for [알고리즘] 12891. DNA 비밀번호

0. 문제 12891번: DNA 비밀번호 1. 문제 이해 수학 잘 못함. 2. 제출 조건을 만족하는 부분 순열을 구하는 문제다. 매번 문자열을 새로 카운팅하면 시간을 초과한다. 슬라이딩 원도우를 사용해서 나가는 것과 들어오는 것만 체크한다.

[알고리즘] 2023. 신기한 소수

작성자:
Featured image for [알고리즘] 2023. 신기한 소수

0. 문제 2023번: 신기한 소수 1. 시간초과 2. 시간 줄이기 위를 바탕으로 코드를 최적화한다. 먼저 수(i)를 만들고 특정 자리까지만 숫자(num)를 가져오기 위해서 Math.pow()를 사용했다. 무조건 숫자(i)를 만들고 각 자리의 수가 2, 3번 조건을 만족하는지 확인하다 보니 불필요한 연산이 발생했다. 1번과 2번 조건을 만족하는 숫자만 생성하고 3번 조건을 만족하는지 확인하면 불필요한 연산을 줄일 수 있다. 재귀함수로 … 더 읽기

[Java] Stack, Queue, Priority Queue

작성자:
Featured image for [Java] Stack, Queue, Priority Queue

1. Stack Stack underflow와 overflow를 조심하자. 2. Queue Java의 java.util.Queue는 interface다. 구현체로는 대표적으로 ArrayDeque 또는 LinkedList를 사용한다. 대부분의 상황에선 LinkedList보다는 ArrayDeque를 사용하자. ArrayDeque 양쪽 끝에서 삽입, 삭제하기에 효율적이다. 3. Priority Queue 기본은 오름차순으로 정렬한다. 정렬의 순서를 자신이 원하는 방법으로 바꾸고 싶다. → Comparator를 추가한다. 또는 Comparable을 구현해도 된다. Data Structure Insertion Time Complexity Deletion Time … 더 읽기

[Java] 부분집합

작성자:
Featured image for [Java] 부분집합

  종류 설명 기호 시간 복잡도 순열 N개의 원소 중 R개의 원소로 순서를 가진 부분집합을 만드는 경우의 수 nPr O(N!) 조합 N개의 원소 중 R개의 원소로 부분집합을 만드는 경우의 수 nCr O(n! /( r! x (n-r)!)) 부분집합 N개의 원소로 부분집합을 만드는 모든 경우의 수 nHr O(2^N) 집합에 포함된 원소들을 선택하는 것. 원소들의 그룹에서 최적의 부분 … 더 읽기