꾸준히 개발하자

비트 마스킹이란? 정수의 이진수 표현을 자료구조로 쓰는 기법으로 0, 1로 true/false, on/off와 같은 상태를 나타내는 것이 가능하다. 비트 마스크의 장점 1. 빠른 수행시간 - 비트 마스킹은 bit연산이므로 거의 모든 연산이 O(1)의 시간 복잡도를 갖고 있다. 2. 간결한 코드 - 다양한 집합 연산을 비트 연산자를 이용하여 한 줄로 작성이 가능하다. 3. 작은 메모리 사용량 - 1bit로 상태 저장이 가능하므로 메모리 사용량이 적어 DP에 유리하다. 비트 연산자 비트 연산자 논리 의미 & AND 양쪽 비트가 모두 1인 경우에만 1, 나머지 모든 경우 0 | OR 양쪽 비트가 모두 0인 경우에만 0, 나머지 모든 경우 1 ^ XOR 양쪽 비트가 서로 다른 경우 1, 같은 경우 0 ~ NOT..

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

문제 세준이는 N개의 물건을 가지고 있고, 최대 C만큼의 무게를 넣을 수 있는 가방을 하나 가지고 있다. N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. 출력 첫째 줄에 가방에 넣는 방법의 수를 출력한다. https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다...

자료구조와 알고리즘/백준 2023. 5. 25. 03:01

문제 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000) 출력 문제의 조건을 만족하는 쌍의 개수를 출력한다. https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다..

자료구조와 알고리즘/백준 2023. 5. 23. 07:25

문제 소설가인 김대전은 소설을 여러 장(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