CS STUDY

https://leetcode.com/problems/permutations/ Permutations - 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 이번 포스팅에서는 DFS를 이용한 순열에 대해서 정리해 보겠다 순열은 다음 그래프처럼 DFS로 해결할 수 있다. 풀이 방법에는 두가지 방법이 있다. 먼저 재귀구조로 문제를 풀어보겠다. def permute(nums): sol=[] def dfs(index,array): if len(array) == len(num..

https://leetcode.com/problems/number-of-islands/ Number of Islands - 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 입력값이 정확히 그래프는 아니지만 사실상 동서남북이 모두 연결된 그래프로 가정하고 동일한 형태로 처리할 수 있으며, 네 방향 각각 DFS 재귀를 이용해 탐색을 끝마치면 1이 증가하는 형태로 육지의 개수를 파악할 수 있다. class Solution: def numIslands(self, grid..

그래프의 각 정점을 방문하는 그래프 순회에는 크게 깊이 우선 탐색(Depth-Frist-Search(이하 DFS))과 너비 우선 탐색(Breadth-First_search(이하 BFS))의 2가지 알고리즘이 있다. DFS는 주로 스택으로 구현하거나 재귀로 구현하며, 이후에 살펴볼 백트래킹을 통해 뛰어난 효용을 보인다. 반면 BFS는 주로 큐로 구현하며, 그래프의 최단 경로를 구하는 문제 등에 사용된다. 아래 그림과 같은 순회 그래프를 살펴보자. 그래프를 표현하는 방법에는 크게 인접 행렬과 인접 리스트의 2가지 방법이 있는데, 이번 포스팅에서는 위 그래프를 인접 리스트로 표현하겠다. 1. DFS graph={ 1:[2,3,4], 2:[5], 3:[5], 4:[], 5:[6,7], 6:[], 7:[3] } ..

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 덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라. 이 문제는 매우 쉽다. 그러나 최적화할 수 있는 여러가지 방법이 숨어 있어서 코딩 인터뷰 시 높은 빈도로 출제되는 문제..