Algorithm
-
장난꾸러기 현수Algorithm 2022. 6. 21. 13:29
문제) 현수네 반에는 N명의 학생들이 있습니다. 선생님은 반 학생들에게 반 번호를 정해 주기 위해 운동장에 반 학생들을 키가 가장 작은 학 생부터 일렬로 키순으로 세웠습니다. 제일 앞에 가장 작은 학생부터 반 번호를 1번부터 N번까 지 부여합니다. 현수는 짝꿍보다 키가 큽니다. 그런데 현수가 앞 번호를 받고 싶어 짝꿍과 자리를 바꿨습니다. 선생님은 이 사실을 모르고 학생들에게 서있는 순서대로 번호를 부여했습니 다. 현수와 짝꿍이 자리를 바꾼 반 학생들의 일렬로 서있는 키 정보가 주어질 때 현수가 받은 번 호와 현수 짝꿍이 받은 번호를 차례로 출력하는 프로그램을 작성하세요. function solution(arr) { let answer = []; const fmArr = arr.slice().sort((..
-
Least Recently Used(카카오 캐시 문제 변형)Algorithm 2022. 6. 21. 11:17
문제) 캐시메모리는 CPU와 주기억장치(DRAM) 사이의 고속의 임시 메모리로서 CPU가 처리할 작업 을 저장해 놓았다가 필요할 바로 사용해서 처리속도를 높이는 장치이다. 워낙 비싸고 용량이 작아 효율적으로 사용해야 한다. 철수의 컴퓨터는 캐시메모리 사용 규칙이 LRU 알고리즘을 따 른다. LRU 알고리즘은 Least Recently Used 의 약자로 직역하자면 가장 최근에 사용되지 않은 것 정도의 의미를 가지고 있습니다. 캐시에서 작업을 제거할 때 가장 오랫동안 사용하지 않은 것을 제거하겠다는 알고리즘입니다. 만약 캐시의 사이즈가 5이고 작업이 2 3 1 6 7 순으로 저장되어 있다면, (맨 앞이 가장 최근에 쓰인 작업이고, 맨 뒤는 가장 오랫동안 쓰이지 않은 작업이다.) 1) Cache Miss :..
-
큐(Queue)Algorithm 2022. 6. 20. 16:02
큐(queue)는 한쪽 방향으로 데이터가 삽입되고 반대 방향으로 데이터가 삭제되는 구조다. 다음과 같은 마트의 계산대에서는 계산대에 먼저 도착한 고객이 먼저 계산하고 나가는데, 큐의 좋은 예라 할 수 있다. 자바스크립트에서는 배열과 관련된 함수 shift(), push()를 이용해 이를 쉽게 삭제하고 추가할 수 있다. 예시 1) 공주구하기 1부터 n까지의 번호를 가진 왕자들이 있다. 원형으로 앉아 1번부터 차례대로 숫자를 1부터 부르는데 지정된 숫자 k를 부르는 사람이 한명씩 빠지며 한명이 빠질 때마다 숫자가 초기화 되며 그다음 차례가 다시 1부터 부른다. 최종적으로 남은 한명이 공주를 구하러가는 이야기 function solution(id, num) { let answer = 0; let princes..
-
쇠막대기 절단Algorithm 2022. 6. 20. 13:37
소괄호로만 구성된 문자열이다. 연속된 닫힌 괄호 () 를 레이저로 두고 레이저를 감싸는 괄호를 쇠막대기라 하였을 때 레이저가 관통하여 자른 쇠막대기의 개수를 구하는 문제이다. 스택을 이용하여 풀었는데 레이저와 쇠막대기를 어떻게 구분하여 스택 상자에서 처리할지 골머리를 앓다가 완성된 로직은 다음과 같다. function solution(str) { let answer = 0; let stack = []; for (let i = 0; i < str.length; i++) { // )) 괄호 두 개 만나면 제거 후 막대 개수 카운트 if (str[i - 1] === ")" && str[i] === ")") { for (let j = 1; j < stack.length - 1; j++) { if (stack[s..
-
후위표기식 계산Algorithm 2022. 6. 20. 10:23
알고리즘 문제를 통해 '후위 표기식' 연산이라는 새로운 개념을 접하게 되었다. 우리가 일반적으로 사용하는 것이 피연산자(-,+,*,/)가 숫자 가운데 위치한 상태로 계산하는 방식이 '중위 표기식' 이라면 후위 표기식은 피연산자가 연속된 숫자 뒤에 위치하여 계산을 하는 방식이다. 예를 들어 12+ 라는 식이 주어지면 1+2로 계산을 한다. 12+ => 1 + 2 123+- 라는 계산식이 주어지면 첫 번째 피연산자와 마주치는 값인 23+를 먼저 계산하고 다음 피연산자와의 수식을 실행해준다. 23+ => 2+ 3 1(5)- => -4 이를 내가 생각한 알고리즘으로 구현했다. stack문제를 접하면서 마주친 개념이라 stack을 당연히 사용하겠거니 스포를 당해 쉽게 구현할 수 있었다. function cal(a..
-
크레인 인형 뽑기 게임Algorithm/프로그래머스 2022. 6. 18. 23:05
인프런에서 자바스크립트 알고리즘 기초 강의만 듣다가 처음으로 다른 사이트에 있는 문제에 도전하였다. 프로그래머스 사이트를 이용하였고 작성한 코드 제출 후 모든 테스트 케이스가 다 맞는 짜릿함을 맛봐서 내가 고민한 흔적과 삽질(?)의 순간들을 기록으로 남겨야겠다는 생각이 들었다. 또 다른 사람의 풀이를 볼 수 있어서 좀 더 효율적인 코드가 있으면 내 코드랑도 한번 비교를 해봐야겠다. https://programmers.co.kr/learn/courses/30/lessons/64061# 코딩테스트 연습 - 크레인 인형뽑기 게임 [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] [1,5,3,5,1,2,1,4] 4 programmers.co.kr 처음..