[16~20일차] TIL 및 회고

 

[16일차]

 

자료구조

List

List는 Java에서 제공하는 Collection 요소 중 하나로, 순서가 있는 데이터의 집합을 다루기 위한 인터페이스이다.

보통 코딩테스트 기준으로 리스트는 ArrayList를 의미한다.

ArrayList<Integer> list = new ArrayList<>();

 

배열과 ArrayList의 가장 큰 차이는 아래와 같다.

- 배열 : 크기가 고정되어 있어서 데이터를 삽입하거나 삭제할 수 없다.

- ArrayList : 크기가 가변적이며, 새 데이터의 삽입 or 기존 데이터 삭제가 가능하다.

 

ArrayList는 크기가 가변적이며 데이터의 가공이 가능하다는 장점이 있지만, 새 데이터를 맨 뒤에 추가할 때는 시간복잡도가 O(1)이며, 기존 데이터 삭제 및 데이터 중간 삽입 시 시간복잡도가 O(N)까지 커질 수 있다. 

그럼에도 배열은 시간복잡도가 O(1) 이기 때문에 자주 사용한다.

---

여기서 잠깐, 시간복잡도의 개념을 잠깐 알아보자

시간복잡도 란?

 

개념

알고리즘의 성능을 나타내는 지표로, 입력 크기에 대한 연산 횟수의 상한을 의미한다. 낮으면 낮을수록 좋다.

 

측정 방법

알고리즘이 시작한 순간부터 결과값이 나올 때까지의 연산 횟수를 구한다.

만약 결과값을 구하기 위해 총 N번의 수행이 필요하다면, O(N)이 되는 것이다.

이에 반해 수행을 딱 1번만 필요하다면, O(1)이 되는 것이다.

 

예를 들어, 별 찍기 문제를 보자.

 

별 찍기 문제는 별을 점진적으로 찍어내서 N까지 찍어내는 것이다.

그럼 연산 횟수가 1, 2, 3, 4, ..., N-1, N 까지 가기 때문에 ( 1 + 2 + 3 + .. + N-1 + N ) / 2 = N(N-1) / 2 이다.

시간복잡도는 최고차항에서 계수를 빼고 계산하기 때문에 별 찍기 문제의 시간 복잡도는 O(N^2)이 된다.

 

또, 주로 특정 결과값을 도출하기 위해 특정값을 반씩 줄이는 동작을 한다면 시간복잡도는 O(logN)이다.

 

출처 1. https://wikidocs.net/232020 2. https://velog.io/@zxcvbnm5288/Nov.-10-2020-Big-O-natation%EB%B9%85%EC%98%A4-%ED%91%9C%EA%B8%B0%EB%B2%95

 

 

---

 

List의 index는 0 ~ size()-1 이며, 중간 삽입할 수 있는 index는 0 ~ size() 까지이다.

ArrayLIst의 주된 메소드는 다음과 같다.

- 추가 : add()

- 접근 : get()

- 삭제 : remove()

* 유용한 메소드 :

    배열 : 전체 개수 - length, 모든 데이터 정렬 - sort, 모든 데이터를 string으로 반환 - toString()

    ArrayList : 전체 개수 - size(), 빈 값 여부 반환 - isEmpty(), 모든 데이터 정렬 - sort()

 

 

Set

Set은 특정한 값들을 저장하는 추상자료형이다.

Set은 데이터를 저장하는 순서가 없고, 중복된 값을 저장할 수 없다. 이는 list와는 완전히 반대되는 성격을 띄고 있다.

 

Set 자체는 인터페이스로 제공되며, HashSet, TreeSet, LinkedHashSet이 있다.

- HashSet : Set의 대표 클래스이며, 중복된 값을 저장할 수 없고, 저장 순서도 없다.

- TreeSet : 데이터가 오름차순으로 정렬되어 저장된다.

- LinkedHashSet : 데이터가 입력된 순서대로 저장된다.

HashSet<String> set1 = new HashSet<>();

 

 

 

Map

Map은 유일한 key 값으로 value를 관리하는 자료구조이다. key 값은 유니크해야 하며, 검색이 가장 빠른 자료구조이다.

주요 구현 클래스로는 HashMap, TreeMap, LinkedHashMap 등이 있다. 

Map은 인터페이스이므로 직접 인스턴스를 생성할 수 없기에 new HashMap과 같이 구체적인 구현 클래스의 인스턴스를 생성해야 한다.

// Map
Map<String, Object> map = new HashMap<String, Object>();

// HashMap - 좀 더 구체적이다
HashMap<String, Object> hashMap = new HashMap<String, Object>();

 

데이터 검색 방법

key 값으로 일치하는 key가 있는지 확인하고, 일치하는 키를 찾으면 key-value 값을 출력한다.

 

---

[17일차]

자료 구조의 종류

 

선형 자료구조

이전 데이터와 다음 데이터가 1:1로 구성된 자료구조이다.

종류 : 배열, Stack, Queue, LinkedList

 

비선형 자료구조

이전 데이터와 다음 데이터가 1:N으로 N:1, N:M으로 구성된 자료구조이다.

종류 : Tree, Graph

 

 

---

그래프 (Graph)

개념

그래프는 정점(Node, Vertex)과 간선(Edge)를 이용한 비선형 데이터 구조이다.

간선은 두 정점을 연결하는 선으로 두 정점이 연결되어 있다를 의미한다. 

탐색 방법에는 BFS, DFS가 있다.

 

종류

- 무향 (양방향) 그래프 : 방향 X

- 유향 (단방향) 그래프 : 방향 O

 

* 양방향이고, Cycle이 있는 경우 방문체크가 필수이다. (visited boolean 배열 사용)

 

가중치 (비용)

- 간선에 가중치가 있는 경우 : A -> B로 이동하는 거리값, 비용을 구한다.

- 간선에 가중치가 없는 경우 : 연결되어 있다는 표시로 1, true로 표현 / 연결되어 있지 않다는 표시로 0, false로 표현한다.

 

---

너비 우선 탐색 (BFS, Breadth First Search)

개념

시작 노드를 기준으로 거리가 가장 가까운 노드를 우선 방문하는 방식이다.

 

순서

1. 루트 노드부터 시작해서 자식 노드를 차례대로 방문한다 ( = 가까운 노드를 방문한다)

2. Queue 자료구조를 이용해서 해당 노드의 인접된 노드를 처리한다 

3. visited 배열에 방문체크를 한다

4. 모든 노드들을 방문한다

5. 더 이상 방문할 노드가 없으면 depth 를 내려간다

6. 해당 depth의 인접한 모든 노드들을 우선 방문한다

 

시간복잡도

- 인접 행렬로 구현 : O(N^2)

- 인접 리스트로 구현 : O(N+E)

 

 

 

---

깊이 우선 탐색 (DFS, Depth First Search)

개념

현재 탐색 중인 노드를 기준으로 연결된 노드를 즉시 방문하는 방식이다. 주로 재귀함수를 사용해서 해결한다.

 

순서

1. 루트 노드부터 시작해서 자식 노드를 모두 탐색한다

2. Stack 자료구조를 이용해서 해당 노드를 저장한다

3. 더 이상 방문할 노드가 없으면 다시 돌아와서 자식 노드를 방문한다

 

시간복잡도

- O(N+E)

https://velog.io/@vagabondms/DFS-vs-BFS

 

둘 다 비슷하지만, DFS는 모든 경우의 수를 구하는 문제일 때, BFS는 최단 경로를 찾는 문제일 때 사용하면 된다.

 

최단거리, 최소비용

- 가중치가 없을 경우 : BFS의 시간복잡도는 O(N)이다.

- 가중치가 있는 경우 : DFS = BFS 이며, 시간복잡도는 O(3^N-2*M-2)이다.

 

---

[19일차]

서로소

개념

서로소 집합(겹치지 않는 집합)끼리 나눠진 원소를 처리하기 위한 자료구조이다. 유니온-파인드 알고리즘을 사용하여 문제를 해결한다.

 

 

유니온-파인드 알고리즘

이 알고리즘은 루트 노드를 find로 탐색하고, union으로 합치는 알고리즘이다.

 

find 연산 (찾기 연산)

특정 노드의 루트 노드가 무엇인지 탐색하는 방법이다. 보통 특정 노드가 같은 집합에 있는지 확인할 때 사용한다. 이때 연산은 재귀함수로 구현한다.

 

순서

1. 현재 노드의 부모 노드를 확인한다

2. 부모 노드를 확인하다가 부모 노드 = 루트 노드이면 find 연산을 종료한다

 

이 연산의 최악의 시간복잡도는 O(N)이 될 수 있다. 이를 개선하기 위해 경로 압축을 활용해서 해결할 수 있다.

경로 압축이란 집합을 구성하는 트리를 평평하게 만들어서 트리의 depth를 줄이는 방법이다. 

 

 

union 연산 (합치기 연산)

두 집합을 하나로 합치는 연산이며, 이는 두 집합의 루트 노드를 같게 하는 방법이다. 

 

순서

1. 주어진 두 노드의 루트 노드를 찾기 연산(find)를 통해 찾는다

2. 루트 노드를 찾으면 두 루트 노드를 같에 한다 (이때 어떤 노드로 합치든 상관없다)

 

public class DisjointSet {
	static int N;
	static int[] parents;
	
	/*
	 * 모든 원소들에 대한 초기 값을 설정 하는 함수
	 * - 자기 자신을 root로 설정 한다. 
	 */
	public static void make() {
		for (int i = 0; i < N; i++) {
			parents[i] = i;
		}
	}
	
	/*
	 * 인자로 전달 받은 원소(v)의 root를 찾는 기능
	 */
	public static int find(int v) {
		// root를 찾은 경우 (나 자신 return)
		if(parents[v] == v) return v;	// 내가 root라는 소리
		
		// v가 root가 아니므로 v의 부모로 가본다.
		return find(parents[v]);
	}
	
	
	/*
	 * 인자로 받은 두 원소의 집합이 다른 경우 합치는 기능
	 */
	public static boolean union(int a, int b) {
		// 두 원소의 root를 찾아서
		int aRoot = find(a);
		int bRoot = find(b);
		
		// 두 원소의 root가 동일하면  => 같은 집합이므로 union 하면 안됨
		if (aRoot == bRoot) return false;
		
		// 두 원소의 root가 다르면 	 => union
		parents[aRoot] = bRoot;
		return true;
	}
	
	public static void main(String[] args) {
		N= 6;
		parents = new int [N];
		make();
    }
}

 

참고로 find(), union() 메서드의 시간복잡도는 O(logN)이다. 유니온-파인드 알고리즘의 시간복잡도는 O(NlogN)으로 계산해도 된다고 한다.

 

---

회고

이번주에는 그래프 위주로 진도를 나갔다. 개념은 접해봤지만, 실제 문제로 푸려고 하니 어렵게 느껴졌다. 그런데 그래프도 재귀함수를 사용해서 풀기 때문에 더욱 재귀함수를 이해하고 있었어야 했다.

재귀도 개념은 쉽지만 구현이 끝도 없이 어려운 것 같다.

 

정말 많이 풀어보는 방법밖에 없을 것 같다.

 

 

수요일에는 LG 유플러스에서 주관하는 유플텍플에 다녀왔다.

실제로 현직자분들과 대화를 나눌 수 있어서 더 뜻 깊은 시간이었다. 

 

나는 이런 곳에 가면 질문할 거리들이 생각이 안나서 옆에서 그냥 듣고 있던 적이 많았는데, 다른 사람들은 폭풍 질문을 하는 것을 보고 자극을 받았고, 나도 무엇이라도 얻고 가야겠다는 생각에 실제로 궁금했던 tailwindCSS를 현업에서도 사용하는지 여쭤보았다.

실제로 이번에 tailwindCSS와 lucide-react를 사용하는 방향으로 리팩토링을 진행했다고 하였다.

현재 프로젝트에서도 tailwindCSS와 lucide-react를 사용해서 구현했는데, 더 적극적으로 사용해도 좋을 것 같다. 

특히 lucide-react은 뭔가 실제로 사용하는 지 궁금했다. 왜냐면 icon을 호출해서 사용하는 방식이라서 편하긴 했지만, 실제로 사용되는지 의문이 들었는데 이번 기회에 해소할 수 있어서 좋았다.

 

그리고 다른 사람들의 질의응답도 들어보니, 성능 개선은 선택이 아닌 필수라는 생각이 들었다. 

아옹 더 열심히 해야겠다는 생각이 들었다. 그래도 유플텍플에 가서 많은 자극을 얻고 왔다!

 

 

제일 좋았던 건 아무래도 경품 당첨? ㅎ_ㅎ

유용하게 잘 쓰겠습니다

유플러스 감사합니다 저를 받아주세요 (제발)