공부 기록

스패닝 트리: 그래프에서 일부 간선을 선택해서 만든 트리

최소 스패닝 트리: 스패닝 트리 중에 선택한 간선의 가중치 합이 최소인 트리

스패닝 트리를 구하는 알고리즘

• Prim: 정점을 점점 확장해 나가는 방식 (힙을 써서 구현 - 정점번호, 가중치 저장) --> 최소값을 우선 순위 큐를 이용하면 최소 값을 logE만에 찾을 수 있다. 이 경우 시간복잡도는 O(ElogE)가 된다. 모든 간선이 힙에 한번 씩 들어갔다가 나오기 때문
  1. 그래프에서 아무 정점이나 선택한다.
  2. 선택한 정점과 선택하지 않은 정점을 연결하는 간선 중에 최소값을 고른다. 이 간선을 (u, v)라고 한다.
  3. 선택한 간선을 최소 스패닝 트리에 추가하고, 선택하지 않았던 정점 v를 선택한다.
  4. 2번으로 돌아간다

• Kruskal: 간선을 점점 확장해 나가는 방법
  1. 가중치가 작은 edge부터 살펴본다 --> 간선의 길이 순으로 먼저 정렬해야 한다. O(ElogE)
  2. edge e가 (u, v, c)일 때,  u와 v가 서로 다른 집합이면 e를 최소 스패닝 트리에 추가한다. O(E) - union/find 연산

Prim 알고리즘 풀이

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int v = in.nextInt();
		int e = in.nextInt();

		LinkedList<Edge>[] pair = new LinkedList[v + 1];
		HashSet<Integer> vSet = new HashSet<Integer>();
		for (int i = 1; i <= v; i++) {
			pair[i] = new LinkedList<Edge>();
			vSet.add(i);
		}
		for (int i = 0; i < e; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			long cost = in.nextLong();

			pair[start].add(new Edge(end, cost));
			pair[end].add(new Edge(start, cost));
		}

		int currentNode = 1;
		long ans = 0;
		vSet.remove(1);

		PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
		pq.addAll(pair[currentNode]);

		while (!vSet.isEmpty()) {
			Edge minEdge = pq.poll();

			if (vSet.contains(minEdge.v)) {
				ans += minEdge.cost;
				currentNode = minEdge.v;
				vSet.remove(currentNode);
				pq.addAll(pair[currentNode]);
			}
		}
		System.out.println(ans);
	}
}

class Edge implements Comparable<Edge> {
	int v;
	long cost;

	public Edge(int v, long cost) {
		this.v = v;
		this.cost = cost;
	}

	@Override
	public int compareTo(Edge o) {
		return Long.compare(this.cost, o.cost);
	}
}

Kruskal 알고리즘 풀이

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int v = in.nextInt();
		int e = in.nextInt();

		PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
		int vSet[] = new int[v + 1];

		for (int i = 1; i <= v; i++) {
			vSet[i] = i;
		}

		for (int i = 0; i < e; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			long cost = in.nextLong();

			pq.add(new Edge(start, end, cost));
		}

		long ans = 0;
		if (!pq.isEmpty()) {
			Edge firstEdge = pq.poll();
			ans += firstEdge.cost;
			union(firstEdge.v1, firstEdge.v2, vSet);
		}

		while (!isFinished(vSet) && !pq.isEmpty()) {
			Edge minEdge = pq.poll();

			int v1Contains = find(minEdge.v1, vSet);
			int v2Contains = find(minEdge.v2, vSet);

			if (v1Contains != v2Contains) {
				ans += minEdge.cost;
				union(minEdge.v1, minEdge.v2, vSet);
			}
		}
		System.out.println(ans);
	}

	public static void union(int x, int y, int[] vSet) {
		int ux = find(x, vSet);
		int uy = find(y, vSet);

		vSet[uy] = ux;
	}

	public static int find(int x, int[] vSet) {
		if (vSet[x] == x) {
			return x;
		}

		vSet[x] = find(vSet[x], vSet);
		return vSet[x];
	}

	public static boolean isFinished(int[] vSet) {
		int now = vSet[1];
		for (int i = 1; i < vSet.length; i++) {
			if (vSet[i] != now) {
				return false;
			}
		}
		return true;
	}
}

class Edge implements Comparable<Edge> {
	int v1, v2;
	long cost;

	public Edge(int v1, int v2, long cost) {
		this.v1 = v1;
		this.v2 = v2;
		this.cost = cost;
	}

	@Override
	public int compareTo(Edge o) {
		return Long.compare(this.cost, o.cost);
	}
}

세그먼트 트리는 구간의 최솟값을 구하는데 가장 효율적인 자료구조이다.

• 각 노드에 저장되는 값은 3가지이다 --> 저장되는 칸의 번호, 구간 시작, 구간 끝 (구간시작==구간끝: 리프 노드)
• 예를 들어 3~5 노드는 구간 3~5에서 최솟값을  저장하고 있다.
• 배열을 이용해서 구할 수 있다. --> x의 왼쪽 자식은 2x, 오른쪽 자식은 2x+1 이런 식으로,,,
• 모든 노드는 자식이 무조건 0개 또는 2개이다.
• 리프 노드가 n개인 full binary tree가 필요한 노드의 개수: 높이 h=lgn일 때 2^(h+1)

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();

		int arr[] = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			arr[i] = in.nextInt();
		}

		int h = (int) Math.ceil(Math.log(n) / Math.log(2));
		int maxTree[] = new int[1 << (h + 1)];
		int minTree[] = new int[1 << (h + 1)];

		initTree(true, arr, maxTree, 1, 1, n);
		initTree(false, arr, minTree, 1, 1, n);

		for (int i = 0; i < m; i++) {
			int start = in.nextInt();
			int end = in.nextInt();

			System.out.print(findSegment(false, minTree, 1, 1, n, start, end) + " ");
			System.out.println(findSegment(true, maxTree, 1, 1, n, start, end));
		}
	}

	public static int initTree(boolean isMaxTree, int[] arr, int[] tree, int index, int start, int end) {
		if (start == end) {
			tree[index] = arr[start];
			return tree[index];
		}

		int mid = (start + end) / 2;

		if (isMaxTree) {
			tree[index] = Math.max(initTree(isMaxTree, arr, tree, index * 2, start, mid),
					initTree(isMaxTree, arr, tree, index * 2 + 1, mid + 1, end));

			return tree[index];
		} else {
			tree[index] = Math.min(initTree(isMaxTree, arr, tree, index * 2, start, mid),
					initTree(isMaxTree, arr, tree, index * 2 + 1, mid + 1, end));

			return tree[index];
		}
	}

	public static int findSegment(boolean isFindMax, int[] tree, int index, int start, int end, int left, int right) {

		if (left > end || right < start) {
			// 범위와 관계 없어서 볼 필요가 없을 때
			return -1;
		}

		if (left <= start && right >= end) {
			// 범위에 구간이 포함되는 경우, left - start - end - right
			return tree[index];
		}

		// 범위에 구간이 일부 포함되는 경우
		// left - start - right - end 또는
		// start - left - right - end
		int mid = (start + end) / 2;
		if (isFindMax) {
			return Math.max(findSegment(isFindMax, tree, index * 2, start, mid, left, right),
					findSegment(isFindMax, tree, index * 2 + 1, mid + 1, end, left, right));
		} else {
			int segmentLeft = findSegment(isFindMax, tree, index * 2, start, mid, left, right);
			int segmentRight = findSegment(isFindMax, tree, index * 2 + 1, mid + 1, end, left, right);

			if (segmentLeft == -1) {
				return segmentRight;
			} else if (segmentRight == -1) {
				return segmentLeft;
			} else {
				return Math.min(segmentLeft, segmentRight);
			}
		}
	}
}

누적합은 앞에서부터 누적해서 더한 값을 뜻한다.

s[i] = a[i]+a[2]+...+a[i]

이 문제는 (a[i]+...+a[j])%m인 (i, j) 쌍의 갯수를 구하는 문제이다.

누적합을 구해두고 for문으로 (a[i]+...+a[j])를 구하면 O(N^2)만에 풀 수 있지만,

n<=10^6이고 시간 제한이 1초이므로 다른 방법을 생각해야 한다.

 (a[i]+...+a[j])%m == 0

<=> (s[j]-s[i-1])%m == 0

<=> s[j]%m == s[i-1]%m 와 같으므로

mod[k]: s[i]%m == k인 i의 갯수를 저장한다면

mode[k]C2를 모두 더하면 된다.

주의할 점은 s[i]%m==0인 i는 그 자체로 답이 되므로 바로 ans++해준다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		int m=in.nextInt();
		
		int sum=0;
		long mod[]=new long[m];
		long ans=0;
		
		for(int i=0;i<n;i++) {
			int input=in.nextInt();
			sum+=input;
			sum%=m;
			mod[sum]++;
			
			if(sum==0) {
				ans++;
			}
		}
		
		for(int i=0;i<m;i++) {
			long value = mod[i];
			long combination = value*(value-1)/Long.valueOf(2);
			ans+=combination;
		}
		System.out.println(ans);
	}
}

구하려고 하는 구간의 크기가 L로 결정되어 있을 때, 

모든 크기 L인 구간의 최솟값을 구하는 것이 sliding window 문제이다.

(세그먼트 트리나 다이나믹 프로그래밍 등으로도 풀 수 있다)

이 문제를 풀기 위해서는 덱을 이용해서 푸는데, 덱에 값과 인덱스를 저장한다.

덱에는 최대 L개의 값을 저장하고, 덱에 들어있는 값은 항상 증가하는 순서대로 저장한다.

• 덱은 값이 증가하는 순서로 저장되어 있다 --> 가장 처음 값이 최소값이다.
• 가장 처음 값의 인덱스와 현재 값의 인덱스의 차이가 L보다 큰지 작은지 검사한다.
• 가장 마지막 값이 현재 값보다 큰지 작은지 검사한다.
  • 덱의 마지막 값이 현재 값보다 크면 덱에서 제거하고 현재 값을 넣는다.

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken());
		int l=Integer.parseInt(st.nextToken());
		int arr[]=new int[n];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		
		Deque<Node> deque=new ArrayDeque<Node>();
		for(int i=0;i<n;i++) {
			int currentValue=arr[i];
			
			if(!deque.isEmpty() && deque.getFirst().index <=i-l) {
				// 최솟값이 될 수 없는 경우: 인덱스 차이가 넘 크다
				deque.pollFirst();
			}
			
			while(!deque.isEmpty() && deque.getLast().value>currentValue) {
				// 최솟값이 될 수 없는 경우: 값이 넘 크다
				deque.pollLast();
			}
			
			deque.offer(new Node(currentValue, i));
			arr[i] = deque.getFirst().value;
		}
		
		for(int i=0;i<n;i++) {
			bw.write(arr[i] + " ");
		}
		
		bw.flush();
		bw.close();
	}
}
class Node{
	int value;
	int index;
	
	public Node(int value, int index) {
		this.value=value;
		this.index=index;
	}
}

안드로이드 어플리케이션 최소 접속일 경우 튜토리얼 페이지를 띄우도록 한다.

이전다음

0

튜토리얼 페이지는

1. 슬라이드로 넘어가야 하고
2. 앱 실행시 최초 한번만 실행되어야 한다

슬라이드 activity를 만들기 위해서 viewPager을 사용하려고 했는데,

https://developer.android.com/training/animation/vp2-migration

viewPager2가 새로 나왔다고 해서 이걸로 만들어봤다.

기존의 viewPager는 PagerAdapter 기반으로,

스크롤 시 instantiateItem() 와 destroyItem() 메서드가 호출된다 --> 스크롤 할 때 버벅거림

이를 해결하려면 RecyclerView에 PagerSnapHelper로 해결할 수 있는데 복잡함

하지만 viewPager2는 RecyclerView기반이므로 따로 PagerSnapHelper를 만들 필요 없다.

(그리고 viewPager2는 final 클래스라서 커스텀 할 수 없음)

먼저 dependency를 추가해준다.

implementation "androidx.viewpager2:viewpager2:1.0.0"

activity_tutorial.xml

<?xml version="1.0" encoding="utf-8"?>
<androidx.viewpager2.widget.ViewPager2
    xmlns:android="http://schemas.android.com/apk/res/android"
    android:id="@+id/tutorial_viewpager"
    android:layout_width="match_parent"
    android:layout_height="match_parent" />

• 여기서는 괜찮았지만, 원래 viewpager2의 layout_width와 layout_height는 match_parent로 해 주어야 에러가 안난다고 한다. 그래서 만약에 크기를 지정해서 사용하고 싶다면 viewpager2를 다른 뷰 그룹으로 감싸주고 상위 뷰의 크기를 변경하도록 해야한다.

tutorial_1~4.xml

<?xml version="1.0" encoding="utf-8"?>
<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
    android:layout_width="match_parent"
    android:layout_height="match_parent">

    <ImageView
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:src="@drawable/tutorial_1" />

</RelativeLayout>

tutorial_5.xml

<?xml version="1.0" encoding="utf-8"?>
<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
    android:id="@+id/splash_view"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:opacity="opaque">

    <ImageView
        android:layout_width="95dp"
        android:layout_height="128dp"
        android:layout_centerHorizontal="true"
        android:layout_marginTop="196dp"
        android:layout_marginBottom="316dp"
        android:gravity="center"
        android:src="@drawable/splash_icon_color" />

    <TextView
        android:layout_width="110dp"
        android:layout_height="100dp"
        android:layout_centerHorizontal="true"
        android:layout_marginTop="334dp"
        android:layout_marginBottom="264dp"
        android:fontFamily="@font/baskervillebold"
        android:text="@string/app_name"
        android:textColor="@color/colorPriary"
        android:textSize="37sp" />

    <Button
        android:id="@+id/tutorial_end_button"
        android:layout_width="184dp"
        android:layout_height="48dp"
        android:layout_centerHorizontal="true"
        android:layout_marginTop="408dp"
        android:layout_marginBottom="184dp"
        android:background="@drawable/rounded_button"
        android:text="@string/app_start"
        android:textColor="@color/colorPriary"
        android:typeface="sans" />
</RelativeLayout>

그 다음 Adapter를 만들어줘야 하는데,

viewPager2는 RecylerView.Adapter 또는 FragmentStateAdapter로 설정할 수 있다.

Adapter란 하나의 객체로서, 뷰와 그 뷰에 올릴 데이터를 연결한다.

즉, 데이터의 원본을 받아 관리하고, 뷰가 출력할 수 있는 형태로 데이터를 제공한다.

암튼 두 어댑터의 차이점을 알아보니 아래와 같음

• RecyclerView.Adapter
  • viewPager가 PagerAdapter로 뷰를 통해 페이징 하는 경우
  • pagerAdapter: if you only want to have code that isn't going to be reused
• FragmentStateAdapter
  • viewPager가 FragmentPagerAdapter로 정해진 소수의 fragment를 통해 페이징 하는 경우
  • viewPager가 FragmentStatePagerAdapter로 많은 수/다이나믹한 프래그먼트를 통해 페이징 하는 경우
  • fragment--Adapter: you can use fragments inside this. if you want to have fragments that are going to be used in other parts of your code ~~

그래서 FragmentStateAdapter으로 ScreenSlidePagerAdapter을 구현하도록 했다.

package com.app.priaryapp.adapter;

import androidx.annotation.NonNull;
import androidx.fragment.app.Fragment;
import androidx.fragment.app.FragmentActivity;
import androidx.viewpager2.adapter.FragmentStateAdapter;

import com.app.priaryapp.view.tutorial.TutorialFragment;

import java.util.ArrayList;
import java.util.List;

public class ScreenSlidePagerAdapter extends FragmentStateAdapter {

    private List<Integer> layouts = new ArrayList<>();

    public ScreenSlidePagerAdapter(FragmentActivity fragmentActivity, List<Integer> layouts) {
        super(fragmentActivity);
        this.layouts = layouts;
    }

    @NonNull
    @Override
    public Fragment createFragment(int position) {
        return TutorialFragment.newInstance(layouts.get(position));
    }


    @Override
    public int getItemCount() {
        return layouts.size();
    }
}

ScreenSlidePagerAdapter는 알아서 TutorialFragment를 객체를 만든다. 이 때 주의할 점은 button객체와 onclick을 붙일 때 fragment 안에 있는 것이므로 fragment에서 해야하지 뒤에 나오는 TutorialActivity에서 하면 Null Pointer Error가 나와서 안됨

package com.app.priaryapp.view.tutorial;

import android.content.Intent;
import android.os.Bundle;
import android.view.LayoutInflater;
import android.view.View;
import android.view.ViewGroup;
import android.widget.Button;

import androidx.annotation.Nullable;
import androidx.fragment.app.Fragment;

import com.app.priaryapp.MainActivity;
import com.app.priaryapp.R;

public class TutorialFragment extends Fragment {

    private Button buttonTutorialEnd;

    private TutorialFragment() {
    }

    public static TutorialFragment newInstance(int page) {
        TutorialFragment tutorialFragment = new TutorialFragment();
        Bundle args = new Bundle();
        args.putInt("tutorial_page", page);
        tutorialFragment.setArguments(args);
        return tutorialFragment;
    }

    @Override
    public View onCreateView(LayoutInflater inflater, @Nullable ViewGroup container, @Nullable Bundle savedInstanceState) {

        int page = this.getArguments().getInt("tutorial_page");
        View view = inflater.inflate(page, container, false);

        if (page == R.layout.tutorial_5) {
            buttonTutorialEnd = view.findViewById(R.id.tutorial_end_button);
            buttonTutorialEnd.setOnClickListener(new View.OnClickListener() {
                @Override
                public void onClick(View view) {
                    getActivity().startActivity(new Intent(getActivity(), MainActivity.class));
                    getActivity().finish();
                }
            });
        }

        return view;

    }
}

참고: recycler view가 넘겨질 때 애니메이션을 설정하기 위해 ZoomOutPageTransformer 추가

package com.app.priaryapp.util;

import android.view.View;

import androidx.annotation.NonNull;
import androidx.viewpager2.widget.ViewPager2;

public class ZoomOutPageTransformer implements ViewPager2.PageTransformer {

    private static final float MIN_SCALE = 0.85f;
    private static final float MIN_ALPHA = 0.5f;

    @Override
    public void transformPage(@NonNull View page, float position) {
        int pageWidth = page.getWidth();
        int pageHeight = page.getHeight();

        if (position < -1) {
            page.setAlpha(0f);
        } else if (position <= 1) {
            float scaleFactor = Math.max(MIN_SCALE, 1 - Math.abs(position));
            float vertMargin = pageHeight * (1 - scaleFactor) / 2;
            float horzMargin = pageWidth * (1 - scaleFactor) / 2;
            if (position < 0) {
                page.setTranslationX(horzMargin - vertMargin / 2);
            } else {
                page.setTranslationX(-horzMargin + vertMargin / 2);
            }

            page.setScaleX(scaleFactor);
            page.setScaleY(scaleFactor);

            page.setAlpha(MIN_ALPHA + (scaleFactor - MIN_SCALE) / (1 - MIN_SCALE) * (1 - MIN_ALPHA));
        } else {
            page.setAlpha(0f);
        }
    }
}

그 다음 TutorialActivity를 만든다.

package com.app.priaryapp.view.tutorial;

import android.os.Bundle;

import androidx.fragment.app.FragmentActivity;
import androidx.viewpager2.adapter.FragmentStateAdapter;
import androidx.viewpager2.widget.ViewPager2;

import com.app.priaryapp.R;
import com.app.priaryapp.util.ZoomOutPageTransformer;
import com.app.priaryapp.adapter.ScreenSlidePagerAdapter;

import java.util.ArrayList;
import java.util.List;

public class TutorialActivity extends FragmentActivity {

    private ViewPager2 tutorialViewPager;
    private FragmentStateAdapter tutorialPagerAdapter;
    private List<Integer> tutorialLayouts;

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_tutorial);

        tutorialViewPager = findViewById(R.id.tutorial_viewpager);
        tutorialViewPager.setPageTransformer(new ZoomOutPageTransformer());
        tutorialLayouts = new ArrayList<>();
        tutorialLayouts.add(R.layout.tutorial_1);
        tutorialLayouts.add(R.layout.tutorial_2);
        tutorialLayouts.add(R.layout.tutorial_3);
        tutorialLayouts.add(R.layout.tutorial_4);
        tutorialLayouts.add(R.layout.tutorial_5);

        tutorialPagerAdapter = new ScreenSlidePagerAdapter(this, tutorialLayouts);
        tutorialViewPager.setAdapter(tutorialPagerAdapter);

    }
}

마지막으로 앱을 처음 깔았을 때 단 한번만 튜토리얼 페이지가 나오도록 해야 하기 때문에

SharedPreference로 튜토리얼 페이지가 실행됐는지 저장해두고, false인 경우에만 튜토리얼 페이지를 실행하도록 한다.

package com.app.priaryapp;

import android.app.Activity;
import android.content.Intent;
import android.content.SharedPreferences;
import android.os.Bundle;

import com.app.priaryapp.view.splash.SplashActivity;
import com.app.priaryapp.view.tutorial.TutorialActivity;

public class MainActivity extends Activity {

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);
        Intent intent = new Intent(this, SplashActivity.class);
        startActivity(intent);

        SharedPreferences sharedPreferences = getSharedPreferences("checkFirstAccess", Activity.MODE_PRIVATE);
        boolean checkFirstAccess = sharedPreferences.getBoolean("checkFirstAccess", false);


        if (!checkFirstAccess) {
            SharedPreferences.Editor editor = sharedPreferences.edit();
            editor.putBoolean("checkFirstAccess", true);
            editor.apply();

            Intent tutorialIntent = new Intent(MainActivity.this, TutorialActivity.class);
            startActivity(tutorialIntent);
            finish();
        }
    }
}

참고로 안드로이드 프로젝트는 MVP 패턴(Model-View-Presenter)으로 패키지를 나누는게 좋다고 한다.

• View: Activity/Fragment가 해당되며 실제 뷰에 대한 직접적인 접근을 담당한다. 뷰에서 발생하는 이벤트는 직접 핸들링 할 수 있으나 Presenter에 위임하도록 한다. 위임하는 방법은 액티비티가 뷰 인터페이스를 구현해서 Presenter에서 코드를 만들 인터페이스를 갖도록 하면 된다고 한다. 이렇게 하면 특정 뷰와 결합되지 않고 가상 뷰를 구현하여 간단한 유닛 테스트를 할 수 있다.
• Presenter: MVC 모델에서 컨트롤러 역할과 비슷한데, 뷰에 연결되는 것이 아니라 인터페이스로 연결된다. 뷰와 모델 사이의 자료 전달 역할을 한다.
• Model: 앱 데이터를 말하는데, 데이터 그 자체 외에도 데이터를 관리, 수집, 수정 등을 하는 부분이다.

splash screen 가이드는 2가지가 있다.

• placeholder UI: 로딩 전에 UI 등을 placeholder로 미리 보여줄 때 (로딩화면 같은...?)
• branded launch: 앱 시작할 때 순간적으로 브랜드 로고 등을 띄우는 경우

그 중 두번째에 해당하기 때문에 branded launch를 사용할건데,

처음에는 handler를 사용하지 않고 style에서 xml을 list-layer로 만든 뒤 activity_main의 background로 설정 함으로써

일정 시간의 지연 시간 없이 (사용자가 기다릴 필요 없이) 앱이 준비가 다 되면 넘어가도록 하려고 했는데,

아쉽게도 splash 화면에 text가 들어가서 위 방법으로 진행하지 못했다.

text를 꼭 넣고 싶다면 텍스트를 png로 저장해서 비트 맵으로 넣거나 vectorDrawable을 사용하면 되긴 한데,,,

위 두 가지 방법을 쓰느니 그냥 layer xml로 만들고 handler로 intent를 보내기로 했다.

• MainActivity.java

Main에서 SplashActivity를 부른다. 

package com.app.priaryapp;

import android.app.Activity;
import android.content.Intent;
import android.os.Bundle;

public class MainActivity extends Activity {

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);
        Intent intent=new Intent(this, SplashActivity.class);
        startActivity(intent);
    }
}

• SplashActivity.java --> manifest 파일에 추가하는 것 잊지 말 것

지금은 뒤에 더 추가하지 않았지만, 메인 화면 말고 다른 화면을 띄울거면 run() 함수 내부의 finish() 전에

Intent intent= new Intent(getApplicationContext(), 다른 클래스.class);

startActivity(intent);

위 코드를 추가함으로써 다른 화면으로 넘어갈 수 있다. finish()는 현재 액티비티를 종료하는 함수이다.

아래 코드에서 스플래시 화면은 뒤로가기를 할 수 없도록 onBackPressed() 함수를 추가해 두었다.

package com.app.priaryapp;

import android.app.Activity;
import android.os.Bundle;
import android.os.Handler;

public class SplashActivity extends Activity {
    private final int SPLASH_TIME=1000;

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.splash);

        new Handler().postDelayed(new Runnable() {
            @Override
            public void run() {
                finish();
            }
        }, SPLASH_TIME);
    }

    @Override
    public void onBackPressed(){

    }
}

https://material.io/design/communication/launch-screen.html#usage

나중에 시간 남으면 스플래시 화면에 애니메이션 넣을 예정인데 참고 자료 - xml로 애니메이션 설정하네,,, 신기하다

https://developer.android.com/training/animation

2020/07/15 - [알고리즘 공부] - boj 11437: LCA

두 정점간의 거리는 LCA를 사용해서 구할 수 있다.

먼저 LCA를 구한 뒤, LCA까지의 거리를 모두 더하면 된다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();

		int[] depth = new int[n + 1];
		int[] parentNode = new int[n + 1];
		int[] distances = new int[n + 1];
		boolean[] isVisited = new boolean[n + 1];
		LinkedList<Node> pair[] = new LinkedList[n + 1];
		for (int i = 1; i <= n; i++) {
			pair[i] = new LinkedList<Node>();
		}

		for (int i = 1; i < n; i++) {
			int node1 = in.nextInt();
			int node2 = in.nextInt();
			int distance = in.nextInt();
			pair[node1].add(new Node(node2, distance));
			pair[node2].add(new Node(node1, distance));
		}

		depth = calculateNodeDepth(pair, parentNode, distances, n);

		int test = in.nextInt();

		for (int t = 0; t < test; t++) {

			int node1 = in.nextInt();
			int node2 = in.nextInt();

			int depth1 = depth[node1];
			int depth2 = depth[node2];
			int distance = 0;

			if (depth1 < depth2) {
				int tmp = node1;
				node1 = node2;
				node2 = tmp;

				depth1 = depth[node1];
				depth2 = depth[node2];
			}

			distance = calculateLCA(parentNode, depth, distances, node1, node2);
			System.out.println(distance);
		}
	}

	public static int calculateLCA(int parent[], int depth[], int distance[], int node1, int node2) {

		int depth1 = depth[node1];
		int depth2 = depth[node2];
		int ans = 0;

		while (depth1 > depth2) {
			ans += distance[node1];
			node1 = parent[node1];
			depth1 = depth[node1];
		}

		while (node1 != node2) {
			ans += distance[node1];
			ans += distance[node2];
			node1 = parent[node1];
			node2 = parent[node2];
		}
		
		return ans;
	}

	public static int[] calculateNodeDepth(LinkedList<Node> pair[], int parent[], int distance[], int n) {
		Queue<Node> queue = new LinkedList<Node>();
		int depth[] = new int[n + 1];
		boolean isVisited[] = new boolean[n + 1];

		queue.add(new Node(1, 0));
		depth[1] = 0;
		isVisited[1] = true;

		while (!queue.isEmpty()) {

			Node node = queue.poll();

			for (Node i : pair[node.name]) {
				if (!isVisited[i.name]) {
					queue.add(i);
					depth[i.name] = depth[node.name] + 1;
					parent[i.name] = node.name;
					distance[i.name] = i.distance;
					isVisited[i.name] = true;
				}
			}
		}
		return depth;
	}
}

class Node {
	int name;
	int distance;

	public Node(int name, int distance) {
		this.name = name;
		this.distance = distance;
	}
}

LCA: Lowest common Ancestor

두 노드의 가장 가까운 공통 조상을 찾는 문제이다.

LCA를 찾기 위해서는 두 노드의 level과 부모를 알아야한다.

따라서

• 두 노드의 레벨이 다르면, 레벨이 같을 때까지 레벨이 큰 것을 한 칸씩 위로 올린다.
• 두 노드의 레벨이 같아지면, 같은 노드가 될 때까지 한 칸씩 위로 올린다.

인접 행렬을 사용하면 메모리 초과가 생기고,

Queue에 pair을 저장하면 나중에 bfs를 돌 때 시간 초과가 생기므로

LinkedList의 배열에  pair을 저장하고 바로 꺼내 쓸 수 있도록 한다.

이 문제의 주의할 점은 입력 시 어떤 노드가 parent이고 어떤 노드가 child인지 알 수 없으므로

bfs을 돌 때 parent와 child를 정의할 수 있다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();

		int[] depth = new int[n + 1];
		int[] parentNode = new int[n + 1];
		boolean[] isVisited = new boolean[n + 1];
		LinkedList<Integer> pair[] = new LinkedList[n + 1];
		for (int i = 1; i <= n; i++) {
			pair[i] = new LinkedList<Integer>();
		}

		for (int i = 1; i < n; i++) {
			int node1 = in.nextInt();
			int node2 = in.nextInt();
			pair[node1].add(node2);
			pair[node2].add(node1);
		}

		depth = calculateNodeDepth(pair, parentNode, n);

		int test = in.nextInt();
		int ans = 1;
		for (int t = 0; t < test; t++) {

			int node1 = in.nextInt();
			int node2 = in.nextInt();

			int depth1 = depth[node1];
			int depth2 = depth[node2];

			if (depth1 < depth2) {
				ans = calculateLCA(parentNode, depth, node2, node1);
			} else{
            	ans = calculateLCA(parentNode, depth, node1, node2);
            }
			System.out.println(ans);
		}
	}

	public static int calculateLCA(int parent[], int depth[], int node1, int node2) {

		int depth1 = depth[node1];
		int depth2 = depth[node2];
		int ans = 1;

		while (depth1 > depth2) {
			node1 = parent[node1];
			depth1 = depth[node1];
		}

		while (node1 != node2) {
			node1 = parent[node1];
			node2 = parent[node2];
		}

		ans = node1;
		return ans;
	}

	public static int[] calculateNodeDepth(LinkedList<Integer> pair[], int parent[], int n) {
		Queue<Integer> queue = new LinkedList<Integer>();
		int depth[] = new int[n + 1];
		boolean isVisited[] = new boolean[n + 1];

		queue.add(1);
		depth[1] = 0;
		isVisited[1] = true;

		while (!queue.isEmpty()) {

			int node = queue.poll();

			for (int i : pair[node]) {
				if (!isVisited[i]) {
					queue.add(i);
					depth[i] = depth[node] + 1;
					parent[i] = node;
					isVisited[i] = true;
				}
			}
		}
		return depth;
	}
}