재미를 추구하는 편

배열 (Array)선형 자료구조로 속도가 빠르고 효율적이다.동일한 요소를 연속적으로 저장하여 데이터 접근이 용이하다.인덱스를 사용하기 때문에 특정 인덱스의 데이터에 즉시 접근할 수 있다.연속된 메모리 주소를 사용하기 때문에 공간을 절약할 수 있다.크기가 고정되어 있으며 크기 변경이 불가능하다.삽입 및 삭제 시 시간 복잡도는 O(N)이다.연결 리스트 (Linked List)각 요소가 노드(node)로 이루어져 있으며, 각 노드는 다음 노드의 포인터를 가지고 있다.메모리 사용이 효율적이다.삽입 및 삭제 시 시간 복잡도는 O(1)이다.인덱스를 사용한 접근 시간은 O(N)으로 느리다.포인터를 저장할 공간이 추가로 필요하다. 특정 index에 값을 삽입 한다면 array 와 linked list 중 어떤 것이 빠..

https://www.acmicpc.net/problem/1238 오랜만에 올리는 문제후기!! 보자마자 알게된 것은 최단 거리 찾는 문제이다.처음보는 도착지만 알려주는 유형이다. 그래서 처음에는 각 마을에서 출발해서 도착지에 도착한것을하나하나 탐색해서 리스트로 저장한 다음 최댓값을 구할 예정이었다.  그러나 생각해보니 출발지 무작위 A 에서 목적지 B까지 걸리는 시간을 구하는 것은B에서 출발해서 모든 마을 까지 도달 하는 시간이라는 것을 깨닫게 되었다!와우!!단 길이 단방향이니 반대로 그래프를 저장해 준다면 수월하게 해결 될 것 같았다. 가는 방향뿐 아니라 오는 길 또한 저장 해주어야 하니역방향을 따로 저장 해주고결과 또한 따로 저장해주면 A와 B 왕복의 최대값을 구할 수 있다.  import java...

https://www.acmicpc.net/problem/11834 이 문제는 이진 탐색을 가장한 수학 문제이다.  일단 배열을 나열해 보면마지막 숫자들이 속한 그룹(n)의 제곱임을 알 수있다. 또한 그룹 내부에서도자신 그룹의 첫번째 숫자를 1 이라고 할때 2씩 커지기 때문에이전그룹의 마지막 숫자에서 현재 그룹에서의 index를 구해서2*index -1을 해주면 문제를 풀 수 있다. 해당 풀이를 식으로 구현해 보면 (I는 입력받은 숫자이다.)답이 2*I -n으로 간단하게 나온다 단 I가 10의 100승으로 아주 크기 때문에모든 숫자는 BigInteger로 처리해 주어야 하고n을 구할때도 이진 탐색으로 구현하여 시간을 최대한 줄여주어야 한다.정답import java.io.*;import java.math...

이분 탐색이분탐색 원리 오른차순 또는 내림차순으로 정렬된 배열에 적용 가능한 탐색 기법정렬된 배열에서 특정 값을 찾을때 정 중앙에 위치한 값을 활용하면 빠른 속도로 탐색을 끝낼수 있다.   이분 탐색 알고리즘시간복잡도: O(logN)반복문과 재귀 두 가지 방법을 사용할 수 있다.자료를 오름차순으로 정렬한다.자료의 중간값(mid)이 찾고자 하는 값(target)인지 비교한다.mid 값이 target과 다르다면 대소관계를 비교하여 탐색 범위를 좁히고, target과 mid 값이 같을 때까지 아래 조건에 따라 2번과 3번을 반복한다.          ⓐ target이 mid 값 보다 작으면 end를 mid 왼쪽 값으로 바꿔준다. (절반의 왼쪽 탐색)          ⓑ target이 mid 값 보다 크면 st..

해시코드(hashCode)란?  해시코드란 객체를 식별하는 정수값입니다. Java에서 모든 객체는 `Object` 클래스의 `hashCode()` 메서드를 통해 자신만의 해시코드를 반환할 수 있습니다. 이 해시코드는 다음과 같은 특징을 가집니다: 1. 고유성(Uniqueness): 서로 다른 객체는 서로 다른 해시코드를 가져야 합니다. 2. 동일성(Equality): 동일한 객체는 항상 같은 해시코드를 반환해야 합니다. 3. 계산 효율성: 해시코드 계산은 빠르고 효율적이어야 합니다. 4. 균등 분포: 해시코드 값은 가능한 한 균등하게 분포되어야 합니다. 해시코드와 해시 테이블해시코드의 진가는 해시 테이블(Hash Table) 자료구조에서 발휘됩니다. Java의 `HashMap`과 `HashSet`은 내부..

stack?"쌓다"라는 의미로 데이터를 하나씩 쌓아 올린 형태의 자료 구조,한쪽 끝에서만 자료를 넣고 뺄수 있는 후입선출 LIFO(Last in First Out) 형식의 자료구조 이다. stack을 지양하는 이유 1. interface의 유연성java에서는 다중상속을 지원하지 않으며stack은 클래스 이므로 확장이 불가능 하다 반면 deque은 인터페이스 이다.인터페이스는 클래스 상속보다 더욱 유연하기 때문에이미 상속을 받은 클래스 더라도인터페이스를 구현할 수 잇다.  → 인터페이스인 deque이 클래스인 stack 보다 객체지향관점에서 더욱 많은 유연성을 지원 2. 동기화 메소드 및 성능Vector.class를 상속하여 사용→  thread safety 를 위한 전통적인 방법이며 단점 발생(threa..

ArrayDeque vs LinkedListArrayDeque1. 내부구현배열을 기반으로 한 데크(Double-Ended Queue) 구현체크기를 동적으로 조절할 수 있어서 큐에 요소를 추가하거나 제거할 때 크기를 변경할 필요가 없다.2. 성능큐의 크기를 동적으로 조절할 수 있으므로, 큐의 앞 또는 뒤에서의 요소 추가 및 제거가 상수 시간(O(1)) 이다.3. 접근 시간배열을 사용하기 때문에 인덱스를 통한 빠른 접근이 가능하다.4. 메모리 사용각 요소는 배열에 저장되므로 메모리 사용이 연속적이다.고정된 크기의 배열을 사용하는 것이 아니라 동적으로 크기가 조절되므로 메모리 사용이 효율적이다.LinkedList1. 내부구현이중 연결 리스트를 기반으로 한 데크 구현체각 요소는 이전 요소와 다음 요소를 가리키는..

세그먼트 트리여러 개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터의 합을 구하는 방법특정 구간의 합을 가장 빠르게 구하는법 1. 기존방식순서대로 하나씩 들고와서 더하기 → 시간복잡도 O(N) 2. 트리구조로 구하기세그먼티 트리 초기화 및 생성 함수arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]tree = [0] * (len(arr) * 4)​ 세그먼트 트리의 크기는 배열의 개수 N일 때,N보다 큰 가장 가까운 N의 제곱수를 구해 그것의 2배를 하여 미리 크기 구하기→  실제로는 데이터의 개수 N에 4를 곱한 크기만큼 미리 세그먼트 트리의 크기 할당  왼쪽 자식 노드의 번호는 2번이 되며, 0~4까지의 arr 구간 합의 값이 삽입된다.오른쪽 자식 노드의 번호는 3번이 되며, 5..

Key, value 값으로 이루어진 Collector 이다 key는 중복 될 수 없다. stream 을 사용한 작성words.stream() .collect(Collectors.groupingBy(Function.identity(), Collectors.counting())) map의 stream 사용entrySet을 빼서 사용map.entrySet().stream().filter(i -> i.getValue() == n)//개수 같은거만 filter .map(Map.Entry::getKey)//키만 빼서 .sorted() .collect(Collectors.toList());//정렬 map의 sort일반적으로 안되지만 stream 은 가능map.entrySet().stream() ..

https://www.acmicpc.net/problem/4374\ 틀렸습니다를 보고 들어온 사람들을 위한 간단 tip글자 쪼개기 단위는 빈칸이 아닙니다. a-z가 아닌 모든 글자에요! static String reg = "[\\W_]+";이걸로 시간 뺏기신 모든 분들 응원합니다 ㅜㅜ   최근 올라온 지 얼마 안된 것 같은 문제들을 조금씩 도전하고 있는데java풀이가 하나도 없는 문제는 처음 인것 같다.사실 입출력에 관한 문제 이니 크게 문제 설명할 것은 없는듯 하고한줄 씩입력 받아서 쪼개고 다시 넣어서입력 된 숫자 빈도에 맞는 글자들만 다시 return 하면 되는 방식 이다. 요즘 stream 사용을 열심히 공부하는 중이기 때문에stream 위주로 보면 좋을 것 같다. import java.io...