최민철 크루님

약력

• 비전공자
• 삼성전자 임베디드 SW 입사
• 컨설팅, 코드스테이츠 2년차
• 인하대 등 겸임 교수

자료구조

자료구조란?
자료에 대한 구조 data structure
자료를 어떻게 저장하고 어떻게 조회하고 써먹을지에 대한 방법들

알고리즘이란?
how to solve
문제를 해결하는 방법
유한한 지시사항들의 집합(결국 해결을 해야 하니까 유한해야 한다)

a set of finite instructions that solve the given problem
ex. 라면을 끓이는 방법

-> 그러므로 코드 없이 문제를 풀 수 있어야 한다
코드는 우리 생각을 표현하는 도구
REM을 통해 데이터 저장

직접 실행을 하고 관찰(패턴, 특징을 찾아내야한다)
조급함을 버리고 봐야한다
BFS, DFS인지 확인하기 전에 먼저 관찰

완전 탐색(exhaustive search)
-모든 경우의 수를 빠짐없이 확인해보는 것
-시작과 끝, 순서를 생각
ex. DFS, BFS 깊이 우선, 너비 우선
- 70%

더 어렵게 나오는 건 완전 탐색만으로 풀 수 없는 방법 요구
:ex. 시간을 더 짧게 줌
1)Binary Search, Binary Search Tree
탐색 기법, 이진탐색을 적용할 수 있게 만든 자료구조
전체 모든 경우의 수를 알고 있을 때 사용할 수 있는 방법
=> up&down 같은 게임들 : 1~50 중에서 반띵해서 각각 구하는 것
2)가장 큰, 가장 적게 류의 문제 : 동적 계획법

이외 알고리즘을 알아야 하는 수준의 곳들은 안 가는 것이 좋음
왜냐 너무 어려움

기술에 있어서 거의 모든 상황은 trade-off (이해상충)
= 다른 것도 저하를 시키지 않으면서 모든 것을 다 잡을 수는 없다
그러므로 각각의 장점을 알고 이를 적재적소로 사용할 줄 알아야 한다

자주 쓰는 자료구조

스택

큐

배열은 인덱스를 관리한다

const Q = [];

let front =0;
let rear = 0;

conse enQ = node => {
Q.push(node)
rear++
}

const deQ = () => {
Q.shift()
front++
}

//front, rear를 사용해서 인덱스 관리 가능

그래프 - DFS, BFS
: 컴퓨터는 RAM에 내용을 저장하는데 성능도 안 좋고 사이즈도 작아서 이에 효율적으로 데이터를 저장하고 활용할 수 있는 방법이 중요했다.

트리는 고난이도

2시간은 고민(에디터를 키지 않는다) //생각이 정리하기 전에는 코드를 짜지 않는다!!

• 1시간 코드를 짜고
  정답/해설을 본다
  답을 보고 배우면 내게 아니라고 생각하지만 답을 이해하는 것도 공부다
  알고리즘은 문제가 더럽게 많아서 아무리 답을 봐도 모르는 문제가 더 많다
  

onst matrix = [
[0, 0, 1, 0],
[0, 1, 0, 0],
[0, 0, 1, 0],
[0, 1, 0, 0],
]

function bfs(src) {
// 첫 출발을 안다고 가정
// 출발 정점이 주어져 있음
const Q = [];

const enQ = node => Q.push(node)
const deQ = () => {
    const head = Q[0];
    Q.shift()
    return head
}
const isEmpty = () => Q.length === 0
const isVisited = Array(matrix.length).fill(false)

Q.push(src)
isVisited[src] = true;
//
while(isEmpty() === false) {
    const head = deQ();
    // if (head === 777) {
    //     answer = head
    //     break;
    // }

    // head를 기준으로 깊이 1인 정점들을 싹 다 조사하기
    for (let i = 0; i < matrix[0].lenth; i++) {
        // 조건에 맞으면 Q에 넣어야 한다.
        // 방문 여부도 함께 고려한다.
        if ( && isVisited[node] === false) {
            enQ(node)
        }
    }
}

// 답 찾았는지 확인하고
// 리턴하던가 정답 변수에 넣던가
// answer = ,,,

}