들쮜의 개발자일지

풀면서 게속 들은 생각은 파이썬으로 풀었다면 정말 쉽게 풀었겠다... 라는 것

문제에서 대놓고 재귀함수를 사용하라고 알려주고 있듯이 재귀함수로 구현하면 풀 수 있다.

재귀만 돌리면 풀 수 있는 문제라 딱히 설명할 것이 없는데, 계속 StringBuilder를 만들어주는게 여간 귀찮은게 아니었다.

그냥 더해도 되긴 하지만 문자열과 문자열을 쌩으로 더하는 건 괜히 찝찝하다...

점점 알고리즘을 풀면서 클래스를 만들거나, 함수로 나누어서 푸는것에 익숙해지고있다.

삼성 역량테스트 B형을 못 따면 B형 특강은 다른 회사 코테와 많이 달라 공부가 의미 없다고 이야기하는 사람들도 많고, 은근 공감도 하지만

그래도 알고리즘 푸는 능력 향상에 꽤 도움이 되는 건 인정 안 할 수가 없다.

import java.util.*;

class Solution {
    public String solution(String p) {
        String answer = "";
        answer = getUV(p);
        
        return answer;
    }
    
    
    
    
    private static String getUV(String p){
        if(p.equals("")) return "";
        StringBuilder sb = new StringBuilder();
        String[] uv = new String[2];
        int left = 0;
        int right = 0;
        int idx = 0;
        for(int i=0; i<p.length(); i++){
            if(p.charAt(i)=='('){
                left +=1;
            }else{
                right +=1;
            }
            if(left == right){
                sb.append(p.charAt(i)+"");
                idx = i;
                break;
            }else{
                sb.append(p.charAt(i)+"");
            }
        }
        String u = "";
        if(sb.length() !=0){
            u = sb.toString();
        }
        sb.setLength(0);
        for(int i=idx+1; i<p.length(); i++){
            sb.append(p.charAt(i)+"");
        }
        String v = "";
        if(sb.length() != 0){
            v = sb.toString();
        }
        
        uv[0] = u;
        uv[1] = v;
        if(check(u)){
            return u + getUV(v);
        }
        StringBuilder tmpSb = new StringBuilder();
        tmpSb.append("(");
        tmpSb.append(getUV(v));
        tmpSb.append(")");
        u = u.substring(1, u.length()-1);
        for(int i=0; i<u.length(); i++){
            if(u.charAt(i) == '('){
                tmpSb.append(")");
            }else{
                tmpSb.append("(");
            }
        }
        
        
        return tmpSb.toString(); 
    }
    
    private static boolean check(String u){
        
        Stack<Character> stack = new Stack<>();
        for(int i=0; i<u.length(); i++){
            if(u.charAt(i) == '('){
                stack.push('(');
            }else{
                if(stack.isEmpty()){
                    return false;
                }else{
                    stack.pop();
                }
            }
        }
        if(!stack.isEmpty()){
            return false;
        }else{
            return true;
        }
    }
}

늑대의 개수가 양과 동일해지지 않도록 탐색을 하면서 양을 최대한 많이 챙겨야 하는 문제입니다.

처음엔 BFS를 생각했는데, 왼쪽부터 도는 것과 오른쪽 부터 도는 것의 차이가 생겨서 제대로 된 탐색이 어려웠고,

그리디 알고리즘으로 생각을 전환하였습니다.

양을 만나기 위해 필요한 늑대의 수를 배열에 담고, 오름차순으로 정렬하여 현재 양의 개수 - 1보다 적다면 해당 양을 챙길 수 있다는 가정하에 진행하였으나, 

해당 양을 데리러 가는 길에 만나서 내가 데리고 있는 늑대의 수를 체크하기가 어려웠습니다. 

다시 생각해보면 해당 양을 만나기 위해 필요한 늑대의 수가 아닌, 늑대의 인덱스를 담아두어 방문처리를 해주면 될 것 같긴 한데, 이렇게 되면 해당 양을 만나러 갈 때 거치게 되는 늑대의 수가 뒤죽박죽 됐고,

늑대를 제거하는 식으로 생각을 해도, 어떤 늑대를 제거하는 것이 가장 그리디한 방법인지 찾기가 어려웠습니다.

똑같이 양을 만나러 갈 때 필요한 늑대의 수가 2마리더라도, 자식이 2개인 늑대노드를 제거하는게 더 이득일지... 다 고려를 해야하는걸까 고민하던차에

이리 생각하고 저리 생각해도 자꾸 막혀 다시 문제를 살펴보니 info 개수가 17개더군요..

눈치를 챘어야 하는데... 제발 문제를 풀기 전에 문제 조건을 다시 한 번 봐야겠다는 다짐을 하게 되는 문제였습니다.

브루트포스라는 걸 알았으니, 이제 늑대 수와 양 수를 저장해두어 분기마다  갈 수 있는 모든 노드에 대해 완전탐색을 해주면 됩니다.

import java.util.*;

class Solution {
    static List<List<Integer>> adj = new ArrayList<>();
    static boolean[] wolf;
    static int ans;
    public int solution(int[] info, int[][] edges) {
        int answer = 0;
        wolf = new boolean[info.length];
        
        for(int i=0; i<info.length; i++){
            adj.add(new ArrayList<>());
            if(info[i] == 1){
                wolf[i] = true;
            }
        }
        for(int[] edge : edges){
            adj.get(edge[0]).add(edge[1]);
        }
        dfs(0, new ArrayList<>(), 0, 1, new boolean[info.length]);
        return ans;
    }
    private static void dfs(int i, List<Integer> lst, int wolfCnt, int sheepCnt, boolean[] visited){
        ans = Math.max(ans, sheepCnt);
        List<Integer> arr = new ArrayList<>();
        for(int num : adj.get(i)){
            if(!visited[num]){
                arr.add(num);
            }
        }
        for(int num : lst){
            if(!visited[num]){
                arr.add(num);
            }
        }
        
        for(int node : arr){
            if(!wolf[node] && !visited[node]){
                visited[node] = true;
                dfs(node, arr, wolfCnt, sheepCnt+1, visited);
                visited[node] = false;
            }
            if(wolf[node] && !visited[node] && sheepCnt - 1 > wolfCnt){
                visited[node] = true;
                dfs(node, arr, wolfCnt+1, sheepCnt, visited);
                visited[node] = false;
            }
        }
    }
}

https://leetcode.com/problems/trapping-rain-water/

SSAFY 셔틀버스를 타는 1시간동안 멍 때리고 유튜브를 볼 게 아니라 이렇게 알고리즘을 풀 수 있다는 생각을 왜 이제서야 했는지 모르겠다.

무접점 키보드가 아니라 키압이 좀 무거운 바저적을 사용하는게 단점이었는데, 정말 소리가 하나도 안 난다는 장점이 있어서 버스 내에서 알고맂므을 풀 수 있다는 걸 이제야 생각했다

힌트 1. 물은 나보다 큰 벽이 다가왔을 앞에 나왔을 때만 담겨질 수 있다.

힌트 2. 가장 왼쪽 값은 자신보다 같거나 큰 값이 나오기 전까지 바뀌지 않는다.

힌트 3. 자신보다 큰 벽이 왔을 때 물이 담기는 양은 가장 왼쪽 벽과 앞에 나온 벽 중 작은 값 - 각 인덱스의 높이다.

class Solution {
    public int trap(int[] height) {
        int start = 0;
        int[] water = new int[height.length];
        for(int i=1; i<height.length; i++){
            // 이전 값보다 증가했을 경우 물이 찰 가능성이 있음
            if(i!=1 && height[i] - height[i-1] > 0){
                int num = Math.min(height[start], height[i]);
                for(int j=start; j<i; j++){
                    water[j] = Math.max(water[j], num - height[j]);
                }
            }

            if(height[i] >= height[start]){
                start = i;
            }
        }
        int ans = 0;
        for(int num : water){
            ans += num;
        }
        return ans;
    }
}

https://leetcode.com/problems/find-median-from-data-stream/description/

힌트 1. 중앙값을 찾는 문제인데, 중앙값이란 원소 개수가 홀수개일 때, 중앙값 x를 기준으로 x보다 작은 값이 n개 x보다 큰 값이 n개인 수이다.

힌트 2. 원소 개수가 짝수개일 경우 x보다 작은 원소가 n 개 y보다 큰 원소가 n개인 (x + y) / 2값이 중앙값이 된다.

힌트 3. x보다 작은 n개의 수가 담긴 리스트는 원소개수가 n+1개인 max heap의 최댓값이 x일 경우이다.

힌트 4. y보다 큰 n개의 수가 담긴 리스트는 원소 개수가 n+1개인 min heap의 최솟값이 y일 경우이다.

힌트 5. 위의 명제가 성립하기 위해서는 x<=y이어야만 한다.

class MedianFinder {

    private static PriorityQueue<Integer> maxHeap;
    private static PriorityQueue<Integer> minHeap; 
    public MedianFinder() {
        //Heap 초기화
        maxHeap = new PriorityQueue<>((a, b) -> b-a);
        minHeap = new PriorityQueue<>();
    }
    
    public void addNum(int num) {

        // 1. maxHeap과 minHeap에 번갈아가면서 숫자를 채운다
        if(maxHeap.size() == minHeap.size()){
maxHeap.add(num);
        }else{
            minHeap.add(num);
        }
        
        // 2. minHeap의 최솟값은 maxHeap의 최댓값보다 크거나 같아야한다
        if(maxHeap.isEmpty() || minHeap.isEmpty()) return;

        // 2-1. minHeap의 최솟값이 maxHeap의 최댓값보다 작으면 둘의 위치를 바꿔준다.
        while(maxHeap.peek() > minHeap.peek()){
            int tmp = minHeap.poll();
            minHeap.add(maxHeap.poll());
            maxHeap.add(tmp);
        }
    }
    
    public double findMedian() {
        // 3. maxHeap부터 채울 것이므로 maxHeap이 비어있다면 return null;
        if(maxHeap.isEmpty()) return 0.0;

        // 3-1. maxHeap과 minHeap의 사이즈가 같다면 각각의 최대 최소를 뽑아서 2로 나누기
        if(maxHeap.size() == minHeap.size())
        { 
            return (double) (maxHeap.peek() + minHeap.peek()) / 2;
        }// 3-2. maxHeap과 minHeap의 사이즈가 다르다면 maxHeap의 최댓값이 중앙값
        else{
            return (double) maxHeap.peek();

        }

    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

nums1 리스트와 nums2 리스트의 순서쌍 중 순서쌍의 합이 가장 작은 k개의 순서쌍을 출력하는 문제

힌트 1. nums1의 길이는 10만, nums2의 길이도 10만이지만 k는 1만개밖에 되지 않는다. 최대 nums1[k-1] + nums2[0]이거나 nums1[0] + nums2[k-1] 까지만 찾아도 되기 때문에 최대 k제곱번만 돌아도 된다. 10만 -> 1만으로 확 줄일 수가 있다.

힌트 2. nums1[0]과 nums2[0]을 비교했다면 그 다음 비교해야 하는 수는 nums1[0]과 nums2[1]이다. nums1[0]과 nums2[2], nums1[0]과 nums2[3]을 벌써 체크할 필요는 없다.

힌트 3. nums1[0]부터 nums1[k-1]까지의 값들과 nums2[0]의 값들을 모두 min-heap에 넣는다. 그리고 최솟값을 뺀다. 그 다음으로 가장 가능성 있는 순서쌍은 이번에 뺀 순서쌍에서 nums2의 인덱스를 하나 증가한 값이다

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> resV = new ArrayList<>(); // Result list to store the pairs
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
       
       // 1. nums1의 모든 값들과 nums2의 0번째 인덱스를 더한 값 모두 최소힙에 넣기
       int idx = 0;
       for(int num : nums1){
           // 1-1 . 1번째는 nums1의 값, 2번째는 순서쌍의 합(최소힙 Comparator에 사용), 3번째는 num2의 인덱스
           pq.add(new int[]{num, num + nums2[0], 0});
           idx++;

           if(idx == k) break;
       }

       List<List<Integer>> ans = new ArrayList<>();
       // 2. Heap에서 하나를 뽑아서 정답 리스트에 추가하고 그 다음으로 가능성 있는 수를 Heap에 넣기
       while(k-- > 0){
             if(pq.isEmpty()){
               return ans;
           }
           int[] cur = pq.poll();
           List<Integer> lst = new ArrayList<>();
           
           // 2-1. 최소값의 nums1, nums2값 넣기
           lst.add(cur[0]);
           lst.add(nums2[cur[2]]); 
           ans.add(lst);

           // 2-2 . 가능성 있는 수 heap에 넣기
           if(cur[2] + 1 < nums2.length){
            pq.add(new int[]{cur[0], cur[0]+nums2[cur[2]+1], cur[2]+1});
           }
         

       }
       return ans;


    }
}

 속도는 잘 나오지만 메모리가 간당간당 해져버린다.

메모리를 어떻게 줄여야 할지는 감이 잡히질 않는다...

2D게임에서 왼쪽 오른쪽으로 방향전환을 해야할 때가 있다.

이 때 unity는 spriter renderer 컴포넌트로 Flip 유무를 체크해줄 수가 있다.

 using System.Collections;
using System.Collections.Generic;
using Unity.VisualScripting;
using UnityEngine;
using UnityEngine.InputSystem;

public class Player : MonoBehaviour
{
    public Vector2 inputVec;

    Rigidbody2D rigid;
    SpriteRenderer spriter;

    public float speed;
    // Start is called before the first frame update
    void Awake()
    {
        rigid = GetComponent<Rigidbody2D>();
        spriter = GetComponent<SpriteRenderer>();
    }

    // Update is called once per frame
    void Update()
    {
        

    }

    private void FixedUpdate()
    {
        /*        // 1.  힘을 준다
                rigid.AddForce(inputVec);

                // 2. 속도 제어
                rigid.velocity = inputVec;
        */
        // 3. 위치 이동
        Vector2 next = inputVec * speed * Time.fixedDeltaTime;
        print(speed);
        print(next);
        
        rigid.MovePosition(rigid.position + next);
    }

    private void LateUpdate()
    {
        if(inputVec.x != 0)
        {
            spriter.flipX = inputVec.x < 0;
        }
    }

    void OnMove(InputValue value)
    {
        inputVec = value.Get<Vector2>();
    }
 
}

SpriteRenderer 컴포넌트를 가져온 뒤 해당 컴포넌트의 Flip 요소를 가지고 와서 X값에 체크박스릃 오른족 왼쪽 여부에 따라 true false로 바꿔주면 된다.

애니메이션을 넣는 방법은 3D보다 2D가 훨씬 간단하다.

sprite가 없다면 이것도 굉장히 어려운 작업이긴 하겠지만...

이런식으로 필요한 스프라이트들을 다중선택한 뒤 적용하고 싶은 Object에 넣어주면 해당 오브젝트가 애니메이션을 가지게 된다.

애니메이션을 만들면 이렇게 애니메이터가 자동으로 생성되고 이것들을 조합해서 애니메이션을 만들 수 있다.

특정 포인트에서 특정 애니메이션을 실행시킬 수 있는데

에를들어 InputVec의 x, y값이 0이면 stand (default값으로 설정도 가능)

값이 있으면 특정 애니메이션 이런식으로!

왼쪽의 Parameter에 변수들을 생성할 수 있는데 이것들은 C# 스크립트에서 Animator 컴포넌트를 가져와서 조절해줄 수가 있다

float값은 SetFloat("변수명", 값) 으로 수정이 가능하다.

이 변수값에 따라 애니메이션을 작동시킨다면 예를 들어, Speed 값을 넣어서 speed가 0.1 이상일 경우 작동을 하게 한다면

오른쪽의 컨디션에 Parameter값을 넣어 조절을 해주고 

 using System.Collections;
using System.Collections.Generic;
using Unity.VisualScripting;
using UnityEngine;
using UnityEngine.InputSystem;

public class Player : MonoBehaviour
{
    public Vector2 inputVec;

    Rigidbody2D rigid;
    SpriteRenderer spriter;
    Animator anim;

    public float speed;
    // Start is called before the first frame update
    void Awake()
    {
        rigid = GetComponent<Rigidbody2D>();
        spriter = GetComponent<SpriteRenderer>();
        anim = GetComponent<Animator>();
    }

    // Update is called once per frame
    void Update()
    {
        

    }

    private void FixedUpdate()
    {
        /*        // 1.  힘을 준다
                rigid.AddForce(inputVec);

                // 2. 속도 제어
                rigid.velocity = inputVec;
        */
        // 3. 위치 이동
        Vector2 next = inputVec * speed * Time.fixedDeltaTime;
        print(speed);
        print(next);
        
        rigid.MovePosition(rigid.position + next);
    }

    private void LateUpdate()
    {
        anim.SetFloat("Speed", inputVec.magnitude);
        
        if(inputVec.x != 0)
        {

            spriter.flipX = inputVec.x < 0;
        }
    }

    void OnMove(InputValue value)
    {
        inputVec = value.Get<Vector2>();
    }
 
}

다음과 같이 SetFloat로 Speed값을 벡터의 크기값 magnitude로 넣어주면 이제 Input값이 생길 때마다 걷는 애니메이션이 작동하게 될 것이다.

그리고 이런 Parameter와 Trigger 같은 애니메이션 요소들은 오버라이드가 가능하므로 다른 Sprite들을 묶어 애니메이션으로 만든 뒤 오버라이드 시키면 다른 오브젝트에도 같은 애니메이션을 적용할 수가 있다

드디어 내가 원하던 게임을 만들 수 있는 시간이 왔다

SSAFY에서 1학기 Django와 Vue를 배우면서 Python과 JavaScript에 익숙해지고

2학기에 Spring Boot를 사용해보면서 Java에 익숙해졌으니

이제 정말 내가 원하던 남자의 로망 게임을 만들어 볼 준비가 됐다고 생각한다.

Unity는 또 C#을 사용해서 만들지만 C#은 자바와 굉장히 비슷한 문법을 가지고 있기 때문에 전혀 문제가 되지 않을 것 같다.

개발을 너무 늦은 나이에 시작한 것이 아닌가라는 생각도 들지만, 늦게 시작했기 때문에 더 쉽고 빠르게 공부할 수 있다는 건 큰 메리트라고 생각한다.

 using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.InputSystem;

public class Player : MonoBehaviour
{
    Vector2 inputVec;

    Rigidbody2D rigid;

    public float speed;
    // Start is called before the first frame update
    void Awake()
    {
        rigid = GetComponent<Rigidbody2D>();
    }

    // Update is called once per frame
    void Update()
    {
        inputVec.x = Input.GetAxisRaw("Horizontal");

        inputVec.y = Input.GetAxisRaw("Vertical");

    }

    private void FixedUpdate()
    {
/*        // 1.  힘을 준다
        rigid.AddForce(inputVec);

        // 2. 속도 제어
        rigid.velocity = inputVec;
*/
        // 3. 위치 이동
        Vector2 next = inputVec.normalized * speed *  Time.deltaTime;
        rigid.MovePosition(rigid.position + next);
    }

 
}

원래는 이런식으로 Player가 이동을 한다.

힘을 주거나, 속도를 제어하거나 혹은 MovePosition으로 위치를 이동시키는 방식으로 이동을 하는데 

Input Vector를 만들고 거기에 GetAxis값들로 Input Manager에 있는 Horizontal과 Vertical값을 가져오는 방식이다. 

이 과정을 Plyaer Input을 통해 간단하게 처리해줄 수가 있게 됐다.

위와 같이 Player Input 컴포넌트를 생성할 수 있고 액션을 만들어서 간단하게 Input값으로 Vector값을 조절할 수 있게 됐다.

다음과 같이 Press 됐을 때 Vector값을 이동하고 이동되는 값은 normailze로 일반화해준다.

 using System.Collections;
using System.Collections.Generic;
using Unity.VisualScripting;
using UnityEngine;
using UnityEngine.InputSystem;

public class Player : MonoBehaviour
{
    Vector2 inputVec;

    Rigidbody2D rigid;

    public float speed;
    // Start is called before the first frame update
    void Awake()
    {
        rigid = GetComponent<Rigidbody2D>();
    }

    // Update is called once per frame
    void Update()
    {
        

    }

    private void FixedUpdate()
    {
        /*        // 1.  힘을 준다
                rigid.AddForce(inputVec);

                // 2. 속도 제어
                rigid.velocity = inputVec;
        */
        // 3. 위치 이동
        Vector2 next = inputVec * speed * Time.fixedDeltaTime;
        rigid.MovePosition(rigid.position + next);
    }

    void OnMove(InputValue value)
    {
        inputVec = value.Get<Vector2>();
    }
 
}

그럼 OnMove라는 함수로 InputValue 값을 받아올 수가 있고, value에서 우리가 넣어둔 Processor의 값 Vector2를 가져와서 넣어주면 이 한 줄로 굳이 InputManager를 이용하지 않고 간단하게 이동을 처리할 수 있게 되었다.

자바로 처음으로 이분탐색을 구현해보았는데, 파이썬이랑 사실상 다를게 없어서 가볍게 구현할 수 있는 문제.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXNQOb3avD0DFAXS 

인덱스를 선택하고 거기서 오른쪽으로 최장 몇칸 갈 수 있는지를 체크한다.

왼쪽은 고려하지 않아도 되는게, 왼쪽 인덱스에 바로 붙어있어 연속되는 수강일이 있다고 하더라도, 이미 왼쪽에서 처리해주면서 넘어왔기 때문에 왼쪽은 볼 필요가 없다.

1. 반복문으로 모든 수강일를 돌기

2. 오른쪽 인덱스로 하나 늘어날 때마다 수강한 날이 하나 늘어남

3. 오른쪽 인덱스 - 선택한 인덱스 + 1 = 수강한 날의 일 수, 오른쪽 값 - 선택한 값 + 1 = 전체 일 수

4. 전체 일 수 - 수강한 날 수 = 해킹해서 채워야 하는 날 수

5. 정답의 최솟값은 각각의 수강 날짜가 너무 범위가 커서 수강 날짜를 이을 수 없어, 하나의 날짜에 p로 덧붙이는 경우

ex) 4 420 (수강한 날은 2일이지만, 전체 일수는 417일, 그러므로 하나만 고르고 p로 이어붙이는 1+p가 최솟값)

6. 오른쪽 인덱스를 정하고 나면 해당 인덱스까지 연속으로 잇기 위해 필요한 날짜만큼 p에서 빼고, 남은 p값은 추가로 더해주기 == 해당 기간동안 수강한 날수 + p

import java.util.*;
import java.io.*;
public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int t = 1; t<= T; t++){
            int n = sc.nextInt();
            int p = sc.nextInt();
            int[] lst = new int[n];
            for(int i=0; i<n; i++){
                lst[i] = sc.nextInt();
            }
            int answer = 1 + p;
            for(int i=0; i<n-1; i++){
                int start = i+1;
                int end = n-1;
                int res = i;


                while(start <= end){
                    int mid = (start + end)/2;
                    int totalDay = lst[mid] - lst[i] + 1;
                    int attendDay = mid - i + 1;
                    if(totalDay - attendDay <= p){
                        start = mid + 1;
                        res = mid;
                    }else{
                        end = mid - 1;
                    }
                }
                int totalDay = lst[res] - lst[i] + 1;
                int attendDay = res - i + 1;
                answer = Math.max(answer, p - (totalDay - attendDay) + totalDay);

            }
            System.out.println("#"+t+" "+answer);
        }

    }
}