CS STUDY

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 간단해 보이지만 간단히 완전탐색으로 풀면 시간복잡도가 최악의 경우 n! 이 되기때문에 스택을 써야한다 또한 인덱스를 저장해야하기 때문에 스택안에 리스트가 들어가는 구조로 풀어줘야 한다. import sys N=int(sys.stdin.readline()) tower=list(map(int,sys.stdin.readline().split())) stack=[] ans=[] for i in rang..

https://leetcode.com/problems/top-k-frequent-elements/ Top K Frequent Elements - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 1. Counter를 이용한 음수 순 추출 요소의 값을 키로 하는 해시 테이블을 만들고 여기에 빈도 수를 저장한 다음, 우서눈위 큐(Priority Queue)를 이용해 k번만큼 추출하면 k번 이상 등장하는 요소를 손쉽게 추출할 수 있다. 파이썬에서 우선순위 큐는 힙을..

FIFO(first in first out)로 처리되는, 줄을 서는 것에 비유할 수 있는 큐는 상대적으로 스택에 비해서는 쓰임새가 적다. 그러나 스택에 비해서 그렇다는 얘기일 뿐, 이후에 살펴보게 될 데크나 우선순위 큐 같은 변형들은 여러 분야에서 매우 유용하게 쓰인다. 1. 큐를 이용한 스택 구현 - push() 할 때 큐를 이용해 재정렬 class MyStack: def __init__ (self): self.q=collections.deque() def push(self,x): self.q.append(x) # 요소 삽입 후 맨 앞에 두는 상태로 재정렬 for _ in range(len(self.q) - 1): self.q.append(self.q.popleft()) def pop(self): re..

https://leetcode.com/problems/daily-temperatures/ Daily Temperatures - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 매일의 화씨 온도 리스트 T를 입력받아서, 더 따뜻한 날씨를 위해서는 며칠을 더 기다려야 하는지를 출력하라. 이 문제도 스택을 이용하면 상당히 좋은 성능으로 문제를 해결 할 수 있다. 1. answer=[0]*len(temperature)로 두어서 정답값을 바로바로 참조해서 변경할 수 있도록..

https://leetcode.com/problems/remove-duplicate-letters/ Remove Duplicate Letters - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 중복된 문자를 지우고 사전식 순서로 나열하라. 상당히 난해한 문제이다. 그러나 스택으로 해결할 수 있다. 먼저 collections.counter 객체를 이용해서 각 알파벳의 출현 수를 구할 수 있다. set() 자료형을 사용해서 중복되지 않게 자료들을 넣을 수 있다. ..

https://leetcode.com/problems/valid-parentheses/submissions/ Valid Parentheses - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 괄호로 된 입력값이 유효한지 판별하라. 전형적인 스택 문제로 매우 쉬우면서도 기본기를 점검할 수 있는 좋은 문제이다. class Solution: def isValid(self, s: str) -> bool: d={'}':'{',']':'[',')':'('} stack=[]..

스택과 큐는 프로그래밍이라는 개념이 탄생할 때부터 사용된 가장 고전적인 자료구조 중 하나로, 그중에서도 스택은 거의 모든 애플리케이션을 만들 때 사용되는 자료구조이다. LIFO(last in first out_후입선출), 큐는 FIFO(first in first out_선입선출)로 처리된다. 파이썬은 스택 자료형을 별도로 제공하지는 않지만, 리스트가 사실상 스택의 모든 연산을 지원한다. 큐 또한 마찬가지다. 리스트는 큐의 모든 연산을 지원한다. 다만 리스트는 동적 배열로 구혀노디어 있어 큐의 연산을 수행하기에는 효율적이지 않기 때문에, 큐를 위해서는 데크라는 별도의 자료형을 사용해야 좋은 성능을 낼 수 있다. 연결 리스트를 이용한 스택 ADT 구현 class Node: def __init__(self,i..

자료구조는 크게 메모리 공간 기반의 연속 방식과 포인터 기반의 연결 방식으로 나뉜다. 배열은 이 중에서 연속 방식의 가장 기본이 되는 자료형이다. https://leetcode.com/problems/two-sum/ Two Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라. 이 문제는 매우 쉽다. 그러나 최적화할 수 있는 여러가지 방법이 숨어 있어서 코딩 인터뷰 시 높은 빈도로 출제되는 문제..