뭘 배웠지?

알고리즘 3강을 보며 배운내용 3대 알고리즘중 하나 분할정복 방법의 원리, 특징, 단계를 알아봐야지 분할정복 방법 원리 순환적(recursively) 문제를 하향식(top-down) 접근 문제를 계속 분할하고, 해결된 값(해)를 결합해서 문제의 답을 구한다 특징 분학된 작은 문제는 원래 문제와 같다 입력 크키가 작아진 것 분할된 작은 문제는 독립적이다 그래서 반복해서 분할과 결과를 합칠 수 있다 처리 단계 분할: 문제를 여러 개의 작은 문제로 나누기 정복: 작은 문제를 더 분할되지 않을 크기가 되면 해를 구하기 결합: 정복된 해를 결합해서 원래 문제의 해(값)을 구한다 결합 단계가 없는 문제도 있다고 한다 분할 정복은 어디에 쓸까? 이진 탐색, 퀵 정렬, 합병 정렬, 선택 문제 이진 탐색 한 쪽만 조지는..

알고리즘 2강을 보며 배운내용 알고리즘의 정의 입출력, 명확성, 유한성, 유효성을 만족하고 효율적이어야 한다 순차탐색 처음부터 순서대로 찾는 방법 이진 탐색 반으로 나눠서 탐색 순서대로 되어있을 때 사용하면 좋다 랜덤이면 사용할 수 없다 대표적인 알고리즘 설계 기법 3가지 분할정복(divide and conquer) 동적 프로그래밍(dynamic programming) 욕심쟁이(greedy) 알고리즘 분석 정확성, 효율성 효율성 분석 메모리 양 => 공간 복잡도(space complexity) 수행 시간 => 시간 복잡도(time complexity) 메모리 적게 쓰고, 수행 시간 짧은게 좋은 알고리즘 보통 시간 복잡도만 따진다(메모리는 구하기 쉬워서) 시간 복잡도 알고리즘 단위 연산의 수행 횟수의 더해..

알고리즘 1강을 보며 배운내용 알고리즘 준비 자료구조 프로그래밍 언어 능력 수학적 능력 이 있으면 잘 할 수 있다 컴퓨터 과학 컴퓨터로 문제를 해결하기 위한 학문 즉 알고리즘은 문제 해결을 위한 효율적인 레시피 컴퓨터로 문제를 풀기위해 알고리즘이 필요하다 자료구조 컴퓨터에서 데이터 사이 논리적 관계 표현, 조직화 자료구조, 알고리즘을 잘 이용하면 좋은 프로그램 만들 수 있다 기본 자료구조 선형 한 줄로 줄 세울 수 있는 자료구조 배열, 연결리스트, 스택, 큐 비선형 줄 세울 수 없는 자료구조 트리, 그래프 각 자료구조의 구성과, 삽입, 삭제 방법을 알자 트리, 그래프는 익숙치 않다 모든 자료구조는 배열 혹은 연결 리스트로 구현한다 아~ 단순해서 좋다 트리 노드의 차수: 각 노드가 가지고 있는 자식 노드 ..

그래프 정점: 여러가지 특성을 가지는 객체 간선: 정점들 간의 관계 그래프 종류 무방향그래프: 정점간 방향이 없는 그래프 방향 그래프: 정점간 방향이 있는 그래프 그래프 특징 자기 자신을 향하는 간선은 없다 중복된 간선은 없다 그래프 표현 방식 인접행렬 - 무방향 그래프 대각선 기준으로 대칭이다 가중치 없을 때 0, 1로 표현 인접행렬 - 무방향 그래프 feat. 가중치 가중치 있어서 가중치 인접행렬 - 방향 그래프 인접행렬 - 방향 그래프 feat 가중치 # 그래프 표시 # Dictionary graph = {0: {1: 5, 2: 1, 3: 1}, 2: {1: 4}, 3: {0: 3}} # List graph = [[0, 5, 1, 1], [0, 0, 0, 0], [0, 4, 0, 0], [3, 0,..

엘리스 알고리즘의 정석에서 배운 내용 알고리즘 유한성 무한루프는 알고리즘이 아니다 명확성 입력 출력 효과성 재귀호출 함수가 자기 자신 호출 왜 사용할까? 수학적 귀납법 모든 자연수 n에 대해 n!

자바스크립트로 알고리즘 문제를 풀 때 프로그래머스 같은 곳이 아니라면 직접 입력을 구현이 필요하다 몇 가지 방법을 사용해봤는데 그 중에서 자주 사용하는 것을 까먹기 전에 기록 해놓아야겠다 3가지를 주로 사용했다 최근 것부터 살펴보면 readline 방법 1 readline 방법 2 fs 방법 1번은 엘리스 코딩 하며 2번은 엘리스 코딩 테스트를 준비하며 3번은 백준을 할 때 사용했던 것 1번 readline 방법 1 이 방법은 엘리스 코딩에서 배우다가 밑에 나올 2번 방법으로 답이 안나오는 문제가 1개 있었다 그 문제를 풀기위해 변형했다 터미널에 입력을 나가기 위해 컨트롤 + C 혹은 컨트롤 + D 를 눌러줘야된다 답안 제출시에는 자동으로 된다 const readline = require('readlin..

알고리즘 공부하며 배운내용 구름 - Binary Search 이진 탐색으로 찾고 싶은 수를 찾자 이진 탐색 알고리즘 리스트의 중간의 값을 임의로 선택, 찾고자 하는 값과 비교 만약 찾고자 하는 값이 크면(mid target), 중간이 가장 큰 값이 된다. 검색이 반복될 때 마다 값을 찾을 확률은 2배가 된다. 속도가 빠르다 단점은 정렬된 리스트에만 사용할 수 있다. 들어오는 값 첫 줄에 배열의 크기 둘 째줄에 수가 오름차순으로 셋 째줄에 찾고자 하는 수 예) 5 1 5 7 9 10 9 구하고 싶은 값 찾고하 하는 값이 들어온 수에서 몇 번째에 있는지 출력 예) 4 생각 구름 설명대로 찬찬히 따라가보자 코드 오늘도 ..

알고리즘 공부하며 배운내용 구름 - 근묵자흑 신기하게도 숫자를 한 곳에 모아놓으니 근묵자흑처럼 작은 숫자로 변한다고 한다. 1부터 N까지 수열이 주어지고, 연속된 K개를 선택할 수 있다. 최소 몇 번을 해야 다 같은 1이 되겠는가 물어보는 문제 들어오는 값 첫 줄에 수열의 숫자 N, 연속해서 선택할 수 있는 K가 주어진다. 둘 째줄에 수열이 들어온다. 예) 4 3 2 3 1 4 구하고 싶은 값 최소 몇 번 선택을 해야되는지 출력 예) 2 생각 무슨 규칙이 있을 것 같아서 밑의 작업을 했다. 3 3 => 1 4 3 => 2 5 3 => 2 6 3 => 3 7 3 => 3 8 3 => 4 9 3 => 4 시간을 꽤 썼지만 찾았다. 이 시간이 다음엔 더 빨라지기를 밑에 수열은 전혀 필요없었다. 코드 // Ru..

알고리즘 공부하며 배운내용 Node 입출력으로 영원히 고통받을 줄 알았는데 방법을 찾았다!!! 방법 => 전 포스트 링크 백준 2750번 - 수 정렬하기 들어온 내용을 오름차순으로 한 줄씩 출력하는 간단한 문제다. 들어오는 값 첫 줄에는 숫자 전체 개수가 들어오고, 둘 째줄부터 오름차순할 숫자가 들어온다. 예) 5 5 2 3 4 1 구하고 싶은 값 들어온 숫자를 오름차순으로 한 줄씩 출력 예) 1 2 3 4 5 코드 const readline = require('readline') const rl = readline.createInterface({ input: process.stdin, output: process.stdout }) let input = [] rl.on('line', function(li..

알고리즘 공부하며 배운내용 백준 2751번 - 수 정렬하기 오름차순으로 정렬한다. 들어오는 값 첫 줄에 전체 숫자 개수 N, 둘째 줄부터 N개의 숫자 중복된 숫자는 안들어온다. 예) 5 5 4 3 2 1 구하고 싶은 값 오름차순 정렬 예) 1 2 3 4 5 생각 병합정렬로 풀어보자 코드 첫 번째 코드 - 메모리 초과 병합 정렬 방법 병합 정렬 코드가 메모리 초과로 안된다 다른 정렬로 해야겠다 const fs = require('fs') let input = fs.readFileSync('/dev/stdin').toString().split('\n') let [N, ...order] = input.map(Number) order = mergeSort(order) function mergeSort(arr) ..