[백준] 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

[자료구조] 펜윅 트리 (Fenwick Tree) - Binary Indexed Tree

목 차 펜윅 트리(Fenwick Tree) 펜윅 트리와 세그먼트 트리 펜윅 트리를 구현하며 배운 것들 구현 방법 펜윅 트리(Fenwick Tree) Binary Indexed Tree 라고도 불리는 펜윅트리는 수열의 특정 구간의 합을 빠르게 계산하고, 요소를 빠르게 변경 할 수 있는 자료구조 이다. 특징 시간 복잡도: update 와 sum 메서드 모두 O(log n)의 시간 복잡도를 가진다. 공간 복잡도: O(n) 만큼의 공간을 사용한다. 작동 원리 SUM 함수: 구간 합을 구하는 함수 UPDATE 함수: 특정 요소가 변경되면 그 요소에 영향을 받는 인덱스를 타고 올라가며 변경한다. 펜윅 트리와 세그먼트 트리 세그먼트 트리 펜윅 트리 구조 이진 트리 기반 배열 기반 시간 복잡도 업데이트 & 구간 합 모..

Algorithm 2023.12.06

[알고리즘] 위상 정렬 (Topology Sort)

목 차 위상정렬(Topological Sorting) 기본 개념 및 조건 위상정렬을 구현하며 배운 것들 구현 방법 위상정렬(Topological Sorting) 위상정렬은 방향이 있는 그래프에서 유효하다. 예를 들면, 여러 작업이 서로 의존 관계를 가질 때, 어떤 순서로 작업을 진행해야 하는지를 결정할 때 유용하다. 위상정렬은 결과가 매 번 다를 수 있다. 예를 들면, 4는 2의 앞에 있어야 하고, 3은 1의 앞에 있어야 한다고 가정할 때 예상되는 경우의 수는 4231, 4321, 4312 등 여러 개가 될 수 있다. 기본 개념 및 조건 방향성 그래프: 각 간선에 방향이 있는 그래프여야 한다. 단방향 그래프: 각 간선에 방향이 있되 양방향이지 않아야 한다. 위상정렬을 구현하며 배운 것들 최적화 전 더보기..

Algorithm 2023.11.29

[자료구조] 세그먼트 트리 (Segment Tree)

목 차 세그먼트 트리 개념 세그먼트 트리를 하며 배운 것들 세그먼트 트리 코드 세그먼트 트리 개념 세그먼트 트리는 구간 쿼리와 업데이트를 최적으로 수행할 수 있는 유연한 자료구조이다. 주로 구간 합, 또는 구간 내 최솟값이나 최댓값을 찾는 문제에 사용된다. 기본 구조 트리 구조: 세그먼트 트리는 이진 트리 구조이며, 각 노드는 배열의 특정 구간(Segment)을 대표한다. 리프 노드: 트리 구조에서 자식 노드가 없는 노드를 말한다. 즉 트리 가장 아래에 위치한 노드들을 말한다. 내부 노드: 자식 노드들의 값을 합치거나 비교하여 해당 구간의 값을 저장한 노드들을 말한다. 작동 원리 트리 초기화: 주어진 배열로 완전 이진 트리를 만든다. O(N) SUM함수: 구간합을 구하는 함수 O(log N) UPDATE..

Algorithm 2023.11.21

[알고리즘] 다익스트라(Dijkstra algorithm)와 우선순위 큐(MinHeap)

목 차 최소 힙 (MinHeap) 다익스트라 알고리즘 기본 개념 다익스트라 알고리즘 구현 최소 힙 (MinHeap) 다익스트라 알고리즘은 우선순위 큐(MinHeap)를 사용하는 것이 일반적이다. 최소 힙(MinHeap)의 정의 최소힙은 부모 노드가 자식 노드 보다 작거나 같은 값을 가지고 있는 이진 트리이다. 힙의 루트에는 트리에서 가장 작은 값이 위치한다. 최소 힙(MinHeap)의 연산 - 삽입: 새로운 요소를 힙의 마지막에 추가한 후, 부모 노드와 비교하며 위치를 조정하여 힙 속성을 만족시킨다. - 추출: 힙의 루트노드를 제거하고 마지막 노드를 루트로 이동시킨 다음, 자식들과 비교하며 위치를 조정하여 힙 속성을 만족시킨다. 여기서 추출할 때 JS 기준으로 shift() 메서드를 사용하면 앞에 노드를..

Algorithm 2023.11.14

[자료구조] 우선순위 큐(Priority Queue)

목 차 우선순위 큐 최소 힙 시간 복잡도 작동 원리 구현 코드 우선순위 큐 우선순위 큐(Priority Queue)는 말 그대로 우선순위를 가진 요소들을 저장하는 자료구조이다. 우선순위가 가장 높은 요소를 먼저 꺼낼 수 있게 한다. 대표적으로 최소 힙, 최대 힙이 있다. 최소 힙 다익스트라 알고리즘(Dijkstra Algorithm)을 학습하기 전에 우선순위 큐를 배우고 그중에서 최소 힙을 배우기에 이 번에는 최소 힙만 다룰 예정이다. 시간 복잡도 우선순위 큐를 구현하는 방법에는 여러 가지 있지만, 힙(Heap) 자료구조를 사용하는 것이 가장 효율적이고 우선순위가 가장 높은 데이터를 꺼내는데 O(log N) 만큼 걸린다. 작동 원리 1. 삽입(Insert): 새로운 요소는 항상 배열의 마지막에 들어간다(..

Algorithm 2023.10.26

[백준] 2579: 계단 오르기 - JS (DP)

목 차 문제 접근 방식 풀이 문제 각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오. 접근 방식 dp 배열에는 각 계단으로 갈 때 까지의 최대 점수를 저장한다. 예를 들어, 점수가 stairs = [10, 20, 15, 25, 10, 20]인 계단이 존재한다면 dp[1] = 10, dp[2] = 30, dp[3] = 35 ... ... 이렇게 저장하는 것이다. 규칙을 정리해 본다면, n번 째 계단으로 가는 방식은 두 가지 존재한다. dp[n-2] + stairs[n - 1] (두 계단을 오른 경우) dp[n-3] + stairs[n - 2] + stairs[n - 1] (두 계단을 오르고 한 계단을 올랐을 경우) 그리고 우리는 이 두 가지 ..

Algorithm 2023.10.21