플레이데이터 풀스택 백엔드 9기 4월 3주차 회고

플레이데이터 풀스택 백엔드 9기 5주차 주간회고 및 학습기록 (다섯번째 기록)

---

Facts

이번 주는 자료구조와 알고리즘을 중점적으로 배웠다. List, Stack, Queue, 동적계획법 등을 이해하려고 노력했지만 아직 내가 스스로 만들어 쓸 정도로 완벽하게 이해하지는 못한 거 같다. 전반적인 컨셉과 어떤 식으로 구현되는지는 이해됐지만 역시 직접 작성해봐야 완전히 깨달을 수 있을 것이다. 특히 Stack을 이용한 백준 괄호 문제를 실습으로 풀었는데, 2차 테스트 코드를 끝내 못 뚫고 선생님 찬스를 이용했다. 선생님의 해답은 나의 것과 전혀 달랐다. 난 Stack을 이용해서 풀어야 할 문제를 그저 패턴 찾기 방식으로 풀려고 한 반면, 선생님의 풀이는 Stack 자료구조를 완전하게 잘 사용한 방식이었다. Stack 구조를 완전히 이해하지 못했서 그랬다기보다는, 사용법을 전혀 생각하지 못했었다. 

 

나름 치열하게 자료구조와 알고리즘을 공부하는 사이, 매니저님들께서는 작은 이벤트를 열어주셨다. MBTI를 맞추면 커피를 사주시는 이벤트였다. 생명수와도 같은 커피를 얻어먹을 수 있다니, 이 기회는 놓치면 안되기 때문에 꽤나 오래 고민했다. 그리고 그 결과! 역시 내 예상은 빗나가지 않았다. 정답을 맞췄고 덕분에 맛있는 커피를 얻어먹었다. 작은 이벤트들을 이렇게 종종 열어주셔서 즐겁고 감사하다. 시험공부하다가 잠깐 보는 유튜브 같달까. 그리고 책 나눔 이벤트 덕분에 평소 관심 있던 데이터분석 관련 책을 두 권 받았다. 여러 방면에서 수강생들의 공부를 도와주시는 거 같아 감사했다.

 

금요일에는 자료구조와 알고리즘 진도를 마치고 UML과 유스케이스 다이어그램 그리는 방법에 대해 배웠다. 수업을 들으며 유난히 집중이 잘된다는 느낌이 들었는데, 비교적 쉽기 때문에 집중이 잘 된 것이었다. whimsical이라는 사이트에서 유스케이스 다이어그램을 그렸는데, 이를 지원하는 툴이 많고 편리했다. 세상에는 좋은 사이트가 많다.

---

Feelings

선생님께서 자료구조를 이용해서 문제를 푸시는 모습을 보면서 막막한 기분이 들었다. 물론 실습 문제들을 푸는 과정은 너무나도 재미있었다. 그렇지만 자료구조를 이용해서 코딩 문제를 푸는 건, 뭐랄까 내 사고체계를 뜯어 고쳐서 해야 하는 일처럼 느껴졌다. 점화식을 어떻게 작성해야 할지, 이런 문제들과 자료구조를 구현하는 것에 어떻게 적응할 수 있을지, 얼마나 문제를 풀어야 익숙하게 해결할 수 있을지...여러 생각이 들었다. 물론 겨우 일주일 동안 자료구조 공부해놓고 막막하다고 징징대는 건 좀 웃기기는 하다. 고수분들은 적응하기까지 엄청나게 많은 시간을 쏟아부었을 것이다. 고작 일주일 공부한 내가 난리칠 수는 없는 노릇이다. 그렇지만 벽 앞에서 희망 먼저 떠올리기란 참 쉽지 않은가보다. 선생님을 비롯한 여러 고수들의 처음도 당연히 나와 같았을 것이라는 걸 상기하며 천천히, 꾸준하게 자료구조 공부를 해야겠다. 

 

이번 주는 수업에 집중을 잘했다. 물론 수요일 오전시간에 좀 졸았지만, 그 시간을 제외하면 똘망똘망하게 수업을 들었다. (DFS, BFS가 어려워서.. 회피 심리로 졸아버렸다) 자료구조 공부가 조금 지겹게 느껴지기도 했지만, 빨리 익숙해지고 싶어서 집중하려고 노력했다. 점화식을 찾고 동적계획법으로 실습 문제를 푸는 과정은 엄청 즐겁게 느껴지기도 했다. 자꾸 어렵다고 회피하지 말고 직접 코드를 짜고 문제를 풀어보는 게 더 재밌게 공부할 수 있는 방법인 것 같다. 이제 하루에 한 문제라도 백준 문제를 풀어봐야겠다. 

---

Findings

1. Stack을 이용한 백준 괄호문제(9012) 풀이

(https://www.acmicpc.net/problem/9012)

• 내가 작성한 비효율적인 풀이

package com.section03.stack;

import java.util.Stack;

public class Practice1_MyAnswer {

    public String solution(String input) {
        Stack<Character> stack = new Stack<>();
        char[] chars = input.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            stack.push(chars[i]);
        }

        int countOfLeft = 0;
        int countOfRight = 0;

        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '(') {
                countOfLeft++;
            } else {
                countOfRight++;
            }
        }

        if (chars[0] == ')' || chars[chars.length - 1] == '(' || chars.length % 2 == 1 || countOfLeft != countOfRight) {
            return "NO";
        } else {
            return "YES";
        }
    }
}

- 패턴을 나름 분석해서 패턴에 어긋나는 케이스를 모두 제외해보았다. 여는 괄호와 닫는 괄호의 수가 다르거나, 양 끝에 여는 괄호와 닫는 괄호가 적절히 오지 않거나,  전체 괄호 수가 홀수면 NO가 나오게 했다. 

- 1차 테스트 코드를 무난하게 통과하길래 잘한 건 줄 알았다. 근데 2차 테스트 (7~9)에서 막혀버렸다. 

- 이럴 수가. 이걸 다 뚫어내는 경우가 있다니. 

())(() 		// 테스트 코드 결과 NO가 나와야하는데, 내 코드는 이 경우를 YES로 처리한다. 
		//이거 보고 짜증이 솟구쳤다.

• 선생님께서 보여주신 풀이

package com.section03.stack;

import java.util.Stack;

public class Practice1 {
    public String solution(String input) {
        Stack<Character> stack = new Stack<>();
        for(char c : input.toCharArray()) {
            if(c == '(') {
                // 여는 괄호인 경우 stack에 push
                stack.push(c);
            } else {
                // 스택이 비어서 괄호를 꺼낼 수 없다면 여는 괄호가 부족해서 짝이 안 맞는 상황
                if(stack.isEmpty()) return "NO";
                // 닫는 괄호인 경우 stack에서 pop
                stack.pop();
            }
        }

        // 모든 문자에 대해서 처리 했는데 스택에 여는 괄호가 남아있다는 것은 닫는 괄호가 부족해서 짝이 안 맞는 상황
        if(!stack.isEmpty()) return "NO";

        return "YES";
    }

}

- 내가 생각한 방식이랑 전혀 달랐다. 난 스택이라는 자료구조를 전혀 이용하지 못한 반면, 이 해답은 스택을 잘 활용한 구조였다.

- 자료구조를 적절하게 이용하려면, 먼저 자료구조에 대한 기본 이해와 사용법을 익혀야 한다. 그 후 반복적인 문제 풀이를 통해 체화시켜야 할 거 같다. 매일 한 문제씩 풀어야겠다,,,!

 

2. 피보나치 수열에서 동적계획법을 사용하면 좋은 점 

• 기본재귀함수를 이용하여 피보나치 수열을 구현

/* 기본 재귀 함수 */
    public static int getFibonacci(int n) {
        if (n == 0) return 0;
        else if (n == 1) return 1;
        return getFibonacci(n - 1) + getFibonacci(n - 2);
    }

- 기본 재귀함수로 피보나치 수열의 10번째, 40번째 항을 구했더니 무려 1초가 넘게 걸렸다. 컴퓨터에게 1초는 억겁의 시간이 아니던가. 말도 안되는 효율이다.

• 동적계획법 - TopDown 방식으로 피보나치 수열을 구현

/*
     * DP - Top Down 방식
     * 메모이제이션 (Memoization) : 연산 결과를 메모리에 저장해 두었다가 동일한 연산을 반복할 때
     * 이전에 계산된 결과를 재활용하는 기법
     * */

     static int[] dp = new int[50];
     public static int getFibonacciDP(int n) {
         if (n==0) return 0;
         else if (n==1) return 1;

         // 1. 확인 : 함수 호출 전 해당 입력에 대한 결과가 이미 저장되었는지 확인
         if (dp[n] == 0) {

             // 2. 저장 : 계산되지 않은 값은 연산 후 특정 자료구조에 저장
             dp[n] = getFibonacciDP(n-1) + getFibonacciDP(n-2);
         }

         // 3. 재활용 : 저장된 결과가 있다면 다시 계산하지 않고 저장된 값을 반환
         return dp[n];
     }

• 동적계획법 - BottomUp 방식으로 피보나치 수열을 구현

/* DP - Bottom Up 방식
    * 타뷸레이션 (Tabulation) : 문제를 부분 문제로 나눈 뒤 작은 문제부터 차례로 그 결과를 테이블에 저장하는 방식
    * */
    static int getFibonacciNumberIter(int n) {
        int[] arr = new int[n + 1];
        arr[0] = 0;
        arr[1] = 1;

        if(n == 0) return arr[0];
        else if(n == 1) return arr[1];
        else {
            for (int i = 2; i <= n; i++) {
                arr[i] = arr[i - 1] + arr[i - 2];
            }
            return arr[n];
        }
    }

- 맨 처음 피보나치 수열을 구현하라고 하셨을 때 가장 먼저 생각한 방식이다. 가장 효율적인 거 같다. 

- 이렇게 동적계획법을 이용하면 중복계산을 피하고, 큰 문제를 작은 문제로 나눠서 해결할 수 있기 때문에 효율을 극대화할 수 있다는 장점이 있다. 

 

 

3. 유스케이스 - <extend>와 <include>

• 유스케이스 : 시스템이 사용자(액터)에게 제공하는 기능(행동)을 그림으로 나타낸 UML 다이어그램

- 포함관계(include)와 확장관계(extend)의 화살표 방향이 자꾸 헷갈렸다. 처음에는 집합과의 유사성을 떠올렸다. 이를테면 "게시글 등록을 하려면 카테고리 선택을 먼저 해야 한다"처럼 " 일종의 충분/필요조건 관계를 파악하려고 한 것이다. 근데 이런 논리로 접근하면 조금 헷갈리는 부분이 발생할 수 있다. 포함관계에서는 이 논리가 쉽게 적용될 수 있어도, 확장관계에서는 잘 들어맞지 않았다. 포함관계와 달리 확장관계는 '선택'이 가능한 관계이기 때문이다. 이런 경우는 "기본적으로는 이런 행동을 할 수 있는데, 부가적으로 이런 행동까지 가능해"라는 논리를 따르면 잘 들어맞았다. 따라서 포함관계에서는 충분/필요조건의 논리를, 확장관계에서는 기본행동과 부가적인 수단을 잘 구별할 필요가 있다.

---

Future

1. 이쯤에서 상기해보자. 플레이데이터에서 나의 목표는 "최대한 많은 것을 흡수하는 것"이다. 

2. 매일 한 문제씩 백준 문제를 푸는 습관을 가져봐야겠다. 쉽지는 않겠지만,,,ㅎㅎ

3. 다음 주는 야구보러 가기 때문에 공부 시간이 좀 적어진다. 할 일을 미리미리 해둬야겠다.