[자바] indexOf와 lastIndexOf의 사용법
2022. 6. 26. 22:40
자바
indexOf & lastIndexOf indexOf IndexOf와 lastIndexOf 모두 String클래스에 포함된 메서드로써 특정 문자가 어떤 문자열에서 몇번째 위치에 자리잡고 있는지를 Integer 타입으로 반환시켜준다. 문자열.indexOf(특정문자)로 사용하며, 사용법이 매우 간단하니 바로 예시를 들어 설명하겠다. public class Test { public static void main(String[] args) { String str = "Hello Java!!"; System.out.println(str.indexOf("J")); System.out.println(str.indexOf("l")); System.out.println(str.indexOf("l", 3)); } } 출력..
[자바] toCharArray() 메서드를 이용해서 문자열을 뽑아보자
2022. 6. 26. 22:17
자바
toCharArray() String 클래스에 있는 toCharArray() 메서드를 알아보겠다. 문자열을 Character 타입의 배열로 변환시키는 메서드다. 사용방법이 매우 간단하므로, 간단한 예시를 들어보겠다. import java.util.Arrays; public class Test { public static void main(String[] args) { String str = "Hello Java!!"; char[] c = str.toCharArray(); System.out.println(Arrays.toString(c)); } } 출력 [H, e, l, l, o, , J, a, v, a, !, !] 공백도 배열에 포함된다는 것에 주의하자. 문자열을 Character 타입의 배열로 전환시..
[자바] 트라이(Trie) 개념과 삽입/검색/삭제 구현까지
2022. 6. 25. 23:56
자바
트라이(Trie) 트라이 역시 트리형태의 자료구조라 보면 된다. 정렬된 트리 구조를 지니고 있으며, 시간복잡도는 O(N)이다. 대신, 사전에 문자열들을 트라이 형태로 구축을 해야한다. 트라이의 구조 문자열이 apple, april, ace, bear, best가 있으면 트라이는 위 사진처럼 구현된다. 문자열의 맨 앞자리부터 공통된 부분을 하나의 노드로 잡고 서로 다른 문자열을 자식노드만 나눠서 쭉 연결하는 구조이다. 그렇기 때문에 문자열의 갯수 M에 따른 시간복잡도 O(MN)을 가졌다고 볼 수 있다. 트라이 - 삽입 문자열의 맨 앞자리부터 비교하며 공통된 문자를 하나의 노드로 묶기때문에, 맨 앞 문자부터 삽입하면 된다. 단, 지금처럼 apple, april이 존재하는 상황에서 app 문자열이 삽입되면 a..
[자바] Comparable 인터페이스로 값 정렬하기
2022. 6. 25. 15:30
자바
Comparable 값을 비교할 때 사용하는 이 두가지는 모두 "인터페이스"이다. 각각의 추상메서드를 갖고있는 이 인터페이스들은 implements해서 사용하며, 반드시 해당 추상메서드를 implements하는 클래스 내부에서 구현해야한다. https://imcoding.tistory.com/10 인터페이스(Interface) .java 인터페이스(Interface) 인터페이스는 하나의 추상적 개념이다. 가령 자동차를 예시로 들어보자. 자동차의 사전 뜻은 다음과 같다. 자동차 (自動車) [명사] 원동기를 장치하여 그 동력으로 바퀴를 굴 imcoding.tistory.com 그렇다면 왜 해당 인터페이스를 사용할까? primitive 타입의 데이터도 부등호만으로 비교가 가능한데 말이다. 만약 우리가 prim..
[자바] 인터페이스(Interface)
2022. 6. 24. 23:27
자바
인터페이스(Interface) 인터페이스는 하나의 추상적 개념이다. 가령 자동차를 예시로 들어보자. 자동차의 사전 뜻은 다음과 같다. 자동차 (自動車) [명사] 원동기를 장치하여 그 동력으로 바퀴를 굴려서 철길이나 가설된 선에 의하지 아니하고 땅 위를 움직이도록 만든 차. 승용차, 승합자동차, 화물자동차, 특수자동차 및 이륜자동차가 있다. 그렇다. 자동차는 결국 여러 부품들이 들어가 사람이 타고다닐 수 있도록 만들어진 것을 뜻한다. 그것을 통상적으로 자동차라 부르며, 이를 구성하는 부품들과 바퀴와 좌석의 개수 등에 따라 얼마든지 다양한 형태로 존재할 수 있다. 추상적이라는 건 결국 껍데기라고 생각해도 무방할 것 같다. 인터페이스도 마찬가지다. 인터페이스 안에 여러 상수와 메서드를 선언하고, 이를 impl..
[자바] 우선순위 큐(Priority Queue)
2022. 6. 24. 18:06
자바
우선순위 큐(Priority Queue) 개념 일반적인 큐에서는 먼저 들어간 데이터가 먼저 나오는 FIFO 구조였으나, 우선순위 큐에서는 그렇지 않다. 관리하는 데이터마다 우선순위가 있으며 Dequeue시 우선순위가 높은 순서대로 나간다. 단, 우선순위가 같다면 FIFO 방식으로 나간다. 자바에서는 기본적으로 PriorityQueue를 제공하고있다. 구현방법 일반적인 상황에서 enqueue와 dequeue의 횟수가 비슷하게 발생한다. 그렇기때문에 전체적인 복잡도가 낮은 힙을 이용해 주로 구현한다. 우선순위 큐를 힙으로 구현한다면, 삽입 및 삭제 후 우선순위에 따라 데이터가 재배치되는 원리는 최소힙 및 최대힙의 삽입 & 삭제와 동일하다. https://imcoding.tistory.com/7 힙(Heap)..
[알고리즘] 프로그래머스 Lv2 오픈채팅방 문제풀이
2022. 6. 22. 18:50
알고리즘
문제 출처: https://programmers.co.kr/learn/courses/30/lessons/42888?language=java 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다. "[닉네임]님이 들어왔습니다." 채팅방에서 누군가 나가면 다음 메시지가 출력된다. "[닉네임]님이 나갔습니다." 채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다. 채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다. 채팅방에서 닉네임을 변경한다. 닉네임을 변경할 때는 기존에 채팅방에 출력되어 있던 메시지의 닉네임도 전부 변경된다. 예를 들어, 채팅방에 "Muzi"와 ..
[자바] 힙(Heap) - 최대힙 / 최소힙 개념과 구현. java
2022. 6. 22. 18:33
자바
힙(Heap) 완전 이진트리의 형태를 갖는다. 완전 이진트리는 마지막 레벨을 제외하고 모든 레벨의 노드가 꽉 차있다. 다만, 마지막 레벨의 노드는 왼쪽부터 채워져야한다. 가령 사진에서 마지막 레벨의 노드가 오른쪽에 붙어있다면 완전 이진트리가 아니게된다. 포화 이진트리는 모든 레벨에서 노드가 차있는 경우를 말한다. 이진탐색트리와는 반대로 중복 값을 허용한다. 최소 힙은 부모노드가 자식노드보다 작은 값을 가지며, 최대 힙은 그 반대이다. 따라서 루트노드 값이 최댓값 혹은 최솟값이다. 형제노드간 크기 차이는 고려하지 않는 반 정렬 상태다. 최솟값이나 최댓값을 찾아내는데 유용한 자료구조이다. 최소 힙에서 삽입 트리의 가장 아래쪽에 데이터를 삽입한다. 만약 부모노드보다 키 값이 작다면 부모노드와 위치 교체를 반복..
[자바] 업캐스팅과 다운캐스팅
2022. 6. 21. 15:51
자바
캐스팅(Casting) 상속 관계에 있는 부모클래스와 자식클래스간에 형변환이 이루어지는 것을 말한다. 업캐스팅과 다운캐스팅이 있다. 업캐스팅(Up casting) 자식클래스의 객체가 부모클래스로 형변환 되는 것을 말한다. 아래에서 코드로 살펴보겠다. class pruit { int price; pruit() { } pruit(int price) { this.price = price; } } class apple extends pruit { String color; apple(int price, String color) { super(price); this.color = color; } } class pricaty { public static void main(String[] args) { apple A ..
[자바] 균형 이진 탐색 트리 - AVL트리의 개념과 삽입 구현까지
2022. 6. 18. 21:39
자바
균형 이진 탐색 트리 영어로는 Balenced Binary Search Tree 라고 명명한다. 노드를 삽입하거나 삭제할 때 트리가 오른쪽과 왼쪽 길이의 균형을 이루도록 하는 것이다. 균형을 이룬다는 것은 양쪽의 길이 차이가 1을 초과하지 않는 것을 말한다. 기본적으로 이진 탐색 트리의 성질을 유지하고 있어야 한다. (이진탐색트리: https://imcoding.tistory.com/4 ) AVL트리와 Red-Black트리가 있으며, AVL트리에 대해 다뤄보겠다. 왼쪽 Case1은 30, 20, 40, 10 순서로 노드가 들어온 이진 탐색 트리이다. 그리고 왼쪽과 오른쪽의 길이 차이가 1을 초과하지 않기 때문에 균형 이진 탐색 트리로 볼 수 있다. 반면 Case2는 5, 10, 20, 30 순서로 노드가..
[자바] 이진 탐색 트리 (Binary Search Tree)
2022. 6. 18. 19:33
자바
이진 탐색 트리 구조 규칙 1. 왼쪽 자식 노드의 키는 부모 노드의 키보다 작아야 한다. 2. 오른쪽 자식 노드의 키는 부모 노드의 키보다 커야 한다. 3. 중복된 키는 허용되지 않는다. (노드 추가 과정에서 중복 키 발견 시 탐색이 종료된다.) 4. 서브트리도 모두 1, 2, 3번 규칙을 만족한다 특징 1. 중위순회로 순회하면 오름차순 정렬된다. (1, 10, 15, 20, 25, 30) 2. 자식 노드를 찾을 때 현재 노드와 값의 크기를 비교하여 기본 이진트리보다 빠르게 탐색할 수 있다. 단, 왼쪽과 오른쪽 노드간 death 크기가 균형을 이루어야한다. (균형상태: O(logN) / 불균형상태: O(N)) 3. 찾는 데이터가 없으면 null을 반환한다. (이진트리 순회 종류: https://imcod..
[자바] Tree의 개념, 종류, 재귀함수를 이용한 구현까지
2022. 6. 17. 15:40
자바
트리(Tree) 노드와 링크로 구성된 자료구조를 말한다. 폴더, 조직도 등의 계층적 구조를 나타낼 때 사용한다. 용어설명 (위 사진참고) Node: 트리구조에서 값을 담고있는 단위 Edge: 노드간 연결선 (link 혹은 branch라고도 함) Root: 부모가 없는 최상단의 노드 (A) Leaf: 자식이 없는 노드 (E, F, G) 내부노드: Leaf 노드를 제외한 나머지 노드 부모노드: (상대적 개념) 연결된 두 노드 중 상위 노드 자식노드: (상대적 개념) 연결된 두 노드 중 하위 노드 형제노드: 같은 부모와 연결된 노드 Depth: 루트(최상단 노드)에서 특정 노드까지 Edge의 수 Level: 트리의 깊이를 의미함. Lv.0부터 시작한다. (Lv.2: D, E, F) Height: 가장 큰 레벨..