Computer Science 156

알고리즘 :: From Here To Here, 슬라이딩 윈도우

알고리즘 공부하며 배운내용 여기서부터 여기까지(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] //..

인공지능 강의 5화 :: 지식기반 시스템, 선언적 지식, 전문가 시스템

인공지능 강의 5화를 보며 배운내용 키워드 지식기반 시스템: 특정 분야의 지식을 쉽게 접근할 수 있는 형태로 컴퓨터에 체계적으로 축적, 사용 - 핵심 구성요소: 지식베이스와 추론기관 절차적 지식: 어떤 경우에 무엇을 어떻게 할 것인가에 대한 지식, 지식 사용에 대한 제어 정보가 지식 자체에 내포, 추론의 적합성이나 지식 획득의 효율이 안좋다. 선언적 지식: 상호 독립적, 단편적인 지식을 나열해 놓은 형태, 추론기관이 별도로 존재, 추론기관 프로그램에 의해 지식이 활용 지식 베이스: 대상 분야의 지식을 포함한 문제풀이에 필요한 지식을 체계적으로 저장하는 지식기반 시스템의 구성 요소 추론기관: 지식 베이스 내의 지식을 이용하여 추론, 결론을 제시하는 지식기반 시스템의 구성 요소 - 규칙 해석기 + 스케쥴러가..

선형대수 강의 6화 :: 크래머, 행렬식 이용 역행렬, 삼각형 면적

선형대수 6화를 듣고 배운내용 크래머 공식(Cramer's rule) 일차연립방정식이 방정식의 수와 미지수의 수가 서로 같을 때, 행렬식을 이용해서 각 미지수의 해를 구하는 해법 행렬식 구하는 법을 알아야겠다. 역행렬 구할 때 기본행연산 방법이 사람이 하기에 좋고 행렬식을 이용하는 방법이 컴퓨터로 계산할 때 편하다 소행렬식(minor): n-1차 행렬식값 수반행렬(adjoint matrix) 여인수 행렬의 전치 A = n차 정방행렬 B = A의 여인수행렬 BT = A의 수반행렬 역행렬 구하는 공식 A-1 = adjA / |A| 행렬식과 수반행렬 구하는 방법을 알면된다. 삼각형의 면적 구하기 삼각형 세 점 (x1, y1) (x2, y2) (x3, y3)을, 3차 행렬로 만들어 행렬식을 구해주면 평행사변형 ..

알고리즘 :: node.js 입출력 방법 #백준 #구름

알고리즘 공부하며 배운내용 하단에 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..

프로그래밍언어론 강의 5화 :: 구문 분석

프로그래밍언어론 5화를 듣고 배운내용 프로그램 분석 문자 => 어휘 => 구문 토큰: 어휘 분석을 통해 얻어지는 것 => 연산자, 구분자, 식별자, 예약어 등 구문 분석 유도 구문 규칙을 이용해서 프로그램을 만드는 과정 유도가 가능하면 문법적 오류가 없는 유효한 프로그램 파스 트리(Parse Tree) 유도를 트리 형태로 나타낸 것 구조 루트 노드: 시작 비단말 기호 비단말 노드: 비단말 기호 단말 노드: 단말 기호 끝에 있다 그래서 단말 노드라 그런다 비단말은 밑에 자식 노드가 있다는 뜻이겠네 단말 노드를 왼쪽부터 오른쪽으로 차례로 나열하면 프로그램이 된다. 파스트리가 존재하면 구문에 부합하는 표현 존재하지 않으면 오류 있는 표현 모호한 문법 동일한 표현에 대해 서로 다른 파스 트리가 만들어지는 문법 ..

인공지능 강의 4화 :: 게임트리, α-β 가지치기, 몬테카를로

인공지능 강의 4화를 보며 배운내용 KEYWORDS 최대최소 탐색: 교대로 수를 두는 2인 게임에서 나의 수와 상대의 응수를 나타내는 게임 트리에서 수를 결정하기 위한 탐색 기법 α-β 가지치기: 최대최소 탐색트리의 불필요한 가지를 잘라내서 탐색의 성능을 높이기 위한 알고리즘 몬테카를로 트리 탐색: 게임과 같은 의사결정 문제의 해결을 위해 무작위 표본화를 바탕으로 구성되는 탐색트리로부터 최적의 선택을 하기 위한 경험적 알고리즘 A* 알고리즘: 다음 확장할 노드를 결정할 때 그 노드까지 도달하는 경로비용과 그 노드로 부터 목표 노드에 도달하기 위한 경로비용 예측치의 합이 최소인 노드를 선택하여 탐색 최대최소 탐색(minimax search) 나 =>내가 둘 수 있는 가장 유리한 수(Maxmize) 상대 =..

728x90