본문 바로가기
위장 - 프로그래머스 (Java, Level 2) package programmers; import java.util.HashMap; import java.util.Iterator; public class 위장 { public int solution(String[][] clothes) { int answer = 1; HashMap hashMap = new HashMap(); for(int i=0; i 2022. 2. 8.
전화번호 목록 - 프로그래머스 (Java, Level 2) import java.util.Arrays; import java.util.HashMap; public class 전화번호목록 { public boolean solutionHash(String[] phone_book) { boolean answer = true; HashMap hashMap = new HashMap(); for(int i=0; i 2022. 2. 7.
완주하지 못한 선수 - 프로그래머스 (Java, Level 1) import java.util.Arrays; import java.util.HashMap; import java.util.Iterator; import java.util.Map; import java.util.Set; class 완주하지못한선수 { public String solution(String[] participant, String[] completion) { Arrays.sort(participant); Arrays.sort(completion); //두 배열을 정렬하면, 같은 index에서의 요소가 다르다면 해당 participant배열의 요소가 완주하지 못한 참가자 int i = 0; for(i=0; i 2022. 2. 7.
트리 Binary Search Tree -> AVL Tree -> B Tree (-> B+ Tree) BST의 검색/삽입/삭제 평균 시간복잡도는 O(logN)이다. 데이터 삽입 순서에 따라 tree의 균형이 달라진다. 최악의 경우는 한쪽으로만 쏠려 선형 구조처럼 된 경우이다. 이 때 시간복잡도는 O(logN)이 아닌 O(N)이다. AVL Tree는 BST에서 이러한 상황이 안나오게 삽입, 삭제 시 트리의 균형을 맞춰주는 알고리즘을 추가했다. 이 때문에 검색/삽입/삭제 시간 복잡도는 최악의 상황에도 O(logN)이 되었다. 트리의 성능은 트리의 높이가 낮을수록 높다. 이를 위해서는 하나의 레벨에 더 많은 key를 저장하고, 더 많은 자식노드를 가지면 된다. 이것이 B Tree이다. 하나의 노드는 하나 이상의 k.. 2021. 12. 8.
(Java) 백준 1021 : 회전하는 큐 문제 : https://www.acmicpc.net/problem/1021 풀이 앞, 뒤 양쪽으로 삽입/삭제가 가능한 자료구조인 Deque를 사용하면 좋겠다. Deque인터페이스를 구현하는 ArrayDeque, LinkedList 클래스 중 선택한다. 1. 타겟이 맨 앞으로 올 때까지 이동시킨다. 1.1 왼쪽으로 이동이 빠르다면 첫 번째 요소를 마지막으로 옮긴다. 1.2 오른쪽으로 이동이 빠르다면 마지막 요소를 처음으로 옮긴다. 2. 타겟을 삭제한다. 3. 다음 타겟을 1번부터 반복한다. 공부할 내용 StringTokenizer 기본 사용법 Deque 기본 개념 ArrayDeque vs LinkedList import java.io.BufferedReader; import java.io.IOExcepti.. 2021. 12. 6.
(Java) 백준 5639 : 이진 검색 트리 풀이1 : Tree, Node 클래스 생성하여 postorder메소드 재귀적으로 구현 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; class Tree { Node root; Tree() { this.root = null; } public void insert(int key) { root = insertNode(root, key); } private Node insertNode(Node node, int key) { Node newNode = new Node(key, null, null); if(node==null) { return newNode; } else { if(node.keyk.. 2021. 11. 30.
카운팅 정렬 (도수 정렬, 계수 정렬) 요소의 대소 관계를 판단하지 않고 정렬하는 알고리즘 시간복잡도는 일단 O(N)이다. 뒤에서부터 진행하면 안정적이다. 중간에 도수분포표/누적도수분포표에 해당하는 배열을 새로 사용해야 한다. 그리고 배열의 요소값의 범위에 따라 해당 배열의 길이가 달라진다! 즉, 정렬하는 요소수는 적은데 요소값의 범위가 엄청 크다면, 극단적으로 엄청난 메모리가 낭비된다. 2021. 11. 20.
병합 정렬 요소가 2개 이상인 경우, 1. 앞 부분을 병합 정렬한다. 2. 뒷 부분을 병합 정렬한다. 3. 앞 부분과 뒷 부분을 병합한다. 추가 공간을 필요로 하기 때문에 제자리 정렬이 아니다. 안정적이다. 이진트리로 대입해서 생각해보면, 이진트리의 높이, 즉, 반으로 나눗 횟수, 다시 병합할 횟수, stage 수 등등 -> logN 어느 한 레벨에서 노드 2^M개, 한 노드에 있는 요소수 N*(1/2)^M개이므로 한 레벨에서 비교에 대한 복잡도는 O(2^M * N*(1/2)^M) -> O(N)이다. 따라서 O(NlogN)의 시간복잡도를 가진다. 2021. 11. 20.
셸 정렬 삽입 정렬의 장단점을 보면, 장점 : 거의 정렬은 마친 상태에서는 속도가 굉장히 빠르다. 단점 : 타겟 요소가 이전 요소들(정렬된)보다 작으면 이동하는 횟수가 많아진다. 셸 정렬은 단점을 보완하고 장점을 살리기 위해 고안된 정렬 알고리즘이다. 삽입 위치가 멀 경우, 한 칸씩 비교하면서 교환하는 것이 오래 걸리기 때문에, 일정 간격으로 띄엄띄엄 비교/교환을 한다는 아이디어다. 그리고 이 간격을 줄여가다보면 정렬이 완료될 것이다. 1. 얼만큼 띄어가면서 검사할 지 간격을 정한다. 2. 해당 간격만큼 요소들을 띄워 묶어서 그룹 별로 나눈다. 3. 나눈 그룹 별로 각자 삽입 정렬을 한다. 4. 적당한 간격으로, 적당한 횟수만큼 진행하여 거의 정렬된 배열을 만든다. 5. 최종적으로 1을 간격으로 하여 삽입 정렬을.. 2021. 11. 19.
삽입 정렬 정렬되지 않은 부분의 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입하는 알고리즘 * 타겟인 요소와 이전 위치(이미 정렬된)에 있는 요소들을 비교하여 알맞은 위치를 찾는다. 1. 타겟 요소와 바로 이전 요소와 비교 2. 타겟 요소가 작다면 이전 요소와 교환하고 아니면 종료 3. (교환했다면) 타겟 요소와 교환한 위치의 이전 요소와 비교 4. 타겟 요소가 작다면 교환하고 아니면 종료 5. 하나의 요소의 위치가 정해지면 원래 타겟 요소 다음 위치의 요소로 위 과정을 반복한다. 차례대로 비교/교환하므로 안정적이다. 거의 정렬된 경우에는 (best 상황) n번의 비교만 하고 교환하는 과정이 없으므로, O(N) 역순인 경우 (worst 상황) 타겟 요소가 이전 요소들 중에 제일 작을 것이므로, 타겟 요소를 맨 .. 2021. 11. 16.

티스토리툴바