분류 전체보기

패스트캠퍼스 챌린지 9일차

날짜 : 2021 년 11 월 9 일 시청 강의 : 01. 어떻게든 푼다. 완전 탐색 (Brute Force) 완전탐색 모든 경우를 전부 탐색 4가지 문제 유형으로 나누어 볼 수 있음. [문제유형] 1. N개의 원소 중 중복 없이 M 개를 순서있게 나열 2. N개의 원소 중 중복 없이 M 개를 고르기 3. N개의 원소 중 중복 허용하여 M 개를 순서있게 나열 4. N개의 원소 중 중복 허용하여 M 개를 고르기 완전탐색으로 문제를 풀 때, 백트래킹이 자주 사용되는데 dfs는 백트래킹 문제 방법 중 하나임 따라서, 완전탐색으로 문제를 풀이하는 경우에, public static void recurrsive(int depth){ //재귀 } public static void main(String[] args){..

패스트캠퍼스 챌린지 8일차

날짜 : 2021 년 11 월 8 일 시청 강의 : 백트래킹 알고리즘 이해 (1) 벌써 8일차라니..신기하다.. 오늘은 백트래킹 알고리즘이해 (1)을 들었다. 포스팅 작성 후, N 퀸을 직접 구현해보고 백트래킹 알고리즘 이해 (2)를 듣는게 나을 것 같다. 애니웨이.. 백트래킹 제약 조건 만족 문제에서 해를 찾기 위한 전략 해가 될 수 있는 다양한 후보근을 트리 형태로 표현 (State Space Tree) 진짜 트리는 아니고, dfs 로 풀 수 있다. How it works... 1. 루트 노드를 하나 잡아서, 해가 될 수 있는지 판단 2. 해가 될 수 있다면 해당 해의 child 가 해가 될 수 있는지 판단 3. 해가 될 수 없다면, 다시 그 전 조건으로 돌아간다. 이때, 해가 될 수 없는 노드의 자..

패스트캠퍼스 챌린지 7일차

날짜 : 2021년 11월 7일 시청 강의 ; SQL CH02 SQL 공부를 해야해서 오늘은 알고리즘 강의가 아니라 SQL 강의를 들었다. 기본적인 기능들을 알려주셨는데, 나는 MySQL을 사용하기 때문에, https://www.mysqltutorial.org/ 를 참고하여 정리해 보았다. Querying Data 📌 SELECT FROM: Use the SELECT statement to select data from a table. Use the SELECT * to select data from all columns of a table. SELECT: MySQL SELECT statement doesn’t require the FROM clause Use the dual table if you wa..

패스트캠퍼스 챌린지 6일차

날짜 : 2021 년 11 월 6 일 시청 강의 : 프림 알고리즘 (1), 프림 알고리즘 (2) 오늘 시청한 강의는 프림 알고리즘이다. 내가 뭘들은건가싶다 주르륵.. 크루스칼은 이해가 좀 됬는데 역시 옛날부터 포기한 프림 알고리즘은 차원이 달랐다.. 일단 개념만 이해하고 코드는 나중에 이해하기로 결심했다. 크루스칼 vs 프림 알고리즘 1. 크루스칼 알고리즘 : 간선 정보를 정렬 -> 가장 가중치가 낮은 간선부터 사이클이 생기지 않도록 연결 2. 프림 알고리즘 : 시작 정점을 선택 -> 정점의 인접 간선 중 가중치가 최소인 간선을 연결 프림 알고리즘 https://www.cs.usfca.edu/~galles/visualization/Prim.html Prim MST Visualzation www.cs.us..

패스트캠퍼스 챌린지 5일차

날짜 : 2021 년 11 월 5 일 시청 강의 : 최소 신장 트리의 이해와 크루스칼 알고리즘 (1) ~ (4) 그래프 탐색 : 크루스칼과 프림 알고리즘은 최소 신장 트리를 활용하는 문제이다. 이중에서, 오늘은 크루스칼 알고리즘에 대해 배웠다. 신장 트리 (Spanning Tree) 전체 노드가 연결되어 있다. 사이클이 존재하지 않는다. 위 그래프에서, 그래프 G 는 사이클이 존재한다. 스패닝 트리는, 모든 노드가 연결되어있으면서 사이클이 존재하지 않는 그래프다 최소 신장 트리 가중치가 존재하는 신장 트리 중, 간선의 합(weight)이 가장 작은 트리 만약, 앞의 신장 트리가 다음과 같은 가중치를 가지고 있다고 가정해보자. 그렇다면, 최소 신장 트리는 가중치가 가장 작은 트리로 첫번째 스패닝 트리가 최..

패스트캠퍼스 챌린지 4일차

날짜 : 2021 년 11 월 4 일 시청 강의 : 최단 경로 알고리즘 이해 (1) , 최단 경로 알고리즘 이해 (2) , 최단 경로 알고리즘 이해 (3) , 최단 경로 - 다익스트라 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는 것 유형 1. 단일 출발 (다익스트라) 특정 노드 -> 모든 그래프 돌아다니면서 가장 짧은 경로 찾기 2. 단일 도착 모든 노드에서 출발 -> 특정 노드로 도착하는 가장 짧은 경로 3. 단일쌍 u~ V까지의 최소 경로 (1 개) 4. 전체쌍 모든 쌍에 대한 최단 경로 다익스트라 알고리즘 다익스트라 알고리즘은 우선 순위 큐를 사용한다 우선순위 큐를 활용하여 풀이하는 방식은 BFS 방식과 매우 유사한데, 이는 자식놔 연결된 노드를 체크하여 탐색하기 때문이다...