2023년 10월 11일 알고리즘 문제풀이 문제 1 프로세스 문제 링크 1차 시도 나의 생각 프로세스가 담긴 배열에서 첫번째가 우리가 알고싶은 프로세스 인지 아닌지, 또 가장 높은 우선순위를 지녀 실행될 차례인지, 아닌지로 구분하였다. location은 현재 우리가 알고싶은 프로세스의 index이고, answer는 몇번째로 실행되었는지를 의미한다. 알고 싶은 프로세스 관심 없는 프로세스 최우선순위 answer 출력 popleft() 한다. 실행되었기 떄문에 answer 1 증가 차우선순위 popleft()하여 맨 뒤로 보낸다. location도 맨 뒤로 설정한다. popleft()후 맨 뒤로 보낸다. locaion 1 감소 결과 정답 ...
12일차 게일 라크만 맥도웰의 코딩 인터뷰 완전 분석 3.3 ~ 3.6 내용 정리 9 면접 문제 3.3 접시 무더기 접시 무더기를 생각해보자. 접시를 너무 높이 쌓으면 무너져 내릴 것이다. 따라서 현실에서는 접시를 쌓다가 무더기가 어느 정도 높아지면 새로운 무더기를 만든다. 이것을 흉내 내는 자료구조 SetOfStacks를 구현해 보라. SetOfStacks는 여러 개의 스택으로 구성되어 있으며, 이전 스택이 지정된 용량을 초과하는 경우 새로운 스택을 생성해야 한다. SetOfStacks.push()와 SetOfStacks.pop()은 스택이 하나인 경우와 동일하게 동작해야 한다(다시 말해, pop()은 정확히 하나의 스택이 있을 때와 동일한 값을 반환해야 한다). ...
12일차 게일 라크만 맥도웰의 코딩 인터뷰 완전 분석 p.144 ~ p.146, 3.1, 3.2 내용 정리 9 면접 문제 03 스택과 큐 스택 구현하기 스택 자료구조는 데이터를 쌓아 올린다(stack)는 의미이다. LIFO(Last-In-Fisrt-Out)에 따라 자료를 배열한다. 연산은 다음과 같다. pop(): 가장 위에 있는 항목을 제거한다. push(item): item 하나를 가장 윗 부분에 추가한다. peek(): 가장 위에 있는 항목을 반환한다. isEmpty(): 스택이 비어 있을 때에 true를 반환한다. 배열과 달리 상수 시간에 i번째 항목에 접근할 수 없다. 데이터를 추가하거나 삭제하는 연산은 상수시간에 가능하다. 재귀함수에서 많이 사용한다. 큐 구현하기 FIFO(First-In-First-Out) 순서를 따른다. 연산은 다음과 같다. add(item): item을 리스트의 끝부분에 추가한다. remove(): 리스트의 첫 번째 항목을 제거한다. peak(): 큐에서 가장 위에 있는 항목을 반환한다. isEmpty(): 큐가 비어 있을 때에 true를 반환한다. 큐를 연결리스트로 구현할 수 있다. BFS나 캐시를 구현할 떄 종종 사용한다. 면접 문제 3.1 한 개로 세 개 배열 한 개로 스택 세 개를 어떻게 구현할지 설명하라. ...
2023년 9월 4일 알고리즘 문제풀이 문제 1 백준 1167 문제 링크 1차 시도 나의 생각 입력값을 list로 받은 후 가장 앞인 0번 index는 어떤 정점의 정보인지를 나타낸다고 생각하였고 그 이후 둘 씩 짝지어서 도착 정점과 거리로 설정하였다. 이를 바탕으로 인접리스트를 만들고 index를 2씩 뛰어넘어 -1이 나오면 더이상 정보가 없으므로 다음 줄로 넘어갔다. 이후에는 두 점간의 거리를 bfs를 통해 탐색하도록 하였다. 모든 점간의 거리를 찾아 최댓값을 도출하였다. 하지만 메모리,시간초과가 뜬다… 다찾아보면 안되나보다. ...
2023년 8월 17일 알고리즘 문제풀이 문제 1 올바른 괄호 문제 링크 1차 시도 나의 생각 문자열을 앞부터 한글자씩 스택에 넣는다. 여는 괄호’(‘는 무조건 넣고, 닫는 괄호’)‘는 경우가 나누어진다. 스택에 마지막으로 들어가있는 원소가 여는 괄호면 합쳐서 올바른 괄호니 마지막에 들어간것을 pop해준다. 스택이 비어있으면 올바른 괄호가 아니라는 의미이다. 단어의 모든 글자를 순회했는데 아직 스택에 괄호가 남아있다면 올바르지 못한 괄호이다. 결과 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 from collections import deque def solution(s): answer = True arr = list(s) q = deque() for i in range(len(s)): if arr[i] == '(': q.append(arr[i]) else: if not q or q[-1] != '(': return False elif q[-1] == '(': q.pop() continue if q: return False else: return answer 문제 2 디스크 컨트롤러 문제 링크 ...