Skip to content

Latest commit

 

History

History
227 lines (215 loc) · 23.9 KB

README.md

File metadata and controls

227 lines (215 loc) · 23.9 KB
Raw

PS

프로그래머스

문제 - 솔루션

leetcode

문제 - 솔루션

hackerrank

문제 - 솔루션

알고리즘 관련 책 정리 Book

  • 연습문제 풀이
  • 개념 정리

    • 여러 문장이 순차적으로 실행되는 구조를 순차적 구조(concatenation structure)라고 한다.

    • 알고리즘이란?
      문제를 해결하기 위한 것으로, 명확하게 정의되고 순서가 있는 유한 개의 규칙으로 이루어진 집합

    • 사전 판단 반복(while(){}, for(;;){})과 사후 판단 반복(do{}while())의 차이점
      사전 판단 반복은 조건문의 결과가 true일 때만 {}에 진입하여 반복하지만 사후 판단 반복은 일단 {}에 한 번 진입하고 조건문의 결과에 따라 반복할 지를 결정한다. 사후 판단 반복은 {}에 무조건 한 번은 진입한다.

    • 논리 연산자의 단축 평가(short circuit evaluation)
      예를 들어 (num < 10 || num > 99)의 경우, 왼쪽 피연산자의 결과가 true이면 오른쪽 피연산자의 결과에 관계 없이 전체 결과는 true가 된다. (num < 10 && num > 99)의 경우 왼쪽 피연산자의 결과가 false이며 오른쪽 피연산자의 결과에 관계 없이 전체 결과는 false이다. 이처럼 왼쪽 피연산자의 결과만으로 전체 결과가 확정될 때 오른쪽 피연산자를 평가하지 않으며 이를 단축 평가라고 한다.

    • 드모르간 법칙
      각 조건을 부정하고 논리곱을 논리합으로, 논리합을 논리곱으로 바꾸고 다시 전체를 부정하면 원래의 조건과 같다.

    • 자료구조란?
      데이터 단위와 데이터 자체 사이의 물리적 또는 논리적인 관계, 쉽게 말해 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법
      데이터 단위 : 데이터를 구성하는 한 덩어리

    • 배열 : 같은 자료형의 구성 요소들이 하나의 집합으로 모여있는 자료구조.

    • java.util.Random
      Random 클래스는 선형 합동법이라는 계산법으로 48비트의 seed를 특정 수(난수)로 바꾼다.

    • String 클래스

      String r = "ABC";

      초기자의 "ABC"는 문자열 리터럴이다. 문자열 리터럴은 단순히 문자가 늘어서 있는 것이 아니라 String형 인스턴스에 대한 참조이다. String 클래스는 문자열을 넣어두기 위한 private final char[], 문자 수를 나타내는 private final int가 있으며 이외에도 field, constructor, method가 있다.

    • 소수

      1. 자신과 1 이외의 정수로 나누어떨어지지 않는 정수. 그러므로 어떤 정수 n에 대하여 2부터 n-1까지의 어떤 정수로도 나누어떨어지지 않으면 n이 소수임을 알수있다.
      2. 그런데 만약 n이 2와 3으로 나누어떨어지지 않으면 2*2인 4와 2*3인 6으로도 나누어떨어지지 않는 것을 알 수 있다. 따라서 정수 n이 2부터 n-1까지의 어떤 소수로도 나누어떨어지지 않으면 n이 소수임을 알 수 있다. 그리고 4이상의 짝수는 2로 나누어떨어지므로 2를 제외한 나머지 짝수는 소수가 될 수 있는 조건을 만족하지 않는다.
      3. 100의 약수는 아래와 같다.
        ① 2*50
        ② 4*25
        ③ 5*20
        ④ 10*10
        ⑤ 20*5
        ⑥ 25*4
        ⑧ 50*2
        100의 약수들을 통해 만약 100이 5로 나누어떨어지지 않으면 20으로도 나누어 떨어지지 않는 것을 알 수 있다. 이러한 성질은 ① ~ ④까지만 확인하면 된다. 이후는 반복되기 때문이다. 따라서 정수 100은 2부터 100의 제곱근인 10이하의 어떤 양의 정수로도 나누어떨어지지 않으면 소수이다. 그리고 위의 2번 조건에 따라 10이하의 어떤 소수로도 나누어떨어지지 않으면 소수임을 알 수 있다.
      4. 1~3번 조건으로 어떤 정수 n이 n 제곱근 이하의 소수로 나누어떨어지지 않으면 n은 소수임을 알 수 있다. n 제곱근 이하의 소수를 p라 했을 때 p <= sqrt(n)을 만족해야 하고, 제곱근을 구하는 것보다 제곱의 결과를 구하는 것이 더 빠르기 때문에 p^2 <= n을 사용하는 것이 낫다.

    • 윤년
      지구가 태양 둘레를 한 바퀴 도는 일 수는 정확히 365일이 아니기에 4로 나누어떨어지는 해를 윤년으로 하여 1년을 366일로 합니다. 하지만 그래도 정확하지 않으므로 100으로 나누어 떨어지고 400으로 나누어떨어지지 않는 해를 평년으로 합니다.

      if ( year % 4 == 0 && year % 100 != 0 || year % 400 == 0 )
    System.out.print( year + "년은 윤년입니다.");

    • 다차원 배열
      자바는 엄밀한 의미에서 다차원 배열은 없다. 왜냐하면 2차원 배열을 '배열의 배열'로 생각하기 때문이다. 따라서 in[][] x = new int[2][4]에서 배열 x의 형은 "int형을 구성 자료형으로 하는 배열"을 구성 자료형으로 하는 배열이다.

    • 배열 검색에 사용되는 알고리즘
      선형 검색, 이진 검색, 해시법(체인법, 개방 주소법)

      • 선형 검색
        무작위로 직선 모양으로 늘어선 요소들에서 원하는 값을 찾기위해 처음부터 끝까지 순서대로 탐색하는 방법.
        무한 루프에서 원하는 값을 찾기 위해 선형 검색할 때 두 가지 종료 조건을 사용하게 되는데, 하나씩 증가시키던 인덱스의 값이 배열의 길이와 같아지거나 원하는 값을 찾았을 때, 이렇게 두 가지 종료 조건을 사용하게 된다. 종료 조건이 두 가지 뿐이니 검사 비용이 얼마 되지 않겠지라고 생각할 수 있지만 수 많은 배열이 있다면 종료 조건을 검사하는 비용도 무시하지 못하게 된다. 이럴 때 사용할 수 있는 방법으로 **보초법(sentinel method)**이 있다. 원래 크기보다 하나 더 늘려 만든 배열의 맨 끝에 원하는 값을 넣고 선형 검색을 하는 것이다. 이럴 경우 무한 루프의 종료 조건은 원하는 값을 찾았을 때 종료하는 조건만 사용하면 되고, 종료 이후 인덱스의 값을 검사해서 인덱스의 값이 하나 더 늘린 배열의 길이라면 원하는 값을 찾지 못한 것이고, 그렇지 않다면 원하는 값을 찾았다는 것을 알 수 있다.

      • 이진 검색
        요소들이 오름차순이나 내림차순으로 정렬되어있을 때 가운데 요소를 검사하면서 검사 범위를 절반씩 줄여나가는 탐색 방법.

        오름차순으로 정렬된 배열에서 이진 검색 function

        1. left = 0, right = arr.length - 1, center = (left + right) / 2  
2. do{}while() 루프 시작  
3. arr[center]가 원하는 값이면 return arr[center]  
    원하는 값보다 작다면 left = center + 1, center = (left + right) / 2  
    원하는 값보다 크다면 right = center - 1, center = (left + right) / 2  
4. left가 right보다 작거나 같다면 루프 반복, 그렇지 않다면 루프 종료  
5. return -1

    • 오버로딩 : 같은 이름의 메서드로 매개변수만 다르게 정의하는 방법.

    • 오버라이딩 : 상위 클래스의 메서드를 하위 클래스에서 재정의하는 방법.

    • java.util.Arrays.binarySearch
      모든 자료형 배열에서 검색할 수 있다. 오름차순으로 정렬되있다고 가정한다.
      주어진 배열에서 원하는 key 검색에 성공하면 key와 일치하는 요소의 인덱스를 반환한다. 일치하는 요소가 여러개일 경우 무작위로 인덱스를 반환한다.
      key 검색에 실패하면 삽입 포인트를 x라 할때 -x-1을 반환한다. 예를 들어 {1,2,3,5,6} 배열에서 key=4를 검색하면 검색에 실패한다. 이때 key=4의 삽입 포인트는 index = 3 이다. 따라서 -3-1 = -4를 반환한다.

      • static int binarySearch(Object[] a, Object key)
        자연 정렬이라는 방법으로 요소의 대소 관계를 판단.
      • staic int binarySearch(T[] a, T key, Comparator<? super T> c)
        자연 순서가 아닌 순서로 줄지어 있는 배열에서 검색하거나 자연 순서를 논리적으로 갖지 않는 배열에서 검색할 때 사용함. 자연 순서가 아닌 특정 순서(Comparator<? super T> c)를 사용할 경우 특정 순서로 정렬한 후 해당 메서드를 호출해야함.

    • 문자열 정렬과 자연 정렬

      문자열 정렬 자연 정렬
      책1 책1
      책10 책2
      책100 책10
      책2 책100

    • 클래스 메서드와 인스턴스 메서드
      클래스 안에 선언된 메서드에 static이 붙으면 클래스 메서드이고 그렇지 않으면 인스턴스 메서드이다. 클래스 메서드는 인스터스를 만들지 않고도 <클래스 이름>.<메서드 이름>으로 사용할 수 있으며 프로그램 런타임 동안 1개만 만들어진다. 클래스 안에 선언된 변수에 static이 붙으면 클래스 변수이며 클래스 메서드와 마찬가지로 인스턴스 생성없이 사용할 수 있으며 프로그램 런타임 동안 1개만 생성된다.

    • 제네릭
      처리해야할 대상의 자료형에 의존하지 않는 클래스(인터페이스) 구현 방식.

      class 클래스이름 <파라미터, ...> { /*...*/}
interface 인터페이스이름 <파라미터, ...> { /*...*/}
      • 파라미터 작성 방법
        1. 1개의 대문자를 사용한다.(소문자는 가급적 사용하지 않는다.)
        2. 컬렉션(collection)의 자료형은 element의 앞글자인 E를 사용한다.
        3. 맵(Map)의 키(key), 값(value)은 key와 value의 앞글자인 K와 V를 사용한다.
        4. 일반적으로는 T를 사용한다.

    • 스택
      스택은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조로 데이터의 입력과 출력 순서는 후입선출이다. 스택에 데이터를 넣는 작업을 푸시(push)라서 하고, 데이터를 꺼내는 작업을 팝(pop)이라고 한다. 푸시와 팝이 일어나는 위치를 꼭대기(top)이라고 하고, 스택의 가장 아랫부분을 바닥(bottom)이라고 한다.
      푸시와 팝의 등 스택에 대한 모든 작업은 스택 포인터로 이루어진다. 따라서 배열 요솟값을 변경할 필요없이 스택 포인터를 변경하면 된다.

    • 큐
      큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출 구조로 되어 있다. 큐에 데이터를 넣는 작업을 인큐(enqueue)라 하고, 데이터를 꺼내는 작업을 디큐(dequeue), 데이터를 꺼내는 쪽을 프런트(front), 데이터를 넣는 쪽을 리어(rear)라고 한다.

    • 재귀
      어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 한다.

      # 팩토리얼 구하는 메서드  
int factorial(int n) {
    if( n > 0)
        return n * factorial( n - 1 );
    else
        return 1;
}

      factorial 메서드는 n이 0보다 클 때, factorial( n - 1 )을 구하기 위해서 다시 factorial을 호출한다. 이러한 메서드 호출 방식을 재귀 호출(recursive call)이라고 한다.

      • 직접 재귀와 간접 재귀
        메서드 내부에서 자기 자신을 호출하면 직접 재귀, 다른 메서드를 호출하는데 그 다른 메서드가 자기 사진을 호출하면 간접 재귀.

    • 유클리드 호제법
      두 정수 x, y의 최대공약수를 gcd(x, y)라 하자. x = az와 y = bz를 만족하는 정수 a, b와 최대의 정수 z가 존재할 때 z를 gcd(x, y)라고 한다.
      두 정수의 최대공약수(greatest common divisor)를 재귀적으로 구하는 방법은 직사각형을 정사각형으로 완전히 채운 뒤, 직사각형이 정사각형으로 완전히 채워질 때 정사각형의 한 변의 길이를 구하는 문제와 같다.

      int gcd(int x, int y){
    if( y == 0)
        return x;
    else return (y, x%y);
}