스택

[프로그래머스 Lv.3] 가장 먼 노드 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이3단계 치고 BFS를 사용하는 문제이기 때문에, 풀이 방법이 익숙해 쉽게 풀 수 있었던 것 같다. BFS처럼 큐를 사용해 그래프를 순회하면서 시작 정점(1번 정점)에서부터의 거리를 계산하고, 이 중 거리가 가장 먼 정점들의 수를 세는 방식으로 간단하게 풀이할 수 있다.from collections import defaultdict, dequedef solution(n, edges): ..

[프로그래머스 Lv.2] 기능개발 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42586 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이이 문제 유형이 스택/큐 문제라고 지정되어 있긴 하지만, 스택이나 큐를 사용하지 않고 풀이하였다. 문제 풀이 아이디어는 아래와 같다.우선 ceil 내장 함수를 사용해 완료되기까지 걸리는 날짜를 새로운 배열 rests에 저장한다.rests 배열을 순회하며, 현재 인덱스의 이전까지의 최대값(max_time)보다 큰 값이 나타날 때까지의 누적값(cnt)를 키워간다.max_time은 아직까지 ..

[프로그래머스 Lv.2] 주식가격 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42584 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이사실 이 문제는 스택 문제라고 표현되어 있긴 하나, 이중 for문으로 풀어도 제한 시간 내에 통과할 수 있는 문제이다. 스택을 사용한 풀이는 스택을 더 싼 가격이 나타낼 때까지 가격의 위치(인덱스)를 보관하고 있는 통으로 사용한다는 아이디어로 풀면 된다. 레벨 2 문제치고는 스택을 저런 아이디어를 가지고 사용한다는 것이 조금 어려웠던 것 같다. def solution(prices): ..

[프로그래머스 Lv.2] 짝지어 제거하기 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12973 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이레벨 2 문제임에도 아이디어를 생각하는 것이 상당히 까다로운 문제였다.문자열의 길이가 1000000개이기 때문에 파이썬이 초당 2000만 번의 연산을 한다는 것을 생각하면 O(n^2) 이하의 알고리즘으로 풀어야 한다.그렇기에 O(n)이나 O(nlogn)으로 풀 수 있는 방법을 생각해야 하고, 그 방법으로 스택을 사용하였다.아래의 코드와 같이 진행하면 O(n)의 시간복잡도를 보여 시간 내..

(CS) 단일 연결 리스트 vs 원형 연결 리스트, Stack으로 Queue 구현, 원형 큐 구현

단일 연결 리스트 vs 원형 연결 리스트 단일 연결 리스트와 원형 연결 리스트는 연결 리스트의 일종으로, 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다. 데이터를 노드에 저장하고 노드들을 링크로 연결하여 데이터를 관리하는 자료구조이다. 하지만 다음과 같은 차이점이 있다. 단일 연결 리스트(Singly Linked List) 원형 연결 리스트(Circular Linked List) 리스트의 끝은 NULL로 표시 리스트의 순회는 단방향으로만 가능 리스트의 끝은 NULL이 아닌, 첫 번째 노드를 가리키는 포인터로 표시 마지막 노드의 다음 노드는 첫 번째 노드가 되어 원형적인 형태 리스트의 순회는 양방향으로 가능 다음 노드만을 가리키는 포인터만으로 구현되기 때문에 구현이 간단하고 메모리를 적게..

(C++) 백준 2504번 - 괄호의 값

문제 링크 : https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X www.acmicpc.net 풀이 스택을 이용하여 풀이를 진행하면 된다. 올바른 입력인지 확인하는 것은 이전에도 풀어보았기 때문에 어렵지 않으나, 값들을 곱해주는 것이 무척 어려웠다. 더하는 것은 단순히 이전에 나온 것이 짝이 맞는 괄호인지만 확인하면 돼서 어렵지 않았는데, 곱해주는 것은 고민해 봐도 도저히 생각이 나지 않아서 다른 사람의 풀이를 참고하였다. 열린 괄호가 입력되었을 때 곱해주는 아이디어가 ..

(C++) 백준 4949번 - 균형잡힌 세상

문제 링크 : https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다 www.acmicpc.net 풀이 닫는 괄호들이 나왔을 때 짝이 맞는 괄호가 stack의 Top에 위치해 있다면 이는 균형 잡힌 문장이라고 볼 수 있다는 점이 이 문제 풀이의 핵심 요소이다. 처음에 제출했을 때 실패가 나와서 왜 그런지 생각해 봤더니 "( ) ( ) ["와 같이 열린 괄호가 더 많은 경우여서 애초에 균형이 맞지 않은 것들을 예외 처리하지 못한 것이 원인이었다. 따라서 마지막..

(C++) 백준 2841번 - 외계인의 기타 연주

문제 링크 : https://www.acmicpc.net/problem/2841 2841번: 외계인의 기타 연주 첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000) 다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수 www.acmicpc.net 풀이 이전의 스택 문제들과 비슷하게 접근하여 풀었다. 기타의 줄이 6줄이므로 6개의 stack을 가지는 배열을 선언하였다. 아무 프렛도 안 누른 상태를 가정하여 0을 스택에 넣고 시작했는데, 이 덕분에 스택이 비어 오류가 발생하는 것을 걱정하지 않아도 된다. #include #include using namespace std; stack A[6..

(C++) 백준 2493번 - 탑

문제 링크 : https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 풀이 처음에 다음과 같이 풀어보았다. #include #include using namespace std; stack T, tmp, answer; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; while(n--){ int i; cin >> i; T.push(i); } while(1){ int num = T.s..

(Python) 백준 1874번 - 스택 수열

문제 링크 : https://www.acmicpc.net/problem/1874 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 풀이 deque를 stack으로 사용하여, 입력으로 들어오는 수열을 만들기 위해 발생할 수 있는 모든 경우를 생각하며 하나씩 구현하였다. import sys from collections import deque n = int(sys.stdin.readline()) stack = deque() # 입력 ..