알고리즘

[알고리즘]프로그래머스 - N으로 표현 <동적계획법(DP)>

프로그래머스 - N으로 표현 문제 설명 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요. 제한사항 N은 1 이상 9 이하입니다. number는 1 이상 32,000 이하입니다. 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다. 최솟값이 8보다 크면 -1을 return 합니다. 입출력 예 N n..

[알고리즘] 백준 13904 과제 node.js (Greedy)

그리디 관련 문제를 풀다가 이상한 점을 발견했다. 오름차순 내림차순에 따라 정답이 맞고 틀렸기 때문이다. https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 풀이 방법 주어진 과제들을 순서대로 정렬한 뒤, 각 마감일까지의 날짜 중에서 가장 높은 점수를 얻을 수 있는 과제를 선택하는 방식으로 탐욕적으로 접근하였다. ❌틀린 코드 let input = require("fs").readFileSync("예제.txt").toString().split("\n"); const N = parseInt(in..

[알고리즘] 탐욕법(Greedy)

탐욕법 (Greedy) 그리디 알고리즘 (탐욕법, Greedy Algorithm) 이란? 탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. '각 단계에서 최적이라고 생각되는 것을 선택'해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘 - 이 때, 항상 최적의 값을 보장하는 것이 아니라 최적의 값의 '근사한 값'을 목표로 한다. 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다. 그리디 알고리즘 활용 기법 1. 탐욕 선택 속상 (greedy choice property) 각 단계에서 '최선의 선택'을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우를 말한다. 즉, 각 단계에서..

[알고리즘] 완전탐색 예제 # 1 단순 브루트포스

프로그래머스 Level 1 최소직사각형 https://school.programmers.co.kr/learn/courses/30/lessons/86491?language=javascript 더보기 명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다. 아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다. 명함 번호 가로 길이 세로 길이 1 60 50 2 30 70 3 60 30 4 80 40 가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로)..

[알고리즘] 완전 탐색

완전 탐색 (Brute Force) 1. 완전 탐색이란? 가능한 모든 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미한다. '무식하게 푼다'라는 의미인 Brute-Force (브루트 포스)라고도 부른다. 알고리즘을 모르는 사람이 프로그래밍 문제를 푼다면, 당연히 가능한 모든 경우들을 다 구해서 그중에 만족하는 답을 찾아낼 것이고 이 과정 자체가 완전 탐색이다. 대신에 이 방식은 절대 답을 못 구하는 경우는 없으므로 나름 강력한 방법이다. 하지만, 알고리즘을 사용할 때는, 기본적으로 2가지 규칙을 적용한다. 1. 사용된 알고리즘이 적절한가? ( 문제를 해결할 수 있는가 ) -> 만족 2. 효율적으로 동작하는가? -> 제한이 따르는 경우가 있음 (시간복잡도 측면) 2. 완전 탐색 기법 활용 방법 1. ..

[알고리즘] Hash

Key-value쌍으로 데이터를 빠르게 찾아보세요. 👩🏼‍💻 해시 키와 값이 한 쌍으로 구성된 데이터 👩🏼‍💻 해시 테이블 key, value가 쌍을 이룬 형태로 데이터가 저장 되어있는 자료구조 데이터 검색과 저장이 아주 빠르게 진행됨 검색과 저장의 평균적인 시간복잡도가 O(1+α(적재율))에 수렴 👩🏼‍💻 해시 테이블의 원리 파이썬의 딕셔너리와 동일 [JS에서 해시 쓰는 방법] 사실 js에서 일반 배열에서 Key값에 문자열이 주는게 가능함 왜? js배열은 우리가 알고있는 배열과 조금 다른 희소배열이기 때문 희소배열 : 여러개의 자료형을 허락하는 배열 🚨 Map key가 있는 데이터를 저장하는데 쓰이는 자료구조 key값은 문자열 또한 가능 new Map() -> Map 객체를 만들때 쓰인다. map.se..

[알고리즘] 브루트 포스(brute force)

브루트 포스 (brute force) Brute : 무식한 + Force : 힘 = 무식한 힘 완전탐색 알고리즘 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져옴 브루트 포스 알고리즘을 설계할 때는 해가 하나 이상 존재한다는 가정을 세우고 모든 범위를 탐색하기 때문에 무조건 정답을 찾을 수 있음 어떤 방식으로든 전체 탐색으로 문제를 해결한다면 브루트 포스 알고리즘으로 풀었다고 할 수 있음 선형 구조를 전체적으로 탐색하는 순차탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)가 기본적인 도구 장점 알고리즘을 설계하고 구현하기 매우 쉬움 복잡한 알고리즘 없이 빠르게 구현 가능 단점 알고리즘의 실행 시간이 매우 오래 걸림 메모리 효율면에서 매..

[BOJ] 2738 : 행렬 덧셈 (node.js)

백준 2738번을 풀다가 아래 사진까지는 유도를 했는데 이중배열일 경우 아래의 예제 출력처럼 출력하는 방법이 궁금했다. sol 1. 많은 사람들이 이 방법을 이용해서 풀이를 했다 하지만 console을 찍었을 때 마지막 줄에도 + "\n"가 되어 줄바꿈이 출력되는 것이 신경 쓰였다. sol 2. 두번째 방법으로 찾아본 방법은 forEach로 해보았다. 사실 forEach에 대한 문법은 잘 알지 못했는데 이번에 제대로 찾아보게 되었다. forEach 메서드 배열에서 루프를 돌 때 사용 array.forEach(function(currentValue, index, arr)); function(currentValue, index, arr) - 배열의 각 항목에 대해 실행할 함수 currentValue - 배열..