3일 차 배운 것 정리 (1)

자료구조와 알고리즘

1. 자료구조와 알고리즘이 중요한 이유

1-a. 자료구조와 알고리즘이란 (d)

• 재료선택 → 도구선택 → 레시피 → 요리완성
• 재료는 데이터
• 도구는 자료구조
• 레시피는 알고리즘
• 요리는 소프트웨어, 요리사는 개발자, 먹는사람은 사용자

자료구조란 메모리를 효율적으로 사용하며, 빠르고 안정적으로 데이터를 처리하는 것이 목표 상황에 따라 유용하게 사용될 수 있도록 특정구조를 이룸

• 종류 - 스택, 큐, 그래프, 트리

알고리즘이란 특정 문제를 효율적이고, 빠르게 해결하는 것을 목표로 정해진 일련의 절차나 방법을 공식화하여 표현한 것

• 종류 - 이진탐색, 최단거리, ...

1-b. 중요한 이유

• 기초 코딩 능력 - 코딩능력, 논리적사고, 문제해결능력

• 전문 분야 지식 - 프론트,백엔드 분야별 특화지식, 깊이있고 최신트렌드에 대한 지식

• 기본 CS 지식 - 운영체제, 네트워크. 컴퓨터공학지식, 예외사항 대처 가능

• 논리적 사고: 논리적으로 해결가능한 방법인지 판단

• 전산화 능력: 사고한 것을 코드로 표현하는 능력

• 엣지케이스 탐색

2. 자료구조의 종류 (완료)

2-a. 자료구조 선택에 무엇은 고려해야하는가

• 현실에서의 수행 프로세스 고려
• 영화고르기 → 줄서기 → 좌석선택 → 비용지불

• 소프트웨어에서 처리 프로세스
• 영화를 검색 → 트라이 자료구조
• 고객이 많은 경우 줄을 서야한다. → 큐(Queue)
• 고객은 좌석을 선택할 수 있어야한다. → 해시태이블(HashTable)

2-b. 자료구조의 종류

단순구조 - 정수, 실수, 문자열, 논리

선형구조 - 배열, 연결리스트. 스택, 큐

한 원소 뒤에 하나의 원소만이 존재하여 나열된 형태

비선형구조 - 트리, 그래프

원소간 다대다 관계를 가지는 구조

3. 시간복잡도

3-a. 우리는 프로그램의 성능을 정확히 알 수 있는가?

• 선형시간 < 로그시간 < 선형시간 < 선형지수시간 < 2차시간 < 지수시간 < 팩토리얼시간

• 빅오표기법의 상수와 계수가 없는 이유
• 빅오표기법은 점근적 표기법을 따르기 때문에
• 계수 법칙 : n이 무한에 가까울 수록 상수 k의 크기는 의미가 없다.
• 합의 법칙: 빅오 끼리는 더해질 수 있다.
• 곱의 법칙: 빅오 끼리는 곱해질 수 있다.

• 실제 성능을 측정하는 방법
• Date객체를 이용하여 시작과 끝시간 빼서 계산

4. 배열

4-a. 배열이란

배열은 연관된 데이터를 연속적인 형태로 표현한 자료구조 각 원소들은 순서대로 번호(index)를 가지게 된다.

5. 연결리스트

5-a. 연결리스트란?

각 요소를 포인터로 연결하여 관리하는 선형 자료구조 요소(노드)는 데이터 영역과 포인터 영역으로 구성

• 메모리 저장방식의 차이
배열은 메모리상에서 연속적으로 저장되지만, 링크드리스트는 포인터 주소값을 통해 공간에 제약없이 존재

• Singly Linked List



• 탐색 O(n)
• 방문노드의 데이터영역과 찾는 값을 비교
• 다르다면 포인터 영역에 따라 다음 노드로 이동하여 반복
• 추가 O(1)
• 추가노드의 포인터영역을 다음 노드로 지정
• 이전노드의 포인터영역을 추가 노드로 지정
• 삭제 O(1)
• 이전 노드의 포인터를 다음노드로 지정
• 삭제 노드의 포인터 삭제

• Doubly Linked List



• 추가
• 추가노드의 다음포인터를 다음노드로 변경
• 다음노드의 이전포인터를 추가노드로 변경
• 이전노드의 다음포인터를 추가노드로 변경
• 추가노드의 이전포인터를 이전노드로 변경
• 삭제
• 이전노드의 다음포인터를 다음노드로 변경
• 다음노드의 이전포인터를 이전노드로 변경
• 삭제노드 삭제

• Circular Linked List (환영 링크드리스트)



• 탐색종료 조건이 필요함

6. 스택

6-a. 스택이란

Last In First Out을 가지는 선형 자료구조. 가장 최근에 들어온 것이 가장 먼저 나간다.

• 함수호출은 대표적인 스택 자료구조이다.

• Array의 push 및 pop을 통해 스택을 구현할 수 있다.

6-b. 실습

• 💻올바른 괄호 문제 스택을 사용하여 풀어보기
풀이방법
• 오픈브라켓을 스택에 쌓는다 → count를 +1 해준다.
• 클로즈브라켓일 경우 스택에서 제거한다 → count -1 을 해준다
• count가 마이너스가 된다면, 없는 스택을 빼려고 한 것이므로 false를 리턴해준다.
나의풀이

function solution(s){
    let open_braket_cnt = 0;
    
    for(let i = 0; i < s.length; i++){
        if(open_braket_cnt < 0) return false;
        
        if(s[i] === '('){
            open_braket_cnt += 1;
        } else {
            open_braket_cnt -= 1;
        }
    }
    return (open_braket_cnt === 0) ? true : false;
}

해설 참고
💡
전체적인 로직은 같았고, 변수명을 추상화하고, 불필요한 삼항연산제 제거 필요

function solution(s){
    let count = 0;
    
    for(let i = 0; i < s.length; i++){
        if(count < 0) return false;
        
        if(s[i] === '('){
            count += 1;
        } else {
            count -= 1;
        }
    }
    return (count === 0)
}