본문 바로가기

Develop/Algorithm29

DP - LIS, 냅색 알고리즘 LIS (Longest Increasing Subsequence) 주어진 수열에서 가장 긴 증가하는 부분 수열을 찾는 알고리즘이다. 부분 수열은 원래 수열의 순서를 유지하되, 연속하지 않은 원소들로 이루어진 수열을 말한다. public static int solution() { Collections.sort(bricks); dy[0] = bricks.get(0).height; int answer = dy[0]; for (int i = 1; i = 0; j--) { if (bricks.get(i).weight max) { max = dy[j]; .. 2023. 8. 3.
Java) 이진탐색트리 구현 package org.example; import java.util.ArrayList; public class Tree { // 트리를 구성하는 노드 클래스입니다. public static class Node { private int data; private Node left; private Node right; // 생성자 public Node(int data) { this.setData(data); setLeft(null); setRight(null); } public int getData() { return data; } public Node getLeft() { return left; } public Node getRight() { return right; } public void setData(.. 2023. 7. 28.
연결된 그룹 개수 찾기(DFS) 1. 각 노드의 방문 여부를 체크할 배열 생성 2. 각 노드에 연결된 노드를 추가할 배열 리스트를 추가 3. 각 노드에 연결된 노드들을 찾아 각 노드의 배열 리스트에 추가 4. 방문하지 않은 노드일 경우, dfs 진행 및 count 1 증가 dfs - 1. 방문할 노드인 경우 즉시 탈출, - 2. 해당 노드를 방문한 걸로 바꾸기 - 3. 연결된 노드들을 순회하면서 방문하지 않은 노드가 있다면, dfs 진행 class Solution { static List graph = new ArrayList(); static boolean[] visited; public int solution(int n, int[][] computers) { // 1 visited = new boolean[n]; // 2 for (.. 2023. 4. 25.
너비 우선 탐색(BFS) vs 깊이 우선 탐색(DFS) 일단, 둘을 다음 그림을 통해 이해해보자. 너비 우선 탐색(BFS) 특징 depth는 0이 아닌 1부터 시작 노드 수가 적고 깊이가 얕은, 검색 대상의 규모가 작은 경우, 유리하다. 큐 이용 장점 답이 되는 경로가 여러 개인 경우에, 최단 경로를 보장한다. 최단 경로가 존재하면, 어느 한 경로가 무한히 깊어진다 하더라도, 최단 경로를 반드시 찾을 수 있다. 단점 DFS에 비해 저장 공간의 필요성이 크다. DFS와는 달리 큐를 이용해서 다음에 탐색할 노드를 저장하므로, 노드의 수가 많을수록 필요 없는 노드들까지 저장해야 하기 때문이다. 최악의 경우에는 모든 경로를 다 살펴봐야 한다. 깊이 우선 탐색(DFS) 특징 depth는 0이 아닌 1부터 시작 검색 대상의 규모가 클 경우, 유리하다. 재귀, 스택 이용.. 2023. 4. 25.
우선순위 큐(Priority Queue)를 공부하면서 Queue는 먼저 선입선출(FIFO)이라는 특징을 가지는 구조이다. (Stack은 후입선출 - LIFO) 그럼 우선순위 큐는? 우선순위 큐는 말 그대로 우선순위가 높은 데이터를 먼저 뽑아내는 구조를 말한다. 그럼 여기서 의아할 게 어떤 기준을 가지고 우선순위를 정하는 걸까 싶은데, 단순히 요소의 크기를 우선순위를 잡고 오름차순, 내림차순 정렬을 할 수 있고, 우선순위 큐의 타입을 배열로 지정한다면, 특정 요소의 크기순으로 우선순위 기준을 잡을 수도 있다. Queue pq = new PriorityQueue(Comparator.comparingInt(o -> o[1])); (pq라는 우선순위 큐에는 int타입의 1차원 배열이 들어가게 되고, 배열의 1번째 인덱스의 값을 기준으로 정렬이 된다) Java에서 .. 2023. 3. 6.
2개 리스트의 교집합, 합집합, 차집합 구하기 교집합 retainAll() 메서드로 두 리스트의 교집합 구하기 import java.util.Set; import java.util.HashSet; import java.util.Arrays; import java.util.List; import java.util.ArrayList; public class Test { public static void main(String[] args) { Set str1Set = new HashSet(Arrays.asList("ab", "bc", "cd", "ef", "fg")); Set str2Set = new HashSet(Arrays.asList("cd", "ef", "fg", "gh", "hi")); Set intersection = new HashSet(st.. 2023. 2. 17.
LRU(Least Recently Used) Cache 교체 알고리즘 Programmers Lv.2 - [1차] 캐시 캐시(Cache)는 연산에 필요한 데이터들을 미리 저장하는 임시 메모리이다. 연산을 처리할 때, CPU에서 주기억장치, 보조기억장치까지 도달해서 연산을 처리한다. 이는 물리적으로 거리가 멀어서 비용이 많이 든다. 캐시의 경우는 CPU 바로 옆에 붙어있기 때문에, 물리적으로 거리가 가까워 비용이 적다. 그렇기 때문에, 연산에 자주 사용되는 값이나 데이터들을 캐시에 미리 적재해놓으면 접근 시간을 줄여 성능을 높일 수 있다. 캐시 히트(Hit)율, 캐시 미스(Miss)율이라는 것이 존재한다. 캐시에 적재된 데이터들을 사용하여 연산을 처리하면, 캐시 히트율이 올라가는 거고, 적재된 데이터들을 사용하지 않으면 캐시 미스율이 올라가는 것이다. LRU 캐시 교체 알고리.. 2023. 2. 8.
모듈러 연산(Modulo Operation) 어떤 하나의 숫자를 다른 숫자로 나눈 나머지를 구하는 연산으로, 나머지 연산(mod)이라고 한다. 정수론에서 모듈러 연산이란 정수의 합과 곱을 어떤 주어진 수의 나머지에 대하여 정의하는 방법이라고 한다. 모듈로 연산 사칙 연산 덧셈 : (a + b) % M = ((a % M) + (b % M)) % M 뺄셈 : (a - b) % M = ((a % M) - (a % M)) % M 곱셈 : (a * b) % M = ((a * M) * (b * M)) % M 나눗셈 : 모듈로 연산에서 나눗셈은 곱셈 역원(multiplicative inverse)을 곱하는 방식으로 이루어진다. (모듈로 곱셈 역원은 항상 존재하는 것이 아니라, b와 M이 서로소(coprime)일 때만 존재) Ref) - https://johng.. 2022. 12. 24.
연속된 수의 합으로 특정 수를 만들 수 있는 경우의 수 Programmers Lv.2 '숫자의 표현' 문제를 풀다가 정말 간단한 풀이가 보여서, 관련 개념을 정리하려고 한다. 문제는 다음과 같다. 15라는 숫자가 주어지면, 15를 만들 수 있는 연속된 수의 합의 경우의 수들을 반환하면 된다. ex) number : 15 1 + 2 + 3 + 4 + 5 = 15 - 1️⃣ 4 + 5 + 6 = 15 - 2️⃣ 7 + 8 = 15 - 3️⃣ 15 = 15 - 4️⃣ 총 경우의 수 4가지로 4를 반환 내가 작성해서 제출했던 풀이는 다음과 같다. 주어진 숫자까지 반복문을 돌고, 그 내부에서 또 임시의 i를 만들어서 연속된 수의 합이 주어진 숫자가 되는 경우를 찾는 방법을 사용했다. 주어진 숫자가 15라고 가정하면, tempI는 1부터 5까지 더해질 것이고, 주어진 .. 2022. 12. 21.

티스토리툴바