[플레이데이터 풀스택 백엔드 9기] 5주차 - 자료구조/알고리즘

FerryLa·2025년 4월 20일

Java 회고(주간)

[플레이데이터 풀스택 백엔드 9기] 회고(주간)

목록 보기

4/25

서론

5주차 - (04/15 ~ 04/22)

자바 교육 과정을 마무리하고, 기초적이고 대표적인 알고리즘 문제풀이를 접하는 한 주였습니다.

일생활에서도 많은 일이 있었습니다. 그런 일들도 마무리되어 가는 과정이고,
체계화가 되고 있어 보다 빠른 학습이 가능할 것으로 보입니다.

1. 내용정리

[자료구조]

Tree

트리는 그래프의 일종이며, 계층적인 데이터 표현과 효율적인 검색이 가능 다만, 구현이 복잡
자식 노드를 최대 2개(Degree = 2) 이진트리라고 함
전위(Preorder) : A B D E C F G / 중위(Inorder) : D B E A F C G / 후위(Postorder): D E B F G C A
insert(x): 데이터 x를 트리에 추가
delete(x): 데이터 x를 트리에서 제거
search(x): 데이터 x를 트리에서 검색
traverse(): 트리를 순회하며 데이터를 처리
3가지 트리 순회 (각 위치에 대한 것만 바뀜)
TreeSet은 트리의 구조로 중복 없이 순서만 추가

Heap O(log n) / O(n)

최댓값 또는 최솟값을 빠르게 찾을 수 있음
완전 이진 트리, 빠르게 처리 가능하나 순차접근은 비효율적
우선순위 queue, 정렬, 스케줄링 등에 사용
보통 배열을 이용하여 힙을 구현 / 포인터를 이용한 구현 가능
insert(x): 데이터 x를 힙에 추가
extractMin(): 힙에서 최솟값을 제거하고 반환
extractMax(): 힙에서 최댓값을 제거하고 반환
peek(): 힙의 최솟값 또는 최댓값을 제거하지 않고 반환
heapify(): 배열을 힙 구조로 변환
isEmpty(): 힙이 비어 있는지 확인
size(): 힙의 현재 크기를 반환
clear(): 힙을 비움

Graph O(1)

복잡한 관계와 경로를 효율적으로 표현 가능
노드가 복잡하고 간선이 필요 / 간선 제거도 가능
무방향 그래프는 인접 행렬을 모두 사용하도록
addNode(x): 노드 x를 그래프에 추가
addEdge(x, y): 노드 x와 y를 연결하는 간선을 추가
removeNode(x): 노드 x를 그래프에서 제거
removeEdge(x, y): 노드 x와 y를 연결하는 간선을 제거
findPath(x, y): 노드 x에서 y까지의 경로를 찾음
traverse(): 그래프를 순회하며 데이터를 처리

가중치

길찾기 (최단거리)
양쪽에 다 쓸 수 있다. 이번엔 방향을 제시

[알고리즘]

정렬(Sort)

버블 정렬 평균 O(n2)

서로 인접한 두 원소를 검사하여 하나 씩 배열하는 방법
선택 정렬 평균 O(n2)
최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법
삽입 정렬 O(n2)
이미정렬된데이터범위에정렬되지않은데이터를적절한위치에삽입시켜정렬하는방법
인덱스보다 앞으로 인덱스를 탐색하면서 기존 값 보다 큰 경우 뒤로 하나씩 인덱스를 밀어냄
퀵정렬 평균 O(n log n)
(tip) 퀵정렬은 debugging을 해보기
low, high, pivot을 활용한 (pivot의 양 옆 while문)
pivot의 설정 방식에따라 퀵정렬의 성능이 달라짐
병합정렬 O(n log n)
분할 정복(Divide and Conquer) 방식으로 배열을 반씩 나누어 정렬한 후 병합(Merge)하는 방식

좌표배열 탐색(Search)

/* map에 그래프 정보 작성 */
        for(int i = 0; i < edge; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            map[a][b] = 1;
            // 무방향 그래프이므로 둘 다 1로 설정
            // map[a][b] = map[b][a] = 1;
        }

깊이 우선 탐색(DFS)

(LIFO) 후입 선출 구조의 stack을 활용 or 재귀호출 사용
한 방향으로 깊게 탐색 후 돌아와서 다른 경로 탐색
순서
1. stack.push(start) : start 노드부터 탐색 시작
2. visit[start] : 연결된 노드를 찾고 스택에 넣음 / 방문 배열에 기록
3. 더 이상 갈 수 없을 때까지 "깊이" 들어감
4. 막히면 스택에서 꺼내며 "되돌아감"
5. 전체 연결된 노드를 다 탐색할 때까지 반복

너비 우선 탐색(BFS)

(FIFO) 선입 선출 구조인 큐(Queue)를 활용해 탐색 시작
그래프의 경우 시작 위치(start)의 좌표(x, y)를 큐에 넣어 상하좌우 탐색 (빌 떄까지 반복)
가장 가까운 노드부터 차례대로 탐색 (최단 거리 기준)
목표 노드에 도착하는 경로가 여러 개일 때 최단 경로 보장
방문한 노드는 visited 배열 또는 그래프 자체에서 표시
ex) 미로 탐색(최단 경로), 토마토 문제 등

[1][1]         [1][2]         [1][3]
              ↑(0,-1)↑
         
[2][1] ←(-1,0) [2][2] →(1,0)→ [2][3]
         
               ↓(0,1)↓
[3][1]         [3][2]         [3][3]

그리디 (greedy)

선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 것 (탐욕적 선택)

제한적 의미가 있는 문제들을 가지고 사용하는 것
선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택
적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사
해답 검사(Solution Check) : 원래의 문제가 해결되었는지 검사, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복
ex) 동전 거스름돈, 회의실 배정

JUnit (테스트코드)

프레임워크(JUnit)에 의해 자동 실행되는 내부 코드이기에 public을 쓸필요 없다
메소드명을 한글로 써도 사용할 수 있다.
문자, 숫자, 날짜도 테스트가 가능하다.

어노테이션 정리

- @BeforeAll  // 모든 테스트 전에 딱 1번 실행되는 메서드 지정
- @BeforeEach // 각 테스트 전에 실행
- @AfterEach  // 각 테스트 후 실행
- @Test // 테스트 코드 실행
- @DisplayName("") // 테스트 이름
- @Timeout // test 실행시간 제한 테스트
- @ParameterizedTest // 여러 입력값으로 테스트 반복 실행
- @MethodSource("") // 테스트 데이터 제공

다익스트라 알고리즘

가중치와 최단거리 : 가는 거리의 가중치의 값을 다 더했을 때 가장 적은 값을 고름
모든 정점과의 최단 거리 : 음의 가중치가 없음

최소 신장 트리 - 크루스칼알고리즘

가중치의 합이 최소
가중치 오름착순 정렬
Union시 parant 배열

동적 계획법 (Dynamic Programming)

복잡한 문제를 여러 개의 간단한 문제로 분리하여 문제들을 해결하는 방법 (큰 문제를 작은 문제로 나눔)

작은 문제들이 반복돼 나타내 작은 문제들의 결과값은 항상 같음

점화식

수열의 합 사이에 성립하는 관계식 (대표적인 예)
피보나치 : f(n) = f(n-1) + (n-2)
봉지 3, 5kg 최소 패턴을 공식화 : f(n) = f(n-3) or f(n-5) + 1
그외 펙토리얼, 동전 교환, 평범한 배낭, 계단 오르기 등

// 기본 재귀 함수 - 피보나치 수열
public static int getFibonacciNumber(int n) {
        if(n == 0) return 0;
        else if(n == 1) return 1;
        return getFibonacciNumber(n - 1) + getFibonacciNumber(n - 2);
}

메모이제이션(memoization)

재귀 함수 호출 중 메모리에 저장해서 되돌아감
Top Down 방식으로 결과가 필요해질 때 계산해두는 방식

// 메모이제이션 dp에 저장
dp[n] = getFibonacciNumberDP(n - 1) + getFibonacciNumberDP(n - 2);

// '계단 연속 오르기' 문제에서 2, 3칸 중복 불가
for(int i = 3; i <= n; i++) {
    dp[i] = Math.max(dp[i-3] + arr[i-1], dp[i-2]) + arr[i];
}

타뷸레이션(Tabulation)

Bottom Up 방식으로 필요하지 않은 값도 미리 계산해두는 방식
반복문으로 점점 쌓아 올림

[설계]

요구사항(개인역량)

애자일 스프린트 : 문서화 변화에 유연하게 대응하고, 짧은 개발 사이클을 통해 점진적으로 제품 개선
주의사항

팀원 역량 파악이 첫 번째
적어도 업무의 스토리 앞,뒤 정도는 알아야 함
변동사항이 있으면 즉시 전파
팀원과의 소통으로 효율성 극대화
회고를 통해 개선 점검
(노션 등) 협업 툴로 업무를 명확히 나누고 공유

유스케이스 다이어그램

유스케이스는 실제로 현실에서 발생하는 기능 (사용자가 눈에 보이는 하나의 기능 단위)

텍스트를 Actor와 기능을 통하여 관계를 나타냄
윔지컬 주소 : https://whimsical.com/1-5JC6DftJCXCk6VF24soxNz
ex) whimsical, figma

[JDBC]

관계형 데이터 베이스(java와 mysql 연결하기)

DriverManager Class

데이터 원본에 JDBC driver를 통하여 Connection을 만드는 역할 / Driver는 인터페이스 역할

build grandle에 mysql Driver 추가
implementation 'mysql:mysql-connector-java:8.0.33'
Class.forName() : 사용할 Driver 등록 (ClassNotFoundException 예외처리 반드시)
getConnection() : Connection 객체를 반환하며, 이 객체를 통해 DBMS에 연결
url : 연결할 Database의 주소
user : Database에 접속할 user 이름
password : Database 접속을 위한 비밀번호
Statement
createStatement(); // 쿼리문 생성
executeQuery() : 이 메소드는 조회를 하기위한 쿼리를 실행하기위해서 사용
close() : Connection, Statement, ResultSet 모두 close()를 통해 자원을 반납해야 함

PreparedStatement

위치홀더(placeholder) 개념에 해당되는 인수가 많아 특정 값만 바꾸어 여러 번 실행하는 상황에 유용하다.

SQL 문을 ?로 템플릿화하여 미리 컴파일하고, 그 컴파일 결과(실행 계획)를 DB가 캐시에 저장하여 반복 실행 시 빠르게 처리
SQL injection 공격에 대하여 안전
setString() : 메소드로 위치홀더의 순서와 넣어 줄 변수 값을 세팅
executeQuery() : 메소드를 호출하여 SQL문 수행

ResultSet

SELECT문 수행 성공 시 반환한 결과값을 받아오는 객체

getString() : 현재 커서 위치에 존재하는 로우에서 인자로 전달하는 컬럼의 결과 값 반환
next() : 커서 위치를 하나 내리면서 다음 행이 존재하면 true, 존재하지 않으면 false 반환

JDBC Configuration Properties 파일 작성

driver=com.mysql.cj.jdbc.Driver
url=jdbc:mysql://localhost/employee
user=ohgiraffers
password=ohgiraffers

DriverManager Class (추가)
JDBCTemplate에서 효율적인 트랜잭션, close 처리 (자동설정 가능)

PreparedStatement (추가)
[취약코드]
String query = "SELECT * FROM employee WHERE emp_id = '" + empId + "' AND EMP_NAME = '" + empName + "'";

SQL 인젝션(SQL Injection)에 취약한 코드 - 보안상 PreparedStatement 사용
입력값이 문자열로 감싸져 그대로 처리되며 SQL 구문에 영향을 주지 않음
Statement타입이기도 함 / 상속구조이기 때문이고, 그래서 다형성을 적용할 수 있다.
그래서, close는 기존 Statement의 객체를 가져다 쓸 수 있다.

MVC2 (model, view, controller)

각 계층마다 해야할 역할과 책임
view : 사용자가 보는 화면, 기능의 결과에 따라 보여질 페이지
controller : 사용자가 전달한 값을 정제해야할 경우가 있으면 처리, 적절한 service계층으로 전달, 결과 에 따른 페이지 이동
service : 연결 객체를 생성, 비지니스로직, 트랜잭션 처리
repository : 비지니스 로직에 따라 insert(생성), select, insert / DB와 연결하고 결과값을 잘 리턴

[모델링]

복잡한 현실 세계를 단순화하고 목적에 부합하며 정확한 내용으로 표현하기 위함 (단순화, 추상화, 명확화)
데이터 관점 모델링 : 데이터 중심, 실제 속성과 데이터, 데이터 간의 관계에 대한 모델링 (예: ERD 산출)
프로세스 모델링 : 업무 처리 중심으로 순서와 조건으로 실행되는지 표현
상관 모델링 : 프로세스와 데이터 사이의 상호작용 중심

무결성

무결성 데이터 값이 정확한 상태를 의미(완전하고 정확해야함)
엔티티 무결성(Entity Integrity) : 모든 인스턴스는 고유해야 하며 인스턴스를 대표하는 속성에는 널 값을 가지면 안됨 (같은 데이터를 두 번 저장하지 않음)
참조 무결성 : 엔티티의 왜래 식별자 속성은 참조하는 인티티의 주 식별자 값에 포함되거나 널이어야 함
도메인 무결성(Domain Integrity) : 특정 속성 값은 같은 데이터 타입, 길이, 널 여부, 중복 값 허용 (NOT NULL, CHECK, 데이터 타입 등을 통해 구현됨)
업무 무결성(Business Integrity) : 기업에서 업무를 수행하는 방법이나 데이터를 처리하는 규칙

2. 문제 풀이

[문제풀이]

계단 오르기 문제

풀이
1. 수열 문제라는 것을 파악하고 점화식을 뽑아내는게 관건
2. 빠른 처리를 위해 Scanner 대신 BufferedReader를 사용
3. 두 가지 경우의 점화식 중 최대값을 뽑아내기 위해 Math.max를 활용

'연속 3계단 금지'라는 조건을 만족하기 위해 두 가지 점화식을 뽑아냄

가능 상황 1. 직전 계단에서 올라오는 상황
i-3 -> i-1 -> i 로 이동해야만 한다.
가능 상황 2. 두 계단 전에 올라오는 상황 -> i-2 전의 상황을 고려할 필요
1번 : dp[i-3] + arr[i-1]
2번 : dp[i-2] + arr[i]

[풀이 코드]

    public static int solution(String input) throws IOException {
        
        BufferedReader br = new BufferedReader(new StringReader(input));
        int n = Integer.parseInt(br.readLine());    // 계단의 개수
        int[] arr = new int[n + 1];                 // 계단별 점수
        int[] dp = new int[n + 1];                  // 최적(최대 점수 합계)의 값 누적
        
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        // 초기값 설정
        dp[1] = arr[1];
        if(n >= 2) dp[2] = dp[1] + arr[2];

        // 점화식은 3번 계단부터 적용
        for(int i = 3; i <= n; i++) {
            dp[i] = Math.max(dp[i-3] + arr[i-1], dp[i-2]) + arr[i];
        }
        return dp[n];
    }
}

위 문제풀이는 아직 익숙치 않은 예외처리도 필요한 상황이였습니다.

강사님께서 함께 풀어주신 문제, 막막한 문제였는데 이렇게 간단하게 코드로 풀어낼 수 있다는 것을 알았습니다.
당장은 이런 문제를 풀어내지 못하지만, 기억에 깊이 남는 문제였습니다.

3. 마무리

> 좋았거나 내가 잘한 점

전체적으로 체계화가 되고 있습니다.
복습하며 마무리하는 것에 익숙해졌습니다.

> 아쉬웠던 점

지난 몇 주간 욕심이 과했던 것 같습니다. 조급함도 많았고, 일생활에서 신경 쓰일 일이 많았던 것 같습니다.
인간 관계에 너무 신경쓴 점도 큰 문제였던 것 같습니다.
대신 적응기가 지나 이제부터는 문제점을 보다 명확히 짚는 과정이 될 거 같습니다.

> 개선할 점

조금 더 길게 보고 조금함을 덜어내도록 할 예정입니다.
수업시간 이해하는 것에 어려움이 있어 선행 학습이 부족한 것 같습니다.

> 다음주 계획

공부에 집중할 수 있게 수면조절, TASK관리, 운동에 신경 쓸 예정입니다.
프로젝트 관련 기획 / 유스케이스, 모델링, DDD 분석, 피그마 등의 활동이 있을 예정입니다.

04/21 : 4지 선다 개념 시험
04/23 : PCCE 코딩테스트
04/23 ~ 24 : 프로젝트 (수요일, 목요일)
05/31 : SQLD 자격증 시험

코딩테스트와 프로젝트로 객관적인 평가를 받을 예정입니다.

FerryLa

김지환

이전 포스트

[플레이데이터 풀스택 백엔드 9기] 4주차 - List

다음 포스트