ExiiS 프로그래밍 저장소

ANR은 그려지는 UI 응답을 기준으로 측정된다.

하지만 유니티 이벤트 함수 호출 순서를 보면 Start, Awake 모두 렌더링 이전에 일어나는데

Awake -> Start로 옮긴다면 ANR이 감소할까? 라는 의문이 들었음.

여기서 핵심적인 내용은 Awake에 작성된 함수는 모두 호출된다는 것, Start는 활성화 시 호출된다는 것.

따라서 게임이 시작될 때 Awake -> Start로 이동하는 것은 게임 시작지점의 부하를 줄일 수 있게된다.

Awake에서 아래와 같이 초기화를 많이 하는데, Start나 혹은 Enable 이벤트가 있어 미리 초기화가 필요하다면,

아래와 같이 변경하여 초반 부하를 줄이도록 하자.

void Awake() {
	rectTf = GetComponent<RectTransform>();
    ...
}

void Enable(){ // or Start.
	rectTf ??= GetComponent<RectTransform>();
    ...
}

0. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12938

1. 접근

최대 만 개의 숫자 조합을 구하는건 말이 안된다고 생각했다.

집합의 곱이 최대가 되는 경우를 생각해보니 원소들이 평균값에 근접할수록 곱이 최대가 된다는 사실을 확인,

해당 전략으로 접근하였다.

2. source code

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(int n, int s) {
    vector<int> answer;
    int mid = s/n;
    //불가능할 때
    if(mid == 0){
        answer.push_back(-1);
        return answer;
    }
    int div = n;
    for(int i=0; i<n    -1; i++){
        int cur = s/div;
        answer.push_back(cur);
        s-=cur;
        div--;
    }
    answer.push_back(s);
    sort(answer.begin(), answer.end());
    
    return answer;
}

3. 추가

https://velog.io/@slow_cosmos/c%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%B5%9C%EA%B3%A0%EC%9D%98-%EC%A7%91%ED%95%A9

최적화 하면 위 블로그와 같은 코드를 작성할 수 있다.

원리는 동일하나 몫을 (평균값 + 1)로 배분하는 방식으로 접근하였다.

조금 더 효율적이고 깔끔하게 코드를 작성하는 방법인 듯 하다.

https://school.programmers.co.kr/learn/courses/30/lessons/42860

문제 자체는 심플하다.

게임하면서 한번쯤 보았을 닉네임 설정 창에서

AAAA... 로 초기화된 상태에서 내가 원하는 닉네임을 만드는데 최소한의 움직임을 구하는 문제이다.

해당 문제를 편하게 분해하자면,

1. 왼쪽 오른쪽으로 이동

2. 위 아래를 이용하여 문자 이동

두 개의 과정으로 나눌 수 있다.

위/아래를 이용하여 문자를 이동하는 것은 문자열이 주어진다면 고정값이 된다.

왼쪽 혹은 오른쪽으로 이동하는 것은 여러가지 이동 방법이 정해져 있지만(왼쪽 or 오른쪽 등)

문자를 이동하는 것은 더욱 짧은 것이 확실히 정해져있기 때문이다.

처음에는 모든 경우의 수를 탐색해볼까라는 생각을 가져봤는데, 시간 초과로 인하여 문제가 해결되지 않았다.

다음번에는 크게 다섯가지 경우를 기반으로 계산하는 방법을 사용했는데, 다음과 같다.

* 움직이지 않음

* 왼쪽으로만 이동

* 오른쪽으로만 이동

* 왼쪽으로 이동하다 오른쪽으로 이동

* 오른쪽으로 이동하다 왼쪽으로 이동

위의 경우를 탐색하는 과정을 소스코드로 옮기면 답을 찾을 수 있는 알고리즘이 완성된다.

자세한 설명은 아래 소스코드의 주석을 활용하였다.

using System;

public class Solution {
	/* len, str : 접근용이성을 위하여 class 변수 선언 */
    int len;
    string str;
    
    public int solution(string name) {
    	/* count는 먼저, 알파벳의 이동(고정값)을 저장하는 변수
           min은 반환 될 최소값 입니다. */
        int count = 0;
        int min = 0;
        
        /* class 변수 초기화 */
        str = name;
        len = name.Length;
        
        // 우선 바꿔야 할 알파벳 순서 미리 계산
        // -> 해당 하는 순서는 문자열에 대하여 고정적이다.
        foreach(char c in name)
            count += getCharMove(c);
        
        // count가 0이라는 것은 모든 문자가 'A'로 이루어졌으며 굳이 이동할 필요가 없음을 의미한다.
        if(count == 0) return 0;
        
        /*아래 주석처리된 소스코드는 생략 가능하나 이해를 위해 남겨놓음.
           - 오른쪽으로만 갈 때
        min = getRightMove(0) + count;
        
           - 왼쪽으로만 갈 때
        int temp = getLeftMove(0) + count;
        min = min<temp ? min : temp;*/
        
        min = 999;
        int temp = 0;
        
        for(int i=0; i<len; i++){
            // R to L
            // 오른쪽으로 i만큼 이동한 뒤 해당 위치에서 왼쪽으로 가는 경우
            temp = i + getLeftMove(i) + count;
            min = min<temp ? min : temp;
            
            // L to R
            // 왼쪽으로 i만큼 이동한 뒤 해당 위치에서 오른쪽으로 가는 경우,
            // 왼쪽으로 i만큼 이동하였으니 시작 위치로 len-i를 전달
            temp = i + getRightMove(len-i) + count;
            min = min<temp ? min : temp;
        }
        
        return min;
    }
    
    int getRightMove(int start){
        //오른쪽으로 갈 경우 오른쪽으로 가야하는 최대 거리를 찾아서 더함.
        //한칸씩 왼쪽으로 탐색하여 'A'가 아닌 문자를 찾을 때 까지.
        int cur = start-1 > -1 ? start-1 : len-1; // 언더플로우 처리, 음수가 될 경우 최대값을 취해야함.
        int loop = len-1; //시작변수로 부터 len-1번 반복
        int moves = len-1; //기본적으로 len-1번 이동한다. 'A'를 만날 때 마다 해당하는 문자는 바꿀 필요가 없어 -1해준다.
        
        for(int j=0; j<loop; j++){
            if(str[cur] != 'A'){
            	//만약 맨 첫 loop에서 아래 return을 취한다면, 다른 모든 문자들이 'A'가 아닌경우.
                return moves;
            }
            else{
            	// 만약 'A'를 만날경우 해당 문자는 안바꿔도 되므로 이동할 수고가 없다.
                // 따라서 이동 횟수 -1
                moves--;
                cur = cur-1 > -1 ? cur-1 : len-1;
            }
        }
        
        // 시작 문자를 제외하고 다른 문자들이 모두 'A'일 경우
        // 굳이 이동할 필요가 없어 return 0
        return 0;
    }
    
    int getLeftMove(int start){
        //왼쪽으로 갈 경우 왼쪽으로 가야하는 최대 거리를 찾아서 더함.
        //한칸씩 오른쪽으로 탐색하여 'A'가 아닌 문자를 찾을 때 까지.
        int cur = start+1 >= len ? 0 : start+1;
        int loop = len-1;
        int moves = len-1;
        
        for(int j=0; j<loop; j++){
            if(str[cur] != 'A'){
                return moves;
            }
            else{
                moves--;
                cur = cur+1 >= len ? 0 : cur+1;
            }
        }
        
        // 시작 문자를 제외하고 다른 문자들이 모두 'A'일 경우
        // 굳이 이동할 필요가 없어 return 0
        return 0;
    }
    
    // 해당 문자를 만들기 위하여 필요한 이동 수를 반환하는 getCharMove 메서드.
    // 알파벳은 'N'을 기점으로 위로 이동하는게 더 빠를지 밑으로 이동할게 더 빠를지 
    // 분기된다. 'N'은 어느쪽으로 하여도 13번의 이동이 필요하다.
    int getCharMove(char c){
        if(c > 'N') return 'Z'-c+1;
        else return c-'A';
    }
}

https://www.acmicpc.net/problem/1753

해당문제는 다익스트라 알고리즘을 Heap을 이용하여 구현하는 문제이다.

#include <vector>
#include <queue>
#include <iostream>

using namespace std;

vector<pair<int, int>> matrix[20005];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

int result[20005];
int INF = 999999;


void dijkstra(int start) {
	result[start] = 0;
	pq.push(make_pair(0, start));

	while (!pq.empty()) {
		int cur = pq.top().second;
		int cost = pq.top().first;
		pq.pop();

		int size = matrix[cur].size();
		for (int i = 0; i < size; i++) {
			int next = matrix[cur][i].second;
			int newCost = matrix[cur][i].first + cost;
			if (result[next] > newCost) {
				result[next] = newCost;
				pq.push(make_pair(newCost, next));
			}
		}
	}
}

int main(void) {
	int n, e;
	cin >> n >> e;

	/* init cost array */
	for (int i = 0; i <= n; i++)
		result[i] = INF;

	int start;
	cin >> start;

	for (int i = 0; i < e; i++) {
		int u, v, c;
		cin >> u >> v >> c;
		matrix[u].push_back(make_pair(c,v));
	}

	dijkstra(start);

	for (int i = 1; i <= n; i++) {
		if (result[i] == INF) cout << "INF\n";
		else cout << result[i] << "\n";
	}
}

다익스트라 알고리즘은 한 점에서부터 다른 노드로의 경로의 최소 값을 구하는 알고리즘이다.

다익스트라의 과정으로는 다음과 같다.

1. 시작 노드는 비용을 0으로 설정한다.

2. 시작 노드를 기준으로 비용 초기값을 설정한다. (인접한 값은 해당 가중치로, 인접하지 않았다면 무한대로)

3. 비용값 중 방문하지 않았고 비용 중 가장 작은 값을 다음 노드로 선택, 방문한다.

4. 선택된 노드까지의 비용 + 선택된 노드에서 인접한 노드로의 경로 비용 vs 인접한 노드의 비용을 비교하여 더 값싼 비용을 선택, 인접 노드로의 경로 비용을 갱신한다.

5. 3번으로 돌아가 반복한다.

여기서 3~4번의 과정을 효율적으로 수행하기 위하여 Heap 구조를 사용한다.

* priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

priority_queue의 경우 기본적으로 less, 즉 내림차순 정렬이다.

위와 같은 선언을 통하여 Min Heap으로 선언 가능하다.

* #include<utility>의 pair를 활용하여 인접 리스트 방식으로 구현이 가능하다.

* pair를 활용한 priority_queue의 비교 순서는 first, second 순서로 비교한다.

https://stackoverflow.com/questions/6184869/what-is-the-difference-between-memoization-and-dynamic-programming

Q.

What is the difference between memoization and dynamic programming? I think dynamic programming is a subset of memoization. Is it right?

Memozation과 DP의 차이점이 무엇인가요? DP가 memoization에 포함되어있는 것 같은데, 맞죠?

A.

Memoization is a term describing an optimization technique where you cache previously computed results, and return the cached result when the same computation is needed again.

Dynamic programming is a technique for solving problems of recursive nature, iteratively and is applicable when the computations of the subproblems overlap.

Dynamic programming is typically implemented using tabulation, but can also be implemented using memoization. So as you can see, neither one is a "subset" of the other.

Memozation은 이전에 계산한 결과를 캐싱하고, 또다시 같은 계산을 해야할 때 그 캐시를 리턴하는 방식의 기술적 최적화를 설명하는 용어 입니다.

DP는 반복 혹은 재귀적인 성격의 문제를 푸는 테크닉입니다. 또한 하위 문제의 계산이 오버랩(겹쳐짐, 반복)된다면 적용 될 수 있습니다.

DP는 일반적으로 테이블을 작성하여 구현되나, memoization을 사용하여 구현할 수도 있습니다. 따라서 보시다싶이 어느 한쪽도 다른쪽의 "subset"이 아닙니다.

A reasonable follow-up question is: What is the difference between tabulation (the typical dynamic programming technique) and memoization?

When you solve a dynamic programming problem using tabulation you solve the problem "bottom up", i.e., by solving all related sub-problems first, typically by filling up an n-dimensional table. Based on the results in the table, the solution to the "top" / original problem is then computed.

If you use memoization to solve the problem you do it by maintaining a map of already solved sub problems. You do it "top down" in the sense that you solve the "top" problem first (which typically recurses down to solve the sub-problems).

이후 나올법 한 질문 : tabulation(DP에서 사용하는)과 memoization 간의 차이점이 무엇인가요?

tabulation을 사용하여 DP 문제를 푼다면 "Bottom UP", 즉 일반적으로 n차원 테이블을 채워나가며 관련된 모든 하위 문제를 먼저 품으로 문제를 푸는 것입니다. 테이블의 결과를 기반으로 최상위(top)/원래 문제에 대한 솔루션이 계산됩니다.

만약 문제를 풀기 위해 memoization을 사용했다면 이미 푼 하위 문제의 map을 maintaning(유지보수)하며 풀 수 있습니다.

(즉 이전 값을 활용하여 다음 문제의 값을 구한다는 의미)

"top down"은 상위 문제를 먼저 푼다는 의미에서 수행할 수 있습니다.

//가져갈 수 있는 돌의 수가 1개 3개일 경우
//9655 돌 게임1

#include<iostream>

using namespace std;

int main(void){
        int n;
        cin >> n;

        int SK[1000] = {-1, 1, 0, 1};

        int result;
        for(int i=4; i<=n; i++)
                SK[i]  = !(SK[i-3] && SK[i-1]);

        if(SK[n])
                cout<<"SK\n";
        else
                cout<<"CY\n";
        return 0;
}

https://www.acmicpc.net/problem/9655

https://www.acmicpc.net/problem/9657

0. 개요

처음 이걸 접했을 때 참 많은 생각이 들었다.

1개일땐 이런 경우..

2개일땐 이런 경우..

그러다 수가 점점 커지면..

9개일땐 8개 or 5개의 경우의수,

그렇다면 거기서 또 파생되는 경우의수....

이 개념을 이해하기 힘들었는데 조금이나마 이 포스팅을 보게 될 사람들이 쉽게 이해할 수 있다면 좋겠다.

1. 문제 설명

n개의 돌이 있고, 각각 번갈아 가며 1개, 3개(혹은 4개까지) 가지고 갈 수 있다.

마지막에 돌을 가지고 가는 사람이 이기는 게임이다.

이 또한 동적 계획법을 사용한다.

동적 계획법의 가장 큰 장점은 이전에 미리 구해놓은 최적해는 더 생각 안하고 가져다 쓸 수 있다는 점이다.

그것을 이용해서 문제를 풀어볼것이다.

남은 돌의 수, 현재 플레이어, 다음 플레이어 순서로 생각을 해본다면 다음과 같아진다.

일단 가장 중요한 것은 빨간색 까지는 우리가 구할 수 있다.

돌이 1개가 남았다면 현재 플레이어가 가져간다면 다음 플레이어는 지게 된다.

돌이 2개가 남았다면 현재 플레이어가 가져간다면 다음 플레이어가 남은 한개를 가져가 다음 플레이어가 승리한다.

돌이 3개가 남았다면 현재 플레이어가 모두 가져가 승리할 수 있다.

여기서 처음에 표를 완성할 때 조차 헷갈렸다.

그래서 이렇게 생각을 해봤다.

표를 이렇게만 딱 놓고 생각해봤다.

현재 남은 돌의 갯수에 대한 승패이다.

지금 구해야 하는 것은 내 턴에 6개가 남았을 때.

여기서 내가 생각한 관점은 "상대에게 지는 수를 줄 수 있는가?" 이다.

즉, 6에서 1, 3을 가져간다면 다음 상대는 5 또는 3의 수를 받을 것이다.

5와 3은 모두 승리하는 경우다.

즉, 상대에게 지는 수를 줄 수 없으므로 내가 패배한다.

다음은 1, 3 그리고 4개까지 돌을 가지고 갈 수 있는 경우이다.

2번의 경우를 제외하고는 나머지 돌을 다 들고가버리면 이길 수 있다.

이것 또한 상대에게 지는 수를 주는것으로 생각해보자.

지금 채워야 하는 것은 5.

내가 상대에게 줄 수 있는 수는 1, 2, 4개가 남은 상황.

2번에 상대가 지는 수가 존재한다.

따라서 5개의 상황에서 내가 3개를 가져간다면 상대는 지게 되는 것이다.

그렇다면 5번은 W로 채워지겠고,

남은 돌이 6개일 경우에도 2, 3, 5개가 남은 경우를 줄 수 있는데, 2개가 남을경우 지는 수이므로 4개를 가져가 승리할 수 있다.

따라서 6번도 W으로 채워질 것이다.

2. 소스코드

//가져가는 경우가 1개, 3개 두가지
//9655 돌 게임1

#include<iostream>

using namespace std;

int main(void){
        int n;
        cin >> n;

        int SK[1000] = {-1, 1, 0, 1};

        int result;
        for(int i=4; i<=n; i++)
                SK[i]  = !(SK[i-3] && SK[i-1]);

        if(SK[n])
                cout<<"SK\n";
        else
                cout<<"CY\n";
        return 0;
}

//가져가는 경우가 1개, 3개, 4개일 경우의 코드
//9657 돌 게임3

#include<iostream>

using namespace std;

int main(void){
        int SK[1000] = {-1, 1, 0, 1, 1};

        int n;
        cin >> n;

        for(int i=5; i<=n; i++)
                SK[i] = !(SK[i-1]&&SK[i-3]&&SK[i-4]);

        if(SK[n])
                cout<<"SK";
        else
                cout<<"CY";
        return 0;
}

3. 여담

참고로 위에서 완성된 배열을 출력해보면 첫 번째 문제는 0, 1, 0, 1....

두번째 문제 또한 특정 패턴을 반복한다.

이를 이용해서 문제를 해결할 수도 있다.