25.11.20일자 - TIL

코딩 테스트 4-1
52분 부터
STL을 사용하는데 익숙해지면 좋다.

배달 문제
방향성이 없는 간선정보를 입력할 때는 (인접 리스트를 사용할 경우)
양쪽으로 향하는 간선 정보를 모두 입력해줘야 오류가 생기지 않는다.  (1->2, 2->1 둘 다 정보가 입력되야 함.)
1:09 부터 풀이 시범

priority_queue 를 활용하는데 있어
최대 힙을 기본으로 구하는데 최소 힙으로 구현하기 위해서는
struct  operator() (조건을 반대로) / greater(less)를 활용하는 방법으로 두 가지가 있고 후자가 구현하기 쉽다.



=============================================================
코딩 테스트 4-2강

해시 함수의 개념과 작동원리를 이해하고, 다양한 해시 기법을 설명할 수 있다.
해시 충돌의 원인과 해결 방법을 이해하고, 충돌 해결 기법을 적용할 수 있다.
테스트에는 잘 안 나오지만 면접 같은 데서 활용될 수 있다.
기반이 될 지식을 많이 다져야 경쟁력이 당연히 커진다.

해시의 개념
 해시 테이블은 키를 사용하여값을 빠르게 접근할 수 있도록 데이터를 구성하는 자료구조.

휴대폰 연락처 예시.(연락처를 구현하는 방법)
배열을 사용하는 방법/해시를 사용하는 방법
배열은 정보가 없으므로 순차 탐색을 통해 이름을 찾고 그에 해당하는 전화번호를 다시 탐색해야한다.
키`값 쌍으로 구성되어 있어 키에 의해 값의 저장 위치가 결정된다. 따라서 검색의 시간은 O(1)이 소모됨.

해시 함수
키를 해시 테이블의 인덱스로 변환하는 역할을 하는 것.
해시 함수가 반환하는 인덱스는 반드시 해시 테이블의 크기보다 작아야 한다.
충돌이 최대한 적게 발생하도록 해시 함수를 설계해야 한다.

나눗셈법
키를 소수로 나눈 나머지를 활용한다.
h(x) = x mod k
x ==키  k==소수

======
// 목적: 나눗셈법을 이용한 해시 함수를 정의하고, 키 값을 해싱한 결과 출력
#include <iostream>
using namespace std;

int hashFunction(int key, int prime) {
    return key % prime;
}

int main() {
    int key = 1234;
    int prime = 11; // 소수 사용
    int hashValue = hashFunction(key, prime);

    cout << "해시값: " << hashValue << endl;

    return 0;
}

/*
출력결과
해시값: 2
*/
======

곱셈법
나눗셈법에서는 해시 테이블의 크기 k를 소수로 설정해야 하는데 소수를 구하는 것 자체가 연산을 꽤 먹는다.
곱셈법은 소수를 사용하지 않고 실수(특히 황금비와 같은 무리수)를 활용하여 해시 인덱스를 계산하는 방법이다.

h(x) = (((x*A)mod I)*m)

키에 황금비를 곱한다.
황금비는 1.6180339877... 이므로
       키를 곱하면 정수 부분과 소수 부분이 나온다.
  2. 1에서 구한 값에 모듈러 1을 취한다.(정수를 버리고 소수 부분만을 가져감)
  3. 2에서 구한 값에 m을 곱해서 정수 부분을 취한다.
m == 크기    m X A(소수) = x 일 때,  0 < x < m 이므로 해시 테이블에 적합한 크기가 된다.

위의 해시 함수들은 키의 자료형이 숫자일 때를 전제로 함.

실제로는 키가 문자열인 경우도 자주 발생한다.

오버플로우를 피해야 하기 때문에(컴퓨터는 수가 큰 것을 감당할 수 없으므로) 각 값을 바로 모듈러 연산을 하면서 합하는 것이 이를 피할 수 있는 방법이다.


========
#include <iostream>
#include <string>
using namespace std;

// 아주 간단한 문자열 해시 함수
// 같은 해시값이 나올 수 있는 문자열을 찾기 위한 예제
int simple_hash(string s) {
    const int m = 400;
    int hash = 0;
    int base = 31;
    for (int i = 0; i < s.length(); i++) {
        // 각 문자의 알파벳 순서에 따라 숫자를 더함 (a=1, b=2, ...)
        int value = s[i] - 'a' + 1;
        hash += value * base;
        base *= 31; // 자리수 효과를 줌
    }
    return hash % m;
}

int main() {
    string str1 = "aa";
    string str2 = "b";

    // 해시값 출력
    cout << "문자열 '" << str1 << "'의 해시값: " << simple_hash(str1) << endl;
    cout << "문자열 '" << str2 << "'의 해시값: " << simple_hash(str2) << endl;

    return 0;
}
========

해시 충돌

체이닝
해시 충돌이 발생했을 때, 해당 해시 버킷에 값을 연결리스트(Linked List)형태로 저장하는 방식.
구현은 간단하지만 충돌이 잦아지면 연결 리스트가 길어져 성능이 떨어진다. O(N)이 될 수는 있으나 이렇게 비효율적이진 않다.

개방 주소법
해시 테이블 내에서 빈 버킷을 찾아 충돌 값을 삽입하는 방식.
별도의 연결 리스트나 외부 메모리를 사용하지 않으므로, 추가 메모리 할당이 없다.
충돌이 많아지면 (군집 형성으로 인한)클러스터링이 발생한다.

이중 해싱
해시 함수를 두 개 사용하는 방법
개방 주소법 보다는 클러스터링이 적게 발생한다는 장점이 있다.

count sort

예외 처리를 잘 해줘야 디버깅을 다시 하지 않을 수 있다.


영어 끝말 잇기
%/N +1으로 참가자 번호를 /N+1으로 몇 번째 답변인지 확인할 수 있다.

카카오톡 오픈 채팅방 문제
문제가 길면 힌트가 많고 이를 잘 따르기만 하면 되는 쉬운 문제일 확률이 높다.


arr(ay) ==배열

모듈러 연산 == 정수의 나눗셈에서 나머지를 계산하는 방법으로 크기를 제한할 때 사용할 수 있는 연산법이다.

===================================================


코딩 테스트 4-3

동적 계획법
문제를 작은 단위로 나누고, 그 해를 활용해 전체 문제를 해결하는 방법을 알아본다.
중복 계산을 줄이고 효율적인 해결 방안을 찾는 전략을 학습한다.

큰 문제를 작은 문제로 나누고 그 결과를 이용해 전체 문제를 푸는 방법.
중복 계산을 줄여 효율적으로 문제를 해결하는 전략도 익힌다.


성립 조건
최적 부분 구조와 중복 부분 문제 가 성립해야 한다.

최적 부분 구조
전체 문제의 최적 해결책이 하위 문제들의 최적 해결책으로부터 구성될 수 있다.

중복 부분 문제
문제의 해결 과정에서 동일한 하위 문제가 여러번 반복적으로 나타나는 경우.
입력 크기가 커질수록 계산량이 급격히 커진다.

동적 계획법을 풀기위한 점화식 수립
최적 부분 구조 및 중복 부분 문제인지 확인
 동적 계획법을 적용하기 위해서는 문제에 최적 부분 구조와 중복 부분 문제의 특성이 있는지 확인해야 한다.
  2.  기저조건 확인
 점화식이 적용되지 않는 가장 작은 문제의 해는 직접 계산해야 하며, 이를 기저 조건으로 설정한다.
  3.  점화식 수립
 작은 문제의 해를 이용하여 큰 문제의 해를 계산할 수 있도록 점화식을 정의한다.

팩토리얼의 예시.
N! = (N-1)! X N 이므로 활용은 가능하지만 중복 부분 문제가 없으므로 효율적인 풀이법은 아니다.
재귀/반복문


피보나치 수
N번째 피보나치 수는 크기가 N이다.
(N-1)번째와 (N-2)번째의 피보나치 수를 구하는 더 작은 문제로 나눌수 있는 최적 부분 구조가 성립함.

(N-1)번 수 = (N-2)번 수 + (N-3)번 수
가 성립하므로 중복 부분 문제도 성립한다.

기저조건
 1번 수 =1, 2번 수 =1

점화식
fibo(N) = fibo(N-1) + fibo(N-2)  (N=>3)


==========
// 목적: 반복문을 이용하여 효율적으로 N번째 피보나치 수를 계산한다
#include <iostream>
using namespace std;

int fibo(int n) {
    if (n == 1 || n == 2) return 1;
    int a = 1, b = 1, result;
    for (int i = 3; i <= n; ++i) {
        result = a + b;
        a = b;
        b = result;
    }
    return result;
}

int main() {
    cout << fibo(10) << endl;
    return 0;
}

// 출력결과
// 55
==========

메모이제이션
한번 계산한 결과를 저장해두고, 이후 동일한 문제가 다시 등장했을 때 이를 재사용하는 기법.
 피보나치 수를 구하는 연산의 예시.

=========
// 목적: 중복 호출을 방지하기 위해 메모이제이션을 적용한 재귀 fibo 함수
#include <iostream>
using namespace std;

const int MAX = 100;
int memo[MAX] = {0};

int fibo(int n) {
    if (memo[n] != 0) return memo[n];
    if (n == 1 || n == 2) return memo[n] = 1;
    return memo[n] = fibo(n - 1) + fibo(n - 2);
}

int main() {
    cout << fibo(5) << endl;
    return 0;
}

// 출력결과
// 5
// ※ fibo(3)은 이미 계산되었기 때문에 다시 호출되지 않고 캐시된 값이 사용됨
==========

최장 증가 부분 수열(LIS)

부분 수열(subsequence)
 주어진 수열에서 일부 원소를 순서를 유지한 채 선택하여 만든 새로운 수열을 의미한다.

최장 증가 부분 수열
부분 수열 중에서 원소들이 오름차순으로 증가하고, 그 길이가 가장 긴 수열을 말한다.

LIS의 길이 동적 계획법으로 구하기
숫자가 점점 증가한다.
원소 간의 전후 관계(수열에서의 순서)는 유지한다.

*max_element() - 최댓값의 위치가 아니라 값을 호출하려면 *을 붙여야 함


2Xn 타일링
제약 조건 1,000,000,007로 나눈 나머지를 반환하라 ==> 오버플로우를 조심해야 하는 제약 조건
(A+B)%m  => ((A%m)+(B%m))%m  공식을 활용해야 한다.

점화식은 간단한 초기 항을 직접 구해보는 것으로 만드는 것이 좋다.

===============================================================
언리얼 2-2 실습
Alt를 사용하여 액터를 복제할 수 있다. - 키를 누르고 이동하면 새 개체가 딸려온다.

선택된 액터를 복제한 좌측의 조금 큰 버전

 

바라보는게 정상적으로 작동하는 모습

 

객체와 캐릭터가 닿으면 캐릭터를 위로 밀어내고 폭발음과 나이아가라 이펙트를 출력하면서 사라지는 명령

출력되는 나이아가라 이펙트의 모습

 

 

 

숙제
3-1 자동문 만들기


3-2 객체를 움직이게 만들고 이와 부딪히면 객체 파괴 + 캐릭터 밀려나기

위의 내용과 객체의 이동값(2-1강의 내용) 그리고 스스로 이동할 수 있는 값을 넣어 해결한 결과물

.