문제 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 풀이과정 💡 아이디어 ✅ 먼저 계산되어야 하는 부호가 앞에 나와야 한다. A*(B+C) ➡️ ABC+* ✅ 즉, 부호를 스택에 순서대로 담았다가, ✅ 스택의 가장 위 부호보다 나중에 계산되어야 하는 부호가 나오면 스택에 담긴 부호들을 처리한다. ✅ 이때 연산의 우선순위는, 괄호 > * / > + - > 앞에 온 부호 ✅ 앞에 온 부호가 항상 스택의 밑에 깔리므로(FILO), 우선순위를 무..
SELECT, WHERE, JOIN, GROUP BY, HAVING, ORDER BY 등의 기본문법은 제외했습니다. 문자열 조작 CONCAT(str1, str2, ...) 문자열 합치기, 하나라도 null 존재하면 null 반환 SUBSTRING(str, 시작, 끝) 부분문자열 추출 LOCATE(str, 찾는 문자열) 문자열 내에서 찾는 문자열이 처음으로 나타나는 위치를 찾아서 해당 위치를 반환, 존재 안하면 0 반환 (시작 인덱스 1) LEFT(str, 개수) RIGHT(str, 개수) 문자열의 왼쪽/오른쪽부터 지정한 개수만큼의 문자를 반환 LENGTH(str) 문자열 길이 LOWER(str) UPPER(str) 문자열의 문자를 모두 대/소문자로 변경 REPLACE(str, 바꾸고 싶은 문자, 바꿀 문..
우선순위 큐 우선순위 큐란? 일반적인 큐(FIFO)와 달리 우선순위가 높은 데이터가 먼저 나가는 자료구조 구현방법 삽입 삭제 배열 O(1) O(N) 링크드리스트 O(1) O(N) 힙 O(logN) O(logN) ⏩️ 우선순위 큐의 삽입, 삭제가 필요할 때는 힙으로 구현하자. 최소 힙 이진트리 구조 모든 부모 노드는 자식 노드보다 값이 작다 최대 힙 이진트리 구조 모든 부모 노드는 자식 노드보다 값이 크다 비겁하지만... 힙이 JS에는 구현이 안되어 있어서 직접 구현해야 한다. 코딩테스트에서 파이썬 사용이 가능하다면 파이썬으로 푸는게 더 유리하다. 파이썬에서는요 import heapq # 힙 배열로 선언 heap = [] # 원소 push heapq.heappush(heap, 1) # 원소 pop cur ..
문제 https://www.acmicpc.net/problem/1327 1327번: 소트 게임 홍준이는 소트 게임을 하려고 한다. 소트 게임은 1부터 N까지 정수로 이루어진 N자리의 순열을 이용한다. 이 게임에선 K가 주어진다. 어떤 수를 뒤집으면, 그 수부터 오른쪽으로 K개의 수를 뒤집 www.acmicpc.net 풀이과정 💡 아이디어 순회는 언제 끝날까? ✅ 주어진 숫자들을 순서대로 정렬한 answer 를 구한다. ✅ 문제의 조건대로 정렬을 반복하다가 answer와 일치하는 순간 정렬 횟수를 반환 ⏩️ 최소 횟수이므로 BFS가 적합 그렇다면 방문처리는 어떻게 해야 할까? ✅ N의 최댓값이 8이므로 숫자 인덱스로 배열 방문처리를 한다면 visited[88888888] 필요 ✅ 객체를 활용하면 메모리를 ..
문제 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;..
문제 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..
1. 배열로 스택 구현하기 그냥 JS 배열 메서드를 사용하면 스택을 활용할 수 있다. 2. 객체로 스택 구현하기 class Stack { #storage; constructor() { this.#storage = {}; this.length = 0; } push(item) { this.#storage[this.length++] = item; } pop() { if (!this.length) return; const item = this.#storage[--this.length]; delete this.#storage[this.length - 1]; return item; } } 3. 링크드리스트로 스택 구현하기 push(item) class Node { constructor(data) { this.dat..
문제 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가 이전보다 낮..
