알고리즘

    코테/자료구조, 알고리즘

    [알고리즘] 최대공약수, 최소공배수 (유클리드 호제법)

    1. 최대 공약수 최대공약수, 최대공배수를 사용하려면 소인수분해를 사용해야 합니다. 하지만 숫자가 크면 클수록 소인수분해의 횟수는 점점 증가하기 때문에 유클리드 호제법을 사용하면 시간복잡도는 단축이 됩니다. 유클리드 호제법은 명시적으로 기술된 가장 오래된 알고리즘으로, 무려 기원전 300년에 쓰여졌다고 합니다. 여기서 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타냅니다. 일반적으로 최대공약수를 구하는 가장 쉬운 방법은 2부터 모든 정수로 나누어 보는 방법이 있을 것 같은데 이의 경우 모든 정수를 나눠야 하므로 시간 복잡도는 O(N)이 됩니다. 유클리드 호제법을 사용한다면 때 a % b이 0이 될 때까지 반복을 해주기 때문에 시간 복잡도를 O(Log N)으로 줄..

    코테/자료구조, 알고리즘

    [알고리즘] 소수 판별식 (에라토스테네스의 체)

    1. num 사이의 숫자를 모두 나눠서 확인하는 방법 function isPrime(num) { for(let i = 2; num > i; i++) { if(num % i === 0) { return false; } } return num > 1; } 2. num 제곱근 까지만 확인 하는 방법 function isPrime(num) { let sqrt = parseInt(Math.sqrt(num)); // num에 제곱근 후 소수점 버림 if (num === 1) { return false; } if (num === 2) { return true; } if (num % 2 === 0) { return false; } // 1, 2에 대한 경우의 수와 2의 배수는 미리 걸러냄 for (let i = 3; ..

    [알고리즘] Algorithm with Math / 정규표현식
    코테/자료구조, 알고리즘

    [알고리즘] Algorithm with Math / 정규표현식

    컴퓨터가 단순하게 연산하기 때문에, 기본적인 컴퓨터 과학과 수학은 통하는 부분이 있습니다. 그러므로 수학을 학습하는 것은 프로그래밍의 기본을 탄탄히 하는 일입니다. 그러므로 수학은 프로그래밍에 많은 도움이 됩니다. 알고리즘 파트에서 다루는 수학은 중학교 수준의 수학입니다. 알고리즘 테스트(코딩 테스트)를 해결하는데 필요한 최소한의 수학을 다룹니다. 프로그래밍을 위한 최소한의 수학이기 때문에 학습해야만 하는 내용입니다. 알고리즘 문제에서 자주 다루는 최소한의 수학만 익혀, 적재적소에 활용할 수 있는 능력을 기르는 것이 가장 큰 목표입니다. 최근 코딩 테스트에 등장하는 알고리즘 문제는 단순히 "너 이 알고리즘 알아?"라고 물어보지 않습니다. 요즘 출제되는 문제는 "특정 방법을 사용해서 풀어 볼래?"라고 물어..

    [알고리즘] Time Complexity / greedy Algorithm / implementation
    코테/자료구조, 알고리즘

    [알고리즘] Time Complexity / greedy Algorithm / implementation

    알고리즘은 문제를 해결하는 최선의 선택입니다. 1. 문제를 이해하고 2. 전략을 세우고 (수도코드, 흐름의 그림, 페어에게 설명) 3. 이에 따라 코드 작성으로 문제 해결 개발자로서 만나게 될 대부분의 개발 태스크는 알고리즘 문제만큼 어렵지 않습니다. 그러나 새로운 문제에 봉착했을 때, 전략과 알고리즘을 구상하여 실제로 코드로 구현해 보는 경험은 매우 중요합니다. 많은 기업에서 주니어 개발자를 채용할 때에, 알고리즘 풀이를 통해 지원자의 역량을 가늠합니다. 알고리즘 풀이를 통해 지원자의 로직과 문제해결 방식을 확인하고, 이를 통해 개발자다운 사고방식을 보게 된다고 합니다. 1. Time Complexity 알고리즘 문제를 풀때 해결하는것도 가장 중요하지만 효율적인 알고리즘을 찾는 것 또한 중요합니다. 효..

    [알고리즘] Graph / Tree / BST
    코테/자료구조, 알고리즘

    [알고리즘] Graph / Tree / BST

    1. Graph 컴퓨터 공학에서 이야기 하는 자료구조 그래프는 전혀 다른 모습을 가지고 있습니다. 자료구조의 그래프는 마치 거미줄처럼 여러개의 점들이 선으로 이어져 있는 복잡한 네트워크 망과 같은 모습을 가지고 있습니다. 그래프는 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조입니다. 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있습니다. 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어집니다. 하나의 점을 그래프에서는 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge) 이라고 합니다. 알아둬야 할 그래프 용어들 무(방)향그래프(undirected graph): 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는것도 가능합니다. 단방향(directed) ..

티스토리툴바