Daniel: The Dev Story
Daniel: The Dev Story
    • 홈
  • 분류 전체보기
    • 프로젝트
    • Spring
    • NodeJS
    • Basics
    • Git
    • DB
    • Algorithm
    • Error
    • Private
      • Private
      • Database
      • Tip
  • 글쓰기
  • 관리자
  • myoskin

      [백준] 9465: 스티커 - Java (DP)

      목 차 문제 접근 방식 풀이 문제 접근 방식 이 문제는 '현재 아이템을 선택할 경우와, 하지 않을 경우를 생각해서 최댓값을 할당해라' 이다. bottom-up, top-down 방식으로 볼 수 있는데, 이번 문제는 top-down 으로 보는 것이 이해하기 쉽다. 각 아이템이 선택될 경우 그 전 아이템을 비교하는 것이다. 무슨 말이냐면 40을 선택하기 전 아이템을 생각해 보면 70에서 넘어오거나, 10에서 넘어오는 것, 둘 중 하나이다. 근데 우리는 dp 배열에 원본 데이터가 아닌 더한 값을 저장하니 실질적으로는 3번 인덱스의 100과 10이 더해진 110과 비교를 하게 될 것이다. 우리는 쉽게 그냥 큰 값을 dp[i][j]에 더하면 되는 것이다. 그리고 이렇게 하는 것이 이해하기 어렵게 말하자면 해당 인..

      Algorithm 2024.01.21

      [백준] 1003: 피보나치 함수 - Java (DP)

      목 차 문제 접근 방식 풀이 문제 접근 방식 이 문제의 요점은 점화식이 아니라 dp의 특성을 활용하는 것이다. Input int[] testCase = new int[N]; 으로 입력으로 들어오는 케이스들을 모두 배열에 담았다. Solution int[][] dp = new int[41][2]; 0

      Algorithm 2024.01.16

      [백준] 1912: 연속합 - Java (DP)

      목 차 문제 접근 방식 풀이 문제 접근 방식 이 문제를 처음 마주하게 되었을 때는 투 포인터 방식으로 풀면 되는 거 아닌가? 왜 DP 문제인 거야? 라고 생각했다. 근데 질문 게시판에서 라는 글이 올라와 있었다. 그래서 DP 문제라는 확신을 가지고 DP 의 개념으로 문제를 보았다. 만약 dp[i - 1], 즉 이전 값이 0보다 작다면 그냥 자기 자신을 dp[i] 번째에 넣으면 된다는 것을 깨닳았다. 그리고 max 값을 저장하는 변수와 비교해서 더 큰 값을 변수에 저장하면 되는 것이었다. 왜냐하면 양의 정수 하나만 존재한다면 마이너스들은 볼 필요도 없을 테니까. 그리고 dp[i - 1] 이 0 보다 큰 양의 정수라면, dp[i - 1] 과 자신을 더한 값을 dp[i] 에 저장하고 max 값과 비교한다. 풀..

      Algorithm 2024.01.15

      [백준] 11727: 2 * n 타일링2 - Java (DP)

      목 차 문제 접근 방식 풀이 문제 접근 방식 DP 문제를 다루는 글에서 항상 언급하지만, 먼저 노가다로 n = 1, 2, 3, 4, 5 정도 까지 그려보거나 계산하고 거기서 점화식을 추출하는 방식으로 한다. 특히 이렇게 점화식을 가져올 수 있는 문제에서는 말이다. 여기서는 어떤 점화식이 있을까? 그래서 그려보았다. n = 4 까지만 그려보았다. 그림에는 없지만 n = 5 일 때는 21 개 이다. 나는 이 챕터에서 내가 점화식을 추출하게 된 과정을 써보려 한다. n = 1: 1 n = 2: 3 n = 3: 5 n = 4: 11 n = 5: 21 이제 n = 5 일 때를 가정하여 어떻게 하면 21이 나올 수 있을까 생각해 본다. n 을 처음부터 다 더해보기도 하고 두 개만 더해보기도 하고.. 근데 보니까 n..

      Algorithm 2024.01.14

      [백준] 2606: 바이러스 - Java (그래프 이론)

      목 차 문제 접근 방식 이 문제를 구현하며 알게된 것들 풀이 문제 접근 방식 BFS Lover 인 나는 이 문제를 보았을 때 바로 BFS가 적합하다고 느꼈다. BFS 방식이 언제나 그렇듯 하나씩 하나씩 근접한 값들을 큐에 넣어 돌리면 된다. 이 문제에서 주의할 점만 알면 30분 내로 풀 수 있는 문제인 것 같다. 그 주의할 점은 바로.. 입력 값 한 쌍이 들어왔을 때, 한 쪽에만 값을 저장하는 행위이다. 예를 들면, 4 3 1 2 2 4 3 2 여기서 앞 쪽 숫자를 a 변수에, 뒤 쪽 숫자를 b 변수에 할당한다고 가정해 보자. 만약 graph[a].add(b); 만 하게된다면, 1, 2, 4는 연결이 되고, 3또한 연결이 되어있지만 출력 값에서는 낙오되는 현상을 볼 수 있다. 이 문제를 구현하며 알게된 ..

      Algorithm 2024.01.11

      [백준] 2178: 미로 탐색 - Java (그래프 이론)

      목 차문제접근 방식이 문제를 구현하며 알게된 것풀이 문제 접근 방식 이번에는 BFS 알고리즘으로 해당 문제를 해결하려고 한다. BFS는 가장 먼저 도착하는 것을 반환하면 되기 때문에 생각보다 간단하다. 자바에는 컬렉션에 Queue 자료구조가 있어 그 것을 활용하면 된다. 나는 배열 형태의 Queue 자료구조를 만들기로 했다. 근데 javascript 와는 달리 Java 의 배열은 정적 배열이기에 Javascript 의 .push 같은 배열 메서드가 제공되지 않는다. (자료구조 Queue 사용해도됨) 그래서 원형 큐(Circular Queue)를 알게되었고, 대안으로 선택하게 되었다. 원형 큐는 다음 소제목 '이 문제를 구현하며 알게된 것' 에서 언급하겠다. 이 문제는 weight 값만 추가하여 [N][M..

      Algorithm 2024.01.11

      [백준] 1932: 정수 삼각형 - Java (DP)

      목 차 문제 접근 방식 풀이 문제 접근 방식 정수 삼각형의 그림은 삼각형의 형태를 하고 있지만, 보면 n 번 째 줄에는 n 개의 정수가 있는 것을 알 수 있다. 코드의 형태로 나타내면 다음과 같다. arr = [ [1], [2, 3], [4, 5, 6], [7, 8, 9, 10], [11, 12, 13, 14, 15] ] DP를 이용해 더한 값을 dp 배열에 추가하는 방식으로 할 예정이다. 먼저 값이 들어가있지 않은 dp 배열을 똑같이 준비해 준다. 그리고 그림을 그려보면 다음 두 식을 산출해 낼 수 있다. dp[n][j] = dp[n - 1][j] + arr[n][j]; dp[n][j + 1] = dp[n - 1][j] + arr[n][j + 1]; 근데 계산을 하는데 곂치는 부분이 있다. 바로 두번째..

      Algorithm 2024.01.11

      [백준] 11726: 2 * n 타일링 - Java (DP)

      목 차 문제 접근 방식 풀이 문제 접근 방식 해당 문제는 피보나치 수열 DP 문제와 비슷하다. 모든 DP 문제가 그렇듯 n = 1일 때, 2일 때, 3일 때 ... ... 를 구해보면 패턴이 보인다. 그리고 그 패턴에서 나는 다음과 같은 점화식을 세웠다. dp[i] = dp[i - 2] + dp[i - 1] 풀이 package src.dp; import java.io.BufferedReader; import java.io.InputStreamReader; public class Tiling { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(..

      Algorithm 2024.01.07

      [백준] 2775: 부녀회장이 될테야 - Java (DP)

      목 차 문제 접근 방식 풀이 문제 접근 방식 먼저 기본값인 [0] 층의 1~14호 까지를 입력한다. 그리고 [1] 층의 1~14호 까지 입력한다. 그리고 더욱 정확한 비교를 위해서 [2]층의 일부분 호수를 입력한다. 처음 숫자는 모두 1로 동일하다. 생각해 보면 [k][n - 1]은 이미 구했던 [k - 1][1] 부터 [k - 1][n - 1] 까지의 합이다. 그럼 여기에 아래층의 같은 호수만 더하면 현재 호수가 된다. 말이 좀 복잡한데 그림으로 알아보자. 먼저 표를 확인 훑고 아래 이미지를 확인해 보자. k 층의 n 호 dp[k][n] [0][n] = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 [1][n] = 1, 3, 6, 10, 15, 21, 28, 36, ..

      Algorithm 2024.01.07

      [백준] 2839: 설탕 배달 - Java (DP)

      목 차 문제 접근 방식 풀이 문제 접근 방식 사실 DP 문제는 점화식만 잘 짜면 그 뒤로는 쉽다. 그래서 나는 DP 문제를 마주하면 먼저 나 혼자 계산해 본다. n = x 일 때 => 봉지 개수 n = 3 ⇒ 1 n = 4 ⇒ -1; n = 5 ⇒ 1 n = 6 ⇒ 2 n = 7 ⇒ -1; n = 8 ⇒ 2 n = 9 ⇒ 3 n = 10 ⇒ 2 n = 11 ⇒ 3 n = 12 ⇒ 4 n = 13 ⇒ 3 n = 14 ⇒ 4 n = 15 ⇒ 3 n = 16 ⇒ 4 n = 17 ⇒ 5 n = 18 ⇒ 4 n = 19 ⇒ 5 n = 20 ⇒ 4 n = 21 ⇒ 5 ... ... 먼저 보면 n 에서는 3과 5만 더할 수 있다. 그 말은 즉, dp[n] 은 n - 5 혹은 n - 3 에서 하나를 더한 값이 된다는 ..

      Algorithm 2024.01.07

      [백준] 10844: 쉬운 계단 수 - Java (DP)

      목 차 문제 접근 방식 풀이 문제 접근 방식 나는 먼저 N=1, 2, 3, 4일 때를 가정해서 손으로 직접 작성해 보았다. [숫자] 는 해당 숫자로 끝나는 수를 말한다. 각 n 마다 0~3만 해보아도 알 수 있다. 핵심 n = 3일 때를 가정해 보자. 0과 9를 제외하면 모두 n - 1 에서 그 전 숫자와 그 다음 숫자의 합이라는 것을 알 수 있다. 말로 하면 어려운데 n = 3이고 2로 끝나는 수를 보자. 212, 232, 432 이렇게 3개 이다. 이제 다시 n - 1(= 2)이고, 1로 끝나는 수와 3으로 끝나는 수를 보자. 21, 23, 43 이렇게 3개 이다. 다시 돌아가 n = 3, 2로 끝나는 수를 보면 지금 이 숫자들에 2를 붙인 수들이다. 그럼이제 점화식을 세울 수 있게된다. 1~8로 끝..

      Algorithm 2024.01.07

      [백준] 1708: 볼록 껍질(Convex Hull) - JS (기하학적 알고리즘)

      목 차 문제 접근 방식 이 문제를 풀며 느낀점 문제 해결 풀이 문제 접근 방식 볼록 껍질(Convex Hull) 알고리즘을 풀기 위한 접근방법은 다양하지만, 나는 그라함 스캔 알고리즘(Graham's Scan Algorithm)을 사용하여 문제를 해결하였다. 그라함 스캔(Graham's Scan) 기준점: y가 가장 작은 점, y가 가장 작은 점이 여러 개일 경우 x가 가장 작은 점을 기준점으로 정한다. 정렬: 점들을 반시계 방향으로 정렬한다. 쉽게 말해서 각도(혹은 기울기)를 기준으로 정렬을 한다. 정렬을 하게 되면 위와 같이 정렬이 될 것이다. 첫 번째 점과 두 번째 점을 스택(Stack)에 넣어준 채로 시작한다.(1번 점과 2번 점이 연결된 상태) 그리고 그다음 점이 반시계 방향인지 시계방향인지를 ..

      Algorithm 2024.01.04

      [알고리즘] 퀵 정렬 (Quick Sort)

      목 차 퀵 정렬(Quick Sort) 기본 개념 퀵 정렬을 구현하며 배운 것들 구현 방법 퀵 정렬(Quick Sort) 기본 개념 퀵 정렬은 분할 정복 전략(Divide and Conquer)을 사용한다. 평균 O(n log n)의 시간 복잡도를 가지고, 최악의 경우(정렬된 배열) O(n^2)의 시간 복잡도를 가진다. pivot 을 먼저 선택하고 그 pivot을 기준으로 더 큰 값과 더 작은 값을 분류한다. 이 것을 '파티셔닝'이라고 하며, 재귀적으로 정렬을 한다. pivot 의 중요성 퀵 정렬에서 pivot 은 시간 복잡도에 큰 영향을 끼친다. 일반적으로 첫 번째 인덱스, 중간 인덱스, 마지막 인덱스를 pivot 으로 설정한다. 퀵 정렬을 구현하며 배운 것들 내가 알고 있던 개념들을 사용하였기에 기술적..

      Algorithm 2023.12.26

      [알고리즘] CounterClockWise(CCW)

      목 차CCW 개요CCW의 기본 원리BOJ - CCW 알고리즘 문제 풀이CCW를 활용한 알고리즘 문제 CCW 개요 CCW 알고리즘은 주어진 점들이 시계 반대 방향으로 정렬이 되어 있는지를 판단하는 알고리즘이다. 이 방법은 기하학적 알고리즘에서 중요한 역할을 하는데, 예를 들면, A, B, C가 순서대로 주어졌을 때 선분AB에 대해서 C가 시계 반대 방향에 위치해 있는지, 시계 방향인지, 아니면 같은 선상에 있는지를 판별하는 방법이다. CCW의 기본 원리 벡터의 외적을 사용해서 외적의 결과가 양수일 경우는 반시계, 음수일 경우 시계 방향에 있다는 의미이다. 외적 공식은 다음과 같다. BOJ - CCW 알고리즘 문제 풀이: 11758 CCW는 공식만 알면 굉장히 쉽기 때문에 CCW 자체는 어렵지 않다. let..

      Algorithm 2023.12.14

      [백준] 2042: 구간 합 구하기 - JS (펜윅트리(BIT))

      목 차 문제 접근 방식 풀이 문제 접근 방식 펜윅 트리는 구간 합을 구하는 것에 특화되어 있는 자료구조 이다. 펜윅 트리를 구성하는 메서드는 update 와 sum 메서드 이다. update // x: 업데이트 하는 인덱스, diff: 원래 값과 바뀐 값의 차이 인자: x, diff 조건: x 0 동작: 인자로 들어온 x 에서 x & -x 를 빼주고 반복하면 1 부터 x 까지의 합을 구할 수 있다. 구간 합은 sum(b) - sum(a - 1) 을 해주면 구할 수 있다. 세그먼트 트리 보다는 구현이 쉬웠는데 범용성이 아쉽다. 구간 합 문제에서 편하게 사용할 수 있을 것 같다. 펜윅 트리를 구현하며 배운 것들 펜윅 트리를 위한 글에서 캡쳐하였다. 풀이 class FenwickTree { // N: 요소 개..

      Algorithm 2023.12.07

      [백준] 2042: 구간 합 구하기 - JS (세그먼트 트리)

      목 차 문제 접근 방식 풀이 문제 접근 방식 세그먼트 트리를 구성하는 3가지 메서드는 initTree, update, sum 메서드이다. initTree 메서드: for문을 사용해서 구현했다. 아직 재귀를 사용하기보다는 for 반복문이 더 편하기 때문이다. 트리를 처음에 초기화 하는 메서드이다. 원본 배열을 가져와서 마지막 레벨 트리에 붙여 넣고, 그리고 하나씩 내려가며 자식들을 더한 값을 저장한다. update 메서드: 변경 된 리프노드를 시작으로 부모를 타고 올라가며 전체적인 트리를 업데이트한다. 세그먼트 트리에서 가장 간단하게 구현할 수 있는 메서드라고 생각한다. sum 메서드: 구간 합을 구하는 메서드이다. 재귀를 이용해서 구현한다. sum 메서드를 구현할 때 참고하면 좋은 3가지가 있다. 구해야..

      Algorithm 2023.12.07

    12345···8
    Daniel: The Dev Story

    찾기

    공지

    최근 글

    인기글

    최근 댓글

    캘린더

      7 / 2025
      일 월 화 수 목 금 토
      1 2 3 4 5
      6 7 8 9 10 11 12
      13 14 15 16 17 18 19
      20 21 22 23 24 25 26
      27 28 29 30 31

    글 보관함

    태그

      알고리즘자바AlgorithmBOJ타입스크립트git백준MYSQL코딩java

    즐겨찾기

    방문자 수

    • Today
    • Yesterday
    • Total
    myoskin

    티스토리툴바

    단축키

    내 블로그

    내 블로그 - 관리자 홈 전환
    Q
    Q
    새 글 쓰기
    W
    W

    블로그 게시글

    글 수정 (권한 있는 경우)
    E
    E
    댓글 영역으로 이동
    C
    C

    모든 영역

    이 페이지의 URL 복사
    S
    S
    맨 위로 이동
    T
    T
    티스토리 홈 이동
    H
    H
    단축키 안내
    Shift + /
    ⇧ + /

    * 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.