꾸준히 개발하자

자바 Spring공부를 하다가 Optional이라는 클래스를 처음봐서 따로 어떤 역할을 하는 클래스인지 찾아보았다. 강의에서 사용한 코드는 다음과 같다. @Override public Optional findById(Long id) { return Optional.ofNullable(store.get(id)); } Optional 클래스란? Optional 클래스는 T타입의 객체를 포장해주는 Wrapper class이다. 보통 어떤 객체의 값에 null이 올 수 있으면 항상 null예외처리(NullPointerException)를 해줘야하는데 Optional을 이용하면 이를 쉽게 처리를 할 수 있다. Optional객체를 만드는 방법에는 3가지가 있다. Optional객체를 만드는 법 1. Optiona..

Java 공부/Java 공부 2023. 5. 9. 17:03

문제수 n개 A1, A2, ..., An이 주어질때 연속된 부분 구간의 합이 m으로 나누어 떨어지는 구간의 개수를 구하시오.https://www.acmicpc.net/problem/10986 10986번: 나머지 합수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j)www.acmicpc.net 이 문제는 누적합의 개념을 알고 있어야 풀 수 있는 문제이다. 누적합은 주어지는 수를 배열에 저장할 때 A1, A2, A3, ... An으로 저장하는게 아니라 A1,  A1+A2,  A1+A2+A3, ... ..

자료구조와 알고리즘/백준 2023. 5. 5. 00:04

boolean containsKey(Object Key) HashMap에 지정된 Key가 포함되어 있는지 알려준다. boolean containsValue(Object Value) HashMap에 지정된 Value가 포함되어 있는지 알려준다. boolean isEmpty HashMap이 비어있는지 확인한다. void clear() HashMap에 저장된 모든 객체를 제거한다. Object put(Object Key, Object Value) HashMap에 Key와 Value를 저장한다. 이때 기존에 해당 Key에 대한 Value가 존재했을 경우에 그 Value값을 반환하고 만약 새로운 Key와 Value가 저장된다면 null을 반환한다. Object remove(Object Key) HashMap에 지..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 5. 3. 14:20

프림 알고리즘 프림 알고리즘은 주어진 그래프에서 MST(Minimum Spanning Tree = 최소 신장 트리)를 찾는 알고리즘이다. MST란 모든 노드를 연결하는 트리 중 간선의 가중치의 합이 가장 작은 트리를 말한다. MST를 찾는 알고리즘은 프림 알고리즘과 크루스칼 알고리즘 2개가 있는데 주어진 그래프의 노드의 개수보다 간선의 수가 훨씬 많을 때는 프림 알고리즘을 사용하는 것이 더 효율적이다. 프림 알고리즘은 다음과 같이 진행된다. 1. 어떤 노드를 방문해 방문처리를 하고 우선순위 큐에 노드와 연결된 간선들을 넣는다 (만약 간선의 도착지가 방문한 노드면 큐에 넣지 않는다) 2. 우선순위 큐는 자동으로 간선의 가중치를 기준으로 오름차순 정렬을 유지한다 3. 큐에서 빼낸 값은 가장 낮은 가중치를 갖..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 4. 28. 18:16

해시법 해시법이란 data를 저장할 인덱스를 간단한 연산으로 구하여 검색, 추가, 삭제를 효율적으로 수행할 수 있는 자료구조이다. 해시법에는 data를 저장할때 key값과 함께 저장하는데 이 key값과 해시 함수(간단한 연산)를 통해 얻은 해시값을 index로 사용한다. 예를 들면 다음과 같다. 해시 함수 : key % 13 key 35 80 75 63 21 1 해시값 (index) 9 2 10 11 8 1 이렇게 key값을 해시함수에 넣어 얻은 해시값을 index로 해서 key값과 data값을 저장하면 된다. 위와 같이 해시값을 index로 하여 key값과 data를 저장하는 자료구조를 해시 테이블이라고 하고 그 안에 요소들을 버킷(bucket)이라고 한다. 해시 테이블에서 원하는 data를 찾으려면 ..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 4. 22. 10:54

위상 정렬 위상 정렬은 그래프의 정렬을 의미한다. 이를 위해서는 그래프가 DAG(Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프)여야 할 필요가 있다. DAG란 간선이 단방향이어야 하며, 사이클이 존재하지 않는(어떤 노드를 출발했을 때 다시 그 노드로 돌아올 수 없는)그래프여야 한다. 위상 정렬은 그렇게 어렵지 않다. 만약 아래와 같은 그래프가 있다고 하자. 동그라미 안에 있는 숫자는 노드의 번호이고 네모 안에 있는 숫자는 노드를 가리키는 간선의 개수이다. 간단하게 다음 규칙에 맞게 정렬을 해주면 된다. (BFS 방법) 1. 네모 안에 숫자가(노드를 가리키는 간선의 개수) 0인 노드들을 Queue에 넣어준다. 2. Queue에서 노드 하나를 빼서 방문한 뒤 해당 노드의 간..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 4. 20. 13:47

이진 탐색 트리 이진 탐색 트리는 이진 트리의 한 종류로써 각 노드가 key 값을 가지고 있다. 모든 노드들은 왼쪽 서브트리에 자신보다 작은 key값을 갖고있는 노드들을 포함하고 오른쪽 서브트리에 자신보다 큰 key값을 갖고있는 노드들을 포함한다. 보통 삽입, 삭제, 검색 등이 O(logN)의 시간복잡도를 갖기 때문에 빠른 정렬, 검색이 가능하다. 또한 중위 순회를 하면 key값의 오름차순으로 노드를 탐색할 수 있다. 단점은 중복 key값을 가질 수 없고 트리가 편향되면 탐색 시간이 늦어진다. (트리가 편향되는 문제를 해결하기 위해 레드-블랙 트리 등의 균형잡힌 이진 탐색 트리가 만들어졌다) 이진 탐색 트리 구현 기본적으로 Tree 클래스를 만들고 내부에 Node 클래스를 만들어 구현한다. Node들은 ..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 4. 18. 03:46

리스트란? 리스트는 데이터를 순서대로 나열해 놓은 자료구조를 말한다. 리스트는 선형 리스트와 연결 리스트로 나눌 수 있는데 선형 리스트는 데이터들이 메모리에서 배열처럼 연속적으로 저장되어있는 리스트를 말하고 연결리스트는 각각의 데이터들이 메모리에 연속적으로 저장되어 있지는 않지만 각각의 데이터 안에 다음 순서의 데이터의 위치가 저장되어있는 리스트이다. 선형 리스트 구현 선형 리스트는 배열과 같은 구조이기 때문에 1차원 배열을 통해 쉽게 구현할 수 있다. class Student{ String name; int no; Student(String s, int n) { name = s; no = n; } } class Main { public static void main(String[] args) throw..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 4. 16. 17:01