알고리즘 풀이/Java(108)
-
[알고리즘] HashMap
중요: 같지 않은 key들이 같은 hashCode를 가지게 하면 해시 충돌이 일어나기 때문에 속도가 느려질 수밖에 없다. 따라서 hashCode가 겹치지 않도록 해주어야 한다. get: O(1) put: O(1) remove: O(1) size: O(1) clear: O(n) containsKey: O(1) containsValue: O(1) getOrDefault: O(1)
2024.03.10 -
[알고리즘] HashSet
특징: 내부적으로는 HashMap을 사용한다. add하는 값을 key로 사용한다. 중요: HashMap은 hashCode() method를 이용해서 key에 대한 해시코드를 구한다. 해시테이블은 이 코드를 해싱 함수를 이용해 버킷에 맵핑한다. Object 객체에서 구현되어 있는 hashCode()는 참조값을 사용한다. Constructor - HashSet(int initialCapacity): 초기 수용량을 줄 수 있다. 너무 크게 하면 iteration 시간이 비효율적이게 된다. add(E e): O(1) clear(): O(n) contains(Object o): O(1) isEmpty(): O(1) iterator(): O(1) remove(Object o): O(1) size(): O(1) sp..
2024.03.10 -
[알고리즘] LinkedList
특징: 시작 노드만 알면 연결된 모든 노드를 알 수 있다. Doubly-linked list size(): O(1) isEmpty(): O(1) get(): O(n) getFirst(): O(1) getLast(): O(1) set(): O(n) iterator(): O(1) listIterator(): O(1) add(E e): O(1) (amortized time) add(int index, E e): O( index 오른쪽 배열 크기) (amortized time) remove(): O(n) removeFirst(): O(1) removeLast(): O(1) peek(): O(1) element(): O(1) peekFirst(): O(1) peekLast(): O(1) pollFirst(): O..
2024.03.10 -
[알고리즘] ArrayList 메서드별 시간 복잡도
size(): O(1) isEmpty(): O(1) get(): O(1) set(): O(1) iterator(): O(1) listIterator(): O(1) add(E e): O(1) (amortized time) add(int index, E e): O( index 오른쪽 배열 크기) (amortized time) remove(): O(n) removeRange(int fromIndex, int toIndex): O(n - fromIndex) indexOf(): O(n) contains(): O(n) addAll(E e): O(m) (넣는 배열 크기) addAll(int index, E e): O(n + m) sort(): O(nlogn) ensureCapacity: O(n) ? clear(): ..
2024.03.09 -
[알고리즘] 프로세서 연결하기
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf#none SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com import java.awt.Point; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; public class Solution { static int N; static i..
2024.02.29 -
[알고리즘] 디버깅 꿀팁
- 분명 논리가 맞는데 틀렸으면 내가 문제를 잘 읽었는지 조건대로 잘 구현했는지를 확인해봐야 한다. - 디버깅 할 때 논리 구조가 머릿속에 있어야 한다. 어떤게 문제일지 도통 모르겠을 때 그림을 그려보거나 내 코드의 논리 구조를 직접 그리며 점검해보는 것이 좋다. - 그 외는 찍어보거나 디버깅툴을 이용해서 확인해보거나 문제를 잘 읽었는지를 확인해보자 - 코드를 작성할 때 직접 말을 하며 논리 구조를 점검해보는게 좋을 듯하다. 대충 넘어가는 부분이 있을 수 있기 때문인데 나중에 디버깅이 어려워질 수 있다.
2024.02.29