티스토리

Juno's daily

검색하기

블로그 홈

Juno's daily

juno-juno.tistory.com/m

Everything is always impossible until someone does it.

구독자: 3

방명록 방문하기

주요 글 목록

점근적 분석(Asymtotic Analysis)과 분할 상환 분석(Amortized Analysis) 1. 점근적 분석(Asymtotic Analysis) 이란 임의의 함수가 N -> ∞ 일때, 어떤 함수 형태에 근접해지는지 분석하는 방법이다. 예를들어 f(n) = n2 + 3n 일때, n이 매우 커진다면, 3n은 n2에 비해서 중요도가 떨어진다. n이 매우 커진다면, "f(n) is asymptotic to n2" 라고 할 수 있다. 이 접근적 분석때문에 시간 복잡도 계산시 최고차항을 제외한 모든 항과 최고차항의 계수를 무시하는 것이다. 2. 점근 표기법(Asymtotic Notation) 점근 표기법에는 세 가지 표기법이 있다. (1) Big- omega (Ω): lower bound. 점근적 하한 (2) Big-O (O): upper bound. 점근적 상한 (3) Big-theta (Θ): tig.. 공감수 0 댓글수 0 2023. 4. 20.
그래프(Graph) 1. Graph - graph is simply a set of values that are related in a pair wise fashion. - Node(=Vertex)와 Edges(간선)로 이루어짐. - great data structure to model real world relationships. - LinkedList는 Tree의 일종이고, Tree는 Graph의 일종이다. (Tree는 directed graph) - self-edge라고 node가 자기 자신을 가리키는 경우가 있을 수 있다. 2. Graph의 종류들 (1) directed : 방향성이 있음. 일방통행 (2) undirected : 방향성이 없음. 양방향 통행 (1) weighted : 가중치 그래프 (2) unweig.. 공감수 3 댓글수 0 2022. 9. 23.
검색 (선형검색, 이진검색) 1. 검색 알고리즘 일단 이 포스트에서 다룰 것은 a의 배열 검색이다. 배열 검색은 다음과 같은 알고리즘을 사용한다. (1) 선형 검색 (Linear Search) : 무작위로 늘어놓은 데이터 모임에서 검색을 수행한다. (2) 이진 검색 (Binary Search) : 일정한 규칙으로 늘어놓은 데이터 모음에서 아주 빠른 검색을 수행한다. (3) 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행한다. 2. 선형 검색 ( ==순차검색 ) 배열에서 검색하는 방법 가운데 가장 기본적인 알고리즘이다. 요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날때 까지 맨 앞부터 순서대로 요소를 검색한다. (기본적으로 n(배열길이) for문 돌면서 키 값 요소와 비교.. 공감수 0 댓글수 0 2022. 9. 17.
정렬(Sorting) - 버블, 선택, 삽입 1. 정렬이란? 정렬은 이름, 학번, 키 등 핵심 항목의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업을 말한다. 이렇게 정렬하면 검색을 더 쉽게 할 수 있다. (파일을 알파벳 순으로 정렬하고 찾으면 더 찾기 쉬운것 처럼) 또한 정렬시에 같은 값의 키를 가진 요소의 순서가 정렬 전후에도 유지되는것을 안정된 정렬이라고 하고, 안정되지 않은 알고리즘을 사용하면 같은 키를 가진 요소의 순서가 정렬 전후에 유지 되지 않는다. 2. 외부 정렬과 내부 정렬 (1) 내부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장 할 수 있는 경우에 사용하는 알고리즘 (2) 외부 정렬 : 정렬할 데이터가 너무 많아 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘 3. 버블 정렬 (Bubbl.. 공감수 0 댓글수 0 2022. 9. 15.
Stack과 Queue 1. Stack이란 스택은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조로, 데이터의 입력과 출력 순서는 LIFO(Last In, First Out)이다. 스택에 데이터를 넣는 작업을 push라고 하고, 스택에서 에이터를 꺼내는 작업을 pop이라고 한다. 스택의 가장 윗부분(push와 pop을 하는)을 top이라고 하고, 스택의 가장 아랫부분을 bottom이라고 한다. Stack은 자리 이동이 없고 순차적으로 데이터를 추가하고 삭제하기 때문에 ArrayList와 같은 배열기반의 컬렉션 클래스를 통해 구현하는 것이 적합하다.. (1) Stack의 예시 : 자바 프로그램에서 메소드를 호출하고 실행하는 프로세스 익히 잘 알고 있는 Call stack의 과정이다. void x() {/* ... */} vo.. 공감수 0 댓글수 0 2022. 7. 26.
이번주 코테문제 풀면서 배운것 3 1. java.util 패키지의 유용한 클래스 (1) java.util 패키지의 Objects 클래스 (java.lang 패키지의 Object 클래스와 유의) - Math 클래스 처럼 모든 클래스가 static. 객체의 비교나 null check에 유용함. - Objects.isNull(obj)이나 Objects.nonNull(obj) 같이 해당 객체가 null인지 아닌지를 boolean 값으로 반환함. - Objects.requireNonNull()은 해당 객체가 null이 아니여야 하는 경우에 사용. null이면 NPE 발생. Parameter 2개 쓰면 (obj, String예외 메세지) 순으로 예외메세지 설정가능. 아래 처럼 매개변수 null check 유효성 검사시 간단히 가능. import j.. 공감수 0 댓글수 0 2022. 7. 19.
이번주 코테문제 풀면서 배운것 2 프로그래머스 1단계들을 다 풀어간다. 사실 뒷부분으로 갈수록 너무 쉬워지고 있다. 빨리 스프링 프로젝트가 끝나고 알고리즘 학습을 하고 싶다. 1. array를 복사할때는 객체와 같아서 그냥 변수에 넣어 주면 안된다. 1) Arrays.copyOf() 사용 2) System.arraycopy() 사용 3) arr.clone() 사용 (2차원 배열에서도 사용) 2. 정수인지 유리수인지 판별하기 위해서 num % 1 == 0 을 사용 할 수 있음. ex ) 제곱수인지 판별 : Math.sqrt(num) % 1 == 0 ? "제곱수" : "제곱수아님" 3. 2차원 배열 (Matrix)에서, arr이 2차원 배열이라고 할때, arr.length 하면 element의 개수가 아니라 row의 개수가 나온다. arr[.. 공감수 0 댓글수 0 2022. 7. 17.
이번주 코테문제 풀면서 배운것. 1. List (arrayList)를 int 배열로 변경하는 방법 list.stream().mapToInt(Integer::intValue).toArray(); Integer배열을 int로 바꿔주는것은 stream을 이용해야한다. 2. List (arrayList)를 String 배열로 변경하는 방법 // list를 string array로 바꾸는 두가지 방법. 1. stream.toArray(Sting[]::new) 2. list.toArray(new String[0]); String[] strings = stringList.toArray(new String[0]); String[] strings2 = stringList.stream().toArray(String[]::new); 위 코드에서 좀 이상한.. 공감수 1 댓글수 0 2022. 6. 13.
Boyer-Moore 법 (문자열 검색 알고리즘) Boyer-Moore법은 브루트 포스법을 개선한 KMP법 보다 효율이 더 우수하기 때문에 실제로 문자열 검색에 널리 사용되는 알고리즘이다. R.S Boyer과 J.S Moore가 만든 Boyer-Moore법은 KMP법보다 효율이 더 좋은데, 원리는 텍스트와 패턴을 비교할때, 패턴의 마지막 문자부터 앞으로 검사를 진행하며, 일치하지 않는 문자가 있으면 미리 준비한 Skip table 에 따라서 패턴을 옮길 크기를 정하는 것이다. Boyer-Moore 법은 두 접근 방식의 결합이다. (1) Bad Character Heuristic (2) Good Suffix Heuristic 위 두 방법은 텍스트에서 패턴을 찾는데 있어 독립적으로 사용될 수 있다. 두 독립적인 접근 방법이 어떻게 Boyer Moore알고리.. 공감수 0 댓글수 0 2022. 5. 28.
KMP 법 (문자열 검색 알고리즘) 1. KMP알고리즘이란 문자열 검색 알고리즘을 지난번 브루트 포스 알고리즘으로 하나하나 반복해서 검색하는 것을 알아보았었다. M개의 문자열(text)에서, N문자열(pattern)이 어디에 포함되어 있는지를 검색하기 위해서, text를 돌면서 pattern과 일치하는 지를 하나하나 검색했었다. 따라서 시간복잡도는 O(MN)이였다. 이를 O(M+N)의 시간 복잡도로 줄일 수 있는 방법이 바로 KMP 알고리즘이다. Knuth, Morris, Pratt 세 사람이 거의 같은 시기에 고안했기 때문에 이들의 이름 앞 글자를 각각 따서 KMP 법이라고 부른다. 그럼 KMP 알고리즘은 어떻게 문자열 검색을 하기에 시간복잡도를 O(N+M)으로 낮출 수 있을까 2. KMP알고리즘을 이해 하기에 앞서 알아야 하는것 (1).. 공감수 0 댓글수 0 2022. 5. 27.
Brute-Force법 오늘 백준 Brute-force 알고리즘에 관련한 문제를 풀다 한번 정리 하고 싶다는 생각이 들어 글을 작성한다. 아래 글은 reference에도 남기겠지만, 'Do it! 자료구조와 함께 배우는 알고리즘 입문'을 정리한 글이다. 1. 브루트-포스(Brute-force)법 완전탐색 알고리즘이다. 모든 경우의 수를 탐색하면서, 요구 조건에 충족되는 결과만을 가져 온다. 선형 검색을 확장한 알고리즘이다. 예시로 문자열을 검색하는 알고리즘을 들어 보자. 문자열에 특정 문자열이 들어 있는지 조사하고, 들어 있따면 그 위치 index 값을 반환하는 프로그램을 작성한다 생각해보자. 텍스트 "ABABCDEFGHA"에서 패턴 "ABC"를 브루트포스법을 이용해 검색하는 순서는 다음과 같다. (1) 문자열의 첫 문자 'A.. 공감수 0 댓글수 0 2022. 5. 11.
소수 판정 방법 1. N 보다 작은 자연수들로 모두 나눠본다. 임의의 수 N이 1과 N을 제외한 다른 수를 약수로 갖는 다면, 그 수는 소수가 아니고, 그렇지 않다면 소수이다. public class PrimeNumber { public static boolean isPrime(int num){ if (num 공감수 0 댓글수 0 2022. 5. 9.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.