데이터 구조 + 알고리즘 소개 [1부]

여러분! 기술 인터뷰에서 자주 사용되는 인기 있는 코드 문제를 다루는 시리즈를 시작하려고 합니다. 제 의도는 이 시리즈를 주간 시리즈로 만들고 댓글에서 솔루션을 공유할 수 있도록 하는 것입니다. 참고로 이러한 문제 중 많은 부분은 Hackerrank , Leetcode , InterviewCake 및 Codewars 과 같은 웹 사이트에서 가져온 것입니다. (등...)

데이터 구조란 무엇입니까? 음, 컴퓨터/프로그램에서 효과적으로 사용할 수 있도록 데이터를 구성하는 특별한 방법입니다. 그렇다면 알고리즘이란 무엇인가? 입력 인스턴스(문제)를 입력으로 취하고 문제(인스턴스)에 대한 출력을 생성하는 단계별 절차입니다.

경고: 코딩 또는 데이터 구조/알고리즘 질문을 받게 될 것이라고 보장할 수는 없지만 실제 인터뷰에서 예상할 수 있는 질문 종류에 대한 아이디어를 제공할 것입니다.

데이터 구조 및 알고리즘에 대한 경험이 전혀 없는 경우 인터뷰 케이크, Udemy Colt Steele 또는 Freecodecamp를 방문하여 기본 사항을 숙지해야 합니다.

내 의도는 이 시리즈에서 다음을 다루는 것입니다.

빅오 🔗

어레이🔗

연결된 목록🔗

스택 및 대기열🔗

해시🔗

분류🔗

트리(이진 검색 트리)🔗

그래프🔗

시스템 설계(추가)🔗

참고: 챌린지는 다음과 같이 표시됩니다 => 예: Big-O(제목) [난이도]


음... 잠깐만요, Alg의 종류는요?

어 그래. 잊어버리기 전에 모든 알고리즘은 다음 패러다임 중 하나로 분류할 수 있습니다.

Brute Force 알고리즘 - 가능한 모든 솔루션을 확인하고 최상의 솔루션을 선택합니다.

동적 프로그래밍 Alg. - 이전의 모든 솔루션을 기반으로 문제를 해결합니다.

Greedy - 미래의 결과에 관계없이 현재 최선의 솔루션을 선택합니다.

Divide & Conquer - 문제를 더 작은 문제 집합으로 나누어 해결하고 마지막에 전체 솔루션을 얻습니다.

첫 게스트 Big O를 소개합니다.

빅 오

코드의 확장성을 결정할 수 있으며, 이는 코드의 효율성을 측정하는 방법을 나타냅니다. 코드의 성능을 정확히 어떻게 계산할 수 있습니까? 런타임 속도인가요? 복잡성/단순성? 컴퓨터의 차이에 관계없이 확장성을 어떻게 다시 계산합니까? 우리는 입력 크기가 얼마나 큰지, 이것이 함수나 알고리즘을 얼마나 느리게 하는지(알고리즘 효율성) 측정할 수 있습니다.


요소(입력)의 수가 증가함에 따라 얼마나 많은 작업을 수행해야 합니까?

선형 시간

const yoda = ['Baby Yoda']
const friends = ['Mandolorian', 'Luke', 'Leila', 'Clone A','Baby Yoda','Dark Vader']
const large = new Array(10000).fill('Baby Yoda')

const findBabyYoda = arr=> {
    for(let i=0; i < arr.length; i++){
      if(arr[i] === 'Baby Yoda'){
        console.log('FOUND YODA!')
      }
    }
}

findBabyYoda(friends) // O(n) - Linear time
// The num of outputs increases proportionally with the num of inputs

일정한 시간

const pineapples = [0,1,2,3,4,5]

const logFirstsPineapples = pineapples => {
    console.log(pineapples[0])  // O(1) - constant time
    console.log(pineapples[1])  // 0(1) - constant time
}


logFirstsPineapples(pineapples) // O(2) 

1- 아래 함수의 Big O는 무엇입니까? Solution

const firstChallenge => input => {
  let a = 10;
  a = 50 + 3;

  for (let i = 0; i < input.length; i++) {
    ramdomFunction();
    let stranger = true;
    a++;
  }
  return a;
}

2- 아래 함수의 Big O는 무엇입니까? Solution

function secondChallenge(input) {
  let a = 5;
  let b = 10;
  let c = 50;
  for (let i = 0; i < input; i++) {
    let x = i + 1;
    let y = i + 2;
    let z = i + 3;

  }
  for (let j = 0; j < input; j++) {
    let p = j * 2;
    let q = j * 2;
  }
  let whoRu= "I don't know";
}

Big(O)를 조금 더 잘 만드는 데 도움이 되는 규칙:

최악의 경우:

자원

Big 0 Spreadsheet

너 아직도 나와 함께 있니?

첫 번째 정류장을 마칠 수 있게 해주셔서 감사합니다. 오늘 본 내용은 매우 기본적인 것 같았지만 이것은 시작일 뿐이며 이 주제를 진행함에 따라 더욱 어려워질 것입니다. 이 주제와 관련하여 질문, 제안 또는 논의할 사항이 있으면 아래에 의견을 말하십시오.

댓글에서 뵙기를 바랍니다!