[CNU SW Academy] 7일차(22.12.09.)

프로그래머스 - 프론트엔드 미니 데브코스

그래프(Graph)

정점과 정점 사이를 연결하는 간선으로 이루어진 비선형자료구조

Node, Edge

 

그래프의 특징

- 정점은 여러 개의 간선을 가질 수 있다.

- 방향 그래프와 무방향 그래프로 나눌 수 있다.

- 간선은 가중치를 가질 수 있다. 

- 사이클이 발생할 수 있다.

 

무방향 그래프

(A, B)와 (B, A)는 같은 간선으로 취급된다.

방향그래프

<A, B>와 <B, A>는 다른 간선으로 취급된다.

 

연결 그래프

모든 정점이 서로 이동가능한 상태인 그래프

비연결 그래프

특정 정점쌍 사이에 간선이 존재하지 않는 그래프 

완전그래프

모든 정점끼리 연결된 상태인 그래프

 

그래프의 구현 방법

1. 인접 행렬

2. 인접 리스트

 

트리(Tree)

방향그래프의 일종으로 정점을 가리키는 간선이 하나밖에 없는 구조를 가지고 있다.

가장 상위에 존재하는 정점을 Root

더 이상 자식이 없는 정점을 Leaf Node

레벨은 Root로부터 몇 번째 깊이인지

루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다.

정점이 N개인 트리는 반드시 N-1개의 간선을 가진다.

 

이진트리(탐색을 위한 알고리즘에 많이 쓰임)

정점이 최대 2개의 자식을 가지는 트리

이진트리, 완전 이진 트리, 포화 이진 트리, 편향 트리

 

트리의 구현 방법

1. 인접 행렬

2. 인접 리스트

 

Left : Index * 2

Right : Index * 2 + 1

Parent : floor(Index / 2)

 

우선순위 큐(자료구조가 아닌 개념이다.)

우선순위가 높은 요소가 먼저 나가는 큐

 

힙

우선순위 큐를 구현하기 위한 가장 적합한 방법

이진 트리 형태를 가진다.

우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 바로 정렬되는 특징

 

힙의 특징

Max Heap, Min Heap

우선순위가 높은 요소를 Root로 배치

JS는 Heap을 지원하지 않음 => 구현해서 사용해야 한다.

 

트라이(Trie)

문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조

검색어 자동완성, 사전찾기 등에 응용될 수 있음

 

트라이 구조

루트는 비어있다.

각 간선은 추가될 문자를 키로 가진다.

각 정점은 이전 정점의 값 + 간선의 키를 값으로 가진다.

해시 테이블과 연결리스트를 이용해 구현할 수 있다.

 

정렬(Sort)

요소들을 일정한 순서대로 열거하는 알고리즘

 

비교식 정렬

1. 버블 정렬

서로 인접한 요소를 검사하여 정렬하는 알고리즘

O(N^2)의 시간복잡도를 가짐

2. 선택 정렬

선택한 요소와 가장 우선순위가 높은 요소를 교환하는 정렬 알고리즘

O(N^2)의 시간복잡도를 가짐

3. 삽입 정렬

선택한 요소를 삽입할 수 있는 위치를 찾아 삽입하는 방식의 알고리즘

O(N^2)의 시간복잡도를 가짐

 

분산식 정렬

분할 정복(Divide and Conquer)

문제를 작은 2개의 문제로 분리하고, 더 이상 분리가 불가능 할 때 처리한 후 합치는 전략

1. 합병 정렬

분할 정복 알고리즘을 이용하며, 최선과 최악이 같은 안정적인 정렬 알고리즘

 O(N log N)의 시간복잡도를 가짐

2. 퀵 정렬

분할 정복 알고리즘을 이용하며, 매우 빠르지만 최악의 경우가 존재하는 불안정 정렬

O(N log N)의 시간복잡도를 가짐

pivot을 기준으로 큰 값, 작은 값으로 나누기

 

JS에서는 array.sort() 함수를 사용

그냥 sort를 하면 아스키코드 기준으로정렬하기 때문에

 

오름차순의 경우

array.sort((a, b) => a - b);

 내림차순의 경우

array.sort((a, b) => b - a);

와 같이 작성해야 한다.

 

이진 탐색(Binary Search)

요소들이 정렬된 상태에서 가능

O(log N)의 시간복잡도를 가짐

배열이나 이진 트리를 이용하여 구현할 수 있다.

left, right, mid

---

하석재강사님

SW아카데미 특강 (클라우드 & 도커)

최고 이슈 쿠버네티스 - 도커 기반

 

클라우드 서비스의 장점

비용절약, 시간절약, 부가가치

 

컨테이너 기반 가상화

- 도커, 쿠버네티스

 

요즘 뜨는 기술

Android

React vs Vue vs Angular

Flutter vs React Native

Tensorflow

 

구글 트렌드를 이용해 검색엔진 기준 트렌드를 찾아볼 수 있다. 

 

가상화 기본개념

가상화의 레벨

- API(Application Programming Interface)

- ABI(Application Binary Interface)

- ISA(Instruction Set Architecture)

 

다음주까지 개인 노트북에 도커 깔아오기

virtualbox, 우분투 설치 -> 리눅스 환경에서는

sudo apt update

sudo apt install docker.io

sudo apt install docker-compose

---

코딩테스트 - 문자 카운팅

문제 : 문자 카운팅

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Map<String, Integer> map = new HashMap<>();

        int total = 0;	//총 단어 개수
        String max_str = "";	//가장 많이 나온 단어
        int max_num = 0;	//가장 많이 나온 단어의 횟수

        while(sc.hasNext()) {	//eof까지 입력
            String[] s = sc.nextLine().split(" |\t|\n");	//공백, tab, 개행으로 split
            for (String i : s) {
                if(i.equals("")) {	//입력된 문자열이 공백인 경우 단어 X
                    continue;
                }
                String key = i.toLowerCase();
                int value = map.get(key) != null ? map.get(key) + 1 : 1;	
                if(value > max_num) {
                    max_str = key;
                    max_num = value;
                }
                map.put(key, value);
                total++;
            }
        }
        double result = Math.round((float)max_num / (float)total * 100) / 100.0;	//소수점 두자리까지
        System.out.println(max_str + " " + result);
    }
}

Java의 map 자료형을 이용해 해결했다.

map에 key값이 존재하는 경우 value + 1을, key값이 존재하지 않는 경우 1을 value로 한 값을 map에 넣어주었다.

if(i.equals("")) {
	continue;
}

이 부분을 추가하지 않아서 틀렸었다.