꾸준히 개발하자

문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오. 예를 들어, C1, C2, C3, C4가 연속적인 네 개의 장을 수록하고 있는 파일이고, 파일 크기가 각각 4..

자료구조와 알고리즘/백준 2023. 5. 16. 19:36

자바 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