Computer Science/자료구조 | 알고리즘

그래프 탐색 알고리즘: DFS/BFS탐색(Search): 많은 양의 데이터 중 원하는 데이터 찾는 과정대표적인 그래프 탐색 알고리즘: DFS/BFS코딩 테스트에서 매우 자주 등장하는 유형스택 자료구조먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조입구와 출구가 동일한 형태로 스택을 시각화 가능삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()Pythonstack = []stack.append(5)stack.append(2)stack.append(3)stack.append(7)stack.pop()stack.append(1)stack.append(4)stack.pop()print(stack[::-1]) # 최상단 원소부터 출력 [1, 3,..

그리디 알고리즘(탐욕법)현재 상황에서 지금 당장 좋은 것만 고르는 방법문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력 요구정당성 분석 중요단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토예시루트 노드부터 시작하여 거쳐 가는 노드의 합을 최대로 만들고 싶음-> 최적의 해는 무엇? / 단순히 매 상황에서 가장 큰 값만 고른다면? 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때 ↑But, 코딩 테스트에서 대부분의 그리디 문제-> 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 이를 추론할 수 있어야 풀리도록 출제 구현(Implementation)머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정구현 유형의 문제 = 풀이를 떠올리는 것은 쉽지만 소스코드..

재귀(Recursion)하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘void func1(int n) { if(n == 0) return; cout  재귀로 푼다 == 귀납적인 방식으로 문제 해결절차지향적 사고 vs. 귀납적 사고void func1(int n){ if (n==0) return; count 절차지향적 사고ex. 1번 도미노가 쓰러진다 -> 2번 도미노가 쓰러진다 ... => 모든 도미노가 쓰러진다3 출력 -> func1(2) 호출 -> 2 출력 -> func1(1) 호출 -> 1 출력 -> func1(0) 호출귀납적 사고ex. 1번 도미노가 쓰러진다, k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다=> 모든 도미노가 쓰러진다func1(1)이 1을 출력,func..

DFS(Depth First Search) 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘 DFS -> 스택 / BFS -> 큐 예시 시작하는 칸을 스택에 넣고 방문했다는 표시를 남김 스택에서 원소 꺼내 그 칸과 상하좌우로 인접한 칸에 대해 3번을 진행 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입 스택이 빌 때까지 2번을 반복 => 모든 칸이 스택에 1번씩 들어감 -> 시간복잡도는 칸이 N개일 때 O(N) (0, 0)과 상하좌우로 이어진 모든 파란칸 확인 (0, 0)에 방문했다는 표시 + 해당 칸 -> 스택에 넣음 스택이 빌 때까지 스택의 top을 빼고 해당 좌표의 상하좌우를 살펴보면서 스택에 넣어주는 작업 ..

BFS(Breadth First Search) 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 -> 너비 우선으로 방문?? 그래프에서 모든 노드를 방문하는 알고리즘 그래프: 정점과 간선으로 이뤄진 자료구조 예시 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김 큐에서 원소 꺼내 그 칸에 상하좌우로 인접한 칸에 대해 3번 진행 해당 칸 이전에 방문했다면 아무것도 하지 않고, 처음 방문했다면 방문했다는 표시 남기고 해당 칸을 큐에 삽입 큐 빌 때까지 2번 반복 => 모든 칸이 큐에 1번씩 들어감 -> 시간복잡도는 칸이 N개일 때 O(N) ex. 행이 R개, 열이 C개 -> O(RC) (0, 0)과 상하좌우로 이어진 모든 파란칸 확인 좌표를 담을 큐 필요 (0, 0)에 방문했다는 표시 + ..

시간 복잡도 배열로 구현 -> 최대 N번 중간에 있는 원소의 삭제 발생 => O(N^2) 연결리스트 -> O(N) => 스택으로 훨씬 간단하게 구현 문자열을 앞에서부터 읽어나갈 때, 닫는 괄호가 남아있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 명령이라고 생각해도 된다 문제 해결 방법 여는 괄호 나옴 -> 스택에 추가 닫는 괄호 나옴 스택이 비어 있음 -> 올바르지 X 괄호 쌍 스택의 top이 짝과 맞지 X 괄호 -> 올바르지 X 괄호 쌍 스택의 top이 짝이 맞는 괄호 -> pop 모든 과정을 끝낸 후 스택에 괄호 남아있음 -> 올바르지 X 괄호 쌍 / 남아있지 X -> 올바른 괄호 쌍