이왕 발 디딘 이승, 원없이 즐겨야하지 않겠소?

DFS (깊이 우선 탐색) 소개 Root Node 혹은 다른 임의의 노드에서 시작해서 다음 분기(Branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. Stack과 재귀함수(Recursion)으로 구현한다. 경로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게되면 다른 방향으로 다시 탐색을 진행 모든 노드를 방문하는 경우에 이 방법을 사용한다. 사용용도 경로찾기 u, v가 주어졌을 때 u -> v로 가는 경로를 찾을 때 그래프의 사이클을 찾을 때 back edge 즉, 순환을 만들어 주는 마지막 edge를 찾는다. 시간복잡도 두 가지의 자료구조(인접 리스트, 인접 행렬)로 구현할 수 있다. 인접 리스트 : O(V + E) 인접 행렬 : O(V^2) 접점(V)..

Study/Algorithm 2022. 3. 19. 23:12

BFS (너비 우선 검색) 정리 소개 Root Node 혹은 다른 임의의 노드에서 인접한 노드를 먼저 탐색하는 방법이다. Queue를 사용해서 구현한다. 시간 복잡도 인접 리스트 : O(V + E) 인접 행렬 : O(V^2) 접점(V), 간선(E) class Graph { private int V; private LinkedList adj[]; Graph(int v) { V = v; adj = new LinkedList[v]; for (int i=0; i

Study/Algorithm 2022. 3. 19. 23:11

백준 온라인 저지 1992번 '쿼드트리' Java 알고리즘 문제풀이 풀이 이 문제는 분할정복(Divide and Conquer)로 풀면된다. 분할정복 사실은 정말 쉬운 개념이다. 복잡한 문제를 해결할 수 있는 작은 단위로 나누어 처리하고 이것을 합치면 된다. 이 문제를 풀면 백준 1780번 문제 종이의 개수도 아주 쉽게 풀 수 있을 것이다. (유사한 문제 풀기 -> 백준 1780번 문제종이 https://developer-mac.tistory.com/38) 그리고 쿼드트리는 단순히 노드가 4개 있는 것이라고 생각하면 된다. 즉, 4개로 쪼개서 4개의 노드가 생겨난다고 생각하면 된다. 먼저 입력을 받은 후 divide 함수에서 재귀적으로 동작하고 if 문을 두어 모든 원소가 0이거나 1일때 빠져나오게 하면..

Study/Algorithm 2022. 3. 19. 23:10

완전탐색 (Brute-Force) BP라고 불리는 완전탐색은 단어 그래로 모든 경우의 수를 다 해보는 것이다. 알고리즘을 풀때 강력한 방식이지만, 시간은 최대로 들어간다. 예를들어 비밀번호가 4자리이고 숫자로만 이루어져 있다면, 0 ~ 9999까지 다 해보면된다. 경우의 수는 10,000가지이다. 만약 한 숫자당 1초가 걸린다고 하면 10,000초 = 2.7시간정도가 걸린다. 따라서 완전탐색을 풀기위해서는 대표적으로 4가지를 생각해볼 수 있다. for문 사용 순열, 조합 사용 재귀함수 사용 비트마스크 사용 2309번 일곱 난쟁이 조합을 이용해서 풀면된다. 1476번 날짜 계산 나머지를 이용 14500번 테트로미노 노가다 문제... 1966번 프린터 큐 큐 개념도 연습할 수 있다. 2231번 분해합 순열(..

Study/Algorithm 2022. 3. 19. 23:07

동적 계획법(Dynamic Programming) 정리 큰 문제를 작은 문제로 나눠서 푸는 알고리즘인데, 코딩테스트에서 자주 출제되는 알고리즘 기법입니다. DP 속성 Overlapping Subproblem (부분 문제가 겹친다.) Optimal Substructure (최적 부분 구조) Overlapping Subproblem 대표적인 예로 피보나치 수를 들 수 있다. Fn = Fn-1 + Fn-2 여기서 Fn을 큰 문제로 생각하고, 우측 항에 있는 Fn-1, Fn-2를 작은 문제로 나눈다고 생각하면 된다. Optimal Substructure 문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있다. 위의 예에서 작은 문제로 쪼갠 우측항의 Fn-1 + Fn-2로 큰 문제인 Fn의 값을 구할 수 ..

Study/Algorithm 2022. 3. 19. 23:07

1. 프로세스(Process)와 스레드(Thread) 먼저, 프로세스(process)란 무엇일까? 프로세스는 단순하게 말하면 일을 처리하는 일련의 과정을 말합니다. 예를 들어, 아침에 일어나 학교에 가는 과정도 하나의 프로세스라고 할 수 있습니다. 아침에 일어나서 씻고 준비를 한다. 역으로 걸어간다 지하철을 탄다 역에서 내려 학교로 간다. 💡 컴퓨터에게는 프로세스란 운영체제로부터 시스템 자원을 할당받는 작업의 단위 컴퓨터에서 연속적으로 실행되고 있는 프로그램 메모리에 올라와 실행되고 있는 프로그램의 인스턴스를 말합니다. 💡 하나의 프로세스는 크게 코드영역(code), 데이터 영역(date), 스택 영역(stack), 힙 영역(heap) 4가지로 이루어져 있습니다. Code : 코드 자체를 구성하는 메모리..

Study/Algorithm 2022. 3. 19. 23:06

1. 프로세스(Process)와 스레드(Thread) 먼저, 프로세스(process)란 무엇일까? 프로세스는 단순하게 말하면 일을 처리하는 일련의 과정을 말합니다. 예를 들어, 아침에 일어나 학교에 가는 과정도 하나의 프로세스라고 할 수 있습니다. 아침에 일어나서 씻고 준비를 한다. 역으로 걸어간다 지하철을 탄다 역에서 내려 학교로 간다. 💡 컴퓨터에게는 프로세스란 운영체제로부터 시스템 자원을 할당받는 작업의 단위 컴퓨터에서 연속적으로 실행되고 있는 프로그램 메모리에 올라와 실행되고 있는 프로그램의 인스턴스를 말합니다. 💡 하나의 프로세스는 크게 코드영역(code), 데이터 영역(date), 스택 영역(stack), 힙 영역(heap) 4가지로 이루어져 있습니다. Code : 코드 자체를 구성하는 메모리..

Study/Algorithm 2022. 3. 19. 23:01

스택 (STACK)이란? 📌 스택의 개념 스택(stack)이란 쌓아 올린다는 것을 의미한다. 따라서 스택 자료구조라는 것은 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다. 📌 스택의 특징 스택은 위의 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을수 있고, top으로 정한 곳을 통해서만 접근할 수 있다. top에는 가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리키고 있으며, 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다. 스택에서 자료를 삭제할 때도 top을 통해서만 가능하다. 스택에서 top을 통해 삽입하는 연산을 'push' , top을 통한 삭제하는 연산을 'pop'이라고 한다. 따라서 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자..

Study/Algorithm 2022. 3. 19. 23:00