꾸준하게 거북이처럼

class MinHeap { constructor() { this.heap = []; } size() { return this.heap.length; } swap(idx1, idx2) { [this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]]; } add(value) {// 값 추가 this.heap.push(value); this.bubbleUp(); } remove() {// Pop if (this.heap.length === 1) { return this.heap.pop(); } const value = this.heap[0]; this.heap[0] =..

class Node { constructor(data) { this.data = data; this.next = null; }}// 큐 클래스class Queue { constructor() { this.head = null; // 제일 앞 노드 this.rear = null; // 제일 뒤 노드 this.length = 0; // 노드의 길이 } isEmpty() { return this.length == 0; } enqueue(data) { // 노드 추가. const node = new Node(data); // data를 가진 node를 만들어준다. if (this.isEmpty()) { // 헤드가 없을 경우 head를 해당 ..

이 글은 면접을 위한 CS 전공지식노트 책 및 강의를 참고하여 정리한 것이다. 배열은 연속된 메모리 공간에 데이터가 쌓인다. 연결리스트는 연속 되지 않은 메모리 공간에 데이터가 쌓인다.(독립적인 공간에 데이터가 저장) 차이를 한 눈에 볼 수 있는 표를 보자면 배열 연결리스트 메모리 공간 연속적 연속X 삽입, 삭제(맨 끝, 맨 앞 제외) O(n) O(1) n번째 요소 참조 O(1) O(n) 탐색 O(n) O(n) 이를 봤을 때, 데이터 추가와 삭제를 많이 하는 것은 연결 리스트, 참조를 많이 하는 것은 배열로 하는 것이 좋다. 연결 리스트는 순차적 접근을 하고, 배열은 랜덤 접근을 하기 때문에, n번째 요소 참조의 시간 복잡도가 위와 같다.

1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 이 문제는 stack의 LIFO 특징을 이용해서 중위 표기식을 후위 표기식으로 변환시키는 문제이다. 입력 받은 문자열을 하나씩 읽어들여 연산자들만 stack에 넣고 각 연산자들의 우선순위 규칙에 맞게 pop, append를 한다. 나머지 피연산자들은 최종적으로 답이 될 빈 문자열에 더해준다. 올 수 있는 모든 연산자: +, -, *, /, (, ) 우선순위 설정: priority = {"*": 1, '/':1, '+':0, '-':0,'(':-1} 나는 문제..

17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 입력 최대 수가 100만 이기 때문에 시간 복잡도를 잘 고려해야한다. for 중복문은 사용할 수 없고 자료구조 stack을 이용했다. 아래 그림은 내가 생각한 풀이를 그림으로 나타냈다. 내 코드 import sys n = int(input()) stack = list(map(int,sys.stdin.readline().split())) ans = [] stack2 = [] ans.append(-1) stack2.append(stack.pop()) while stack: va..

10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 여는 괄호는 stack에 추가, 만일 닫는 괄호 바로 앞에 여는 괄호가 있다면 레이저를 만나는 것이므로, 레이저의 여괄호는 pop하고 스택에 남은 여괄호 즉, 막대기 개수를 센다. 그 이후 닫는 괄호는 막대기가 잘려진 뒷부분 +1 을 해준다. import sys arr = sys.stdin.readline().strip() stack = [] ans = 0 for i in range(len(arr)): if arr[i] == '(': stack.append(arr[i]) e..

17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 괄호 사이에 있는 단어는 제외 한 단어를 뒤집는 문제로, 공백이나 < 여는 괄호를 만나면 stack.pop을 이용해서 단어를 뒤집는 방법을 생각했다. 단어가 아닌 태그는 바로 결과 값을 출력할 문자열에 추가하는 방식으로 구현했다. 여괄호와 닫는 괄호의 개수가 동일하지 않을 때 즉 괄호 안에 문자를 읽는 상태이기 때문에 이는 바로 문자열에 뒤집지 않고 하나씩 추가했다. 내 코드 import sys arr = sys.stdin.read..

1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 처음에 떠올린 문제풀이 방법은 list를 이용해서 insert 나 del 함수를 이용하는 것이었다. 하지만 이 문제는 시간제한이 0.3초로 짧았고, 시간 초과가 났다. 아무래도 최대 명령어 개수가 50만이고, insert만한다면? 파이썬 list 에서 insert의 시간 복잡도는 O(N)이므로, 또한 여기서 최대 문자열 길이는 60만이므로, 50만 * 60만 => 3천만 연산 + 다수의 if문 존재.. 시간 초과가 나기 쉽다. 이쯤되면 pop이나 append와 같..

1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 1 부터 n까지 오름차순으로 오직 stack의 push와 pop만으로 입력받은 수열을 만들 수 있는지 확인하는 문제이다. 예제를 보면서 직접 stack이 pop이 되고 push가 되는 과정을 그려보면 크게 두 가지로 나뉜다. 1. 입력받은 수열 arr1의 원소가 arr2(1~ n까지 수를 pop/push 하는데 사용될 stack)배열에 이미 존재한다면 pop 2. 존재하지 않는다면..

9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net stack자료구조를 생각해서 문제를 풀면 금방 풀 수 있다. 하지만 반례가 있는지 틀렸다.. 문제에 나와있는 예시는 모두 다 정답인데,, 질문검색 목록에 여러 반례를 찾아보았다. 반례는 ')(' 이 문자열이었다. 이 경우에는 올바른 괄호가 아닌 경우다. 내가 올바른 괄호를 잘못 이해한 부분은 서로 다른 괄호가 만나면 상쇄된다고만 생각했다. 하지만 닫는 괄호가 먼저 오고 여괄호가 오는 구조는 올바른 괄호가 아닌 것이다. 처음 코드 -..