알고리즘/문제풀이

알고리즘/문제풀이

[JavaScript][node.js] 백준 1918 후위 표기식

문제 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 풀이과정 💡 아이디어 ✅ 먼저 계산되어야 하는 부호가 앞에 나와야 한다. A*(B+C) ➡️ ABC+* ✅ 즉, 부호를 스택에 순서대로 담았다가, ✅ 스택의 가장 위 부호보다 나중에 계산되어야 하는 부호가 나오면 스택에 담긴 부호들을 처리한다. ✅ 이때 연산의 우선순위는, 괄호 > * / > + - > 앞에 온 부호 ✅ 앞에 온 부호가 항상 스택의 밑에 깔리므로(FILO), 우선순위를 무..

알고리즘/문제풀이

[JavaScript][node.js] 백준 1327 소트 게임

문제 https://www.acmicpc.net/problem/1327 1327번: 소트 게임 홍준이는 소트 게임을 하려고 한다. 소트 게임은 1부터 N까지 정수로 이루어진 N자리의 순열을 이용한다. 이 게임에선 K가 주어진다. 어떤 수를 뒤집으면, 그 수부터 오른쪽으로 K개의 수를 뒤집 www.acmicpc.net 풀이과정 💡 아이디어 순회는 언제 끝날까? ✅ 주어진 숫자들을 순서대로 정렬한 answer 를 구한다. ✅ 문제의 조건대로 정렬을 반복하다가 answer와 일치하는 순간 정렬 횟수를 반환 ⏩️ 최소 횟수이므로 BFS가 적합 그렇다면 방문처리는 어떻게 해야 할까? ✅ N의 최댓값이 8이므로 숫자 인덱스로 배열 방문처리를 한다면 visited[88888888] 필요 ✅ 객체를 활용하면 메모리를 ..

알고리즘/문제풀이

[JavaScript][node.js] 프로그래머스 피로도

문제 https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이과정 S1 - 탐험 가능한 던전의 수를 세는 함수를 따로 만들기 count 함수 function count(arr, start) { let life = start; let count = 0; for(const item of arr) { const [req, minus] = item; if (req 0) { count++; life -= minus; } else { return count;..

알고리즘/문제풀이

[JavaScript][node.js] 백준 1406 에디터

문제 https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 풀이과정 💡 아이디어 실제 cursor 변수를 다룬다고 생각하지 말고, cursor의 왼쪽과 오른쪽에 있어야 할 문자열을 stack으로 관리한다. 명령어 L : 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨) if (c === 'L') { if (cursor_left.length) { const top = cursor_left.pop(); cursor_right.push(top..

알고리즘/문제풀이

[JavaScript][node.js] 백준 11053 가장 긴 증가하는 부분 수열

문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이과정 1차시도 const memo = new Array(n).fill(1); for (let i = 0; i < n - 1; i++) { const start = numbers[i]; for (let j = i + 1; j < n; j++) { memo[j] = start < numbers[j] ? memo[i] + 1 : memo[i]; } } 이 점화식은, i가 이전보다 낮..

알고리즘/문제풀이

[JavaScript][node.js] 백준 14940 쉬운 최단거리

문제 https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 자바스크립트(node.js)로 풀이했습니다. 풀이과정 1차 시도 실패 이유 - 메모리 초과 갈 수 있는 모든 땅에 대해 bfs()를 다 돌림 -> visited는 bfs()를 호출할때마다 계속해서 할당 -> 메모리 초과 이뿐만 아니라 최단거리는 직전 땅의 거리 정보를 이용해 구할 수 있으므로 각 땅이 아니라 전체를 bfs() 돌리는게 맞다 for ..

알고리즘/문제풀이

[JavaScript][node.js] 백준 18111 마인크래프트

문제 https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 자바스크립트(node.js)로 풀이했습니다. 최종코드 const fs = require('fs'); const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt'; const input = fs.readFileSync(filePath).toString().trim().split('\n'); const [n, m, b..

햄oOoOo
'알고리즘/문제풀이' 카테고리의 글 목록