분류 전체보기22 [JAVA] PriorityQueue - 우선순위 큐 기존에 큐에 대해서 다룬적이 있었는데, 이번 주차 알고리즘은 '그래프'! 였다!그래프 이론에 대해 공부하다가 우선순위 큐에 대해 알아야할 것 같아서 따로 빠르게 정리해보고자 한다! 01. PriorityQueue란?일반적인 큐의 구조 FIFO(First In First Out)를 가짐대신, 들어온 순서대로 나가는 것이 아닌 우선순위를 먼저 결정하고 높은 데이터가 먼저 나가는 자료구조* 우선순위큐에 저장할 객체는 Comparable Interface를 구현해야한다->이때 comparaTo method를 오바라이드하여 구현해줘야한다!이 부분에서 우선순위 조건을 리턴해주면, 해당 조건으로 우선순위가 적용되도록 객체를 추출해주는 방식!02. PriorityQueue 선언 및 메소드// 우선순위가 낮은 숫자가 먼.. 2024. 7. 1. [알고리즘] DP DP피보나치 수열로 재귀, DP 모두 비교해보기!1. 재귀함수자기 자신을 호출하는 함수로 반복적으로 호출을 함으로써 원하는 결과를 도출피보나치는 O(2^N) 시간복잡도 걸림public static int fibonacci_recur(int n) { //O(2^N) if (n 2. DP1) DP의 핵심최적 부분 구조'큰 문제의 최적해'가 '작은 문제의 최적해'를 포함하는 성질중복 부분 문제'동일한 작은 문제를 반복적으로 해결'해야 하는 성질💡 이 순서대로 해보자!1. DP 방식을 적용할 수 있는지 확인하기: 최적 부분 구조, 중복 부분 문제인지 따져보기2. 점화식 세우기 : 일반화 할 수 있는 수식 생각하기 2) DP의 종류💡 메모이제이션(Memoization)이란?‘중복 계산'을 피하기.. 2024. 5. 25. [알고리즘] BFS/DFS 0. 그래프0.1 그래프정점(node 혹은 vertex)과 간선(edge)로 이루어지 자료구조정점: 데이터를 저장하는 위치간선: 정점을 연결하는 선인접 정점: 간선에 의해 직접 연결된 정점 (ex. 1과 2는 인접 정점)차수: 무방향 그래프에서 하나의 정점에 인접한 정점의 수ex. 1의 차수: 2와 50.2 그래프 구현 방법0.2.1 인접 행렬 (Adjacency Matrix)2차원 배열 이용matrix[ i ][ j ] == true 라면 i -> j로의 간선이 있음의미int 행렬의 경우 1 = true, 0 = false배열 구성 → 간선 정보 조회빠름 O(1)간선의 개수 무관하게 항상 n^2의 메모리 공간 차지인접한 노드를 찾기 위해 모든 노드 전부 순회해야함0.2.2 인접 리스트(Adjacency.. 2024. 5. 7. [알고리즘] 정렬 정렬 알고리즘 시간 복잡도Bubble Sort (버블 정렬)O(n^2)Selection Sort (선택 정렬)O(n^2)Insertion Sort (삽입 정렬)O(n^2)Quick Sort (퀵 정렬)평균 : O(nlogn) / 최악 : O(n^2)Merge Sort (병합 정렬)O(nlogn)Radix Sort (기수 정렬)O(kn) / k : 최대 데이터의 자릿수Arrays.sort()평균 : O(nlogn) / 최악 : O(n^2)Collections.sort()O(nlogn)1. 버블정렬1.1 개념순서대로 보면서 두 수를 비교해서 오른쪽 수가 왼쪽수보다 더 작으면 교화한번 작업 시 → 맨 마지막 자리에 가장 큰수가 가게 되는 원리즉, 마지막을 제외하고 n-1번 작업을 하면 정렬완료시간 복잡도 O(.. 2024. 5. 7. Kotlin 기본 문법 정리 요즘 코프링에 관심이 좀 생겼는데 마침 모바일프로그래밍 수업도 듣게되었담 ^!^ 그래서 이참에 코틀린 문법을 쬠 정리 해보려구 한다 :) 계속 추가해서 적을 예정임 1. 변수 선언 Var 읽기, 쓰기 가능 Val 읽기만 가능 (== 변경이 불가능!하다) Val(Var) 변수명: 타입 아래는 코드예시이다 Var i: Int = 10 Val j: Int = 10 i = 20 j = 20 //(x)에러 *Tip: 혹여나 나중에 변수를 바꾸면 안될 경우에는 Val 로 미리 선언하여 오류를 통해 방지할 수 이따! 2. ? null 기본적으로 코틀린은 Null을 허용하지않는다! (자바를 주언어로 하는 나에겐... 신세계....!!! ㄱ- 맨날 NPE땜에 스트레쓰받는... ㅋㅅㅋ) 만약 Null을 허용하고싶다면 타입.. 2024. 3. 27. 이전 1 2 3 4 5 다음
