[Java] 변수와 타입 #2

목 차 타입 변수 상수 타입 자바에 있는 주요 타입은 String(문자열), Number(숫자), Boolean(논리) 이다. String(문자형): char: 단일 문자를 저장한다. ex) char letter = 'A' // 출력: A String: char은 단일 문자만 저장한다면, 보통 우리리는 문자열(문자들이 모인)을 사용한다. 문자가 한 개 이상인 값을 저장한다. ex) String name = "Daniel"; // 출력: Daniel ex) String letter = "B"; // 출력: B Number(숫자형): int: 정수를 저장한다. ex) int number = 13; // 출력: 13 long: int 보다 더 큰 범위의 정수를 저장한다. ex) long number = 214..

BE/Basic 2023.12.30

[Java] HelloWorld! #1

목 차 println("HelloWorld!") 해당 Java 정리글은 JavaScript 를 공부하여 이미 여러가지 선행 지식이 있으므로 중요한 것들만 정리하였다. println("HelloWorld!") public class HelloWorldApp { public static void main(String[] args) { System.out.println("HelloWorld!"); } } output

BE/Basic 2023.12.28

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

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

Algorithm/Sort 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/Concept 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/BackJun 2023.12.07

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

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

Algorithm/BackJun 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/Data Structure 2023.12.06

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

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

Algorithm/Sort 2023.11.29

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

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

Algorithm/Data Structure 2023.11.21

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

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

Algorithm/Concept 2023.11.14

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

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

Algorithm/Data Structure 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/BackJun 2023.10.21

[백준] 9095: 1, 2, 3 더하기 - JS (DP)

목 차 문제 접근 방식 풀이 문제 접근 방식 규칙을 먼저 찾아보자. 1의 경우: 1 2의 경우: 2 3의 경우: 4 4의 경우: 7 5의 경우: 13 6의 경우: 24 4의 경우를 살펴보면 앞에 3개를 더한 값이다. 5의 경우도 직전 3개를 더한 값이다. 만약 저 숫자들이 dp 배열에 있다고 한다면, dp[n] = dp[n-1] + dp[n-2] + dp[n-3]이 된다는 의미이다. 반복문의 조건식은 i

Algorithm/BackJun 2023.10.19

[백준] 1717: 집합의 표현 - JS (Union-Find)

목 차 문제 접근 방식 answer 배열이 필요하다! 풀이 문제 접근 방식 이 문제는 Union-Find / Disjoint-Set문제이다. 이 문제에서는 parent 배열과 rank 배열(최적화), 그리고 *answer 배열(JS만 필요한 듯)이 필요하다. answer 배열이 필요한 이유는 접근 방식 챕터의 가장 마지막에 작성하도록 하겠다. 랭크 시스템을 적용하지 않은 Union-Find 알고리즘은 구현하기 쉬운데 Find와 Union 함수를 구현하면 된다. Find: 숫자를 받아오고 계속 타고 올라간다. 올라가면서 num과 parent[num]이 같지 않다면 가장 조상의 인덱스 번호로 바꿔준다. function find(num){ if(num !== parent[num]){ parent[num] = ..

Algorithm/BackJun 2023.10.17

[자료구조] Union Find / Disjoint-Set 알고리즘 개념 및 최적화

목 차 Union-Find Algorithm 기본 개념 최적화 Union-Find Algorithm 기본적으로 Union-Find는 자료구조이다. 하지만 이 자료구조를 지원하는 Union과 Find는 알고리즘이다. 여러 노드가 서로 중복되지 않는 집합 여러 개로 나뉘어 있을 때, 각 집합을 대표하는 노드를 찾거나 두 집합을 합치는 연산을 하는 자료구조이다. 기본 개념 1. Union: 두 개의 원소가 포함된 집합을 하나로 합친다. 2. Find: 주어진 원소가 속한 집합의 대표 노드를 반환한다. 최적화 대표적인 최적화는 '경로압축' 인데, 바로 Find 연산을 수행할 때, 방문한 노드를 모두 그 집합의 대표 노드로 바꾸는 것이다. 여기에 'Rank' 시스템을 도입하면 시간 복잡도가 눈에 띄게 줄어드는데,..

Algorithm/Data Structure 2023.10.16

[백준] 1697: 숨바꼭질 - JS (그래프 탐색(DFS&BFS))

목 차 문제 접근 방식 풀이 문제 접근 방식 이번에는 BFS로 풀려고 한다. 구현 전에 설정한 조건은 다음과 같다. 방식: BFS (queue) 이동: -1, +1, *2 방문 체크: push 후 해당 요소를 1로 바꿈 범위: 100000 while문 조건: queue.length queue 에는 [item(이동), time]이 한 노드임 item과 K가 같다면 출력 후 반복문 종료 push 조건 - 1: item - 1 >= 0 && arr[item - 1] == 0 + 1: item + 1

Algorithm/BackJun 2023.10.12