오늘 목표는 오전에 주어진 강의를 TIL 작성까지 완료하고 이후에는 개인적인 공부를 하는 것이다. 교육과정에서 커리큘럼을 제공해주기에 따라가기만 해보자라고 생각했는데 CS지식, 코테, 프로젝트 등 개인적으로 부족한게 좀 있어서 초반에 상대적으로 여유가 있을 때 뭔가를 더 해야겠다는 생각이 강하게 들었다.
데브코스 FE 3일차
자료구조와 알고리즘
중요한 이유?
요리와 비유할 수 있는데 요리에서 도구와 레시피가 중요하듯 자료구조 도구를 이용해서 적합한 알고리즘 레시피를 사용해야 목적에 맞는 소프트웨어를 개발할 수 있다.
자료구조
메모리를 효율적으로 사용하여 빠르고 안정적으로 데이터를 처리하고자하는 목표로 만들어진 특정한 구조
스택, 큐, 그래프, 트리 등알고리즘
특정 문제를 효율적이고 빠르게 해결하고자 하는 방법을 표현한 것기초 코딩 능력, 전문 분야 지식, 기본 CS 지식을 회사에서는 중요하게 본다.
그 중에서 기초 코딩 능력을 기르기 위해 자료구조와 알고리즘을 공부한다.일머리가 좋은 사람들은 아래 3가지를 잘 한다.
1. 논리적 사고
2. 전산화 능력
3. 엣지 케이스 탐색
자료구조 종류
전산화를 하려면 일단 현실에서 진행되는 프로세스를 정리해야 한다.
강의에서도 예시가 있었지만 한번 생각해보았다.
놀이동산까지 지도를 통해 최단 경로로 찾아간다 -> 그래프
놀이기구에 탑승하기 위해 줄을 선다 -> 큐
크롬 뒤로가기 기능 -> 스택
조직도나 족보 -> 트리
정수 실수 등 단순구조가 있고 그렇지 않은 구조에 선형, 비선형 구조가 나뉜다.
선형 구조는 자료형이 선형으로 나열되어 있다. 한 원소 앞뒤로 하나의 원소만을 가지고 있다. 배열, 스택, 큐, 리스트
비선형 구조는 다대다 관계를 가지고 있고 계층이나 망의 구조를 나타내기 좋다. 트리, 그래프
시간 복잡도
우리는 프로그램의 성능을 정확히 알 수 있을까?
아니라고 생각한다. 물론 대략적으로는 알 수 있겠지만 정확히는 알기 힘들지 않을까..
아닌게 맞았다! 고려해야할 요소가 너무 많다. ex)입력 크기, 디바이스 성능, 최적화, 로직 등등..그래서 해결책으로 나온 것이 Big-O notation이다.
보통 아래의 케이스들이 가장 자주 볼 수 있었던 케이스이다.
//O(n) for (let i = 0; i < n; i++) { // ... } // //O(log n) for (let i = 0; i < n; i *= 2) { // ... } // //O(n log n) for (let i = 0; i < n; i++) { for (let j = 0; j < n; j *= 2) { // ... } // ... } // //O(n^2) for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { // ... } // ... }하지만 빅오 표기법에서 상수를 반영하지 않는 이유는 뭘까?
여러 이유가 있었지만 결국 핵심 첫 번째는 상수항은 무시한다.
ex) for문이후 또 for문이 나오는 경우 O(n + n)이지만 결국 O(n)으로 똑같다.
두 번째 핵심은 가장 큰 항 이외에는 무시하는 것이다.
ex) for문이 있고 2중 for문이 있으면 O(n^2)으로만 표기JS에서 성능 측정하는 방법
Date로 시작과 끝의 차이를 통해 구해준다!console.log("Begin!"); const start_time = new Date().getTime(); const cnt = 100000; let temp = 0; for (let i = 0; i < cnt; i++) { temp = temp + i; } // const end_time = new Date().getTime(); console.log(end_time - start_time); console.log("end");cnt = 100000인 경우 매우 짧아서? 그런지 이렇게 금방 끝났다.
cnt = 1000000000으로 하니 좀 시간이 걸렸고
cnt = 10000000000000으로 했을때는 꽤 기달려도 안나와서 강제 종료 해줬다.
배열
배열이 없었다면? 변수를 여러번 생성하면 된다! 하지만 비효율적이다.
일반적으로 배열은 고정적인 크기를 가지고 있지만 JS나 파이썬 루비 같은 스크립트 언어는 동적으로 크기가 바뀔 수 있다.원소의 Index를 안다면 O(1)으로 빠르게 찾을 수 있고
원소가 삭제되면 해당 index에 빈자리가 생긴다.배열에서 원소를 삭제하는 프로세스
1. 특정 배열의 원소를 삭제한다.
2. 삭제한 배열 뒤에 존재하는 원소들을 한칸씩 당겨준다.
3. 최악의 경우 O(n)만큼 소요된다.배열에서 요소를 추가하는 프로세스
1. 추가하고자 하는 위치 뒤에 있는 원소들을 한칸씩 뒤로 미룬다.
2. 위치에 추가하려는 원소에 데이터를 추가한다.
3. 이때도 O(n)만큼 소요된다.
이러한 특징 때문에 삭제와 추가가 반복되는 경우 배열 사용을 줄이자!연습한 코드
//배열 생성 방법 let arr1 = []; console.log(arr1); // let arr2 = ["a", "b", "c", "d", "e"]; console.log(arr2); // let arr3 = new Array(20).fill(7); console.log(arr3); // let arr4 = Array.from("KOREA"); console.log(arr4); // let arr5 = Array.from({ length: 50 }, (val, index) => { return index + 1; }); console.log(arr5); // //배열 앞 뒤 요소 추가 삭제 const arr = [1, 2, 3, 4, 5]; arr.push(7, 8, 9); // 배열 뒤에 추가 O(1) arr.unshift(0); // 배열 앞에 추가 O(1) console.log(arr); arr.pop(); //배열 맨 뒤 원소 삭제 O(1) arr.shift(); //배열 맨 앞 원소 삭제 O(1) console.log(arr); // arr.splice(5, 0, 77); // 5번째 인덱스에 77추가 O(n) console.log(arr); // arr.splice(4, 1); // 4번째 인덱스 값 삭제 O(n) console.log(arr);이외의 특징
동적이다, 그리고 객체의 특징을 띄고 있어서 원소가 숫자가 아닌 문자열이나 다른 값도 들어갈 수 있다.
참고자료
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/from
https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/splice
연결 리스트
각 요소(노드)를 포인터로 연결하여 관리하는 선형 자료구조
따로 페이지를 파서 공부하고 정리하는게 나을 것 같다. 특히 코드로 구현하며 공부해 보고자 한다.
과제
단일 연결리스트
이중 연결리스트
선형 연결리스트
!링크
스택
프링글스 통처럼 처음 들어간 요소가 맨 나중에 나오는 FILO(First In Last Out)의 개념을 가진 선형 자료구조이다.
JS에서는 배열이 동적이기에 배열을 통해서 간단하게 구현할 수 있다.
특히 push(), pop() 메서드가 있기에 더 쉽다.
문제 풀이
프로그래머스 Lv.2 올바른 괄호 JavaScript 풀이
이전에 풀었던 코드와 오늘 풀이한 코드를 모두 첨부했다. 개인적으로 오늘 풀이한게 더 마음에 든다.
궁금증
- JS에서 연결리스트를 더 간단하게 구현할 방법은 없을까?
오늘 후기
확실히 길다..길어... 짧은 기간에 내용을 압축해서 학습하다보니 혼자 공부해야하는 시간이 압도적으로 많다.
빡센 과정이라는게 시작부터 체감된다. 긍정적인 스트레스이긴 한데 오랜만에 경험하니 풀어주지 않으면 안좋아 질 것 같다. 원래 주말에도 풀 공부를 달릴생각을 했었는데 리프레쉬할 수 있는 시간을 조금씩 가지면서 진행해야겠다. 퍼지면 나만 손해다..!
