뭘 배웠지?

알고리즘 공부하며 배운내용 여기서부터 여기까지(From here to here) 재밌는 문제다. "여기서부터 여기까지 전부 주세요"를 시전 하기 위한 알고리즘 진열된 상품의 가격이 이렇다(단위: 만원 생략) 4, 2, 6, 5, 8, 6, 2, 4, 2, 1 나는 정확히 20만원 어치 살거다 그럼 8부터 4까지 달라고 하면 된다. 4, 2, 6, 5, [8, 6, 2, 4,] 2, 1 But 정확히 10만원 어치 사는 방법은 없네 INPUT - 제공되는 것 살 금액 M과 금액 리스트가 두 줄로 나온다, 이렇게 20 4 2 6 5 8 6 2 4 2 1 OUTPUT - 출력 결과 정해진 금액 M에 구매가능 하면 밑의 텍스트 출력 "Could you get me from here to here?" 못 사는 경..

알고리즘 공부하며 배운내용 가로등 설치 길 시작점부터 가로등이 설치되어 있다. 가로등을 설치해서 각 가로등 사이의 길이를 같게 만들자 0m 3m 9m 12m 이 경우는 6m에 가로등 설치해주면 각 사이가 3m가 되서 같아지겠네 간단히 생각해보면 각 가로등간의 거리를 구해서 거리를 비교해볼 수 있을 것 같다. 하지만 여기서 최대공약수를 이용하면 된다고 한다. 일정한 간격을 유지하게 한다는 말은 규칙이 생긴다는 말 같다. 3 6 9 12 여기서 간격은 3m 그럼 최대공약수는? 3이다 다시 4 8 12 16 여기서 간격은 4m, 최대 최대공약수는? 4다 그래서 최대공약수를 구하고, 배수를 해주며 빠진곳에 가로등을 설치해주면 되는 것 같다. 더 나아가 최대공약수를 구하는 방법은 약수를 구하고 제일 큰 녀석을 구..

골드바흐의 추측 골드바흐 위키 => 링크 아마도 골드바흐가 한 추측이고, 증명이 확실히 안됬기에 추측이라 그러겠지. 이 추측은 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다는 것 예를 들어 4 = 2 + 2 6 = 3 + 3 8 = 3 + 5 10 = 5 + 5 입력값 4 6 8 이런식으로 짝수가 공백으로 구분되서 들어온다 소수의 배열은 준다. 출력값 2 2 3 3 3 5 각 짝수에 적용되는 소수의 쌍을 한 줄씩 보여준다. 만약 해당 짝수의 소수 쌍이 여러 개라면, 두 소수의 차이가 적은 것을 출력 방법 1 - 생각하기 간단한 방법 이중 for문을 돌려서 각 값들을 더해보고 짝수와 값을 비교해본다. 예를들어 짝수가 10이면 i = 2, j = 2 부터 시작해서 i = 2, j = 3 i = 2, j..

거스름돈 개수 세기 큰 동전부터 없애주면 될 것 같다 // VSCode에서 JavaScript 테스트 하기위한 코드 // 메모장에 테스트 케이스 넣고 change.txt로 저장했다. let fs = require('fs'); let input = fs.readFileSync('change.txt') let num = Number(input) // 필요 변수 선언 let coins = [500, 100, 50, 10] let change = 0 // 동전 개수만큼 반복하고 for(let i = 0; i < coins.length; i++) { // 큰 동전부터 나눠주고 저장하고, 나머지하고 저장하고 change += Math.floor(num / coins[i]) num = num % coins[i] //..

알고리즘 공부하며 배운내용 하단에 3가지 링크 모두 node.js에 입출력을 하는 좋은 방법으로 이걸로 알고리즘 연습중이었다. 하지만 readline이 아니면 런타임 에러도 나는 문제도 있고, 특히 어느 교육기관 코딩테스트를 준비하는데, readline 사용해야되고, EOF 마크가 없어서 직접 close 시켜줘야 됐다. 역시 구글을 찾아다녔지만 이해하기 어려웠다. 찾은 방법은 이해가기 살짝 어려웠다. 그래서 끄적여본 코드는 이건데 구름에서 된다?? const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout }); let input = [] rl.on..

소수 개수 세기 알고리즘 : 에라토스테네스의 체 소수는 1과 자기 자신뿐이다. 즉 1과 자기 자신을 제외한 약수가 있으면 소수가 아니다 1. 소수를 알아낸다. 2. 소수로 나눠 떨어지는 모든 수를 소수에서 배재한다. 예를들어 1에서 100까지 소수의 개수를 확인한다면, 2부터 100까지 true로 채운다. *1은 소수가 아니라 2부터 시작 가장 작은 소수는 2이다. 2로 나눠 떨어지는 4, 6, 8, 10, 12, 14, 16, 18 .... 100을 전부 False로 바꾼다. 그 다음은 3 3도 소수다. 3으로 나눠 떨어지는 6, 9, 12, 15, 18, 21 ... 99를 false로 바꾼다. 4는 false가 들어있으니 소수가 아니다 => 생략한다. 이 과정을 100까지 반복한다. 여기서 True..

동적 프로그래밍 큰 문제의 답이 작은 문제의 답이 포함되어 있다. 분할 정복 알고리즘과 비슷하지만 속도가 빠르다, 다른점은 부분 문제의 정답을 저장한뒤 동일 문제에서 저장한 정답을 바로 계산해서 이용한다 피보나치 수의 정의 전 값과 전전 값을 더하는 피보나치 수 f(n) = f(n - 1) + f(n - 2) f(1) = f(2) = 1 f(1) = 1 f(2) = 1 f(3) = f(1) + f(2) = 2 f(4) = f(2) + f(3) = 3 그냥 재귀 알고리즘 유사코드 fib(n) { if(n == 1 or n == 2) then return 1; else return (fib(n - 1) + fib(n - 2)); } 재귀 알고리즘 사용시, 중복 호출이 굉장히 많이 발생한다 -> 비효율 중복되..

큐(Queue) 먼저 집어 넣은 데이터가 먼저 나온다 First In, First Out: FIFO 구조로 저장하는 자료구조 전단(Front), 후단(Rear)이 있다. 삽입(Enqueue) 뒤에 집어 넣는거다, 그럼 후단이 새로 들어온애로 바뀌겠지 삭제(Dequeue) 제일 먼저 들어온 녀석을 삭제하고, 그 다음 녀석이 전단이 된다. 배열로 큐를 구현할 때 문제점 앞의 것을 제거하면 나머지를 앞으로 땡겨와야한다. 그래서 배열에 큐 잘 안쓴다 순환 큐 배열의 끝과 시작이 이어진 것처럼 전단과 후단 관리 문제점 전단과 후단이 같은 위치면 비었나, 가득찼나? 해결 방법 큐 배열 생성할 때 실제 용량보다 1만큼 크게 만들어 전단과 후단 사이를 비운다 전단과 후단이 같으면 빈 상태 후단이 전단보다 1 작으면 가..

스택(Stack) 먼저 들어간 요소가 가장 나중에 나온다 Last-In, First Out: LIFO 자료구조 비행기 캐리어처럼 먼저 실으면 늦게 나오고, 늦게 실으면 먼저 나온다. 스택의 삽입 연산: push 스택의 삭제 연산: pop 스택 응용 예시 예시1) 역순 문자열 만들기 [A] [B] [C] [D] 들어올 때 [D] [C] [B] [A]가 나오도록 배열에 push 사용하듯 push(stack, A) push(stack, B) push(stack, C) push(stack, D) 꺼낼 때는 pop 이용 pop(stack) 하면 D pop(stack) 하면 C pop(stack) 하면 B pop(stack) 하면 A 이 나온다. 예시2) 시스템 스택 함수 호출과 복귀를 보면 시스템 스택이다. 예를..

리스트 동일한 값이 두 번 이상 나타날 수 있는 셀 수 있는 정렬된 값을 나타내는 자료의 구조 시퀀스(Sequence)라고도 함 종류 선형 단일 연결 이중 연결 원형 연결 선형: 순서를 가지고 있다 순차 방식으로 구현 원소를 논리적인 순서대로 연속하여 저장 원소 삽입 삽입할 빈 자리 만들기 빈 자리 이후의 원소를 한자리씩 뒤로 이동 빈 자리에 원소 삽입 원소 삭제 삭제한 자리 이후의 원소들을 한 자리씩 앞으로 이동 단점 삽입, 삭제가 비효율적 그래서 개선한 방법이 단일 연결 리스트 단일 연결: 저장할 때 그 다음 순서의 자료가 있는 위치를 데이터에 포함 각 노드는 다음 노드를 가리키는 포인터(주소 값)를 가짐 맨 앞부분은 머리(Head), 끝 부분은 꼬리(Tail) 노드 추가 앞 노드가 새 노드를 가르키..