Computer Science 156

알고리즘 :: 구름 - Binary Search #JavaScript

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

알고리즘 :: 구름 - 근묵자흑 #JavaScript

알고리즘 공부하며 배운내용 구름 - 근묵자흑 신기하게도 숫자를 한 곳에 모아놓으니 근묵자흑처럼 작은 숫자로 변한다고 한다. 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..

알고리즘 :: 백준 2750번 - 수 정렬하기 #JavaScript

알고리즘 공부하며 배운내용 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번 - 수 정렬하기 #JavaScript

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

알고리즘 :: 백준 2798번 - 변형 블랙잭 #JavaScript

알고리즘 공부하며 배운내용 백준 2798번 - 변형 블랙잭 N장의 카드를 바닥에 높고, M을 외친다. 플레이어는 N장의 카드에서 3장을 선택해 M을 넘지 않고 제일 가깝게 만들어야한다. 들어오는 값 첫째 줄에 카드 개수 N, 지정값 M 둘째 줄에 바닥에 깔린 카드 예) 5 21 5 6 7 8 9 구하고 싶은 값 M을 넘지 않으면서 M에 최대한 제일 가까운 카드 3장의 합 예) 21 생각 모든 경우의 수를 따져봐야 할 듯 코드 세 번의 for문으로 전체 따져봤다 const fs = require('fs') let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n') let fl = input.shift().split(' ') let tot..

알고리즘 :: 찍먹 vs 부먹, 업그레이드 필요, 최소최대 실패

알고리즘 공부하며 배운내용 찍먹 vs 부먹 찍먹과 부먹의 선호도는 -1000부터 1000사이 정수로 표현 수가 작을수록 찍먹 선호, 클수록 부먹 선호 친구를 만날 때 마다 지금까지 만났던 친구의 찍먹과 부먹의 선호도의 중앙값만큼 선호 선호도를 출력 들어오는 값 친구 N명의 선호도가 만난 순서대로 입력 예) 10 -10 5 2 -3 -10 2 구하고 싶은 값 2명째 친구부터 선호도를 순서대로 각 줄에 출력 예) 0 5 3 2 0 2 생각 1. 2개부터 정렬을 해서 중간값을 구할 수 있겠다. 2. 최소값, 최대값으로 중앙값을 구할 수 있겠다. 코드 최소값, 최대값 방법으로 풀려고 하다가 미끄러졌다. 정렬 방법을 마구잡이로 만들었다. // VSCode에서 JavaScript 테스트 하기위한 코드 // 메모장에..

프로그래밍언어론 강의 6화 :: 언어 구현, 인터프리터, 컴파일러

프로그래밍언어론 6화를 듣고 배운내용 프로그래밍 언어 정의 구문 규칙 문맥 자유 문법과 EBNF로 주로 사용 의미 규칙 자연어 주로 사용 프로그래밍 언어 정의 예시: 로봇 제어 언어 구문 규칙 EBNF 사용: ::= { forward | left | right } 의미규칙 forward: 로봇이 앞으로 1만큼 이동 left: 로봇이 왼편으로 90도 회전 right: 로봇이 오른편으로 90도 회전 프로그래밍 언어 구현 그 언어로 작성된 프로그램을 수행하는 프로그램 CPU의 함수 모형 M[Pm](in) = out M: CPU 기계어 Pm: 기계어로 작성된 프로그램 in: 입력 데이터 out: 출력 데이터 프로그래밍 언어 구현 형태 인터프리터 함수 모형 lntL[PL](in) = out IntL: 연어 L의 ..

자료구조 강의 8화 :: 스레드 트리

자료구조 8화를 듣고 배운내용 KEYWORDS 스레드(thread): 정해진 순회 방법에 따른 방문순서를 유지하는 포인터 스레드 트리: 스레드라는 포인터를 갖는 이진 트리 오른쪽 스레드: 정해진 순회 순서에 따른 그 노드의 후속 노드를 가리킴 왼쪽 스레드: 정해진 순회 순서에 따른 그 노드의 선행 노드를 가리킴 이진 트리의 null 포인터 개수: 2(n - (n - 1) = n + 1 스레드 트리 이진 트리의 null 포인터를 활용하기 위한 스레드 트리 자식 노드가 없는 노드의 포인터는 null을 갖는다 스레드라는 포인터를 추가해서 순회를 편리하게 했다. 스레드를 사용하면 노드를 빨리 찾아다닐 수 있다. 구현이 복잡하고, 추가 기억장소를 사용하는 부담이 있다. 스레드 트리의 구현 1 포인터 필드 추가 왼..

알고리즘 :: 상대평가, 정렬 조건, 핵심을 보자

알고리즘 공부하며 배운내용 상대평가 2번의 시험으로 학생들을 선발한다. 그 후 상대평가로 뽑는다. 어떤 학생보다 두 과목 높거나 같은 점수를 받은 학생이 있으면 어떤 학생은 선발이 안된다. 반대로 두 과목 모두 높거나 같은 점수가 없으면 입학한다. 모든 과목의 점수가 같으면 1명만 입학할 수 있다. 예를 들어 3명의 성적이 이렇다면, (700, 800), (800, 800), (700, 700) 세 번째 학생은 불합격이다. 이 데이터를 바탕으로 총 몇 명이 입학할 수 있는지 알아보자 들어오는 값 첫째 줄에 학생수 N이 입력된다. 둘째 줄부터 N줄까지 시험점수 2개가 입력된다. 최소 0점, 최대 1000점 예) 5 100 200 200 300 400 400 300 500 500 300 구하고 싶은 값 합격..

알고리즘 :: 줄 세우기, 병합정렬 응용

알고리즘 공부하며 배운내용 줄 세우기 가게에서 경품권을 줄 선 순서대로 나눠줬다. 경품권이 잘못돼서 다시 나눠줘야 되는데, 본인들이 몇 번째였는지 기억을 못한다. 근데, 모든 사람이 본인 앞에 키가 큰 사람이 몇 명 있었는지 기억한다. 이를 이용해서 어떤 순서로 서 있었는지 알아보자 들어오는 값 키가 작은 사람부터 자신보다 키가 큰 사람이 몇 명 있었는지 입력 예) 3 1 1 0 제일 키가 작은 첫 번째 사람 앞에는 3명의 키 큰 사람이 있었다. 그다음 키가 작은 사람 앞에는 1명의 키 큰 사람이 있었다. . . . 구하고 싶은 값 키가 작은 사람 순서대로 1, 2 ... n 번호가 있다면, 처음 어떻게 서 있었는지 출력 예) 4 2 3 1 제일 작은 사람 앞에 4, 2, 3 번째 사람들이 있었다. 그 ..

728x90