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)이란?‘중복 계산'을 피하기..

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..

정렬 알고리즘 시간 복잡도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(..

요즘 코프링에 관심이 좀 생겼는데 마침 모바일프로그래밍 수업도 듣게되었담 ^!^그래서 이참에 코틀린 문법을 쬠 정리 해보려구 한다 :)계속 추가해서 적을 예정임 1. 변수 선언Var읽기, 쓰기 가능Val읽기만 가능 (== 변경이 불가능!하다)Val(Var) 변수명: 타입아래는 코드예시이다Var i: Int = 10 Val j: Int = 10i = 20j = 20 //(x)에러 *Tip: 혹여나 나중에 변수를 바꾸면 안될 경우에는 Val 로 미리 선언하여 오류를 통해 방지할 수 이따! 2. ? null 기본적으로 코틀린은 Null을 허용하지않는다! (자바를 주언어로 하는 나에겐... 신세계....!!! ㄱ- 맨날 NPE땜에 스트레쓰받는... ㅋㅅㅋ)만약 Null을 허용하고싶다면 타입 옆에 ?를 붙이자!V..

알고리즘 문제를 풀다가 ArrayList로 풀어야 하다가도 리턴은 Array여서 바꿔야할 경우가 많았구, 특히 ArrayList는 Integer 이고, Array는 int 인 경우가 많아 이부분에 대해서 공부가 필요했다!1. ArrayList 두가지 방법1)ArrayList list = new ArrayList(Arrays.asList("aa","bb","cc")); 2)ArrayList list = new ArrayList();list.add("bb");list.add("aa");list.add("cc"); +) ArrayList 출력은 그냥 값을 넣으면 된다! 참고로 그냥 배열(Array)은 Arrays.toString(list)로해야한다는 사실! 2.ArrayList -> String[] 으로 ..

문자열 함수를 정리해볼까 ㅎ ! 한다 1. equals(String s)두개의 문자열이 동일한 값을 가지고 있는지 (true, false) 반환형태는 a.equals(b) 로 !String str = "hello";System.out.println("hello".equals(str)); //true 2.indexOf(String s)문자열에서 특정 문자가 시작되는 인덱스 반환String str = "abcdef";System.out.println(str.indexOf("b"); //1"b"가 아니라 "bcd"이여도 첫번째 글자인 "b" 기준으로 반환 하는거 주의하자! 3.length()문자열 길이 반환String str = "hello";System.out.println(str.length()); //..

알고리즘을 요즘 풀고있는데 스택과 큐에 대한 정리를 하면 좋을것 같은 생각이 ㅠㅠ ...!!각각 어떤 메서드가 있는지 알아보고 열심히 써보도록하자 (´ヮ`) 0. Stack과 Queue 구조 1)Stack(스택)일명 박스쌓기! 선입후출(FILO) 구조 또는 후입선출(LIFO)구조라고 한다!FILO == First In Last Out2)Queue(큐)일명 대기줄!이라고 할수있다. 선입선출(FIFO)구조라고한다. (공정하죠?^,^)FIFO == First In First Out 1.Stack 메서드boolean isEmpty() / empty()Stack이 비어있으면 True,Stack이 비어있지않으면 FalseObject peek()Stack의 맨 위 저장된 객체 반환pop() 과 다른점: 객체를 꺼..

자바에서 정렬을 할 경우 Arrays의 sort()함수를 많이 사용하는데!! 정확하게 알아보자:) Arrays 사용하려면 import java.util.Arrays; 해줘야함!!1. 오름차순어떤 배열이든 미리 선언을 해야함!Arrays.sort()함수를 사용하면된다 ^,^int[] array = {3,4,1,2,5}; //int[] array = new int[] {3,4,1,2,5};Arrays.sort(array); **배열 출력시1) Arrays의 toString() 사용System.out.println(Arrays.toString(array)); //[1,2,3,4,5]그냥 array 혹은 array.toString() 할 시 메모리주소값 출력되니 주의하자! 2) 반복문사용for (int i ..

1. String vs StringBuffer 와 StringBuilderString : 불변성(Immutable)갖음 - 할당된 공간이 변하지 않음StringBuffer, StringBuilder : 가변성(mutable)갖음 - 할당된 공간이 변함String str = new String("hello"); (1)str = str + " world"; //hello world (2) (1)에서는 str --> hello 를 가르켜 메모리 주소가 할당(2)에서는 str --> hello world를 가르켜 메모리 주소가 할당 이때 hello 값이 들어간 메모리영역 != hello world 값이 들어간 메모리영역(즉, hello 값이 들어간 메모리영역은 Garbage가 된다!) 변하지않은 문자열을 추가,..